# Finding a shortest distance in a graph 

from jhplot  import HGraph

c1 = HGraph("Canvas",600,600,1, 1)

v1="v1"
v2="v2"
v3="v3"
v4="v4"
v5="v5"
v6="v6"
v7="v7"
v8="v8"

c1.addVertex( v1 )
c1.addVertex( v2 )
c1.addVertex( v3 )
c1.addVertex( v4 )
c1.addVertex( v5 )
c1.addVertex( v6 )
c1.addVertex( v7 )
c1.addVertex( v8 )

c1.setPos( v1, 130, 40 )
c1.setPos( v2, 60, 200 )
c1.setPos( v3, 310, 330 )
c1.setPos( v4, 380, 70 )
c1.setPos( v5, 300, 150 )
c1.setPos( v6, 50, 20 )
c1.setPos( v7, 400, 380 )
c1.setPos( v8, 50, 400 )

c1.addEdge( v1, v2 )
c1.addEdge( v2, v3 )
c1.addEdge( v3, v1 )
c1.addEdge( v4, v3 )
c1.addEdge( v1, v5 )
c1.addEdge( v2, v6 )
c1.addEdge( v6, v7 )
c1.addEdge( v4, v8 )

c1.visible()


# see: http://jgrapht.org/javadoc/org/jgrapht/alg/package-summary
# http://jgrapht.org/javadoc/org/jgrapht/alg/shortestpath/package-summary
graph=c1.getListenableGraph()
print graph

from org.jgrapht import GraphTests
print "Is complete=", 	GraphTests.isSimple(graph)
print "Is complete=",   GraphTests.isComplete(graph)


from org.jgrapht.alg.shortestpath import DijkstraShortestPath 
print "Find path between ",v1, " and ", v3
d=DijkstraShortestPath(graph)
short=d.getPath(v1,v3)  
# distance measured in the number of edges.
print "Shortest path=",short, " Distance=",short.getLength()


from org.jgrapht.alg.shortestpath import BidirectionalDijkstraShortestPath
print "Find bi-directional shortest path  between ",v1, " and ", v3
d=BidirectionalDijkstraShortestPath(graph)
short=d.getPath(v1,v3)
print "Shortest path=",short, " Distance=",short.getLength()