3

I have an undirected graph and what I would like to do is detect cycles that have three or more nodes in them. Is there a library in R that would do this? If not is there a simple algorithm that I could implement.

test <- data.frame(start=c(1,2,3,4), stop=c(2,3,1,5))

I would like it to come back with 1,2,3 and any other cycles it finds.

yoda230
  • 449
  • 6
  • 14

1 Answers1

3

Well, this won't give you the actual nodes in your cycles, but it will count the cycles of each rank in your graph, so it's a start.

library(igraph)
test <- data.frame(start=c(1,2,3,4), stop=c(2,3,1,5))
g <- graph.data.frame(test)

cycles <- t(sapply(3:dim(test)[1], function(x) {v=graph.motifs.no(g, size=x); c(x,v)}))
colnames(cycles) <- c("size","count")

     size count
[1,]    3     1
[2,]    4     0

I recommend you play around with the igraph library anyway: I couldn't find a solution for you in there, but I suspect that's where you'll find your answer. graph.motifs looks promising, but I wasn't able to interpret the result.

If it doesn't have to be R, the networkx library in python has a simple_cycles() function that should be sufficient for your needs.

import networkx as nx
from networkx.algorithms.cycles import simple_cycles
g = nx.DiGraph()
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)
g.add_edge(3,1)
g.add_edge(4,1)
simple_cycles(g)

# [[1,2,3,1],[1,2,3,4,1]]
David Marx
  • 8,172
  • 3
  • 45
  • 66
  • The only problem I can see with simple_cycles is that it is for directed graphs. My dataset is undirected, it is possible it might still work through. – yoda230 Jul 10 '13 at 09:13
  • 1
    Oh right, undirected. `simple_cycles()` only works for directed. Here are two SO discussions you may find useful: http://stackoverflow.com/a/4028855/819544 and http://stackoverflow.com/a/526371/819544. Looks like you can be clever with a DFS and that might be enough. – David Marx Jul 10 '13 at 11:57