|
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.pdfThe 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/
[Prev in Thread] | Current Thread | [Next in Thread] |