CODEWITHSUNDEEP
pythonalgorithmpython-2.7
twfx
twfx

Reputation: 1694

Cycle detection in a 2-tuple python list

Given a list of edges in 2-tuple, (source, destination), is there any efficient way to determine if a cycle exists? Eg, in the example below, a cycle exists because 1 -> 3 -> 6 -> 4 -> 1. One idea is to calculate the number of occurrence of each integer in the list (again, is there any efficient way to do this?). Is there any better way? I am seeing a problem with 10,000 of 2-tuple edge information.

a = [(1,3), (4,6), (3,6), (1,4)]

Upvotes: 1

Views: 2108

Answers (1)

Niklas B.
Niklas B.

Reputation: 95328

I'm assuming you want to find a cycle in the undirected graph represented by your edge list and you don't want to count "trivial" cycles of size 1 or 2.

You can still use a standard depth-first search, but you need to be a bit careful about the node coloring (a simple flag to signal which nodes you have already visited is not sufficient):

from collections import defaultdict

edges = [(1,3), (4,6), (3,6), (1,4)]
adj = defaultdict(set)
for x, y in edges:
    adj[x].add(y)
    adj[y].add(x)

col = defaultdict(int)
def dfs(x, parent=None):
    if col[x] == 1: return True
    if col[x] == 2: return False
    col[x] = 1
    res = False
    for y in adj[x]:
        if y == parent: continue
        if dfs(y, x): res = True
    col[x] = 2
    return res

for x in adj:
    if dfs(x):
        print "There's a cycle reachable from %d!" % x

This will detect if there is a back edge in the depth-first forest that spans at least 2 levels. This is exactly the case if there is a simple cycle of size >= 2. By storing parent pointers you can actually print the cycle as well if you found it.

For large graphs you might want to use an explicit stack instead of recursion, as illustrated on Wikipedia.

Upvotes: 1

Related Questions