Cycles in undirected graph

[dbtek]

Hi, thanks for awesome graphlib.

Correct me if I'm wrong. findCycles algorithm does not support undirected graphs. Any plans to add this?

[dkottow]

Hi there,

I had the same need.. please find attached a rather straightforward transcript of Sedgewick's book algorithm on it. It finds only a single cycle, I believe you can iteratively break that cycle to find them all (its in the code as well).

graph_util.zip

[dbtek]

I was failed to find a decent way of finding all simple cycles of an undirected graph. Eventually falled back to geometrical (with coordinates) traversing.

The method you propose is also not complete. Removing an edge after finding one cycle may also remove another cycle that is not found. Think of two neighbor cycles with one common edge.

AFAK, there is no good algorithm that finds all simple cycles in an undirected graph. Apply a coordinates aware method, I suggest.

[NickRimer03]

@dkottow Hello there! Some time ago I've solved similar problem for me. First I remove (and remember) all edge duplicates and self-cycles from graph. For example if there are DOT like this: "graph g { a--a; a--b; b--a; a--c; a--d; c--d; d--d1; }" algorithm removes one instance of "a--b" and "a--a" cycle. So we have "graph g { a--b; a--c; a--d; c--d; d--d1; }". In second I use breadth-first search to separate tree-graph from cycled graph (information on wikipedia must be enough). It has only one little thing - you need not to take care of nodes that are already in process. Such node we must remember separately to restore them later. So for our example graph we'll have such picture: point "a" children: [b, c, d] point "b" children: [] -- not "a", we process it earlier. point "c" children: [] -- not "a" as above; also we expected "d", but it's still in process queue, so we need to remove and remember it with it's "c" parent ("c--d;") point "d"children [d1] -- not "a". points "b", "d1" has no children (just parent connection). For now we can draw/process/etc. tree "a--b; a--c; a--d; d--d1;" as we want. In the end all we need is to restore removed "c--d" and duplicates: "a--a", "b--a".

Hope it will help.