Package networkx :: Module cliques
[hide private]
[frames] | no frames]

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