[igraph] Re: Re: shortest paths in a undirected weighted graph

[federico vaglio]

Dear Gabor,

I'm moving from igraph R package to C library for speed reasons and, following your previous suggestion on calculating all possible shortest paths in a undirected weighted graph, I have downloaded, compiled and installed the latest nightly of igraph C-library (igraph-nightly-0.6-2030-20100726.tar.gz).

I can compile igraph_get_shortest_paths_dijkstra.c example source code (shipped with the library) but when I try to run the executable I got the following error:

Error at structural_properties.c:4199 :Weight vector length does not match, Invalid value

Aborted

My pc configuration is Fedora 11 x86_64 with gcc 4.4.1 20090725.

The command I run to compile example is:

gcc -I/usr/local/include/igraph -L/usr/local/lib -ligraph igraph_get_shortest_paths_dijkstra.c -o tst.x

Can you help me ?

Thank you in advance

>Federico,

>

>this is implemented in the coming 0.6 version of igraph, you can

>download a snapshot of the R package, that has it from here:

>http://code.google.com/p/igraph/downloads/detail?name=igraph_nightly_0.6-2030-20100726.tar.gz

>

>Best Regards,

>Gabor

>

>On Wed, Oct 6, 2010 at 11:42 PM, federico vaglio

><address@hidden> wrote:

>> Hi to all,

>> is there a way to get all shortest paths, not just lengths, between two

>> vertices in a undirected weighted graph?

>>

>> get.shortest.paths function has "weights" argument but gives only one

>> shortest path, even if more than one shortest path exist between given

>> vertices.

>>

>> get.all.shortest.paths function returns all possible shortest paths but

>> ignores edge weights, even if passed graph has a weight attribute.

>>

>> How to get the best of both ?

>>

>>

>> Thank you in advance

>>

>> Example code.

>>

>> require(igraph)

>>

>> # create a graph with 5 vertices

>> g <- graph.empty(5, dir=FALSE)

>>

>> # add edges

>> g <- add.edges(g, c(0, 1, 0, 2, 0, 3, 1, 4, 2, 4, 3, 4))

>>

>> # edge weigths

>> E(g)$weight <- c(1, 1, 2, 1, 1, 1)

>>

>> # use weights but return only one path

>> get.shortest.paths(g, from=0, to=4)

>>

>> #

>> # my result

>> #[[1]]

>> #[1] 0 2 4

>>

>>

>> # return all shortes paths but ignore weights

>> get.all.shortest.paths(g, from=0, to=4)

>>

>> #

>> # my result

>> #[[1]]

>> #[1] 0 3 4

>> #

>> #[[2]]

>> #[1] 0 2 4

>> #

>> #[[3]]

>> #[1] 0 1 4

>>

>>

>> _______________________________________________

>> igraph-help mailing list

>> address@hidden

>> http://lists.nongnu.org/mailman/listinfo/igraph-help

>>

>>

>