Re: [igraph] Help - find cycles

[Gábor Csárdi]

On the second though, this is NP-complete, because it includes finding
a Hamiltonian cycle of the graph. So you might as well just use a
subgraph isomorphism algorithm to detect all cycles of a given length.
E.g.

find.cycles <- function(graph, k) {
  ring <- graph.ring(k)
  graph.get.subisomorphisms.vf2(graph, ring)
}

should work for small graphs or small rings.

Best,
Gabor

On 4/14/09, Romildo Martins <address@hidden> wrote:
> Dear,
>
> I need find all circle (cycles) in undireted graphs. In girth
> function, you find the shortest circle in it.
> There is forecast to create a function to detect cycles in a graph?
>
> ex:
> g <- graph( c(0,1,1,2,2,3,3,0,1,3), directed=FALSE )
> plot(g,vertex.shape="circle", layout=layout.circle)
> cycles(g, min=3, max=4)
> [[1]]
> [1] 0 1 3
>
> [[2]]
> [1] 1 2 3
>
> [[3]]
> [1] 0 1 2 3
> Thanks a lot,
>
> Romildo Martins Bezerra
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>


-- 
Gabor Csardi <address@hidden>     UNIL DGM