Source Code for Module networkx.cliques

  1  """ 
  2  Cliques   - Find and manipulate cliques of graphs 
  3   
  4  Note that finding the largest clique of a graph has been 
  5  shown to be an NP complete problem so the algorithms here 
  6  could take a LONG time to run.  In practice it hasn't been  
  7  too bad for the graphs tested. 
  8  """ 
  9  __author__ = """Dan Schult (dschult@colgate.edu)""" 
 10  __date__ = "$Date: 2005-06-15 07:56:03 -0600 (Wed, 15 Jun 2005) $" 
 11  __credits__ = """""" 
 12  __revision__ = "$Revision: 1021 $" 
 13  #    Copyright (C) 2004,2005 by  
 14  #    Aric Hagberg <hagberg@lanl.gov> 
 15  #    Dan Schult <dschult@colgate.edu> 
 16  #    Pieter Swart <swart@lanl.gov> 
 17  #    Distributed under the terms of the GNU Lesser General Public License 
 18  #    http://www.gnu.org/copyleft/lesser.html 
 19   
 20  import networkx 
 21   
 22 -def find_cliques(G): 
 23     """ 
 24     Find_cliques algorithm based on Bron & Kerbosch 
 25      
 26     This algorithm searchs for maximal cliques in a graph. 
 27     maximal cliques are the largest complete subgraph containing 
 28     a given point.  The largest maximal clique is sometimes called 
 29     the maximum clique. 
 30      
 31     This algorithm produces the list of maximal cliques each 
 32     of which are a list of the members of the clique. 
 33      
 34     Based on Algol algorithm published by Bron & Kerbosch 
 35     A C version is available as part of the rambin package. 
 36     http://www.ram.org/computing/rambin/rambin.html 
 37   
 38     Reference:: 
 39   
 40        @article{362367, 
 41         author = {Coen Bron and Joep Kerbosch}, 
 42         title = {Algorithm 457: finding all cliques of an undirected graph}, 
 43         journal = {Commun. ACM}, 
 44         volume = {16}, 
 45         number = {9}, 
 46         year = {1973}, 
 47         issn = {0001-0782}, 
 48         pages = {575--577}, 
 49         doi = {http://doi.acm.org/10.1145/362342.362367}, 
 50         publisher = {ACM Press}, 
 51         } 
 52     """ 
 53     all_nodes=G.nodes() 
 54     num_nodes=G.order() 
 55     clique=[] 
 56     cliques=[] 
 57     _extend(all_nodes,0,num_nodes,G,clique,cliques) 
 58     return cliques 
 59   
 60 -def _extend(old_nodes,num_not,num_left,G,clique,cliques): 
 61     """  
 62     A recursive helper routine for find_cliques 
 63   
 64     This recursive routine explores the "old_nodes" set of nodes 
 65     for complete subgraphs.  num_left is the size of old_nodes.  
 66     The first num_not nodes are called the "not" group by B&K 
 67     because they have already been considered.  
 68     The rest (num_left-num_not) of them are called "candidates". 
 69   
 70     G is the graph,  
 71     clique is the clique being built, 
 72     cliques is a list of maximal cliques found so far. 
 73     """ 
 74     # set up sets nots and cands for easy reference 
 75     cands=old_nodes[num_not:] 
 76     nots=old_nodes[:num_not] 
 77   
 78     #  Look for nodes that are "candidates" with the 
 79     #  most neighbors among the "candidates" 
 80     max_conn=0 
 81     for p in cands: 
 82        isneighbor=lambda v: G.has_edge(p,v)# "isneighbor" function 
 83        conn=0       # count connections for ith node 
 84        for nb in cands:    
 85          if isneighbor(nb): 
 86             conn +=1 
 87        if conn>max_conn: 
 88           fixp=p 
 89           max_conn=conn 
 90           if max_conn > num_left-1: break  # found a most connected node 
 91      
 92     # Note: if max_conn still zero, then no connections among candidates 
 93     #     We can take a shortcut. 
 94     #     If connects to a "not" node, we already got that clique 
 95     #     Otherwise adding it makes a clique! 
 96     if max_conn==0: 
 97       for v in cands: 
 98          not_conn=0 
 99          isneighbor=lambda u:G.has_edge(v,u)  #"isneighbor" function 
100          for u in nots: 
101             if isneighbor(u): 
102                not_conn=1 
103                break 
104          if not_conn==0: 
105            clique.append(v) 
106  ##          print "New Maximal Clique Found!",clique 
107            cliques.append(clique[:]) 
108            clique.remove(v) 
109       return 
110   
111     # Set up the Best Candidate as our fixed point for this tree 
112     # best_position=old_nodes.index(fixp) 
113     fixpneighbor=lambda v: G.has_edge(fixp,v) #"isneighbor" function 
114     v=fixp 
115   
116     # Go through each of the candidate  
117     # nodes trying to build a clique 
118     #       cntr counts how many are left to check 
119     for cntr in range(num_left-num_not-max_conn,0,-1): 
120        # add the best node to the list of clique 
121  ##      print tt,"next candidate is:",v 
122        clique.append(v) 
123        isneighbor=lambda u: G.has_edge(v,u) # "isneighbor" function 
124   
125        # Now create new lists to send to next recursion 
126        # fill new array--starting with "not" nodes 
127        new=[] 
128        for u in nots: 
129           if isneighbor(u): 
130              new.append(u) 
131        new_num_not=len(new) 
132        # now fill rest of new array with "candidate" nodes 
133        for u in cands: 
134           if isneighbor(u): 
135              new.append(u) 
136        new_num_left=len(new) 
137   
138        # check if zero or one node left 
139        if new_num_left == 0: 
140           # Now there are no nodes left in "cand" or "not" to look at 
141           # we have found a maximal clique!!! 
142           cliques.append(clique[:]) 
143  ##         print tt,"No nodes left so it must be a clique!" 
144  ##         print tt,"New Maximal Clique Found!",clique 
145        elif new_num_not<new_num_left: 
146           if new_num_left==1: 
147             #  Only one node left so it must be a clique! 
148             clique.append(new[0]) 
149  ##           print tt,"Only one node left so it must be a clique!" 
150  ##           print tt,"New Maximal Clique Found!",clique 
151             cliques.append(clique[:]) 
152             clique.remove(new[0]) 
153           else: 
154             # Recursion on this routine 
155  ##            print tt,"Going into extend with cntr=",cntr 
156  ##            tt=tt + "  " 
157             _extend(new,new_num_not,new_num_left,G,clique,cliques) 
158  ##            tt=tt[0:len(tt)-2]  # go back to previous indentation  
159  ##    else:    # new_num_not==new_num_left 
160  ##             # no new cliques so we're done with this candidate 
161  ##         print tt,"Only nodes from -not- left" 
162   
163   
164        # Done with checking branches for this node, 
165        # remove it from clique and add it to the NOT group 
166        clique.remove(v) 
167        nots.append(v) 
168        cands.remove(v) 
169        # find next candidate 
170        pos=0 
171        if cntr>1: 
172           while fixpneighbor(cands[pos]): 
173              pos += 1 
174           v=cands[pos] 
175   
176 -def make_max_clique_graph(G,create_using=None,name=None): 
177      """  
178      Create the maximal clique graph of a graph. 
179      It finds the maximal cliques and treats these as nodes. 
180      The nodes are connected if they have common members in  
181      the original graph.  Theory has done a lot with clique 
182      graphs, but I haven't seen much on maximal clique graphs. 
183   
184      Note: This should be the same as make_clique_bipartite followed 
185      by project_up, but it saves all the intermediate stuff. 
186      """ 
187      cliq=find_cliques(G) 
188      size=len(cliq) 
189      if create_using: 
190          B=create_using 
191          B.clear() 
192      else: 
193          B=networkx.Graph() 
194      if name is not None: 
195          B.name=name 
196   
197      for i in range(1,size+1): 
198          B.add_node(i) 
199          cl=cliq[i-1] 
200          for j in range(i+1,size+1): 
201              other_cl=cliq[j-1] 
202              intersect=[ w for w in cl if w in other_cl ] 
203              if intersect:     # Not empty list 
204                  B.add_edge(i,j) 
205      return B 
206   
207 -def make_clique_bipartite(G,fpos=None,create_using=None,name=None): 
208      """  
209      Create a bipartite clique graph from a graph G. 
210      Nodes of G are retained as the "bottom nodes" of B and  
211      cliques of G become "top nodes" of B. 
212      Edges are present if a bottom node belongs to the clique  
213      represented by the top node. 
214    
215      Returns a Graph with additional attribute B.node_type 
216      which is "Bottom" or "Top" appropriately. 
217   
218      if fpos is not None, a second additional attribute B.pos 
219      is created to hold the position tuple of each node for viewing 
220      the bipartite graph. 
221      """ 
222      cliq=find_cliques(G) 
223      if create_using: 
224          B=create_using 
225          B.clear() 
226      else: 
227          B=networkx.Graph() 
228      if name is not None: 
229          B.name=name 
230   
231      B.add_nodes_from(G) 
232      B.node_type={}   # New Attribute for B 
233      for n in B: 
234          B.node_type[n]="Bottom" 
235    
236      i=0 
237      if fpos is not None:  
238         B.pos={}     # New Attribute for B 
239         delta_cpos=1./len(cliq) 
240         delta_ppos=1./G.order() 
241         cpos=0. 
242         ppos=0. 
243      for cl in cliq: 
244         i += 1 
245         name= -i   # Top nodes get negative names 
246         B.add_node(name) 
247         B.node_type[name]="Top" 
248         if fpos is not None:  
249            if not B.pos.has_key(name): 
250               B.pos[name]=(0.2,cpos) 
251               cpos +=delta_cpos 
252         for v in cl: 
253            B.add_edge(name,v) 
254            if fpos is not None: 
255               if not B.pos.has_key(v): 
256                  B.pos[v]=(0.8,ppos) 
257                  ppos +=delta_ppos 
258      return B 
259      
260 -def project_down(B,create_using=None,name=None): 
261      """  
262      Project a bipartite graph B down onto its "Bottom Nodes". 
263      The nodes retain their names and are connected if they 
264      share a common Top Node in the Bipartite Graph. 
265      Returns a Graph. 
266      """ 
267      if create_using: 
268          G=create_using 
269          G.clear() 
270      else: 
271          G=networkx.Graph() 
272      if name is not None: 
273          G.name=name 
274   
275      for v in B.nodes(): 
276         if B.node_type[v]=="Bottom": 
277            G.add_node(v) 
278            for cv in B.neighbors(v): 
279               G.add_edges_from([(v,u) for u in B.neighbors(cv)]) 
280      return G 
281    
282 -def project_up(B,create_using=None,name=None): 
283      """  
284      Project a bipartite graph B up onto its "Top Nodes". 
285      The nodes retain their names and are connected if they 
286      share a common Bottom Node in the Bipartite Graph. 
287      Returns a Graph. 
288      """ 
289      if create_using: 
290          G=create_using 
291          G.clear() 
292      else: 
293          G=networkx.Graph() 
294      if name is not None: 
295          G.name=name 
296   
297      for v in B.nodes(): 
298         if B.node_type[v]=="Top": 
299            vname= -v   #Change sign of name for Top Nodes 
300            G.add_node(vname) 
301            for cv in B.neighbors(v): 
302               # Note: -u changes the name (not Top node anymore) 
303               G.add_edges_from([(vname,-u) for u in B.neighbors(cv) if u!=v]) 
304      return G 
305    
306 -def graph_clique_number(G,cliques=None): 
307      """Return the clique number (size the largest clique) for G. 
308         Optional list of cliques can be input if already computed. 
309      """ 
310      if cliques is None: 
311          cliques=find_cliques(G) 
312      return   max( [len(c) for c in cliques] ) 
313   
314   
315 -def graph_number_of_cliques(G,cliques=None): 
316      """  Returns the number of maximal cliques in G 
317         Optional list of cliques can be input if already computed. 
318      """ 
319      if cliques is None: 
320          cliques=find_cliques(G) 
321      return   len(cliques) 
322   
323    
324 -def node_clique_number(G,nodes=None,with_labels=False,cliques=None): 
325      """ Returns the size of the largest maximal clique containing 
326          each given node.   
327   
328          Returns a single or list depending on input nodes. 
329          Returns a dict keyed by node if "with_labels=True". 
330          Optional list of cliques can be input if already computed. 
331      """ 
332      if nodes is None:                 # none, use entire graph 
333          nodes=G.nodes() 
334      elif  not isinstance(nodes, list):    # check for a list 
335          nodes=[nodes]             # assume it is a single value 
336   
337      if cliques is None: 
338          cliques=find_cliques(G) 
339      d={} 
340      for v in nodes: 
341          d[v]=max([len(c) for c in cliques if v in c]) 
342       
343      if with_labels: return d 
344      if len(d)==1: return d[v] #return single value 
345      return d.values() 
346   
347   
348 -def number_of_cliques(G,nodes=None,cliques=None,with_labels=False): 
349      """ Returns the number of maximal cliques for each node. 
350   
351          Returns a single or list depending on input nodes. 
352          Returns a dict keyed by node if "with_labels=True". 
353          Optional list of cliques can be input if already computed. 
354      """ 
355      if nodes is None: 
356          nodes=G.nodes()   # none, get entire graph 
357      elif  not isinstance(nodes, list):    # check for a list 
358          nodes=[nodes]             # assume it is a single value 
359   
360      if cliques is None: 
361          cliques=find_cliques(G) 
362      numcliq={} 
363      for v in nodes: 
364          numcliq[v]=len([1 for c in cliques if v in c]) 
365   
366      if with_labels: return numcliq 
367      if len(numcliq)==1: return numcliq[v] 
368      return numcliq.values() 
369       
370 -def cliques_containing_node(G,nodes=None,cliques=None,with_labels=False): 
371      """ Returns a list of cliques containing the given node. 
372   
373          Returns a single list or list of lists depending on input nodes. 
374          Returns a dict keyed by node if "with_labels=True". 
375          Optional list of cliques can be input if already computed. 
376      """ 
377      if nodes is None: 
378          nodes=G.nodes()   # none, get entire graph 
379      elif  not isinstance(nodes, list):    # check for a list 
380          nodes=[nodes]             # assume it is a single value 
381   
382      if cliques is None: 
383          cliques=find_cliques(G) 
384      vcliques={} 
385      for v in nodes: 
386          vcliques[v]=[c for c in cliques if v in c] 
387   
388      if with_labels: return vcliques 
389      if len(vcliques)==1: return vcliques[v] 
390      return vcliques.values() 
391   
392 -def _test_suite(): 
393      import doctest 
394      suite = doctest.DocFileSuite('tests/cliques.txt',package='networkx') 
395      return suite 
396   
397   
398  if __name__ == "__main__": 
399      import os    
400      import sys 
401      import unittest 
402      if sys.version_info[:2] < (2, 4): 
403          print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2] 
404          sys.exit(-1) 
405      # directory of networkx package (relative to this) 
406      nxbase=sys.path[0]+os.sep+os.pardir 
407      sys.path.insert(0,nxbase) # prepend to search path 
408      unittest.TextTestRunner().run(_test_suite()) 
409