Lab #5: Graph Cycle Detection

Objective

During this activity, students will be able to:

Design and implement an algorithm that detects if an undirected graph contains a cycle.

Description

This activity must be developed in the pre-assigned teams of two.

In a file called graph_cycle.py, write a Python function called has_cycle that takes as input an initial vertex and a undirected connected graph. The function traverses the graph in DFS (Depth-First Search) order and when it detects a cycle it returns a list with the vertices that conform the path of the cycle. If there are multiple cycles in the graph, the function returns the first one found. The function returns None if the graph contains no cycles.

For example, the following graph contains a cycle:

If the DSF traversal starts at vertex A, the detected cycle has the following path:

D ⇨ C ⇨ E ⇨ D

Bear in mind that:

A cycle can only occur if there are three or more vertices involved.
The cycle’s path starts and ends with the same vertex.

The has_cycle function should be called like this:

has_cycle('A', { 'A': ['B'],
                 'B': ['A', 'D'],
                 'C': ['D', 'E'],
                 'D': ['C', 'E'],
                 'E': ['C', 'D']
               })

Note that strings are used to represent the vertices, while the graph is represented as a dictionary where each key is a string and its associated value is a list of strings (the neighbours of the corresponding vertex).

The previous function call returns the following result:

['D', 'C', 'E', 'D']

Use the following code as a starting point:

# File: graph_cycle.py

from typing import Optional

Graph = dict[str, list[str]]


def has_cycle(initial: str, graph: Graph) -> Optional[list[str]]:
    # The function's code goes here
    ...

Test your program using the following unit tests:

# File: graph_cycle_test.py

from unittest import TestCase, main
from graph_cycle import has_cycle


class TestGraphCycle(TestCase):

    def test_has_cycle_1(self):
        self.assertIsNone(
            has_cycle('A', {
                'A': ['B'],
                'B': ['A']
            }))

    def test_has_cycle_2(self):
        self.assertIsNone(
            has_cycle('A', {
                'A': ['B'],
                'B': ['A', 'C'],
                'C': ['B']
            }))

    def test_has_cycle_3(self):
        self.assertEqual(
            ['A', 'B', 'C', 'A'],
            has_cycle('A', {
                'A': ['B', 'C'],
                'B': ['A', 'C'],
                'C': ['A', 'B']
            }))

    def test_has_cycle_4(self):
        self.assertIsNone(
            has_cycle('C', {
                'A': ['B'],
                'B': ['A', 'C'],
                'C': ['B', 'D'],
                'D': ['C'],
            }))

    def test_has_cycle_5(self):
        self.assertEqual(
            ['B', 'A', 'C', 'B'],
            has_cycle('D', {
                'A': ['B', 'C'],
                'B': ['A', 'C', 'D'],
                'C': ['A', 'B', 'E'],
                'D': ['B', 'E'],
                'E': ['C', 'D']
            }))

    def test_has_cycle_6(self):
        self.assertEqual(
            ['B', 'C', 'E', 'D', 'B'],
            has_cycle('A', {
                'A': ['B'],
                'B': ['A', 'C', 'D'],
                'C': ['B', 'E'],
                'D': ['B', 'E'],
                'E': ['C', 'D']
            }))

    def test_has_cycle_7(self):
        self.assertEqual(
            ['D', 'C', 'E', 'D'],
            has_cycle('A', {
                'A': ['B'],
                'B': ['A', 'D'],
                'C': ['D', 'E'],
                'D': ['C', 'E'],
                'E': ['C', 'D']
            }))

    def test_has_cycle_8(self):
        self.assertIsNone(
            has_cycle('E', {
                'A': ['B'],
                'B': ['A', 'D'],
                'C': ['D'],
                'D': ['B', 'C', 'E'],
                'E': ['D']
            }))

    def test_has_cycle_9(self):
        self.assertEqual(
            ['B', 'A', 'C', 'D', 'B'],
            has_cycle('B', {
                'A': ['B', 'C'],
                'B': ['A', 'D'],
                'C': ['A', 'D'],
                'D': ['B', 'C', 'E'],
                'E': ['D']
            }))

    def test_has_cycle_10(self):
        self.assertEqual(
            ['A', 'B', 'C', 'A'],
            has_cycle('D', {
                'A': ['B', 'C', 'D'],
                'B': ['A', 'C', 'D'],
                'C': ['A', 'B', 'D', 'E'],
                'D': ['A', 'B', 'C', 'E'],
                'E': ['C', 'D']
            }))

    def test_has_cycle_11(self):
        self.assertEqual(
            ['A', 'B', 'D', 'A'],
            has_cycle('E', {
                'A': ['B', 'C', 'D'],
                'B': ['A', 'D'],
                'C': ['A', 'D', 'E'],
                'D': ['A', 'B', 'C', 'E'],
                'E': ['C', 'D']
            }))

    def test_has_cycle_12(self):
        self.assertEqual(
            ['E', 'C', 'A', 'B', 'D', 'E'],
            has_cycle('E', {
                'A': ['B', 'C'],
                'B': ['A', 'D'],
                'C': ['A', 'E'],
                'D': ['B', 'E'],
                'E': ['C', 'D']
            }))

    def test_has_cycle_13(self):
        self.assertEqual(
            ['D', 'E', 'F', 'D'],
            has_cycle('A', {
                'A': ['B'],
                'B': ['A', 'C'],
                'C': ['B', 'D'],
                'D': ['C', 'E', 'F'],
                'E': ['D', 'F'],
                'F': ['D', 'E']
            }))

    def test_has_cycle_14(self):
        self.assertEqual(
            ['D', 'C', 'E', 'D'],
            has_cycle('F', {
                'A': ['B'],
                'B': ['A', 'D'],
                'C': ['D', 'E'],
                'D': ['B', 'C', 'E', 'F'],
                'E': ['C', 'D', 'F'],
                'F': ['D', 'E']
            }))

    def test_has_cycle_15(self):
        self.assertEqual(
            ['E', 'C', 'I', 'H', 'G', 'F', 'D', 'E'],
            has_cycle('B', {
                'A': ['D'],
                'B': ['E'],
                'C': ['E', 'I'],
                'D': ['A', 'E', 'F'],
                'E': ['B', 'C', 'D'],
                'F': ['D', 'G'],
                'G': ['F', 'H'],
                'H': ['G', 'I'],
                'I': ['C', 'H']
            }))

    def test_has_cycle_16(self):
        self.assertEqual(
            ['C', 'I', 'H', 'C'],
            has_cycle('A', {
                'A': ['D'],
                'B': ['E'],
                'C': ['E', 'I', 'H'],
                'D': ['A', 'E', 'F'],
                'E': ['B', 'C', 'D'],
                'F': ['D', 'G'],
                'G': ['F', 'H'],
                'H': ['C', 'G', 'I'],
                'I': ['C', 'H']
            }))

    def test_has_cycle_17(self):
        self.assertIsNone(
            has_cycle('A', {
                'A': ['D'],
                'B': ['E'],
                'C': ['E', 'I'],
                'D': ['A', 'E', 'F'],
                'E': ['B', 'C', 'D'],
                'F': ['D'],
                'G': ['H'],
                'H': ['G', 'I'],
                'I': ['C', 'H']
            }))

    def test_has_cycle_18(self):
        self.assertEqual(
            ['A', 'B', 'C', 'A'],
            has_cycle('D', {
                'A': ['B', 'C', 'D', 'E'],
                'B': ['A', 'C', 'D', 'E'],
                'C': ['A', 'B', 'D', 'E'],
                'D': ['A', 'B', 'C', 'E'],
                'E': ['A', 'B', 'C', 'D']
            }))

    def test_has_cycle_19(self):
        self.assertEqual(
            ['A', 'C', 'E', 'A'],
            has_cycle('B', {
                'A': ['B', 'C', 'D', 'E'],
                'B': ['A'],
                'C': ['A', 'E'],
                'D': ['A'],
                'E': ['A', 'C']
            }))

    def test_has_cycle_20(self):
        self.assertEqual(
            ['F', 'E', 'D', 'C', 'I', 'H', 'G', 'F'],
            has_cycle('F', {
                'A': ['B'],
                'B': ['A', 'C'],
                'C': ['B', 'D', 'I'],
                'D': ['C', 'E'],
                'E': ['D', 'F'],
                'F': ['E', 'G'],
                'G': ['F', 'H'],
                'H': ['G', 'I'],
                'I': ['C', 'H'],
            }))


if __name__ == '__main__':
    main()

Finally, make sure no type or PEP 8 style errors are produced by using the mypy and pycodestyle linters. You can incorporate these tools into VS Code or you can run them at the terminal.

Deliverables

Place in a comment at the top of the graph_cycle.py source file the authors’ personal information (student ID and name), for example:

#----------------------------------------------------------
# Lab #5: Graph Cycle Detection
#
# Date: 07-Oct-2022
# Authors:
#           A01770771 Kamala Khan
#           A01777771 Carol Danvers
#----------------------------------------------------------

Upload Instructions

To deliver the graph_cycle.py file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Friday, October 7.