# -*- coding: utf-8 -*-
# Problem Set 1 / Exercise 3
# Code for Python 2.7
import itertools
import networkx
#create the graph
G = networkx.MultiGraph()
#read csv input data
with open("BerlinU.csv") as f:
f.readline()
for line in f:
x = line.split(",")
G.add_edge(x[0], x[1], weight = float(x[2]))
#compute shortest path
print "Shortest path:", networkx.shortest_path(G, "Hönow", "Krumme Lanke", "weight")
print "Length:", networkx.shortest_path_length(G, "Hönow", "Krumme Lanke", "weight"), "\n"
#compute all paths between two different vertices and take the longest one
maxLength = 0
maxPath = []
for (v, w) in itertools.combinations(G.nodes(), 2):
for path in networkx.all_simple_paths(G, v, w):
length = sum([ max([ G.edge[path[k]][path[k+1]][l]["weight"] for l in G.edge[path[k]][path[k+1]] ]) for k in range(len(path) - 1) ])
if length > maxLength:
maxPath = path[:]
maxLength = length
print "Longest path:", maxPath
print "Length:", maxLength