<commit_before>"""
=======
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
"""
#    Copyright (C) 2004-2008 by
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    All rights reserved.
#    BSD license.
import networkx
from networkx.utils.decorators import *
__author__ = """<NAME> (<EMAIL>)"""
__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']


@not_implemented_for('directed')
def find_cliques(G):
    """Search for all maximal cliques in a graph.

    Maximal cliques are the largest complete subgraph containing
    a given node.  The largest maximal clique is sometimes called
    the maximum clique.

    Returns
    -------
    generator of lists: genetor of member list for each maximal clique

    See Also<commit_msg>added implementation of get_all_cliques together with helper method greater_neighbors<commit_after>"""
=======
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
"""
#    Copyright (C) 2004-2008 by
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    All rights reserved.
#    BSD license.
import networkx
from networkx.utils.decorators import *
__author__ = """<NAME> (<EMAIL>)"""
__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']

def greater_neighbors(G, a_node):
    """Helper method used in get_all_cliques"""
    nodes_sorted = sorted(G.nodes())
    a_node_index = nodes_sorted.index(a_node)

    neighbors_of_a_node = []

    for another_node_index, another_node in enumerate(nodes_sorted):
        if another_node_index > a_node_index and another_node in G.neighbors(a_node):
            neighbors_of_a_node.append(another_node)
    
    return tuple(neighbors_of_a_node)

@not_implemented_for('directed')
def get_all_cliques(G):
    """Returns all cliques in an undirected graph.

    This method returns cliques of size (cardinality) k = 1, 2, 3, ..., maxDegree - 1.
    Where maxDegree is the maximal degree of any node in the graph.

    Keyword arguments
    -----------------
    G: undirected graph

    Returns
    -------
    generator of lists: generator of list for each clique.

    Notes
    -----
    To obtain a list of all cliques, use list(get_all_cliques(G)).

    Based on the algorithm published by Zhang et al. (2005) [1]_ and adapted to output all cliques discovered.
    
    This algorithm is not suitable for directed graphs.

    This algorithm ignores self-loops and parallel edges as
    clique is not conventionally defined with such edges.

    There are often many cliques in graphs. This algorithm however, hopefully, does not run out of memory
    since it only keeps candidate sublists in memory and continuously removes exhausted sublists.

    References
    ----------
    .. [1] <NAME>, <NAME>., <NAME>., <NAME>., <NAME>., <NAME>., 
       Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology 
       Supercomputing, 2005. Proceedings of the ACM/IEEE SC 2005 Conference , vol., no., pp. 12, 12-18 Nov. 2005
       doi: 10.1109/SC.2005.29
       http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1559964&isnumber=33129
    """

    # sorted list of nodes in graph
    nodes_sorted = sorted(G.nodes())

    # starting point: build all 2-clique sublists
    clique_sublists = []
    for a_node_index, a_node in enumerate(nodes_sorted):
        clique_sublist = {}
        # sublist base, sb
        clique_sublist['sb'] = tuple(a_node)
        # common neighbors, cn
        clique_sublist['cn'] = greater_neighbors(G, a_node)
        clique_sublists.append(clique_sublist)

    # output cliques of size k = 1
    for node in nodes_sorted:
        yield [node]

    # output cliques of size k >= 2
    while clique_sublists:
        a_sublist = clique_sublists.pop(0)
        for node_added in a_sublist['cn']:
            neighbors_of_node_added = greater_neighbors(G, node_added)

            current_sublist_base = a_sublist['sb']+tuple(node_added)
            current_sublist_cn = tuple(sorted(set(neighbors_of_node_added).intersection(a_sublist['cn'])))

            #print 'clique: '+str(current_sublist_base)
            yield [[node] for node in current_sublist_base]

            for node in current_sublist_cn:
                new_sublist_base = current_sublist_base+tuple(node)
                new_sublist_cn = tuple(sorted(set(current_sublist_cn).intersection(greater_neighbors(G, node))))
    
                if len(new_sublist_cn) == 0:
                    #print 'clique: '+str(new_sublist_base)
                    yield [[n] for n in new_sublist_base]
                elif len(new_sublist_cn) == 1:
                    #print 'clique: '+str(new_sublist_base)
                    yield [[n] for n in new_sublist_base]
                    #print 'clique: '+str(new_sublist_base+new_sublist_cn)
                    yield [[n] for n in new_sublist_base+new_sublist_cn]
                else:
                    #print 'candidate sublist: '+str([new_sublist_base, new_sublist_cn])
                    clique_sublists.append({'sb': new_sublist_base, 'cn': new_sublist_cn})


@not_implemented_for('directed')
def find_cliques(G):
    """Search for all maximal cliques in a graph.

    Maximal cliques are the largest complete subgraph containing
    a given node.  The largest maximal clique is sometimes called
    the maximum clique.

    Returns
    -------
    generator of lists: genetor of member list for each maximal clique

    See Also
{'fraction_non_alphanumeric': 0.10185920864452566, 'fraction_numerical': 0.011759097409820436, 'mean_word_length': 2.956002514142049, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 33, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7460902', 'n_tokens_mistral': 2058, 'n_tokens_neox': 1945, 'n_words': 564}