bgneal@23: """This module contains the SmallWorldGraph class for 4.4, exercise 4.
bgneal@23: 
bgneal@23: """
bgneal@23: import itertools
bgneal@23: import random
bgneal@23: 
bgneal@23: from Graph import Edge
bgneal@23: from RandomGraph import RandomGraph
bgneal@23: 
bgneal@23: 
bgneal@24: INFINITY = float('Inf')
bgneal@24: 
bgneal@23: class SmallWorldGraph(RandomGraph):
bgneal@23:     """A small world graph for 4.4, exercise 4 in Think Complexity."""
bgneal@23: 
bgneal@23:     def __init__(self, vs, k, p):
bgneal@23:         """Create a small world graph. Parameters:
bgneal@23:             vs - a list of vertices
bgneal@23:             k - regular graph parameter k: the number of edges between vertices
bgneal@23:             p - probability for rewiring.
bgneal@23: 
bgneal@23:         First a regular graph is created from the list of vertices and parameter
bgneal@23:         k, which specifies how many edges each vertex should have. Then the
bgneal@23:         rewire() method is called with parameter p to rewire the graph according
bgneal@23:         to the algorithm by Watts and Strogatz.
bgneal@23: 
bgneal@23:         """
bgneal@23:         super(SmallWorldGraph, self).__init__(vs=vs)
bgneal@23:         self.add_regular_edges(k)
bgneal@23:         self.rewire(p)
bgneal@23: 
bgneal@24:         # give each edge a default length of 1; this is used by the
bgneal@24:         # shortest_path_tree() method
bgneal@24:         for e in self.edges():
bgneal@24:             e.length = 1
bgneal@24: 
bgneal@23:     def rewire(self, p):
bgneal@23:         """Assuming the graph is initially a regular graph, rewires the graph
bgneal@23:         using the Watts and Strogatz algorithm.
bgneal@23: 
bgneal@23:         """
bgneal@23:         # We iterate over the edges in a random order:
bgneal@23:         edges = self.edges()
bgneal@23:         random.shuffle(edges)
bgneal@23:         vertices = self.vertices()
bgneal@23: 
bgneal@23:         for e in edges:
bgneal@23:             if random.random() < p:
bgneal@23:                 v, w = e    # remember the 2 vertices this edge connected
bgneal@23:                 self.remove_edge(e)     # remove from graph
bgneal@23: 
bgneal@23:                 # pick another vertex to connect to v; duplicate edges are
bgneal@23:                 # forbidden
bgneal@23:                 while True:
bgneal@23:                     x = random.choice(vertices)
bgneal@23:                     if v is not x and not self.get_edge(v, x):
bgneal@23:                         self.add_edge(Edge(v, x))
bgneal@23:                         break
bgneal@23: 
bgneal@23:     def clustering_coefficient(self):
bgneal@23:         """Compute the clustering coefficient for this graph as defined by Watts
bgneal@23:         and Strogatz.
bgneal@23: 
bgneal@23:         """
bgneal@23:         cv = {}
bgneal@23:         for v in self:
bgneal@23:             # consider a node and its neighbors
bgneal@23:             nodes = self.out_vertices(v)
bgneal@23:             nodes.append(v)
bgneal@23: 
bgneal@23:             # compute the maximum number of possible edges between these nodes
bgneal@23:             # if they were all connected to each other:
bgneal@23:             n = len(nodes)
bgneal@23:             if n == 1:
bgneal@23:                 # edge case of only 1 node; handle this case to avoid division
bgneal@23:                 # by zero in the general case
bgneal@23:                 cv[v] = 1.0
bgneal@23:                 continue
bgneal@23: 
bgneal@23:             possible = n * (n - 1) / 2.0
bgneal@23: 
bgneal@23:             # now compute how many edges actually exist between the nodes
bgneal@23:             actual = 0
bgneal@23:             for x, y in itertools.combinations(nodes, 2):
bgneal@23:                 if self.get_edge(x, y):
bgneal@23:                     actual += 1
bgneal@23: 
bgneal@23:             # the fraction of actual / possible is this nodes C sub v value
bgneal@23:             cv[v] = actual / possible
bgneal@23: 
bgneal@23:         # The clustering coefficient is the average of all C sub v values
bgneal@23:         if len(cv):
bgneal@23:             return sum(cv.values()) / float(len(cv))
bgneal@23:         return 0.0
bgneal@24: 
bgneal@24:     def shortest_path_tree(self, source, hint=None):
bgneal@24:         """Finds the length of the shortest path from the source vertex to all
bgneal@24:         other vertices in the graph. This length is stored on the vertices as an
bgneal@24:         attribute named 'dist'. The algorithm used is Dijkstra's.
bgneal@24: 
bgneal@24:         hint: if provided, must be a dictionary mapping tuples to already known
bgneal@24:         shortest path distances. This can be used to speed up the algorithm.
bgneal@24: 
bgneal@24:         """
bgneal@24:         if not hint:
bgneal@24:             hint = {}
bgneal@24: 
bgneal@24:         for v in self.vertices():
bgneal@24:             v.dist = hint.get((source, v), INFINITY)
bgneal@24:         source.dist = 0
bgneal@24: 
bgneal@24:         queue = [v for v in self.vertices() if v.dist < INFINITY]
bgneal@24:         sort_flag = True
bgneal@24:         while len(queue):
bgneal@24: 
bgneal@24:             if sort_flag:
bgneal@24:                 queue.sort(key=lambda v: v.dist)
bgneal@24:                 sort_flag = False
bgneal@24: 
bgneal@24:             v = queue.pop(0)
bgneal@24: 
bgneal@24:             # for each neighbor of v, see if we found a new shortest path
bgneal@24:             for w, e in self[v].iteritems():
bgneal@24:                 d = v.dist + e.length
bgneal@24:                 if d < w.dist:
bgneal@24:                     w.dist = d
bgneal@24:                     queue.append(w)
bgneal@24:                     sort_flag = True
bgneal@24: 
bgneal@25:     def all_pairs_floyd_warshall(self):
bgneal@25:         """Finds the shortest paths between all pairs of vertices using the
bgneal@25:         Floyd-Warshall algorithm.
bgneal@25: 
bgneal@25:         http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
bgneal@25: 
bgneal@25:         """
bgneal@25:         vertices = self.vertices()
bgneal@25:         dist = {}
bgneal@25:         for i in vertices:
bgneal@25:             for j in vertices:
bgneal@25:                 if i is j:
bgneal@25:                     dist[i, j] = 0.0
bgneal@25:                 else:
bgneal@25:                     e = self.get_edge(i, j)
bgneal@25:                     dist[i, j] = e.length if e else INFINITY
bgneal@25: 
bgneal@25:         for k in vertices:
bgneal@25:             for i in vertices:
bgneal@25:                 for j in vertices:
bgneal@25:                     d_ik = dist[i, k]
bgneal@25:                     d_kj = dist[k, j]
bgneal@25:                     new_cost = d_ik + d_kj
bgneal@25:                     if new_cost < dist[i, j]:
bgneal@25:                         dist[i, j] = new_cost
bgneal@25: 
bgneal@25:         return dist
bgneal@25: 
bgneal@24:     def big_l(self):
bgneal@24:         """Computes the "big-L" value for the graph as per Watts & Strogatz.
bgneal@24: 
bgneal@24:         big_l() is defined as the number of edges in the shortest path between
bgneal@24:         two vertices, averaged over all vertices.
bgneal@24: 
bgneal@25:         Uses the shortest_path_tree() method, called once for every node.
bgneal@25: 
bgneal@24:         """
bgneal@24:         d = {}
bgneal@24:         for v in self.vertices():
bgneal@24:             self.shortest_path_tree(v, d)
bgneal@24:             t = [((w, v), w.dist) for w in self.vertices() if v is not w]
bgneal@24:             d.update(t)
bgneal@24: 
bgneal@24:         if len(d):
bgneal@24:             return sum(d.values()) / float(len(d))
bgneal@24:         return 0.0
bgneal@25: 
bgneal@25:     def big_l2(self):
bgneal@25:         """Computes the "big-L" value for the graph as per Watts & Strogatz.
bgneal@25: 
bgneal@25:         big_l() is defined as the number of edges in the shortest path between
bgneal@25:         two vertices, averaged over all vertices.
bgneal@25: 
bgneal@25:         Uses the all_pairs_floyd_warshall() method.
bgneal@25: 
bgneal@25:         """
bgneal@25:         dist = self.all_pairs_floyd_warshall()
bgneal@25:         vertices = self.vertices()
bgneal@25:         result = [dist[i, j] for i in vertices for j in vertices if i is not j]
bgneal@25: 
bgneal@25:         if len(result):
bgneal@25:             return sum(result) / float(len(result))
bgneal@25:         return 0.0