Back edges program

Question

I implemented a program that finds back edges on a graph stored a dictionary.

Example :

Input : (graph={'A': ['B','C'], 'B': ['C'], 'C': ['D'], 'D': ['A']}, start='A')
Output : [('D', 'A'), ('B', 'C')]

The problem is that it also returns cross edges, can you help me find where the problem is ? I haven't found an answer for several days.

def ArcA(graph, start):
    stack = []
    discovery_time = {}
    finish_time = {}
    back_edges = []
    time = 0

    stack.append(start)

    while stack:
        current = stack.pop()
        if current not in discovery_time:
            time += 1
            discovery_time[current] = time
            stack.append(current)
            
            for neighbor in graph[current]:
                if neighbor not in discovery_time:
                    stack.append(neighbor)
                elif discovery_time[neighbor] < discovery_time[current]:
                    back_edges.append((current, neighbor))

            time += 1
            finish_time[current] = time

    return back_edges

Thank you !

I expect my code to only returns back edges, but I think that it also returns cross edges.

score 0 · Accepted Answer · answered Feb 09 '23 at 21:32

If I understand this correctly, then back edges lead to neighbors that are in stack at the time, so instead of elif discovery_time[neighbor] < discovery_time[current], you need to use elif neighbor in stack

def ArcA(graph, start):
    stack = []
    discovery_time = {}
    finish_time = {}
    back_edges = []
    time = 0

    stack.append(start)

    while stack:
        current = stack.pop()
        if current not in discovery_time:
            time += 1
            discovery_time[current] = time
            stack.append(current)
            
            for neighbor in graph[current]:
                if neighbor not in discovery_time:
                    stack.append(neighbor)
                elif neighbor in stack: ### EDIT ###
                    back_edges.append((current, neighbor))

            time += 1
            finish_time[current] = time

    return back_edges

and now ArcA(graph={'A': ['B','C'], 'B': ['C'], 'C': ['D'], 'D': ['A']}, start='A') should return just [('D', 'A')] and cross edges like ('B', 'C') should no longer be included in the output.

Back edges program

1 Answers1