<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

"""
__author__ = """<NAME> (<EMAIL>)"""
#    Copyright (C) 2004-2008 by 
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html


__all__ = ['find_cliques', '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 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 algorithm produces the list of maximal cliques each
   of which are a list of the members of the clique.
   
   Based on Algol algorithm published by Bron & Kerbosch
   A C version is available as part of the rambin package.
   http://www.ram.org/computing/rambin/rambin.html

   Reference::

      @article{362367,
       author = {<NAME> and <NAME>},
       title = {Algorithm 457: finding all cliques of an undirected graph},
       journal = {Commun. ACM},
       volume = {16},
       number = {9},
       year = {1973},
       issn = {0001-0782},
       pages = {575--577},
       doi = {http://doi.acm.org/10.1145/362342.362367},
       publisher = {ACM Press},
       }
   """
   all_nodes=G.nodes()
   num_nodes=G.order()
   clique=[]
   cliques=[]
   _extend(all_nodes,0,num_nodes,G,clique,cliques)
   if len(cliques)==0:
      raise networkx.NetworkXError("No cliques found")
   return cliques

def _extend(old_nodes,num_not,num_left,G,clique,cliques):
   """ 
   A recursive helper routine for find_cliques

   This recursive routine explores the "old_nodes" set of nodes
   for complete subgraphs.  num_left is the size of old_nodes. 
   The first num_not nodes are called the "not" group by B&K
   because they have already been considered. 
   The rest (num_left-num_not) of them are called "candidates".

   G is the graph, 
   clique is the clique being built,
   cliques is a list of maximal cliques found so far.
   """
   # set up sets nots and cands for easy reference
   cands=old_nodes[num_not:]
   nots=old_nodes[:num_not]

   #  Look for nodes that are "candidates" with the
   #  most neighbors among the "candidates"
   max_conn=0
   for p in cands:<commit_msg>Revert "fix" to clique.py.  Many routines depend on find_clique() returning an empty list when no cliques.<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

"""
__author__ = """<NAME> (<EMAIL>)"""
#    Copyright (C) 2004-2008 by 
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html


__all__ = ['find_cliques', '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 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 algorithm produces the list of maximal cliques each
   of which are a list of the members of the clique.
   
   Based on Algol algorithm published by Bron & Kerbosch
   A C version is available as part of the rambin package.
   http://www.ram.org/computing/rambin/rambin.html

   Reference::

      @article{362367,
       author = {<NAME> and <NAME>},
       title = {Algorithm 457: finding all cliques of an undirected graph},
       journal = {Commun. ACM},
       volume = {16},
       number = {9},
       year = {1973},
       issn = {0001-0782},
       pages = {575--577},
       doi = {http://doi.acm.org/10.1145/362342.362367},
       publisher = {ACM Press},
       }
   """
   all_nodes=G.nodes()
   num_nodes=G.order()
   clique=[]
   cliques=[]
   _extend(all_nodes,0,num_nodes,G,clique,cliques)
   return cliques

def _extend(old_nodes,num_not,num_left,G,clique,cliques):
   """ 
   A recursive helper routine for find_cliques

   This recursive routine explores the "old_nodes" set of nodes
   for complete subgraphs.  num_left is the size of old_nodes. 
   The first num_not nodes are called the "not" group by B&K
   because they have already been considered. 
   The rest (num_left-num_not) of them are called "candidates".

   G is the graph, 
   clique is the clique being built,
   cliques is a list of maximal cliques found so far.
   """
   # set up sets nots and cands for easy reference
   cands=old_nodes[num_not:]
   nots=old_nodes[:num_not]

   #  Look for nodes that are "candidates" with the
   #  most neighbors among the "candidates"
   max_conn=0
   for p in cands:
{'fraction_non_alphanumeric': 0.09973333333333333, 'fraction_numerical': 0.0208, 'mean_word_length': 3.142857142857143, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, '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': '1980430', 'n_tokens_mistral': 1921, 'n_tokens_neox': 1775, 'n_words': 608}