#### PATTERN | GRAPH #################################################################################
# Copyright (c) 2010 University of Antwerp, Belgium
# Author: Tom De Smedt <tom@organisms.be>
# License: BSD (see LICENSE.txt for details).
# http://www.clips.ua.ac.be/pages/pattern

######################################################################################################
# This module can benefit greatly from loading psyco.

from math     import sqrt, pow
from math     import sin, cos, atan2, degrees, radians, pi
from random   import random
from heapq    import heappush, heappop
from warnings import warn
from codecs   import open

# float("inf") doesn't work on windows.
INFINITE = 1e20

# This module is standalone, line(), ellipse() and Text.draw() 
# must be either implemented or patched:
def line(x1, y1, x2, y2, stroke=(0,0,0,1), strokewidth=1):
    pass
def ellipse(x, y, width, height, fill=(0,0,0,1), stroke=None, strokewidth=1):
    pass

class Text:
    def __init__(self, string, **kwargs):
        self.string = string
        self.__dict__.update(kwargs)
    def copy(self):
        k = self.__dict__.copy()
        k.pop("string")
        return Text(self.string, **k)
    def draw(self):
        pass
        
class Vector(object):
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y
        
class Base(object):
    pass

#--- NODE --------------------------------------------------------------------------------------------

def _copy(x):
    # A color can be represented as a tuple or as a nodebox.graphics.Color object,
    # in which case it needs to be copied by invoking Color.copy().
    return hasattr(x, "copy") and x.copy() or x

class Node(object):
    
    def __init__(self, id="", radius=5, **kwargs):
        """ A node with a unique id in the graph.
            Node.id is drawn as a text label, unless optional parameter text=False.
            Optional parameters include: fill, stroke, strokewidth, text, font, fontsize, fontweight.
        """
        self.graph       = None
        self.links       = Links()
        self.id          = id
        self._x          = 0    # Calculated by Graph.layout.update().
        self._y          = 0    # Calculated by Graph.layout.update().
        self.force       = Vector(0,0)
        self.radius      = radius
        self.fill        = kwargs.get("fill", None)
        self.stroke      = kwargs.get("stroke", (0,0,0,1))
        self.strokewidth = kwargs.get("strokewidth", 1)
        self.text        = kwargs.get("text", True) and \
            Text(unicode(id), 
                   width = 85,
                    fill = kwargs.pop("text", (0,0,0,1)), 
                fontsize = kwargs.pop("fontsize", 11), **kwargs) or None
        self._weight     = None # Calculated by Graph.eigenvector_centrality().
        self._centrality = None # Calculated by Graph.betweenness_centrality().
    
    @property
    def _distance(self):
        # Graph.distance controls the (x,y) spacing between nodes.
        return self.graph and float(self.graph.distance) or 1.0
    
    def _get_x(self):
        return self._x * self._distance
    def _get_y(self):
        return self._y * self._distance
    def _set_x(self, v):
        self._x = v / self._distance
    def _set_y(self, v):
        self._y = v / self._distance

    x = property(_get_x, _set_x)
    y = property(_get_y, _set_y)

    @property
    def edges(self):
        return self.graph is not None \
           and [e for e in self.graph.edges if self.id in (e.node1, e.node2)] \
            or []
    
    @property
    def weight(self):
        if self.graph and self._weight is None:
            self.graph.eigenvector_centrality()
        return self._weight
        
    @property
    def centrality(self):
        if self.graph and self._centrality is None:
            self.graph.betweenness_centrality()
        return self._centrality
        
    def flatten(self, depth=1, _visited=None):
        """ Recursively lists the node and nodes linked to it.
            Depth 0 returns a list with the node.
            Depth 1 returns a list with the node and all the directly linked nodes.
            Depth 2 includes the linked nodes' links, and so on.
        """
        _visited = _visited or {}
        _visited[self.id] = (self, depth)
        if depth >= 1:
            for n in self.links: 
                if n.id not in _visited or _visited[n.id][1] < depth-1:
                    n.flatten(depth-1, _visited)
        return [n for n,d in _visited.values()] # Fast, but not order-preserving.
    
    def draw(self, weighted=False):
        """ Draws the node as a circle with the given radius, fill, stroke and strokewidth.
            Draws the node centrality as a shadow effect when weighted=True.
            Draws the node text label.
            Override this method in a subclass for custom drawing.
        """
        # Draw the node weight as a shadow (based on node betweenness centrality).
        if weighted is not False and self.centrality > (weighted==True and -1 or weighted):
            w = self.centrality * 35
            ellipse(
                self.x, 
                self.y, 
                self.radius*2 + w, 
                self.radius*2 + w, fill=(0,0,0,0.2), stroke=None)
        # Draw the node.
        ellipse(
            self.x, 
            self.y, 
            self.radius*2, 
            self.radius*2, fill=self.fill, stroke=self.stroke, strokewidth=self.strokewidth)
        # Draw the node text label.
        if self.text:
            self.text.draw(
                self.x + self.radius, 
                self.y + self.radius)
        
    def contains(self, x, y):
        return abs(self.x - x) < self.radius*2 and \
               abs(self.y - y) < self.radius*2
               
    def __repr__(self):
        return "%s(id=%s)" % (self.__class__.__name__, repr(self.id))

    def __eq__(self, node):
        return isinstance(node, Node) and self.id == node.id
    def __ne__(self, node):
        return not self.__eq__(node)
        
    def copy(self):
        """ Returns a shallow copy of the node (i.e. linked nodes are not copied).
        """
        n = Node(self.id, self.radius, 
                 text = None,
                 fill = _copy(self.fill),
               stroke = _copy(self.stroke),
          strokewidth = self.strokewidth)
        if self.text: 
            n.text = self.text.copy()
        n.__class__ = self.__class__
        return n

class Links(list):
    
    def __init__(self): 
        """ A list in which each node has an associated edge.
            The edge() method returns the edge for a given node id.
        """
        self.edges = dict()
    
    def append(self, node, edge=None):
        if node.id not in self.edges:
            list.append(self, node)
        self.edges[node.id] = edge

    def remove(self, node):
        list.remove(self, node)
        self.edges.pop(node.id, None)

    def edge(self, node): 
        return self.edges.get(isinstance(node, Node) and node.id or node)

#--- EDGE --------------------------------------------------------------------------------------------

coordinates = lambda x, y, d, a: (x + d*cos(radians(a)), y + d*sin(radians(a)))

class Edge(object):

    def __init__(self, node1, node2, weight=0.0, length=1.0, type=None, stroke=(0,0,0,1), strokewidth=1):
        """ A connection between two nodes.
            Its weight indicates the importance (not the cost) of the connection.
            Its type is useful in a semantic network (e.g. "is-a", "is-part-of", ...)
        """
        self.node1       = node1
        self.node2       = node2
        self.weight      = weight
        self.length      = length
        self.type        = type
        self.stroke      = stroke
        self.strokewidth = strokewidth
        
    def draw(self, weighted=False, directed=False):
        """ Draws the edge as a line with the given stroke and strokewidth (increased with Edge.weight).
            Override this method in a subclass for custom drawing.
        """
        w = weighted and self.weight or 0
        line(
            self.node1.x, 
            self.node1.y, 
            self.node2.x, 
            self.node2.y, stroke=self.stroke, strokewidth=self.strokewidth+w)
        if directed:
            self.draw_arrow(stroke=self.stroke, strokewidth=self.strokewidth+w)
            
    def draw_arrow(self, **kwargs):
        """ Draws the direction of the edge as an arrow on the rim of the receiving node.
        """
        x0, y0 = self.node1.x, self.node1.y
        x1, y1 = self.node2.x, self.node2.y
        # Find the edge's angle based on node1 and node2 position.
        a = degrees(atan2(y1-y0, x1-x0))
        # The arrow points to node2's rim instead of it's center.
        r = self.node2.radius
        d = sqrt(pow(x1-x0, 2) + pow(y1-y0, 2))
        x01, y01 = coordinates(x0, y0, d-r-1, a)
        # Find the two other arrow corners under the given angle.
        r = max(kwargs.get("strokewidth", 1) * 3, 6)
        dx1, dy1 = coordinates(x01, y01, -r, a-20)
        dx2, dy2 = coordinates(x01, y01, -r, a+20)
        line(x01, y01, dx1, dy1, **kwargs)
        line(x01, y01, dx2, dy2, **kwargs)
        line(dx1, dy1, dx2, dy2, **kwargs)
    
    def __repr__(self):
        return "%s(id1=%s, id2=%s)" % (self.__class__.__name__, repr(self.node1.id), repr(self.node2.id))
    
    def copy(self, node1, node2):
        e = Edge(node1, node2, self.weight, self.length, self.type, _copy(self.stroke), self.strokewidth)
        e.__class__ = self.__class__
        return e

#--- GRAPH -------------------------------------------------------------------------------------------

def unique(list):
    u, b = [], {}
    for item in list: 
        if item not in b: u.append(item); b[item]=1
    return u

# Graph layouts:
SPRING = "spring"

# Graph node sort order:
WEIGHT, CENTRALITY = "weight", "centrality"

ALL = "all"

class Graph(dict):
    
    def __init__(self, layout=SPRING, distance=10.0):
        """ A network of nodes connected by edges that can be drawn with a given layout.
        """
        self.nodes    = []
        self.edges    = []
        self.root     = None
        self.distance = distance
        self.layout   = layout==SPRING and GraphSpringLayout(self) or GraphLayout(self)
    
    def append(self, type, *args, **kwargs):
        """ Appends a Node or Edge to the graph: Graph.append(Node, id="rabbit").
        """
        if type is Node:
            return self.add_node(*args, **kwargs)
        if type is Edge:
            return self.add_edge(*args, **kwargs)
    
    def add_node(self, id, *args, **kwargs):
        """ Appends a new Node to the graph.
        """
        n = isinstance(id, Node) and id or self.get(id) or Node(id, *args, **kwargs)
        if n.id not in self:
            self.nodes.append(n)
            self[n.id] = n; n.graph = self
            self.root = kwargs.get("root", False) and n or self.root
        return n
    
    def add_edge(self, id1, id2, *args, **kwargs):
        """ Appends a new Edge to the graph.
        """
        # Create nodes that are not yet part of the graph.
        n1 = self.add_node(id1)
        n2 = self.add_node(id2)
        # Creates an Edge instance.
        # If an edge (in the same direction) already exists, yields that edge instead.
        e1 = n1.links.edge(n2)
        if e1 and e1.node1 == n1 and e1.node2 == n2:
            return e1
        e2 = Edge(n1, n2, *args, **kwargs)
        self.edges.append(e2)
        # Synchronizes Node.links:
        # A.links.edge(B) yields edge A->B
        # B.links.edge(A) yields edge B->A
        n1.links.append(n2, edge=e2)
        n2.links.append(n1, edge=e1 or e2)
        return e2        
            
    def remove(self, x):
        """ Removes the given Node (and all its edges) or Edge from the graph.
            Note: removing Edge a->b does not remove Edge b->a.
        """
        if isinstance(x, Node) and x.id in self:
            self.pop(x.id)
            self.nodes.remove(x); x.graph = None
            # Remove all edges involving the given node.
            for e in list(self.edges):
                if x in (e.node1, e.node2):
                    if x in e.node1.links: e.node1.links.remove(x)
                    if x in e.node2.links: e.node2.links.remove(x)
                    self.edges.remove(e) 
        if isinstance(x, Edge):
            self.edges.remove(x)
    
    def node(self, id):
        """ Returns the node in the graph with the given id.
        """
        return self.get(id)
    
    def edge(self, id1, id2):
        """ Returns the edge between the nodes with given id1 and id2.
        """
        return id1 in self and id2 in self and self[id1].links.edge(id2) or None
    
    def shortest_path(self, node1, node2, heuristic=None, directed=False):
        """ Returns a list of nodes connecting the two nodes.
        """
        try: 
            p = dijkstra_shortest_path(self, node1.id, node2.id, heuristic, directed)
            p = [self[id] for id in p]
            return p
        except IndexError:
            return None

    def eigenvector_centrality(self, normalized=True, reversed=True, rating={}, iterations=100, tolerance=0.0001):
        """ Calculates eigenvector centrality and returns a node => weight dictionary.
            Node.weight is updated in the process.
            Node.weight is higher for nodes with a lot of (indirect) incoming traffic.
        """
        ec = eigenvector_centrality(self, normalized, reversed, rating, iterations, tolerance)
        ec = dict([(self[id], w) for id, w in ec.items()])
        for n, w in ec.items(): 
            n._weight = w
        return ec
            
    def betweenness_centrality(self, normalized=True, directed=False):
        """ Calculates betweenness centrality and returns a node => weight dictionary.
            Node.centrality is updated in the process.
            Node.centrality is higher for nodes with a lot of passing traffic.
        """
        bc = brandes_betweenness_centrality(self, normalized, directed)
        bc = dict([(self[id], w) for id, w in bc.items()])
        for n, w in bc.items(): 
            n._centrality = w
        return bc
        
    def sorted(self, order=WEIGHT, threshold=0.0):
        """ Returns a list of nodes sorted by WEIGHT or CENTRALITY.
            Nodes with a lot of traffic will be at the start of the list.
        """
        o = lambda node: getattr(node, order)
        nodes = [(o(n), n) for n in self.nodes if o(n) > threshold]
        nodes = reversed(sorted(nodes))
        return [n for w, n in nodes]
        
    def prune(self, depth=0):
        """ Removes all nodes with less or equal links than depth.
        """
        for n in [n for n in self.nodes if len(n.links) <= depth]:
            self.remove(n)
            
    def fringe(self, depth=0):
        """ For depth=0, returns the list of leaf nodes (nodes with only one connection).
            For depth=1, returns the list of leaf nodes and their connected nodes, and so on.
        """
        u = []; [u.extend(n.flatten(depth)) for n in self.nodes if len(n.links) == 1]
        return unique(u)
        
    @property
    def density(self):
        # Number of edges vs. maximum number of possible edges.
        # E.g. <0.35 => sparse, >0.65 => dense, 1.0 => complete.
        return 2.0*len(self.edges) / (len(self.nodes) * (len(self.nodes)-1))
        
    def split(self):
        return partition(self)
    
    def update(self, iterations=10, **kwargs):
        """ Graph.layout.update() is called the given number of iterations.
        """
        for i in range(iterations):
            self.layout.update(**kwargs)
        
    def draw(self, weighted=False, directed=False):
        """ Draws all nodes and edges.
        """
        for e in self.edges: 
            e.draw(weighted, directed)
        for n in reversed(self.nodes): # New nodes (with Node._weight=None) first. 
            n.draw(weighted)
            
    def node_at(self, x, y):
        """ Returns the node at (x,y) or None.
        """
        for n in self.nodes:
            if n.contains(x, y): return n
            
    def copy(self, nodes=ALL):
        """ Returns a copy of the graph with the given list of nodes (and connecting edges).
            The layout will be reset.
        """
        g = Graph(layout=None, distance=self.distance)
        g.layout = self.layout.copy(graph=g)
        for n in (nodes==ALL and self.nodes or nodes):
            g.append(n.copy(), root=self.root==n)
        for e in self.edges: 
            if e.node1.id in g and e.node2.id in g:
                g.append(e.copy(
                    node1=g[e.node1.id], 
                    node2=g[e.node2.id]))
        return g

#--- GRAPH LAYOUT ------------------------------------------------------------------------------------
# Graph drawing or graph layout, as a branch of graph theory, 
# applies topology and geometry to derive two-dimensional representations of graphs.

class GraphLayout:
    
    def __init__(self, graph):
        """ Calculates node positions iteratively when GraphLayout.update() is called.
        """
        self.graph = graph
        self.iterations = 0
    
    def update(self):
        self.iterations += 1

    def reset(self):
        self.iterations = 0
        for n in self.graph.nodes:
            n._x = 0
            n._y = 0
            n.force = Vector(0,0)
            
    @property
    def bounds(self):
        """ Returns a (x, y, width, height)-tuple of the approximate layout dimensions.
        """
        x0, y0 = +INFINITE, +INFINITE
        x1, y1 = -INFINITE, -INFINITE
        for n in self.graph.nodes:
            if (n.x < x0): x0 = n.x
            if (n.y < y0): y0 = n.y
            if (n.x > x1): x1 = n.x
            if (n.y > y1): y1 = n.y
        return (x0, y0, x1-x0, y1-y0)

    def copy(self, graph):
        return GraphLayout(self, graph)

class GraphSpringLayout(GraphLayout):
    
    def __init__(self, graph):
        """ A force-based layout in which edges are regarded as springs.
            The forces are applied to the nodes, pulling them closer or pushing them apart.
        """
        # Based on: http://snipplr.com/view/1950/graph-javascript-framework-version-001/
        GraphLayout.__init__(self, graph)
        self.k         = 4.0  # Force constant.
        self.force     = 0.01 # Force multiplier.
        self.repulsion = 15   # Maximum repulsive force radius.

    def _distance(self, node1, node2):
        # Yields a tuple with distances (dx, dy, d, d**2).
        # Ensures that the distance is never zero (which deadlocks the animation).
        dx = node2._x - node1._x
        dy = node2._y - node1._y
        d2 = dx*dx + dy*dy
        if d2 < 0.01:
            dx = random() * 0.1 + 0.1
            dy = random() * 0.1 + 0.1
            d2 = dx*dx + dy*dy
        return dx, dy, sqrt(d2), d2

    def _repulse(self, node1, node2):
        # Updates Node.force with the repulsive force.
        dx, dy, d, d2 = self._distance(node1, node2)
        if d < self.repulsion:
            f = self.k**2 / d2
            node2.force.x += f * dx
            node2.force.y += f * dy
            node1.force.x -= f * dx
            node1.force.y -= f * dy
            
    def _attract(self, node1, node2, weight=0, length=1.0):
        # Updates Node.force with the attractive edge force.
        dx, dy, d, d2 = self._distance(node1, node2)
        d = min(d, self.repulsion)
        f = (d2 - self.k**2) / self.k * length
        f *= weight * 0.5 + 1
        f /= d
        node2.force.x -= f * dx
        node2.force.y -= f * dy
        node1.force.x += f * dx
        node1.force.y += f * dy
        
    def update(self, weight=10.0, limit=0.5):
        """ Updates the position of nodes in the graph.
            The weight parameter determines the impact of edge weight.
            The limit parameter determines the maximum movement each update().
        """
        GraphLayout.update(self)
        # Forces on all nodes due to node-node repulsions.
        for i, n1 in enumerate(self.graph.nodes):
            for j, n2 in enumerate(self.graph.nodes[i+1:]):          
                self._repulse(n1, n2)
        # Forces on nodes due to edge attractions.
        for e in self.graph.edges:
            self._attract(e.node1, e.node2, weight*e.weight, 1.0/(e.length or 0.01))
        # Move nodes by given force.
        for n in self.graph.nodes:
            n._x += max(-limit, min(self.force * n.force.x, limit))
            n._y += max(-limit, min(self.force * n.force.y, limit))
            n.force.x = 0
            n.force.y = 0
            
    def copy(self, graph):
        g = GraphSpringLayout(graph)
        g.k, g.force, g.repulsion = self.k, self.force, self.repulsion
        return g

#--- GRAPH THEORY ------------------------------------------------------------------------------------

def depth_first_search(node, visit=lambda node: False, traversable=lambda node, edge: True, _visited=None):
    """ Visits all the nodes connected to the given root node, depth-first.
        The visit function is called on each node.
        Recursion will stop if it returns True, and subsequently dfs() will return True.
        The traversable function takes the current node and edge,
        and returns True if we are allowed to follow this connection to the next node.
        For example, the traversable for directed edges is follows:
         lambda node, edge: node == edge.node1
    """
    stop = visit(node)
    _visited = _visited or {}
    _visited[node.id] = True
    for n in node.links:
        if stop: return True
        if not traversable(node, node.links.edge(n)): continue
        if not n.id in _visited:
            stop = depth_first_search(n, visit, traversable, _visited)
    return stop
    
dfs = depth_first_search;

def breadth_first_search(node, visit=lambda node: False, traversable=lambda node, edge: True):
    """ Visits all the nodes connected to the given root node, breadth-first.
    """
    q = [node]
    _visited = {}
    while q:
        node = q.pop(0)
        if not node.id in _visited:
            if visit(node):
                return True
            q.extend((n for n in node.links if traversable(node, node.links.edge(n))))
            _visited[node.id] = True
    return False
        
bfs = breadth_first_search;

def adjacency(graph, directed=False, reversed=False, stochastic=False, heuristic=None):
    """ Returns a dictionary indexed by node id1's,
        in which each value is a dictionary of connected node id2's linking to the edge weight.
        If directed=True, edges go from id1 to id2, but not the other way.
        If stochastic=True, all the weights for the neighbors of a given node sum to 1.
        A heuristic function can be given that takes two node id's and returns
        an additional cost for movement between the two nodes.
    """
    map = {}
    for n in graph.nodes:
        map[n.id] = {}
    for e in graph.edges:
        id1, id2 = not reversed and (e.node1.id, e.node2.id) or (e.node2.id, e.node1.id)
        map[id1][id2] = 1.0 - 0.5 * e.weight
        if heuristic:
            map[id1][id2] += heuristic(id1, id2)
        if not directed: 
            map[id2][id1] = map[id1][id2]
    if stochastic:
        for id1 in map:
            n = sum(map[id1].values())
            for id2 in map[id1]: 
                map[id1][id2] /= n
    return map

def dijkstra_shortest_path(graph, id1, id2, heuristic=None, directed=False):
    """ Dijkstra algorithm for finding shortest paths.
        Raises an IndexError between nodes on unconnected graphs.
    """
    # Based on: Connelly Barnes, http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466
    def flatten(list):
        # Flattens a linked list of the form [0,[1,[2,[]]]]
        while len(list) > 0:
            yield list[0]; list=list[1]
    G = adjacency(graph, directed=directed, heuristic=heuristic)
    q = [(0, id1, ())] # Heap of (cost, path_head, path_rest).
    visited = set()    # Visited nodes.
    while True:
        (cost1, n1, path) = heappop(q)
        if n1 not in visited:
            visited.add(n1)
        if n1 == id2:
            return list(flatten(path))[::-1] + [n1]
        path = (n1, path)
        for (n2, cost2) in G[n1].iteritems():
            if n2 not in visited:
                heappush(q, (cost1 + cost2, n2, path))
                
def brandes_betweenness_centrality(graph, normalized=True, directed=False):
    """ Betweenness centrality for nodes in the graph.
        Betweenness centrality is a measure of the number of shortests paths that pass through a node.
        Nodes in high-density areas will get a good score.
    """
    # Ulrik Brandes, A Faster Algorithm for Betweenness Centrality,
    # Journal of Mathematical Sociology 25(2):163-177, 2001,
    # http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
    # Based on: Dijkstra's algorithm for shortest paths modified from Eppstein.
    # Based on: NetworkX 1.0.1: Aric Hagberg, Dan Schult and Pieter Swart.
    # http://python-networkx.sourcearchive.com/documentation/1.0.1/centrality_8py-source.html
    G = graph.keys()
    W = adjacency(graph, directed=directed)
    betweenness = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
    for s in G: 
        S = [] 
        P = {} 
        for v in G: P[v] = [] 
        sigma = dict.fromkeys(G, 0) # sigma[v]=0 for v in G 
        D = {} 
        sigma[s] = 1
        seen = {s: 0}  
        Q = [] # use Q as heap with (distance, node id) tuples 
        heappush(Q, (0, s, s)) 
        while Q:    
            (dist, pred, v) = heappop(Q) 
            if v in D: continue # already searched this node
            sigma[v] = sigma[v] + sigma[pred] # count paths 
            S.append(v) 
            D[v] = dist
            for w in W[v].keys():
                vw_dist = D[v] + W[v][w]
                if w not in D and (w not in seen or vw_dist < seen[w]): 
                    seen[w] = vw_dist 
                    heappush(Q, (vw_dist, v, w))
                    sigma[w] = 0
                    P[w] = [v] 
                elif vw_dist == seen[w]: # handle equal paths 
                    sigma[w] = sigma[w] + sigma[v] 
                    P[w].append(v)
        delta = dict.fromkeys(G,0)  
        while S: 
            w = S.pop() 
            for v in P[w]: 
                delta[v] = delta[v] + (float(sigma[v]) / float(sigma[w])) * (1.0 + delta[w]) 
            if w != s: 
                betweenness[w] = betweenness[w] + delta[w]
    if normalized:
        # Normalize between 0.0 and 1.0.
        m = max(betweenness.values())
        if m == 0: m = 1
    else:
        m = 1
    betweenness = dict([(id, w/m) for id, w in betweenness.iteritems()])
    return betweenness
        
def eigenvector_centrality(graph, normalized=True, reversed=True, rating={}, iterations=100, tolerance=0.0001):
    """ Eigenvector centrality for nodes in the graph (cfr. Google's PageRank).
        Eigenvector centrality is a measure of the importance of a node in a directed network. 
        It rewards nodes with a high potential of (indirectly) connecting to high-scoring nodes.
        Nodes with no incoming connections have a score of zero.
        If you want to measure outgoing connections, reversed should be False.        
    """
    # Based on: NetworkX, Aric Hagberg (hagberg@lanl.gov)
    # http://python-networkx.sourcearchive.com/documentation/1.0.1/centrality_8py-source.html
    def normalize(vector):
        w = 1.0 / (sum(vector.values()) or 1)
        for node in vector: 
            vector[node] *= w
        return vector
    G = adjacency(graph, directed=True, reversed=reversed)
    v = normalize(dict([(n, random()) for n in graph])) # Node ID => weight vector.
    # Eigenvector calculation using the power iteration method: y = Ax.
    # It has no guarantee of convergence.
    for i in range(iterations):
        v0 = v
        v  = dict.fromkeys(v0.keys(), 0)
        for n1 in v:
            for n2 in G[n1]:
                v[n1] += 0.01 + v0[n2] * G[n1][n2] * rating.get(n1, 1)
        normalize(v)
        e = sum([abs(v[n]-v0[n]) for n in v]) # Check for convergence.
        if e < len(G) * tolerance:
            if normalized:
                # Normalize between 0.0 and 1.0.
                m = max(v.values()) or 1
                v = dict([(id, w/m) for id, w in v.items()])
            return v
    warn("node weight is 0 because eigenvector_centrality() did not converge.", Warning)
    return dict([(n, 0) for n in G])

# a | b => all elements from a and all the elements from b. 
# a & b => elements that appear in a as well as in b.
# a - b => elements that appear in a but not in b.
def union(a, b):
    return [x for x in a] + [x for x in b if x not in a]
def intersection(a, b):
    return [x for x in a if x in b]
def difference(a, b):
    return [x for x in a if x not in b]

def partition(graph):
    """ Returns a list of unconnected subgraphs.
    """
    # Creates clusters of nodes and directly connected nodes.
    # Iteratively merges two clusters if they overlap.
    # Optimized: about 2x faster than original implementation.
    g = []
    for n in graph.nodes:
        g.append(dict.fromkeys([n.id for n in n.flatten()], True))
    for i in reversed(range(len(g))):
        for j in reversed(range(i+1, len(g))):
            if g[i] and g[j] and len(intersection(g[i], g[j])) > 0:
                g[i] = union(g[i], g[j])
                g[j] = []
    g = [graph.copy(nodes=[graph[id] for id in n]) for n in g if n]
    g.sort(lambda a, b: len(b) - len(a))
    return g

#--- GRAPH MAINTENANCE -------------------------------------------------------------------------------
# Utility commands for safe linking and unlinking of nodes,
# with respect for the surrounding nodes.

def unlink(graph, node1, node2=None):
    """ Removes the edges between node1 and node2.
        If only node1 is given, removes all edges to and from it.
        This does not remove node1 from the graph.
    """
    for e in list(graph.edges):
        if node1 in (e.node1, e.node2) and node2 in (e.node1, e.node2, None):
            graph.edges.remove(e)
            try:
                node1.links.remove(node2)
                node2.links.remove(node1)
            except: # 'NoneType' object has no attribute 'links'
                pass

def redirect(graph, node1, node2):
    """ Connects all of node1's edges to node2 and unlinks node1.
    """
    for e in graph.edges:
        if node in (e.node1, e.node2):
            if e.node1 == node1 and e.node2 != node2: 
                graph.append(e.copy(node2, e.node2))
            if e.node2 == node1 and e.node1 != node2: 
                graph.append(e.copy(e.node1, node2))
    unlink(graph, node1)

def cut(graph, node):
    """ Unlinks the given node, but keeps edges intact by connecting the surrounding nodes.
        If A, B, C, D are nodes and A->B, B->C, B->D, if we then cut B: A->C, A->D.
    """
    for e in graph.edges:
        if node in (e.node1, e.node2):
            for n in node.links:
                if e.node1 == node and e.node2 != n: 
                    graph.append(e.copy(n, e.node2))
                if e.node2 == node and e.node1 != n: 
                    graph.append(e.copy(e.node1, n))
    unlink(graph, node)

def insert(graph, node, a, b):
    """ Inserts the given node between node a and node b.
        If A, B, C are nodes and A->B, if we then insert C: A->C, C->B.
    """
    for e in graph.edges:
        for (n1,n2) in ((a,b), (b,a)):
            if e.node1 == n1 and e.node2 == n2: 
                graph.append(e.copy(node, n2))
            if e.node1 == n2 and e.node2 == n1: 
                graph.append(e.copy(n2, node))
    unlink(graph, a, b)

#--- HTML CANVAS RENDERER ----------------------------------------------------------------------------

import os, shutil, glob

try:
    MODULE = os.path.dirname(__file__)
except:
    MODULE = ""

DEFAULT, INLINE = "default", "inline"
HTML, CANVAS, STYLE, SCRIPT, DATA = "html", "canvas", "style", "script", "data"

class HTMLCanvasRenderer:
    
    def __init__(self, graph, **kwargs):
        self.graph    = graph
        self._source  = \
            "<!DOCTYPE html>\n" \
            "<html>\n" \
            "<head>\n" \
                "\t<title>%s</title>\n" \
                "\t<meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n" \
                "\t%s\n" \
                "\t<!--[if lte IE 8]><script type=\"text/javascript\" src=\"%sexcanvas.js\"></script><![endif]-->\n" \
                "\t<script type=\"text/javascript\" src=\"%sgraph.js\"></script>\n" \
                "\t%s\n" \
            "</head>\n" \
            "<body onload=\"javascript:init_%s();\">\n" \
                "\t<div id=\"%s\" style=\"width:%spx; height:%spx;\">\n" \
                    "\t\t<canvas id=\"%s\" width=\"%s\" height=\"%s\">\n" \
                    "\t\t</canvas>\n" \
                "\t</div>\n" \
                "\t<p>Generated with " \
                "<a href=\"http://www.clips.ua.ac.be/pages/pattern\">Pattern</a>.</p>\n" \
            "</body>\n" \
            "</html>"
        # HTML
        self.title      = "Graph" # <title>Graph</title>
        self.javascript = "js/"   # Path to excanvas.js + graph.js.
        self.stylesheet = INLINE  # Either None, INLINE, DEFAULT (screen.css) or a custom path.
        self.id         = "graph" # <div id="graph">
        self.ctx        = "_ctx"  # <canvas id="_ctx" width=700 height=500>
        self.width      = 700     # Canvas width in pixels.
        self.height     = 500     # Canvas height in pixels.
        # Javascript:Graph
        self.frames     = 500     # Number of frames of animation.
        self.fps        = 20      # Frames per second.
        self.ipf        = 2       # Iterations per frame.
        self.weighted   = False   # Indicate betweenness centrality as a shadow?
        self.directed   = False   # Indicate edge direction with an arrow?
        self.prune      = None    # None or int, calls Graph.prune() in Javascript.
        self.pack       = True    # Shortens leaf edges, adds eigenvector weight to node radius.
        # Javascript:GraphLayout
        self.distance   = 10      # Node spacing.
        self.k          = 4.0     # Force constant.
        self.force      = 0.01    # Force dampener.
        self.repulsion  = 50      # Repulsive force radius.
        # Data
        self.weight     = [WEIGHT, CENTRALITY] # Calculate these in Python, or True (in Javascript).
        self.href       = {}      # Dictionary of Node.id => URL.
        self.css        = {}      # Dictionary of Node.id => CSS classname.
        # Default options.
        # If a Node or Edge has one of these settings,
        # it is not passed to Javascript to save bandwidth.
        self.default = {
                "radius": 5,
                  "fill": None,
                "stroke": (0,0,0,1),
           "strokewidth": 1,
                  "text": (0,0,0,1),
              "fontsize": 11,
        }
    
    def _escape(self, s):
        return s.replace("\"", "\\\"")
    
    def _rgba(self, clr):
        # Color or tuple to a CSS "rgba(255,255,255,1.0)" string.
        return "\"rgba(%s,%s,%s,%.2f)\"" % (int(clr[0]*255), int(clr[1]*255), int(clr[2]*255), clr[3])

    @property
    def data(self):
        """ Yields a string of Javascript code that loads the nodes and edges into variable g,
            which is a Javascript Graph object (see graph.js).
            This can be the response to a XMLHttpRequest, after wich you move g into your own variable.
        """
        return "".join(self._data())
    
    def _data(self):
        if self.graph.nodes and isinstance(self.weight, (list, tuple)):
            if WEIGHT in self.weight and self.graph.nodes[-1]._weight is None:
                self.graph.eigenvector_centrality()
            if CENTRALITY in self.weight and self.graph.nodes[-1]._centrality is None:
                self.graph.betweenness_centrality()
        s = []
        s.append("var g = new Graph(document.getElementById(\"%s\"), %s);\n" % (self.ctx, self.distance))
        s.append("var n = {")
        if len(self.graph.nodes) > 0:
            s.append("\n")
        # Translate node properties to Javascript dictionary (var n).
        for n in self.graph.nodes:
            p = []
            if n._x != 0:
                p.append("x:%i" % n._x)                           # 0
            if n._y != 0:
                p.append("y:%i" % n._y)                           # 0
            if n.radius != self.default["radius"]:
                p.append("radius:%.1f" % n.radius)                # 5.0
            if n._weight is not None:
                p.append("weight:%.2f" % n.weight)                # 0.00
            if n._centrality is not None:
                p.append("centrality:%.2f" % n.centrality)        # 0.00
            if n.fill != self.default["fill"]:
                p.append("fill:%s" % self._rgba(n.fill))          # [0,0,0,1.0]
            if n.stroke != self.default["stroke"]:
                p.append("stroke:%s" % self._rgba(n.stroke))      # [0,0,0,1.0]
            if n.strokewidth != self.default["strokewidth"]:
                p.append("strokewidth:%.1f" % n.strokewidth)      # 0.5
            if n.text and n.text.fill != self.default["text"]:
                p.append("text:%s" % self._rgba(n.text.fill))     # [0,0,0,1.0]
            if n.text and "font" in n.text.__dict__:
                p.append("font:\"%s\"" % n.text.__dict__["font"]) # "sans-serif"
            if n.text and n.text.__dict__.get("fontsize", self.default["fontsize"]) != self.default["fontsize"]:
                p.append("fontsize:%i" % int(max(1, n.text.fontsize)))
            if n.text and "fontweight" in n.text.__dict__:        # "bold"
                p.append("fontweight:\"%s\"" % n.text.__dict__["fontweight"])
            if n.text and n.text.string != n.id:
                p.append("label:\"%s\"" % n.text.string)
            if n.id in self.href:
                p.append("href:\"%s\"" % self.href[n.id])
            if n.id in self.css:
                p.append("css:\"%s\"" % self.css[n.id])
            s.append("\t\"%s\": {%s},\n" % (self._escape(n.id), ", ".join(p)))
        s.append("};\n")
        s.append("var e = [")
        if len(self.graph.edges) > 0:
            s.append("\n")
        # Translate edge properties to Javascript dictionary (var e).
        for e in self.graph.edges:
            id1, id2 = self._escape(e.node1.id), self._escape(e.node2.id)
            p = []
            if e.weight != 0:
                p.append("weight:%.2f" % e.weight)                # 0.00
            if e.length != 1:
                p.append("length:%.2f" % e.length)                # 1.00
            if e.type is not None:
                p.append("type:\"%s\"" % self.type)               # "is-part-of"
            if e.stroke != self.default["stroke"]:
                p.append("stroke:%s" % self._rgba(e.stroke))      # [0,0,0,1.0]
            if e.strokewidth != self.default["strokewidth"]:
                p.append("strokewidth:%.2f" % e.strokewidth)      # 0.5
            s.append("\t[\"%s\", \"%s\", {%s}],\n" % (id1, id2, ", ".join(p)))
        s.append("];\n")
        # Append the nodes to graph g.
        s.append("for (var id in n) {\n"
                    "\tg.addNode(id, n[id]);\n"
                 "}\n")
        # Append the edges to graph g.
        s.append("for (var i=0; i < e.length; i++) {\n"
                    "\tvar n1 = g.nodeset[e[i][0]];\n"
                    "\tvar n2 = g.nodeset[e[i][1]];\n"
                    "\tg.addEdge(n1, n2, e[i][2]);\n"
                 "}")
        return s

    @property
    def script(self):
        """ Yields a string of Javascript code that loads the nodes and edges into variable g (Graph),
            and starts the animation of the visualization by calling g.loop().
        """
        return "".join(self._script())

    def _script(self):
        s = self._data()
        s.append("\n")
        # Apply node weight to node radius.
        if self.pack: 
            s.append(
                 "for (var i=0; i < g.nodes.length; i++) {\n"
                     "\tvar n = g.nodes[i];\n"
                     "\tn.radius = n.radius + n.radius * n.weight;\n"
                 "}\n")
        # Apply edge length (leaves get shorter edges).
        if self.pack: 
            s.append(
                 "for (var i=0; i < g.nodes.length; i++) {\n"
                     "\tvar e = g.nodes[i].edges();\n"
                     "\tif (e.length == 1) {\n"
                     "\t\te[0].length *= 0.2;\n"
                     "\t}\n"
                 "}\n")
        # Apply eigenvector and betweenness centrality.
        if self.weight is True:
            s.append(
                 "g.eigenvectorCentrality();\n"
                 "g.betweennessCentrality();\n")
        # Apply pruning.
        if self.prune is not None: 
            s.append(
                 "g.prune(%s);\n" % self.prune)
        # Include the layout settings (for clarity).
        s.append("g.layout.k = %s; // Force constant (= edge length).\n"
                 "g.layout.force = %s; // Repulsive strength.\n"
                 "g.layout.repulsion = %s; // Repulsive radius.\n" % (
                    self.k, self.force, self.repulsion))
        # Start the graph animation loop.
        s.append("// Start the animation loop.\n")
        s.append("g.loop({frames:%s, fps:%s, ipf:%s, weighted:%s, directed:%s});" % (
            int(self.frames), 
            int(self.fps), 
            int(self.ipf), 
            str(self.weighted).lower(), 
            str(self.directed).lower()))
        return s
    
    @property
    def canvas(self):
        """ Yields a string of HTML with a <div id="graph"> containing a HTML5 <canvas> element.
        """
        s = [
            "<div id=\"%s\" style=\"width:%spx; height:%spx;\">\n" % (self.id, self.width, self.height),
                "\t<canvas id=\"%s\" width=\"%s\" height=\"%s\">\n" % (self.ctx, self.width, self.height),
                "\t</canvas>\n",
            "</div>"
        ]
        #s.append("\n<script type=\"text/javascript\">\n")
        #s.append("".join(self._script()).replace("\n", "\n\t"))
        #s.append("\n</script>")
        return "".join(s)
    
    @property
    def style(self):
        """ Yields a string of CSS for <div id="graph">.
        """
        return \
            "body { font: 11px sans-serif; }\n" \
            "a { color: dodgerblue; }\n" \
            "#%s {\n" \
                "\tdisplay: block;\n" \
                "\tposition: relative;\n" \
                "\toverflow: hidden;\n" \
                "\tborder: 1px solid #ccc;\n" \
            "}\n" \
            "#%s canvas { }\n" \
            ".node-label { font-size: 11px; }" % (self.id, self.id)
    
    @property
    def html(self):
        """ Yields a string of HTML to visualize the graph using a force-based spring layout.
            The js parameter sets the path to graph.js and excanvas.js (by default, "./").
        """
        js  = self.javascript.rstrip("/")
        js  = (js and js or ".")+"/"
        if self.stylesheet == INLINE:
            css = self.style.replace("\n","\n\t\t").rstrip("\t")
            css = "<style type=\"text/css\">\n\t\t%s\n\t</style>" % css
        elif self.stylesheet == DEFAULT:
            css = "<link rel=\"stylesheet\" href=\"screen.css\" type=\"text/css\" media=\"screen\" />"
        elif self.stylesheet is not None:
            css = "<link rel=\"stylesheet\" href=\"%s\" type=\"text/css\" media=\"screen\" />" % self.stylesheet
        s = self._script()
        s = "".join(s)
        s = s.replace("\n", "\n\t\t")
        s = "<script type=\"text/javascript\">\n\tfunction init_%s() {\n\t\t%s\n\t}\n\t</script>" % (self.id, s)
        s = s.rstrip()
        s = self._source % (
            self.title, 
            css, 
            js, 
            js, 
            s, 
            self.id, 
            self.id, 
            self.width, 
            self.height, 
            self.ctx, 
            self.width, 
            self.height)
        return s

    def render(self, type=HTML):
        if type == HTML:
            return self.html
        if type == CANVAS:
            return self.canvas
        if type == STYLE:
            return self.style
        if type == SCRIPT:
            return self.script
        if type == DATA:
            return self.data

    def export(self, path, overwrite=False, encoding="utf-8"):
        """ Generates a folder at the given path containing an index.html
            that visualizes the graph using the HTML5 <canvas> tag.
        """
        if overwrite and os.path.exists(path):
            shutil.rmtree(path)
        os.mkdir(path) # With overwrite=False, raises OSError if the path already exists.
        os.mkdir(os.path.join(path, "js"))
        # Copy js/graph.js + js/excanvas.js (unless a custom path is given.)
        if self.javascript == "js/":
            for f in glob.glob(os.path.join(MODULE, "js", "*.js")):
                shutil.copy(f, os.path.join(path, "js", os.path.basename(f)))
        # Create screen.css.
        if self.stylesheet == DEFAULT:
            f = open(os.path.join(path, "screen.css"), "w")
            f.write(self.style)
            f.close()
        # Create index.html.
        f = open(os.path.join(path, "index.html"), "w", encoding=encoding)
        f.write(self.html)
        f.close()

def render(graph, type=HTML, **kwargs):
    renderer = HTMLCanvasRenderer(graph)
    renderer.default.update(kwargs.get("default", {}))
    kwargs["default"] = renderer.default
    kwargs["stylesheet"] = kwargs.get("stylesheet", INLINE)
    for k,v in kwargs.items():
        if k in renderer.__dict__: 
            renderer.__dict__[k] = v
    return renderer.render(type)

def export(graph, path, overwrite=False, encoding="utf-8", **kwargs):
    renderer = HTMLCanvasRenderer(graph)
    renderer.default.update(kwargs.get("default", {}))
    kwargs["default"] = renderer.default
    kwargs["stylesheet"] = kwargs.get("stylesheet", DEFAULT)
    for k,v in kwargs.items():
        if k in renderer.__dict__: 
            renderer.__dict__[k] = v
    return renderer.export(path, overwrite)
