Finding all cycles in undirected graphs
I need a working algorithm for finding all simple cycles in an undirected graph. I know the cost can be exponential and the problem is NP-complete, but I am going to use it in a small graph (up to 20-30 vertices) and the cycles are small in number.
After a long research (mainly here) I still don't have a working approach. Here is a summary of my search:
Finding all cycles in an undirected graph
Cycles in an Undirected Graph -> detects only whether there is a cycle or not
Finding polygons within an undirected Graph -> very nice description, but no solution
Finding all cycles in a directed graph -> finds cycles only in directed graphs
Detect cycles in undirected graph using boost graph library
The only answer I found, which approaches my problem, is this one:
Find all cycles in graph, redux
It seems that finding a basic set of cycles and XOR-ing them could do the trick. Finding a basic set of cycles is easy, but I don't understand how to combine them in order to obtain all cycles in the graph...
Solution 1:
For an undirected graph the standard approach is to look for a so called cycle base : a set of simple cycles from which one can generate through combinations all other cycles. These are not necessarily all simple cycles in the graph. Consider for example the following graph:
A
/ \
B ----- C
\ /
D
There are 3 simple cycles here : A-B-C-A, B-C-D-B and A-B-D-C-A. You can however take each 2 of these as a basis and obtain the 3rd as a combination of the 2. This is a substantial difference from directed graphs where one can not combine so freely cycles due to the need to observe edge direction.
The standard baseline algorithm for finding a cycle base for an undirected graph is this : Build a spanning tree and then for each edge which is not part of the tree build a cycle from that edge and some edges on the tree. Such cycle must exist because otherwise the edge would be part of the tree.
For example one of the possible spanning trees for the sample graph above is this:
A
/ \
B C
\
D
The 2 edges not in the tree are B-C and C-D. And the corresponding simple cycles are A-B-C-A and A-B-D-C-A.
You can also build the following spanning tree:
A
/
B ----- C
\
D
And for this spanning tree the simple cycles would be A-B-C-A and B-C-D-B.
The baseline algorithm can be refined in different ways. To the best of my knowledge the best refinement belongs to Paton (K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518.). An open source implementation in Java is available here : http://code.google.com/p/niographs/ .
I should have mentioned how you combine simple cycles from the cycle base to form new simple cycles. You start off by listing in any (but fixed hereafter) order all edges of the graph. Then you represent cycles by sequences of zeros and ones by placing ones in the positions of edges which belong to the cycle and zeros in the positions of edges which are not part of the cycle. Then you do bitwise exclusive OR (XOR) of the sequences. The reason you do XOR is that you want to exclude edges which belong to both cycles and thus make the combined cycle non-simple. You need to check also that the 2 cycles have SOME common edges by checking that the bitwise AND of the sequences is not all zeros. Otherwise the result of XOR will be 2 disjoint cycles rather than a new simple cycle.
Here is an example for the sample graph above:
We start by listing the edges : ((AB), (AC), (BC), (BD), (CD)). Then the simple cycles A-B-C-A, B-D-C-B and A-B-D-C-A are represented as (1, 1, 1, 0, 0), (0, 0, 1, 1, 1) and (1, 1, 0, 1, 1). Now we can for example XOR A-B-C-A with B-D-C-B and the result is (1, 1, 0, 1, 1) which is exactly A-B-D-C-A. Or we can XOR A-B-C-A and A-B-D-C-A with the result being (0, 0, 1, 1, 1). Which is exactly B-D-C-B.
Given a cycle base you can discover all simple cycles by examining all possible combinations of 2 or more distinct base cycles. The procedure is described in more detail here : http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf on page 14.
For the sake of completeness, I would notice that it seems possible (and inefficient) to use algorithms for finding all simple cycles of a directed graph. Every edge of the undirected graph can be replaced by 2 directed edges going in opposite directions. Then algorithms for directed graphs should work. There will be 1 "false" 2-node cycle for every edge of the undirected graph which will have to be ignored and there will be a clockwise and a counterclockwise version of every simple cycle of the undirected graph. Open source implementation in Java of algorithms for finding all cycles in a directed graph can be found at the link I already quoted.
Solution 2:
Axel, I've translated your code to python. About 1/4th the lines of code and clearer to read.
graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
cycles = []
def main():
global graph
global cycles
for edge in graph:
for node in edge:
findNewCycles([node])
for cy in cycles:
path = [str(node) for node in cy]
s = ",".join(path)
print(s)
def findNewCycles(path):
start_node = path[0]
next_node= None
sub = []
#visit each edge and each node of each edge
for edge in graph:
node1, node2 = edge
if start_node in edge:
if node1 == start_node:
next_node = node2
else:
next_node = node1
if not visited(next_node, path):
# neighbor node not on path yet
sub = [next_node]
sub.extend(path)
# explore extended path
findNewCycles(sub);
elif len(path) > 2 and next_node == path[-1]:
# cycle found
p = rotate_to_smallest(path);
inv = invert(p)
if isNew(p) and isNew(inv):
cycles.append(p)
def invert(path):
return rotate_to_smallest(path[::-1])
# rotate cycle path such that it begins with the smallest node
def rotate_to_smallest(path):
n = path.index(min(path))
return path[n:]+path[:n]
def isNew(path):
return not path in cycles
def visited(node, path):
return node in path
main()