help need to get all paths in SPT

[vy]

Hi ,
I am newbie  and have spent few hours in code, and still exploring. Apologies if its very basic question.

In a network I need to build a SPT from a source,  and list all the shortest paths to a given destination. I trying to use graphserver
===
#!/usr/bin/env python
from graphserver.core import Graph, Street, State
gg = Graph()
for i in range(10):
   gg.add_vertex("name_"+str(i))
gg.add_edge( "name_0", "name_3", Street("0-3", 100) )
gg.add_edge( "name_1", "name_3", Street("1-3", 100) )
gg.add_edge( "name_2", "name_3", Street("2-3", 100) )

gg.add_edge( "name_0", "name_4", Street("0-4", 100) )
gg.add_edge( "name_1", "name_4", Street("1-4", 100) )
gg.add_edge( "name_2", "name_4", Street("2-4", 100) )

gg.add_edge( "name_3", "name_4", Street("3-4", 100) )
gg.add_edge( "name_3", "name_5", Street("3-5", 100) )
gg.add_edge( "name_3", "name_6", Street("3-6", 100) )
gg.add_edge( "name_4", "name_5", Street("4-5", 100) )
gg.add_edge( "name_4", "name_6", Street("4-6", 100) )
gg.add_edge( "name_5", "name_6", Street("5-6", 100) )

gg.add_edge( "name_5", "name_7", Street("5-7", 100) )
gg.add_edge( "name_5", "name_8", Street("5-8", 100) )
gg.add_edge( "name_5", "name_9", Street("5-9", 100) )

gg.add_edge( "name_6", "name_7", Street("6-7", 100) )
gg.add_edge( "name_6", "name_8", Street("6-8", 100) )
gg.add_edge( "name_6", "name_9", Street("6-9", 100) )

spt = gg.shortest_path_tree( "name_0", "name_7", State(1,0))
#for s in spt:
   #vertices, edges = s.path("name_7")
vertices, edges = spt.path("name_7")
   #for v in vertices:
      #print v
for e in edges:
   print e
print spt
print spt.size

print spt.get_vertex("name_0")
print spt.get_vertex("name_0").outgoing.count(spt.get_vertex("name_0").outgoing)
print spt.get_vertex("name_0").outgoing
==========
<Edge><Street name='0-4' length='100.000000' rise='0.000000' fall='0.000000' way='0' reverse='False'/></Edge>
<Edge><Street name='4-5' length='100.000000' rise='0.000000' fall='0.000000' way='0' reverse='False'/></Edge>
<Edge><Street name='5-7' length='100.000000' rise='0.000000' fall='0.000000' way='0' reverse='False'/></Edge>
<graphserver.core.ShortestPathTree object at 0x8b8908c>
8
<SPTVertex degree_out='2' degree_in='0' label='name_0'/>
0

====

I would like get all the Shortest paths from 0-7 listed and the count in this case would be 4. I just get one of them.  Please let me know how to get other paths listed. I guess the 8 is the number of links in SPT. If there is any packages that would help me please let me. I would like all the paths be numbered or indexed, so that they can be uniquely identified.

I will be running this on some specific set of nodes as sources.

Thanks and regards,
vy.

[flo]

Hi vy,

as far as I understand you are trying to solve the "k-shortest path problem",
which is a harder problem to solve than just finding one of the shortest paths.
The result of finding all possible short(est) paths is itself a graph
structure and
there are a lot of different paths within that graph that just differ
by one edge...
Probably you only want very few of these paths that are "real" alternatives.

The "shortest path tree" that graphserver computes will just find one
shortest path
because it is a tree (and no graph) where every path from root to a
leave is unique.
Maybe the bidirectional variant in graphserver is capable of finding
several paths..??

flo

> --
> You received this message because you are subscribed to the Google Groups
> "Graphserver" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/graphserver/-/t05hsgBQTBEJ.
> To post to this group, send email to graph...@googlegroups.com.
> To unsubscribe from this group, send email to
> graphserver...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/graphserver?hl=en.