Cycles in directed graph

user_9452708 0
Viewed 63

I am wiring a function to check whether a graph contains a cycle.

It is represented as a list of lists of all indexes of nodes each node is connected to. Nodes are enumerated from 1 (task requirement).

While checking the graph [[2, 3], [], [4], []], the program enters the first listed node correctly, yet in the second iteration, it is assumed that adjlist[node-1] is an int of value 3 rather than an array (or int = 2 at very least)

What am I missing?

The code:

def is_acyclic(adjlist: List, visited: List, path: List) -> bool:
    '''
    :param adjlist: list representation of a graph; eg: [[2, 3], [], [4], []]
    :param visited: visited nodes
    :param path: visited nodes in current iteration
    :return: the graph does not contain a cycle
    '''

    for node in range(1, len(adjlist)+1):
        if node not in visited:
            visited.append(node)
            path.append(node)

            for child in adjlist[node-1]:
                if child in path:
                        return False
                elif child not in visited:
                    if is_acyclic(adjlist[node-1], visited, path) is False:
                        return False

            path.remove(node)
            return True
graph-theory python-3.x python
1 Answers

This is due to the fact that the function is being called recursively. This part of your code keeps trimming the graph adjacency list:

        elif child not in visited:
            if is_acyclic(adjlist[node-1], visited, path, level=level + 1) is False:
                return False

The first time adjacency list is:

[[2, 3], [], [4], []]

and adjlist[node-1] is [2, 3]

the second time around adjacency list is: 

[2, 3]

and adjlist[node-1] is 3

since 2 is already in visited, node actually gets incremented to 2. Hence, you see:

 adjlist[node-1] == adjlist[2-1] == adjlist[1] == 3
user_105088930
Related