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@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@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