Re: finding all cycles in a graph

[Juan Pablo Carbajal]

2012/1/24 Francesco Potortì <address@hidden>:
> 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.
>
>>Furthermore, I don't think we even have a graph representation in
>>Octave.
>
> Can't they simply be represented by a boolean matrix?
>
>>There is this cycle iterator in Sage, though:
>>
>>    http://www.sagemath.org/doc/reference/sage/graphs/digraph.html
>
> Never heard about Sage before.  It may be worth a look at, apparently,
> thanks.
>
> --
> 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
> _______________________________________________
> Help-octave mailing list
> address@hidden
> https://mailman.cae.wisc.edu/listinfo/help-octave

Hi
I solved this problem (in a very non-efficient way, but those were all
times. I can send you the code....not very proud of it though)
following the algorithm in this paper (I may have a copy if you
want... I guess IEEE wont complain for a paper form the '68)
DANIELSON, GORDON . On finding simple paths and circuits in a graph.
IEEE Trans. Circuit Theor. 15 (1968), 294-295.
doi: 10.1109/TCT.1968.1082837

I was solving this problem
https://files.ifi.uzh.ch/ailab/people/carbajal/3cablesReport/report3cables.html

Please do not laugh, this are really old stuff (and matlabotomized!).

Let me know if you like to skim over my code (though the paper should
be more than enough).

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