Goal:
import sys
import graphviz
import pygraphviz
import networkx as nx
from geopy.distance import great_circle
from collections import defaultdict
import numpy as np
import pandas as pd
from IPython.display import display, HTML
iterations = 30 # how many algorithm steps to show?
speedoflight = 200000 # km/s in fibre
While NetworkX is pretty powerful, some of its API is a bit cumbersome. We use a little helper class to make life easier.
class GraphHelper():
def __init__(self, graph=None, path=None):
"""Delegate the actual graph handling to an nx class.
(alternative subclassing, but a bit cumbersome to work with the
networkx classes)
Setup graph attributes like distances and empty data strcutrues
for the routing algorithm: each node gets a distvector to store
its currently computed distance vector and a disttable, storing
the distance vectors it has most recently received from all its
known neighbors."""
if path:
self.gr = nx.read_gml(path)
else:
self.gr = graph
self.compute_distances()
for n, ndata in self.gr.nodes.items():
# self.gr.nodes[n]['distvector'] = defaultdict(lambda: sys.float_info.max)
ndata['distvector'] = defaultdict(lambda: sys.float_info.max)
# self.gr.nodes[n]['disttable'] = dict([
ndata['disttable'] = dict([
(neigh, defaultdict(lambda: sys.float_info.max))
for neigh in self.gr.neighbors(n)
])
for neigh in self.gr.neighbors(n):
ndata['disttable'][neigh][n] = self.gr[n][neigh]['weight']
ndata['distvector'][neigh] = self.gr[n][neigh]['weight']
def show_node(self, n):
"""Display both the current distance vector and all
the node's neighbors recently received distance vectors
in a convenient table, using panda's data frames"""
tmp = self.gr.nodes[n]['disttable']
# let's hope that **DV** will never appear as a node name:
tmp['**DV**'] = self.gr.nodes[n]['distvector']
df = pd.DataFrame.from_dict(tmp)
# display: renders the given HTML directly; df will return HTML
display(df)
def show_nodes(self, n=None):
# TODO: restructure; this is silly.
if not n:
for nn in self.gr.nodes():
print("Node: ", nn)
self.show_node(nn)
else:
self.show_node(n)
def dist_vector_arrives(self, to_node, neighbor, ):
"""Actual routing algorithm: What to do when an update
arrives from a neighbor in the form of a new distance vector?"""
# what do we currently know from this node? This has to be updated
local_dist_vector = self.gr.nodes[to_node]['disttable'][neighbor]
# get the neighbor's distance vector: this is what we just received:
arriving_dist_vector = self.gr.nodes[neighbor]['distvector']
# cost between this node and the neighbor
cost = self.gr.edges[to_node, neighbor]['weight']
# this node's current distance vector to all known destinations
# this has to be updated with information from neighbor
my_dist_vector = self.gr.nodes[to_node]['distvector']
# just for illustration: say what we just know:
print("we learn:")
print(list(arriving_dist_vector.items()))
# do the update, iterate over all entries in the just received information
for k, v in arriving_dist_vector.items():
# add code that updates the local_dist_vector
# and the just received one
# Watch out: distance vectors are defaultdicts that have max_float
# as default value; that should simplify your code quite a bit
#
### BEGIN SOLUTION
local_dist_vector[k] = v + cost
my_dist_vector[k] = min(my_dist_vector[k], local_dist_vector[k])
### END SOLUTION
def compute_distances(self):
"""For initalization, computing distances and latency
between all pairs of nodes. Update corresponding edge
attributes. """
for a, b in self.gr.edges():
node_a = self.gr.nodes[a]
node_b = self.gr.nodes[b]
edge = self.gr[a][b]
# Use geopy functions to compute distance between the nodes
# based on the Latitude and Longitude attributes of the nodes
# Compute latency between them using speedoflight
# store latex in the edge's weight attribute; distance in
# the edge's len attribute
# Watch out: not all nodes need to have meaningful
# Latitude or Longitude information!
### BEGIN SOLUTION
try:
dist = float(great_circle(
(node_a['Latitude'], node_a['Longitude']),
(node_b['Latitude'], node_b['Longitude']),
).km)
time = dist/speedoflight
edge['weight'] = time * 1000 # ok, not SI units, but ms are just easier to read
edge['len'] = dist
except:
edge['weight'] = sys.float_info.max
edge['len'] = sys.float_info.max
### END SOLUTION
def display(self):
"""Show the graph based on graphviz layouting"""
tmp = nx.nx_agraph.to_agraph(self.gr)
# better layout: too slow for Uebung
# tmp.layout('neato')
# tmp.draw('neato.png')
Gr = graphviz.Source(tmp.string())
return Gr
We load a gml description obtained from TopologyZoo (http://www.topology-zoo.org). Nice little todo: directly download from there into a file-like object... We use the NetworkX library to parse the file and to represent the network graph with its attributes.
# H = GraphHelper(path='Abvt.gml')
H = GraphHelper(path='Ans.gml')
TODO: Put link weights into the display
H.display()
H.show_nodes()
For each iteration, select an edge along which we assume a distance vector is sent. Receiving nodes updates its information from this node and compares it to its current best to see if there is any improvement.
edge_list = list(H.gr.edges.items())
for i in range(iterations):
ri = np.random.randint(0, len(edge_list)-1)
# watch out: randint includes BOTH lower and upper limt,
# hence, the -1!
from_node, to_node = edge_list[ri][0]
print("#######################")
print(from_node, " -->> ", to_node)
print("Old information at ", to_node)
H.show_nodes(to_node)
H.dist_vector_arrives(to_node, from_node)
print("Updated information at ", to_node)
H.show_nodes(to_node)