"""
Algorithms to characterize the number of triangles in a graph.

"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
#    Copyright (C) 2004-2008 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.

__all__= ['triangles', 'average_clustering', 'clustering', 'transitivity']

import networkx as nx
from networkx import NetworkXError

def triangles(G,nbunch=None):
    """Compute the number of triangles.

    Finds the number of triangles that include a node as one of the vertices.

    Parameters
    ----------
    G : graph
       A networkx graph
    nbunch : container of nodes, optional
       Compute triangles for nodes in nbunch. The default is all nodes in G.

    Returns
    -------
    out : dictionary
       Number of trianges keyed by node label.
    
    Examples
    --------
    >>> G=nx.complete_graph(5)
    >>> print nx.triangles(G,0)
    6
    >>> print nx.triangles(G)
    {0: 6, 1: 6, 2: 6, 3: 6, 4: 6}
    >>> print nx.triangles(G,(0,1)).values()
    [6, 6]

    Notes
    -----
    When computing triangles for the entire graph 
    each triangle is counted three times, once at each node.

    Self loops are ignored.

    """
    if G.is_directed():
        raise NetworkXError("triangles() is not defined for directed graphs.")
    if nbunch in G: 
        return _triangles_and_degree_iter(G,nbunch).next()[2]/2 # return single value
    return dict( (v,t/2) for v,d,t in _triangles_and_degree_iter(G,nbunch))

def _triangles_and_degree_iter(G,nbunch=None):
    """ Return an iterator of (node, degree, triangles).  

    This double counts triangles so you may want to divide by 2.
    See degree() and triangles() for definitions and details.

    """
    if G.is_multigraph():
        raise NetworkXError("Not defined for multigraphs.")

    if nbunch is None:
        nodes_nbrs = G.adj.iteritems()
    else:
        nodes_nbrs= ( (n,G[n]) for n in G.nbunch_iter(nbunch) )

    for v,v_nbrs in nodes_nbrs:
        vs=set(v_nbrs)
        if v in vs:
            vs.remove(v)
        ntriangles=0
        for w in vs:
            ws=set(G[w])
            if w in ws:
                ws.remove(w)
            ntriangles+=len(vs.intersection(ws))
        yield (v,len(vs),ntriangles)


def average_clustering(G):
    """Compute average clustering coefficient.

    A clustering coefficient for the whole graph is the average, 

    .. math::

       C = \\frac{1}{n}\\sum_{v \in G} c_v,
       
    where :math:`n` is the number of nodes in :math:`G`.

    Parameters
    ----------
    G : graph
       A networkx graph

    Returns
    -------
    out : float
       Average clustering
    
    Examples
    --------
    >>> G=nx.complete_graph(5)
    >>> print nx.average_clustering(G)
    1.0

    Notes
    -----
    This is a space saving routine; it might be faster
    to use clustering to get a list and then take the average.

    Self loops are ignored.

    """
    order=G.order()
    s=sum(clustering(G).values())
    return s/float(order)

def clustering(G,nbunch=None,weights=False):
    """ Compute the clustering coefficient for nodes.

    For each node find the fraction of possible triangles that exist,

    .. math::

      c_v = \\frac{2 T(v)}{deg(v)(deg(v)-1)}

    where :math:`T(v)` is the number of triangles through node :math:`v`.       

    Parameters
    ----------
    G : graph
       A networkx graph
    nbunch : container of nodes, optional
       Limit to specified nodes. Default is entire graph.
    weights : bool, optional
        If True return fraction of connected triples as dictionary
        
    Returns
    -------
    out : float, dictionary or tuple of dictionaries
       Clustering coefficient at specified nodes

    Examples
    --------
    >>> G=nx.complete_graph(5)
    >>> print nx.clustering(G,0)
    1.0
    >>> print nx.clustering(G)
    {0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}


    Notes
    -----
    The weights are the fraction of connected triples in the graph
    which include the keyed node.  Ths is useful for computing
    transitivity.

    Self loops are ignored.

    """
    if G.is_directed():
        raise NetworkXError("Clustering algorithms are not defined for directed graphs.")
    if weights:
        clusterc={}
        weights={}
        for v,d,t in _triangles_and_degree_iter(G,nbunch):
            weights[v]=float(d*(d-1))
            if t==0:
                clusterc[v]=0.0
            else:
                clusterc[v]=t/float(d*(d-1))
        scale=1./sum(weights.itervalues())
        for v,w in weights.iteritems():
            weights[v]=w*scale
        return clusterc,weights

    clusterc={}
    for v,d,t in _triangles_and_degree_iter(G,nbunch):
        if t==0:
            clusterc[v]=0.0
        else:
            clusterc[v]=t/float(d*(d-1))

    if nbunch in G: 
        return clusterc.values()[0] # return single value
    return clusterc

def transitivity(G):
    """Compute transitivity.

    Finds the fraction of all possible triangles which are in fact triangles.
    Possible triangles are identified by the number of "triads" (two edges
    with a shared vertex).

    T = 3*triangles/triads


    Parameters
    ----------
    G : graph
       A networkx graph

    Returns
    -------
    out : float
       Transitivity

    Examples
    --------
    >>> G=nx.complete_graph(5)
    >>> print nx.transitivity(G)
    1.0

"""
    triangles=0 # 6 times number of triangles
    contri=0  # 2 times number of connected triples
    for v,d,t in _triangles_and_degree_iter(G):
        contri += d*(d-1)
        triangles += t
    if triangles==0: # we had no triangles or possible triangles
        return 0.0
    else:
        return triangles/float(contri)