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
14
15
16
17
18
19
20 import networkx
21
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
75 cands=old_nodes[num_not:]
76 nots=old_nodes[:num_not]
77
78
79
80 max_conn=0
81 for p in cands:
82 isneighbor=lambda v: G.has_edge(p,v)
83 conn=0
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
91
92
93
94
95
96 if max_conn==0:
97 for v in cands:
98 not_conn=0
99 isneighbor=lambda u:G.has_edge(v,u)
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
107 cliques.append(clique[:])
108 clique.remove(v)
109 return
110
111
112
113 fixpneighbor=lambda v: G.has_edge(fixp,v)
114 v=fixp
115
116
117
118
119 for cntr in range(num_left-num_not-max_conn,0,-1):
120
121
122 clique.append(v)
123 isneighbor=lambda u: G.has_edge(v,u)
124
125
126
127 new=[]
128 for u in nots:
129 if isneighbor(u):
130 new.append(u)
131 new_num_not=len(new)
132
133 for u in cands:
134 if isneighbor(u):
135 new.append(u)
136 new_num_left=len(new)
137
138
139 if new_num_left == 0:
140
141
142 cliques.append(clique[:])
143
144
145 elif new_num_not<new_num_left:
146 if new_num_left==1:
147
148 clique.append(new[0])
149
150
151 cliques.append(clique[:])
152 clique.remove(new[0])
153 else:
154
155
156
157 _extend(new,new_num_not,new_num_left,G,clique,cliques)
158
159
160
161
162
163
164
165
166 clique.remove(v)
167 nots.append(v)
168 cands.remove(v)
169
170 pos=0
171 if cntr>1:
172 while fixpneighbor(cands[pos]):
173 pos += 1
174 v=cands[pos]
175
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:
204 B.add_edge(i,j)
205 return B
206
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={}
233 for n in B:
234 B.node_type[n]="Bottom"
235
236 i=0
237 if fpos is not None:
238 B.pos={}
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
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
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
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
300 G.add_node(vname)
301 for cv in B.neighbors(v):
302
303 G.add_edges_from([(vname,-u) for u in B.neighbors(cv) if u!=v])
304 return G
305
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
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
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:
333 nodes=G.nodes()
334 elif not isinstance(nodes, list):
335 nodes=[nodes]
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]
345 return d.values()
346
347
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()
357 elif not isinstance(nodes, list):
358 nodes=[nodes]
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
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()
379 elif not isinstance(nodes, list):
380 nodes=[nodes]
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
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
406 nxbase=sys.path[0]+os.sep+os.pardir
407 sys.path.insert(0,nxbase)
408 unittest.TextTestRunner().run(_test_suite())
409