Now it starts the interesting part, we’ll actually go to see one language a time the real program.
The program that given the input we’ve seen in the previous chapter gives us a kind of useful output.
The program is divided in a few different parts:
Optionally we can also graph the result using the library pydot and passing the “-d” flag from the command line.
The Floyd Warshall algorithm is the core of the program, instead of calculating the shortest path from each city of the path we just calculate using dynamic programming techniques the shortest distances between all the nodes.
It maybe slower if we just want the shortest path between two cities but it adds no more computational complexity when the path length grows.
def floyd_warshall(cities, dist):
"""returns a dictionary containing the minumum distances between cities"""
dim = len(cities)
old = new = {}
# first cycle to set the initial configuration
for c1 in cities:
for c2 in cities:
old[(c1, c2)] = [dist[(c1, c2)], [c2]]
# ranging over the distance between nodes
for k in range(1, dim):
for c1 in cities:
for c2 in cities:
diretto = old[(c1, c2)]
before = old[(c1, cities[k-1])]
after = old[(cities[k-1], c2)]
if diretto[0] <= (before[0] + after[0]):
new[(c1, c2)] = diretto
else:
new[(c1, c2)] = [before[0] + after[0], before[1]+after[1]]
old = new
return new
We use two dictionaries to calculate at each step what is the shortest distance at k-th step (with k steps between c1 and c2).
We want to save both the distance and the intermediate cities.
The rest of the code is pretty simple to understand, a nice thing (I believe) can be found here:
for t1, t2 in zip(path, path[1:]):
In general using zip over a list and a list without the first element allows get all the pairs in order:
In [76]: k = range(4) In [77]: for t1, t2 in zip(k, k[1:]): ....: print t1, t2 ....: ....: 0 1 1 2 2 3
So we can execute our navigator program for a fairly simple input and get:
./nav.py -d GRICIGNANO.CANISTRO.BELLINO.FORCE.CONSIGLIO.AFRAGOLA.CASTELPOTO.GRICIGNANO.CASTELPOTO.GORIANO.CASTELPOTO.AFRAGOLA.FORCE 57
In the same folder the program has generated two png files (if it was able to use the pydot module): path.png and pathgraph.png.
The first one shows the full map with distances between cities.
Red node is the starting city, yellow end node and green nodes are intermediate cities (left nodes if we don’t pass trough them).
click on the image to see it larger
In this other png we actually in what order we go trough the map, in form order(distance).
Here there is the full source code:
#!/usr/bin/env python
from copy import deepcopy
from sys import maxint
from sys import argv
from getopt import getopt
def parse_stradario(stradario):
"""parses the file containing the map"""
toparse = open(stradario).readline().split('.')
idx = 0
ncities = int(toparse[idx])
cities = toparse[1 : ncities + 1]
idx = ncities + 1
# main data structure used
dst = {}
for jdx in range(0, ncities * ncities, ncities):
for kdx in range(ncities):
val = int(toparse[idx + jdx + kdx])
if val < 0:
val = maxint
dst[(cities[jdx / ncities], cities[kdx])] = val
return ncities, cities, dst
def parse_percorso(percorso):
"""parses the path"""
return file.readline(open(percorso,'r')).split('.')[:-1]
def floyd_warshall(cities, dist):
"""returns a dictionary containing the minumum distances between cities"""
dim = len(cities)
old = new = {}
# first cycle to set the initial configuration
for c1 in cities:
for c2 in cities:
old[(c1, c2)] = [dist[(c1, c2)], [c2]]
# ranging over the distance between nodes
for k in range(1, dim):
for c1 in cities:
for c2 in cities:
diretto = old[(c1, c2)]
before = old[(c1, cities[k-1])]
after = old[(cities[k-1], c2)]
if diretto[0] <= (before[0] + after[0]):
new[(c1, c2)] = diretto
else:
new[(c1, c2)] = [before[0] + after[0], before[1]+after[1]]
old = new
return new
def draw(cities, dist, path):
"""draws the graphs"""
try:
import pydot
except Exception.ImportError:
print "pydot not present, install it if you want to graph"
return
graph = pydot.Dot(graph_type='graph')
nodes = []
for c in cities:
n = pydot.Node(c, label=c, color='black')
if c == path[0]:
n.set_color('red')
elif c == path[-1]:
n.set_color('yellow')
elif c in path[1 : len(path)-1]:
n.set_color('green')
nodes.append(n)
graph.add_node(n)
for i in range(len(cities)):
for j in range(i + 1, len(cities)):
d = dist[(cities[i], cities[j])]
if d < maxint:
e = pydot.Edge(nodes[i], nodes[j], weight=str(d), label=str(d))
graph.add_edge(e)
pathGraph = pydot.Dot(graph_type='digraph')
# very nice way to enumerate couples of a list
i = 1
for t1, t2 in zip(path, path[1:]):
e = graph.get_edge(t1, t2)
w = 0
# I could have more than one edge from get_edge
if isinstance(e, list):
w = e[0].get_weight()
else:
w = e.get_weight()
e1 = pydot.Edge(pydot.Node(t1, label=t1), pydot.Node(t2, label=t2), label=str(i)+"(" + w + ")")
pathGraph.add_edge(e1)
i += 1
pathGraph.write_png('pathgraph.png')
graph.write_png('path.png')
def usage():
"""docstring for usage"""
print """
./nav.py [-s stradario] [-p path] [-d]
nav.py gets as input (optional) a map and a path chosen and outputs the shortest path,
optionally with option [-d] it also creates two nice graphs with pydot and open them.
"""
def main():
"""Main function"""
strad = "stradario.txt"
path = "percorso.txt"
isdraw = False
opts, args = getopt(argv[1:], "s:p:d")
for o,a in opts:
if o in '-s':
strad = a
if o in '-p':
path = a
if o in '-d':
isdraw = True
n, cities, dist = parse_stradario(strad)
min_dist = floyd_warshall(cities, dist)
percorso = parse_percorso(path)
final_dist = 0
tappe = [percorso[0]]
for i in range(len(percorso)-1):
dst = min_dist[(percorso[i],percorso[i+1])]
final_dist += dst[0]
tappe += dst[1]
print '.'.join(tappe)
print final_dist
if isdraw:
draw(cities, dist, tappe)
if __name__ == '__main__':
main()
I see that there are problems with the comments (every quote is translated into “"” even if I put the source code in the tag).
I have this problem only with this python file, if you have an idea of the reason of that behavior please tell me.
As usual if you have any critique or doubt (or you find some bugs, sure they are plenty) you’re welcome to notice it.
