[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [igraph] bug in get.all.shortest.paths?

**From**: |
Laurin Müller |

**Subject**: |
[igraph] bug in get.all.shortest.paths? |

**Date**: |
Thu, 27 Jan 2011 11:22:17 +0100 |

Hi,
i am using the get.all.shortest.paths method but I think it does not
work correct with graphs where every vertex has the same degree:
with this graph (tree) it works fine:
library(igraph)
library(graph)
library(Rgraphviz)
g = new("graphNEL")
# add nodes
g = addNode("1",g)
g = addNode("2",g)
g = addNode("3",g)
g = addNode("4",g)
g = addNode("5",g)
g = addNode("6",g)
g = addNode("7",g)
# add edges
g = addEdge("1","2",g,1)
g = addEdge("2","3",g,1)
g = addEdge("3","4",g,1)
g = addEdge("4","5",g,1)
g = addEdge("5","6",g,1)
g = addEdge("2","7",g,1)
# return graphNEL
plot(g)
ig <- igraph.from.graphNEL(g)
get.all.shortest.paths(ig,from=0)
but for this graph (a "ring") where every node has the same degree:
g = new("graphNEL")
# add nodes
g = addNode("1",g)
g = addNode("2",g)
g = addNode("3",g)
g = addNode("4",g)
g = addNode("5",g)
g = addNode("6",g)
g = addNode("7",g)
# add edges
g = addEdge("1","2",g,1)
g = addEdge("2","3",g,1)
g = addEdge("3","4",g,1)
g = addEdge("4","5",g,1)
g = addEdge("5","6",g,1)
g = addEdge("6","7",g,1)
g = addEdge("7","1",g,1)
plot(g)
ig <- igraph.from.graphNEL(g)
get.all.shortest.paths(ig,from=0)
i get follwoing result:
[[1]]
[1] 0
[[2]]
[1] 0 1
[[3]]
[1] 0 1 6
aren't there some paths missing.
get.all.shortest.paths(ig,from=3)
results in:
[[1]]
[1] 3
there should be similar results for all nodes because it is a "ring"
structure.
the result should be something like this:
0
0 1
0 1 2
0 1 2 3
0 6 5 4
0 6 5
0 6
or am I wrong?
hope you can help me,
best
Laurin

**[igraph] bug in get.all.shortest.paths?**,
*Laurin Müller* **<=**