Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
given adjacency matrix, detect # of cycles in directed graph
def find_cycles(g, x, path, num_cycles):
if x in path:
num_cycles+=1
return num_cycles
path.append(x)
N = len(g[x])
for i in range(N):
if g[x][i]:
num_cycles = find_cycles(g, i, path, num_cycles)
return num_cycles
# in adjacency list form:
# 1| ->2->3
# 2| ->3
# 3| ->4
# 4| ->2->1
# this graph has 3 unique cycles
g = [[0,0,0,0,0],[0,0,1,1,0],[0,0,0,1,0],[0,0,0,0,1],[0,1,1,0,0]]
print find_cycles(g, 1, [], 0)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.