Dfyjkt

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

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