[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] Re: Re: shortest paths in a undirected weighted graph
From: |
federico vaglio |
Subject: |
[igraph] Re: Re: shortest paths in a undirected weighted graph |
Date: |
Fri, 8 Oct 2010 18:47:35 +0200 |
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:
>
>Best Regards,
>Gabor
>
>On Wed, Oct 6, 2010 at 11:42 PM, federico vaglio
>> 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
>>
>>
>
- [igraph] Re: Re: shortest paths in a undirected weighted graph,
federico vaglio <=