"""
=======
Cliques
=======

Find and manipulate cliques of graphs.

Note that finding the largest clique of a graph has been
shown to be an NP-complete problem; the algorithms here
could take a long time to run. 

http://en.wikipedia.org/wiki/Clique_problem

"""
__author__ = """Dan 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__ = ['find_cliques', 'find_cliques_recursive', 'make_max_clique_graph',
           'make_clique_bipartite' ,'graph_clique_number',
           'graph_number_of_cliques', 'node_clique_number',
           'number_of_cliques', 'cliques_containing_node',
           'project_down', 'project_up']


import networkx

def find_cliques(G):
    """
    Search for all maximal cliques in a graph.
 
    This algorithm searches for maximal cliques in a graph.
    maximal cliques are the largest complete subgraph containing
    a given point.  The largest maximal clique is sometimes called
    the maximum clique.
 
    This implementation is a generator of lists each
    of which contains the members of a maximal clique.
    To obtain a list of cliques, use list(find_cliques(G)).
    The method essentially unrolls the recursion used in
    the references to avoid issues of recursion stack depth.
    
    See Also
    --------
    find_cliques_recursive : 
    A recursive version of the same algorithm

    References
    ----------
    Based on the algorithm published by Bron & Kerbosch (1973)
        http://doi.acm.org/10.1145/362342.362367
    as adapated by Tomita, Tanaka and Takahashi (2006)
        http://dx.doi.org/10.1016/j.tcs.2006.06.015
    and discussed in Cazals and Karande (2008)
        http://dx.doi.org/10.1016/j.tcs.2008.05.010
     """
    # Cache nbrs and find first pivot (highest degree)
    maxconn=-1
    nnbrs={}
    pivotnbrs=set() # handle empty graph
    for n,nbrs in G.adjacency_iter():
        conn = len(nbrs)
        if conn > maxconn:
            nnbrs[n] = pivotnbrs = set(nbrs)
            maxconn = conn
        else:
            nnbrs[n] = set(nbrs)
    # Initial setup
    cand=set(nnbrs)
    smallcand = cand - pivotnbrs
    done=set()
    stack=[]
    clique_so_far=[]
    # Start main loop
    while smallcand or stack:
        try:
            # Any nodes left to check?
            n=smallcand.pop()
        except KeyError:
            # back out clique_so_far
            cand,done,smallcand = stack.pop()
            clique_so_far.pop()
            continue
        # Add next node to clique
        clique_so_far.append(n)
        cand.remove(n)
        done.add(n)
        nn=nnbrs[n]
        new_cand = cand & nn
        new_done = done & nn
        # check if we have more to search
        if not new_cand: 
            if not new_done:
                # Found a clique!
                yield clique_so_far[:]
            clique_so_far.pop()
            continue
        # Shortcut--only one node left!
        if not new_done and len(new_cand)==1:
            yield clique_so_far + list(new_cand)
            clique_so_far.pop()
            continue
        # find pivot node (max connected in cand)
        # look in done nodes first
        numb_cand=len(new_cand)
        maxconndone=-1
        for n in new_done:
            cn = new_cand & nnbrs[n]
            conn=len(cn)
            if conn > maxconndone:
                pivotdonenbrs=cn
                maxconndone=conn
                if maxconndone==numb_cand:
                    break
        # Shortcut--this part of tree already searched
        if maxconndone == numb_cand:  
            clique_so_far.pop()
            continue
        # still finding pivot node
        # look in cand nodes second
        maxconn=-1
        for n in new_cand:
            cn = new_cand & nnbrs[n]
            conn=len(cn)
            if conn > maxconn:
                pivotnbrs=cn
                maxconn=conn
                if maxconn == numb_cand-1:
                    break
        # pivot node is max connected in cand from done or cand
        if maxconndone > maxconn:
            pivotnbrs = pivotdonenbrs
        # save search status for later backout
        stack.append( (cand, done, smallcand) )
        cand=new_cand
        done=new_done
        smallcand = cand - pivotnbrs


def find_cliques_recursive(G):
    """
    Recursive search for all maximal cliques in a graph.
 
    This algorithm searches for maximal cliques in a graph.
    Maximal cliques are the largest complete subgraph containing
    a given point.  The largest maximal clique is sometimes called
    the maximum clique.
 
    This implementation returns a list of lists each of
    which contains the members of a maximal clique.
    
    See Also
    --------
    find_cliques : An nonrecursive version of the same algorithm

    Reference::
 
    Based on the algorithm published by Bron & Kerbosch (1973)
        http://doi.acm.org/10.1145/362342.362367
    as adapated by Tomita, Tanaka and Takahashi (2006)
        http://dx.doi.org/10.1016/j.tcs.2006.06.015
    and discussed in Cazals and Karande (2008)
        http://dx.doi.org/10.1016/j.tcs.2008.05.010
 
    """
    nnbrs={}
    for n,nbrs in G.adjacency_iter():
        nnbrs[n]=set(nbrs)
    if not nnbrs: return [] # empty graph
    cand=set(nnbrs)
    done=set()
    clique_so_far=[]
    cliques=[]
    _extend(nnbrs,cand,done,clique_so_far,cliques)
    return cliques

def _extend(nnbrs,cand,done,so_far,cliques):
    # find pivot node (max connections in cand)
    maxconn=-1
    numb_cand=len(cand)
    for n in done:
        cn = cand & nnbrs[n]
        conn=len(cn)
        if conn > maxconn:
            pivotnbrs=cn
            maxconn=conn
            if conn==numb_cand:
                # All possible cliques already found
                return
    for n in cand:
        cn = cand & nnbrs[n]
        conn=len(cn)
        if conn > maxconn:
            pivotnbrs=cn
            maxconn=conn
    # Use pivot to reduce number of nodes to examine
    smallercand = cand - pivotnbrs
    for n in smallercand:
        cand.remove(n)
        so_far.append(n)
        nn=nnbrs[n]
        new_cand=cand & nn
        new_done=done & nn
        if not new_cand and not new_done:
            # Found the clique
            cliques.append(so_far[:])
        elif not new_done and len(new_cand) is 1:
            # shortcut if only one node left
            cliques.append(so_far+list(new_cand))
        else:
            _extend(nnbrs, new_cand, new_done, so_far, cliques)
        done.add(so_far.pop())


def make_max_clique_graph(G,create_using=None,name=None):
    """ Create the maximal clique graph of a graph. 
   
    Finds the maximal cliques and treats these as nodes.
    The nodes are connected if they have common members in 
    the original graph.  Theory has done a lot with clique
    graphs, but I haven't seen much on maximal clique graphs.

    Notes
    -----
    This should be the same as make_clique_bipartite followed
    by project_up, but it saves all the intermediate steps.
    """
    cliq=map(set,find_cliques(G))
    size=len(cliq)
    if create_using:
        B=create_using
        B.clear()
    else:
        B=networkx.Graph()
    if name is not None:
        B.name=name

    for i,cl in enumerate(cliq):
        B.add_node(i+1)
        for j,other_cl in enumerate(cliq[:i]):
            # if not cl.isdisjoint(other_cl): #Requires 2.6
            intersect=cl & other_cl
            if intersect:     # Not empty 
                B.add_edge(i+1,j+1)
    return B

def make_clique_bipartite(G,fpos=None,create_using=None,name=None):
    """ Create a bipartite clique graph from a graph G. 
   
    Nodes of G are retained as the "bottom nodes" of B and 
    cliques of G become "top nodes" of B.
    Edges are present if a bottom node belongs to the clique 
    represented by the top node.
 
    Returns a Graph with additional attribute dict B.node_type
    which is keyed by nodes to "Bottom" or "Top" appropriately.

    if fpos is not None, a second additional attribute dict B.pos
    is created to hold the position tuple of each node for viewing
    the bipartite graph.

    """
    cliq=list(find_cliques(G))
    if create_using:
        B=create_using
        B.clear()
    else:
        B=networkx.Graph()
    if name is not None:
        B.name=name

    B.add_nodes_from(G)
    B.node_type={}   # New Attribute for B
    for n in B:
        B.node_type[n]="Bottom"
 
    if fpos:
       B.pos={}     # New Attribute for B
       delta_cpos=1./len(cliq)
       delta_ppos=1./G.order()
       cpos=0.
       ppos=0.
    for i,cl in enumerate(cliq):
       name= -i-1   # Top nodes get negative names
       B.add_node(name)
       B.node_type[name]="Top"
       if fpos:
          if name not in B.pos:
             B.pos[name]=(0.2,cpos)
             cpos +=delta_cpos
       for v in cl:
          B.add_edge(name,v)
          if fpos is not None:
             if v not in B.pos:
                B.pos[v]=(0.8,ppos)
                ppos +=delta_ppos
    return B
   
def project_down(B,create_using=None,name=None):
    """Project a bipartite graph B down onto its "bottom nodes". 
    
    The nodes retain their names and are connected if they
    share a common top node in the bipartite graph.

    Returns a Graph.
    """
    if create_using:
        G=create_using
        G.clear()
    else:
        G=networkx.Graph()
    if name is not None:
        G.name=name

    for v,Bvnbrs in B.adjacency_iter():
       if B.node_type[v]=="Bottom":
          G.add_node(v)
          for cv in Bvnbrs:
             G.add_edges_from([(v,u) for u in B[cv] if u!=v])
    return G
 
def project_up(B,create_using=None,name=None):
    """ Project a bipartite graph B down onto its "bottom nodes".
    
    The nodes retain their names and are connected if they
    share a common Bottom Node in the Bipartite Graph.

    Returns a Graph.
    """
    if create_using:
        G=create_using
        G.clear()
    else:
        G=networkx.Graph()
    if name is not None:
        G.name=name

    for v,Bvnbrs in B.adjacency_iter():
       if B.node_type[v]=="Top":
          vname= -v   #Change sign of name for Top Nodes
          G.add_node(vname)
          for cv in Bvnbrs:
             # Note: -u changes the name (not Top node anymore)
             G.add_edges_from([(vname,-u) for u in B[cv] if u!=v])
    return G
 
def graph_clique_number(G,cliques=None):
    """Return the clique number (size of the largest clique) for G.

       An optional list of cliques can be input if already computed.

    """
    if cliques is None:
        cliques=find_cliques(G)
    return   max( [len(c) for c in cliques] )


def graph_number_of_cliques(G,cliques=None):
    """  Returns the number of maximal cliques in G.

       An optional list of cliques can be input if already computed.

    """
    if cliques is None:
        cliques=list(find_cliques(G))
    return   len(cliques)

 
def node_clique_number(G,nodes=None,cliques=None):
    """ Returns the size of the largest maximal clique containing
        each given node.  

        Returns a single or list depending on input nodes.
        Optional list of cliques can be input if already computed.

    """
    if cliques is None:
        cliques=list(find_cliques(G))

    if nodes is None:
        nodes=G.nodes()   # none, get entire graph

    if not isinstance(nodes, list):   # check for a list
        v=nodes
        # assume it is a single value
        d=max([len(c) for c in cliques if v in c])
    else:
        d={}
        for v in nodes:
            d[v]=max([len(c) for c in cliques if v in c])
    return d

    # if nodes is None:                 # none, use entire graph
    #     nodes=G.nodes()
    # elif  not isinstance(nodes, list):    # check for a list
    #     nodes=[nodes]             # assume it is a single value

    # if cliques is None:
    #     cliques=list(find_cliques(G))
    # d={}
    # for v in nodes:
    #     d[v]=max([len(c) for c in cliques if v in c])
    
    # if nodes in G:
    #     return d[v] #return single value
    # return d


def number_of_cliques(G,nodes=None,cliques=None):
    """ Returns the number of maximal cliques for each node.

        Returns a single or list depending on input nodes.
        Optional list of cliques can be input if already computed.

    """
    if cliques is None:
        cliques=list(find_cliques(G))

    if nodes is None:
        nodes=G.nodes()   # none, get entire graph

    if not isinstance(nodes, list):   # check for a list
        v=nodes
        # assume it is a single value
        numcliq=len([1 for c in cliques if v in c])
    else:
        numcliq={}
        for v in nodes:
            numcliq[v]=len([1 for c in cliques if v in c])
    return numcliq

    
def cliques_containing_node(G,nodes=None,cliques=None):
    """ Returns a list of cliques containing the given node.

        Returns a single list or list of lists depending on input nodes.
        Optional list of cliques can be input if already computed.

    """
    if cliques is None:
        cliques=list(find_cliques(G))

    if nodes is None:
        nodes=G.nodes()   # none, get entire graph

    if not isinstance(nodes, list):   # check for a list
        v=nodes
        # assume it is a single value
        vcliques=[c for c in cliques if v in c]
    else:
        vcliques={}
        for v in nodes:
            vcliques[v]=[c for c in cliques if v in c]
    return vcliques