Cycle detection in a 2-tuple python list

Question

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)]

The layout of the numbers 1 3 6 and 4 on a numpad represent a 'cycle' I guess — Tim, Apr 01 '14 at 13:00
There is no cycle in your example. You can reach `6` over two edges but there is no cycle back to `1`. — , Apr 01 '14 at 13:01
True, but `->` indicates direction. I would represent an undirected graph as `1-2`, not `1->2`. — , Apr 01 '14 at 13:02
related: [Cycles in an Undirected Graph](http://stackoverflow.com/q/526331/4279) — jfs, Apr 01 '14 at 13:04
thanks mskimm, that's what I'm looking for. Some good python implementation for cycle detection. — twfx, Apr 01 '14 at 13:18
Do you only need to know if a cycle exists, or do you also need to know what they are? If the first, note that if all the nodes are connected, number of edges = number of nodes - 1 iff there are no cycles. — RemcoGerlich, Apr 01 '14 at 13:18
@RemcoGerlich Actually it's more like edges = number of nodes - number of connected components — Niklas B., Apr 01 '14 at 15:59
@mskimm Actually that is not what OP needs, since nodes have degree > 1 — Niklas B., Apr 01 '14 at 16:38

Niklas B. · Answer 1 · 2014-04-01T15:57:12.967

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.

Cycle detection in a 2-tuple python list

1 Answers1

Linked