Re: finding all cycles in a graph

[Juan Pablo Carbajal]

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,

-- 
M. Sc. Juan Pablo Carbajal
-----
PhD Student
University of Zürich
http://ailab.ifi.uzh.ch/carbajal/