help-octave
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: finding all cycles in a graph


From: Moreno Marzolla
Subject: Re: finding all cycles in a graph
Date: Wed, 25 Jan 2012 14:52:01 +0100
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.24) Gecko/20111108 Thunderbird/3.1.16

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/



reply via email to

[Prev in Thread] Current Thread [Next in Thread]