Q1 (10 marks)

Design a solution to find the first cycle-causing edge in an undirected graph insertion stream.

Problem Statement

Given a set of isolated vertices V = {0, 1, 2, ..., n-1} and a sequence of undirected and unwighted edges, we insert edges in the sequence one by one. Design an algorithm to compute the first edge that creates a cycle in the graph as well as the cycle.

Background & Query Output

In the graph below, the labels on the edges show the insertion order. The sixth inserted edge 5--0 is the first edge that creates a cycle.

Example 1 (the above figure): a cycle exists.

Input:

n = 6
L = [
    (0, 1),
    (1, 2),
    (3, 4),
    (2, 3),
    (4, 5),
    (5, 0)
]

Return value:

[[5, 0], [5, 4, 3, 2, 1, 0, 5]]

Example 2: no edge creates a cycle.

Input:

n = 5
L = [
    (0, 1),
    (1, 2),
    (3, 4)
]

Return value:

None

Doing this Project

Open the code template file Q1.ipynb and make a copy in your own Google Drive. You need to implement a function query(n, L) in the FirstCycleEdgeQuery class. The first parameter n is the number of vertices, and the second parameter L is a list of edges. Each edge is a tuple of two integers representing the endpoints of the edge. The function should return the first cycle-causing edge and a cycle containing it, or None if no cycle is created by any edge. You can assume following properties always hold for the input:

For any vertex v appearing in the edge list, 0 ≤ v < n.
There is no repeated edge in the edge list.

In addition to the implementation, write a supporting document named as Q1.pdf. The document must includes theroretical analysis of your algorithm including the time complexity of the query algorithm, and the space complexity of the data structure you need for query processing. The document should also include an explanation of your algorithm design. Diagrams/figures/examples are are encouraged to illustrate your ideas.

For complexity analysis, you should use n for the number of vertices or/and m for the number of inserted edges. Any standard mathematical notations are accepted including but not limited to sum, +, -, *, /, min, max, and ^.

Required Files

Submit Q1.ipynb and Q1.pdf on Moodle.

Marking Criteria

Marks will be awarded based on:

Code correctness and efficiency (with clear explanation and/or comments): 8 marks
Time complexity analysis: 1 mark
Space complexity analysis: 1 mark

Notes:

Do not change the input/output format of the provided class or method.
Submissions can be tested on larger graphs than those shown in the example.
Your explanation should include your algorithm, efficiency discussion, time complexity, and space complexity.
You cannot import any external libraries or modules other than the Python Standard Library.