"""This module contains the SmallWorldGraph class for 4.4, exercise 4.

"""
import itertools
import random

from Graph import Edge
from RandomGraph import RandomGraph


class SmallWorldGraph(RandomGraph):
    """A small world graph for 4.4, exercise 4 in Think Complexity."""

    def __init__(self, vs, k, p):
        """Create a small world graph. Parameters:
            vs - a list of vertices
            k - regular graph parameter k: the number of edges between vertices
            p - probability for rewiring.

        First a regular graph is created from the list of vertices and parameter
        k, which specifies how many edges each vertex should have. Then the
        rewire() method is called with parameter p to rewire the graph according
        to the algorithm by Watts and Strogatz.

        """
        super(SmallWorldGraph, self).__init__(vs=vs)
        self.add_regular_edges(k)
        self.rewire(p)

    def rewire(self, p):
        """Assuming the graph is initially a regular graph, rewires the graph
        using the Watts and Strogatz algorithm.

        """
        # We iterate over the edges in a random order:
        edges = self.edges()
        random.shuffle(edges)
        vertices = self.vertices()

        for e in edges:
            if random.random() < p:
                v, w = e    # remember the 2 vertices this edge connected
                self.remove_edge(e)     # remove from graph

                # pick another vertex to connect to v; duplicate edges are
                # forbidden
                while True:
                    x = random.choice(vertices)
                    if v is not x and not self.get_edge(v, x):
                        self.add_edge(Edge(v, x))
                        break

    def clustering_coefficient(self):
        """Compute the clustering coefficient for this graph as defined by Watts
        and Strogatz.

        """
        cv = {}
        for v in self:
            # consider a node and its neighbors
            nodes = self.out_vertices(v)
            nodes.append(v)

            # compute the maximum number of possible edges between these nodes
            # if they were all connected to each other:
            n = len(nodes)
            if n == 1:
                # edge case of only 1 node; handle this case to avoid division
                # by zero in the general case
                cv[v] = 1.0
                continue

            possible = n * (n - 1) / 2.0

            # now compute how many edges actually exist between the nodes
            actual = 0
            for x, y in itertools.combinations(nodes, 2):
                if self.get_edge(x, y):
                    actual += 1

            # the fraction of actual / possible is this nodes C sub v value
            cv[v] = actual / possible

        # The clustering coefficient is the average of all C sub v values
        if len(cv):
            return sum(cv.values()) / float(len(cv))
        return 0.0