List of all shortest paths

11 views
Skip to first unread message

Flavio B Gonzaga

unread,
Mar 2, 2010, 3:16:32 PM3/2/10
to guess-discuss
Hi for all,
I would like to obtain the list of all shortest paths between a pair
of nodes.

For example:

If I have 2 shortest paths from v1 to v4, like:
v1 -> v5 -> v4
v1 -> v2 -> v4

If i use v1.unweightedShortestPath(v4), this will return only one
result. In the same mode, if I use v1.dijkstraShortestPath(v4), this
will also return only one path.

So, how to obtain a list containing both results v1->v5->v4 and v1->v2-
>v4?

Thanks!

Flavio

Gutemberg Vieira

unread,
Mar 9, 2010, 7:00:45 AM3/9/10
to guess-discuss
Flavio,

You will need something like this:

from com.hp.hpl.guess.mascopt import MascoptDiGraphProxy

proxy = MascoptDiGraphProxy.createProxy(g)
proxy.kShortestPaths(2,v1,v4)

For more guidance, search the group archives for MascoptDiGraphProxy.

Hope this helps,
Gutemberg



--
You received this message because you are subscribed to the Google Groups "guess-discuss" group.
To post to this group, send email to guess-...@googlegroups.com.
To unsubscribe from this group, send email to guess-discus...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/guess-discuss?hl=en.


Flavio Gonzaga

unread,
Jun 4, 2010, 7:23:03 PM6/4/10
to guess-...@googlegroups.com
Hi,

I implemented the following code to obtain the list of all shortest
paths between all pair of nodes. It works well for small graphs, but
when I run for my graph, which has 15095 nodes, the Guess freezes.

I've calculated the centrality to this graph in Guess, which
calculates internally all shortest paths, and the Guess worked well.

Does anybody has any idea to solve this problem?

######################

from com.hp.hpl.guess.mascopt import MascoptDiGraphProxy;
var_file = open("/Applications/guess/kshortest.txt","w");
for cont1 in g.nodes:
    for cont2 in g.nodes:
        if(cont1 != cont2):
            proxy = MascoptDiGraphProxy.createProxy(g);
            shortest = proxy.kShortestPaths(2,cont1,cont2);
            var_file.write(str(cont1)+str(cont2)+": "+str(shortest)+"\n");
var_file.close();

######################

Thanks,

Flavio

--
Flavio Barbieri Gonzaga

Reply all
Reply to author
Forward
0 new messages