[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: finding all cycles in a graph
From: |
Francesco Potortì |
Subject: |
Re: finding all cycles in a graph |
Date: |
Wed, 25 Jan 2012 22:38:27 +0100 |
>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.
Thanks all. And yes, should anything come out of this I'll let the list
know.
--
Francesco Potortì (ricercatore) Voice: +39.050.315.3058 (op.2111)
ISTI - Area della ricerca CNR Mobile: +39.348.8283.107
via G. Moruzzi 1, I-56124 Pisa Fax: +39.050.315.2040
(entrance 20, 1st floor, room C71) Web: http://fly.isti.cnr.it