How to find SPT and equal weight paths using graphserver?

29 views
Skip to first unread message

vy

unread,
Aug 19, 2012, 4:26:22 AM8/19/12
to graph...@googlegroups.com, V Yegyanathan
Hi.

I am newbie and working on a requirement to get  SPT built from single node of a graph [My actual requirement for multiple nodes but I can extend from here] . 
I would also require all possible SP be identified, and  each paths be clearly identified. I came across graphserver and tried for some time(hrs), both as code walk and exc. sample code.
===
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", None, State(1000,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.paths
print spt.size
print spt.to_dot()

;;;
===
<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 0xb722e06c>
8
digraph G {    name_0 -> name_3;
    name_0 -> name_4;
    name_4 -> name_5;
    name_4 -> name_6;
    name_5 -> name_7;
    name_5 -> name_8;
    name_5 -> name_9;
}

==
I am getting the shortest path tree in dot description, but only one such of  other possibilities. Hence getting edges of only one path of 4 equivalent paths that exist from 0-7. I would like to  get all the  equal weight paths identified.

Is graphserver capable getting this done and if so would like to know, how to do this. Or is there any other package that is capable of doing this.

PS:- I had earlier posted this question, but could not see that listed after a long time and hence reposting.
Thanks and regards,
vy
Reply all
Reply to author
Forward
0 new messages