Re: [igraph] bug in get.all.shortest.paths?

[Tamas Nepusz]

Hi Laurin,

Which igraph version are you using? I have just installed 0.5.5 from
CRAN and it works fine for me; for get.all.shortest.paths(ig, from=X)
where (X is any number from 0-6) I get seven shortest paths as expected.

-- 
Tamas

On 01/27/2011 11:22 AM, Laurin Müller wrote:
> 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-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>