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 1975http://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,