<s> """<STR_LIT>""" <EOL> from collections import deque <EOL> from itertools import chain <EOL> from itertools import combinations <EOL> from itertools import islice <EOL> try : <EOL> from itertools import ifilter as filter <EOL> except ImportError : <EOL> pass <EOL> import networkx <EOL> from networkx . utils import not_implemented_for <EOL> __author__ = """<STR_LIT>""" <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' ] <EOL> @ not_implemented_for ( '<STR_LIT>' ) <EOL> def enumerate_all_cliques ( G ) : <EOL> """<STR_LIT>""" <EOL> index = { } <EOL> nbrs = { } <EOL> for u in G : <EOL> index [ u ] = len ( index ) <EOL> nbrs [ u ] = { v for v in G [ u ] if v not in index } <EOL> queue = deque ( ( [ u ] , sorted ( nbrs [ u ] , key = index . __getitem__ ) ) for u in G ) <EOL> while queue : <EOL> base , cnbrs = map ( list , queue . popleft ( ) ) <EOL> yield base <EOL> for i , u in enumerate ( cnbrs ) : <EOL> queue . append ( ( chain ( base , [ u ] ) , <EOL> filter ( nbrs [ u ] . __contains__ , <EOL> islice ( cnbrs , i + <NUM_LIT:1> , None ) ) ) ) <EOL> @ not_implemented_for ( '<STR_LIT>' ) <EOL> def find_cliques ( G ) : <EOL> """<STR_LIT>""" <EOL> if len ( G ) == <NUM_LIT:0> : <EOL> return <EOL> adj = { u : { v for v in G [ u ] if v != u } for u in G } <EOL> Q = [ None ] <EOL> subg = set ( G ) <EOL> cand = set ( G ) <EOL> u = max ( subg , key = lambda u : len ( cand & adj [ u ] ) ) <EOL> ext_u = cand - adj [ u ] <EOL> stack = [ ] <EOL> try : <EOL> while True : <EOL> if ext_u : <EOL> q = ext_u . pop ( ) <EOL> cand . remove ( q ) <EOL> Q [ - <NUM_LIT:1> ] = q <EOL> adj_q = adj [ q ] <EOL> subg_q = subg & adj_q <EOL> if not subg_q : <EOL> yield Q [ : ] <EOL> else : <EOL> cand_q = cand & adj_q <EOL> if cand_q : <EOL> stack . append ( ( subg , cand , ext_u ) ) <EOL> Q . append ( None ) <EOL> subg = subg_q <EOL> cand = cand_q <EOL> u = max ( subg , key = lambda u : len ( cand & adj [ u ] ) ) <EOL> ext_u = cand - adj [ u ] <EOL> else : <EOL> Q . pop ( ) <EOL> subg , cand , ext_u = stack . pop ( ) <EOL> except IndexError : <EOL> pass <EOL> def find_cliques_recursive ( G ) : <EOL> """<STR_LIT>""" <EOL> if len ( G ) == <NUM_LIT:0> : <EOL> return iter ( [ ] ) <EOL> adj = { u : { v for v in G [ u ] if v != u } for u in G } <EOL> Q = [ ] <EOL> def expand ( subg , cand ) : <EOL> u = max ( subg , key = lambda u : len ( cand & adj [ u ] ) ) <EOL> for q in cand - adj [ u ] : <EOL> cand . remove ( q ) <EOL> Q . append ( q ) <EOL> adj_q = adj [ q ] <EOL> subg_q = subg & adj_q <EOL> if not subg_q : <EOL> yield Q [ : ] <EOL> else : <EOL> cand_q = cand & adj_q <EOL> if cand_q : <EOL> for clique in expand ( subg_q , cand_q ) : <EOL> yield clique <EOL> Q . pop ( ) <EOL> return expand ( set ( G ) , set ( G ) ) <EOL> def make_max_clique_graph ( G , create_using = None ) : <EOL> """<STR_LIT>""" <EOL> B = create_using if create_using is not None else networkx . Graph ( ) <EOL> B . clear ( ) <EOL> cliques = list ( enumerate ( set ( c ) for c in find_cliques ( G ) ) ) <EOL> B . add_nodes_from ( i for i , c in cliques ) <EOL> clique_pairs = combinations ( cliques , <NUM_LIT:2> ) <EOL> B . add_edges_from ( ( i , j ) for ( i , c1 ) , ( j , c2 ) in clique_pairs if c1 & c2 ) <EOL> return B <EOL> def make_clique_bipartite ( G , fpos = None , create_using = None , name = None ) : <EOL> """<STR_LIT>""" <EOL> B = create_using if create_using is not None else networkx . Graph ( ) <EOL> B . clear ( ) <EOL> B . add_nodes_from ( G , bipartite = <NUM_LIT:1> ) <EOL> for i , cl in enumerate ( find_cliques ( G ) ) : <EOL> name = - i - <NUM_LIT:1> <EOL> B . add_node ( name , bipartite = <NUM_LIT:0> ) <EOL> B . add_edges_from ( ( v , name ) for v in cl ) <EOL> return B <EOL> def graph_clique_number ( G , cliques = None ) : <EOL> """<STR_LIT>""" <EOL> if cliques is None : <EOL> cliques = find_cliques ( G ) <EOL> return max ( [ len ( c ) for c in cliques ] ) <EOL> def graph_number_of_cliques ( G , cliques = None ) : <EOL> """<STR_LIT>""" <EOL> if cliques is None : <EOL> cliques = list ( find_cliques ( G ) ) <EOL> return len ( cliques ) <EOL> def node_clique_number ( G , nodes = None , cliques = None ) : <EOL> """<STR_LIT>""" <EOL> if cliques is None : <EOL> if nodes is not None : <EOL> if isinstance ( nodes , list ) : <EOL> d = { } <EOL> for n in nodes : <EOL> H = networkx . ego_graph ( G , n ) <EOL> d [ n ] = max ( ( len ( c ) for c in find_cliques ( H ) ) ) <EOL> else : <EOL> H = networkx . ego_graph ( G , nodes ) <EOL> d = max ( ( len ( c ) for c in find_cliques ( H ) ) ) <EOL> return d <EOL> cliques = list ( find_cliques ( G ) ) <EOL> if nodes is None : <EOL> nodes = list ( G . nodes ( ) ) <EOL> if not isinstance ( nodes , list ) : <EOL> v = nodes <EOL> d = max ( [ len ( c ) for c in cliques if v in c ] ) <EOL> else : <EOL> d = { } <EOL> for v in nodes : <EOL> d [ v ] = max ( [ len ( c ) for c in cliques if v in c ] ) <EOL> return d <EOL> def number_of_cliques ( G , nodes = None , cliques = None ) : <EOL> """<STR_LIT>""" <EOL> if cliques is None : <EOL> cliques = list ( find_cliques ( G ) ) <EOL> if nodes is None : <EOL> nodes = list ( G . nodes ( ) ) <EOL> if not isinstance ( nodes , list ) : <EOL> v = nodes <EOL> numcliq = len ( [ <NUM_LIT:1> for c in cliques if v in c ] ) <EOL> else : <EOL> numcliq = { } <EOL> for v in nodes : <EOL> numcliq [ v ] = len ( [ <NUM_LIT:1> for c in cliques if v in c ] ) <EOL> return numcliq <EOL> def cliques_containing_node ( G , nodes = None , cliques = None ) : <EOL> """<STR_LIT>""" <EOL> if cliques is None : <EOL> cliques = list ( find_cliques ( G ) ) <EOL> if nodes is None : <EOL> nodes = list ( G . nodes ( ) ) <EOL> if not isinstance ( nodes , list ) : <EOL> v = nodes <EOL> vcliques = [ c for c in cliques if v in c ] <EOL> else : <EOL> vcliques = { } <EOL> for v in nodes : <EOL> vcliques [ v ] = [ c for c in cliques if v in c ] <EOL> return vcliques </s>
