Lab #6: 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.

IMPORTANT

For this programming assignment, students are required to complete all work independently and are not permitted to use AI-assisted tools, such as GitHub Copilot, ChatGPT, Gemini, or similar platforms, to automatically generate code. Using AI tools in this way undermines the learning process and violates academic integrity policies. The purpose of this assignment is to assess your understanding and application of the concepts covered in the course. Failure to comply with these guidelines may result in academic penalties, including but not limited to a lower grade.

If you have any questions about the assignment or need clarification on any concepts, please do not hesitate to visit your instructor during office hours. Rely solely on your own knowledge, the course materials, and any authorized resources provided by the instructor.

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 an 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': ['B', '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

type Graph = dict[str, list[str]]


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

Test your code using the tests in the file test_graph_cycle.py (20 tests in total). Make sure your code has no failures and no errors.

Also, verify that your editor has basic type checking enabled. All your code should use type hints adequately.

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 #6: Graph Cycle Detection
#
# Date: 06-Nov-2024
# Authors:
#           A01770771 James Howlett
#           A01777771 Wade Wilson
#----------------------------------------------------------

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 Wednesday, November 6.