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

[Gábor Csárdi]

Federico,

On Fri, Oct 8, 2010 at 6:47 PM, federico vaglio
<address@hidden> wrote:
> 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 am sorry to say, but this will not be any faster in C. (Well, _very_
marginally, maybe.)

> 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,

You did not supply a correct weight vector, i.e. the length of the
weight vector must match the number of edges in the graph.

Btw. igraph_get_shortest_paths_dijkstra is not the same
igraph_get_all_shortest_paths_dijkstra.

Best,
Gabor

> 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
>>>
>>>
>>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM