Re: finding all cycles in a graph

ref: https://cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph

Re: finding all cycles in a graph
From: Juan Pablo Carbajal
Subject: Re: finding all cycles in a graph
Date: Wed, 25 Jan 2012 19:43:48 +0100
On Wed, Jan 25, 2012 at 2:52 PM, Moreno Marzolla
address@hidden wrote:

On 01/24/2012 08:55 PM, Francesco Potortì wrote:

First of all, thanks to you and to those that have answered previously.

Has anyone an Octave program for finding all cycles in a graph?

You're of course aware that there are exponentially many cycles in
general? There usually are better ways to accomplish whatever you need
than looking for all cycles of a graph.

That's what I suspect too. I have been made this request by a colleague
of mine, and anyway I think it may be a useful way of starting to
understand the problem, which anyway involves small graphs only.

Hello,

you might be interested in the algorithm described here:

Donald B. Johnson, "Finding all the elementary circuits of a directed
graph", SIAM J. Comput vol. 4 n. 1 march 1975

http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf

The running time is O( (n+e)(c+1) ) where n=number of nodes, e=number of
edges, c=number of elementary circuits in the graph. However, as said above,
there can be an exponential number of elementary loops in the graph.

I don't know if there are Octave implementations of the algorithm above.

Moreno.

--
Moreno Marzolla
EMail: address@hidden
WWW : http://www.moreno.marzolla.name/

---

Help-octave mailing list
address@hidden
https://mailman.cae.wisc.edu/listinfo/help-octave

Hi Francesco & Paolo,

Definitely the '75 algorithm is worth to be checked. In case you want
to see my code (disclaimer: naive, and highly non-efficient
implementation) of the '68 paper you can get it from here
http://octave.svn.sf.net/viewvc/octave/trunk/octave-forge/main/geometry/devel/graphs/

Here a example of use:

% Create adjacency matrix (in any way you want. I use unvech from the
package general >= 1.2.2 to create a symmetric matrix)
v=round(rand(1,10)>0.4);
A=unvech(v);

[x y]=find(A==1);
i=sub2ind(size(A),x,y);
B=A;
B(i)=y;
Ac=graph2cell(A,'adj');
Bc=graph2cell(B,'varadj');
P=cellmatprod(Bc,Ac);
[P cycles]=simplepath(P);

As you can see even the interface is not the best.

If you re-implement or improve the code, please let us know.

Cheers,