Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for finding and manipulating cliques.
3Finding the largest clique in a graph is NP-complete problem, so most of
4these algorithms have an exponential running time; for more information,
5see the Wikipedia article on the clique problem [1]_.
7.. [1] clique problem:: https://en.wikipedia.org/wiki/Clique_problem
9"""
11from collections import Counter, defaultdict, deque
12from itertools import chain, combinations, islice
14import networkx as nx
15from networkx.utils import not_implemented_for
17__all__ = [
18 "find_cliques",
19 "find_cliques_recursive",
20 "make_max_clique_graph",
21 "make_clique_bipartite",
22 "node_clique_number",
23 "number_of_cliques",
24 "enumerate_all_cliques",
25 "max_weight_clique",
26]
29@not_implemented_for("directed")
30@nx._dispatchable
31def enumerate_all_cliques(G):
32 """Returns all cliques in an undirected graph.
34 This function returns an iterator over cliques, each of which is a
35 list of nodes. The iteration is ordered by cardinality of the
36 cliques: first all cliques of size one, then all cliques of size
37 two, etc.
39 Parameters
40 ----------
41 G : NetworkX graph
42 An undirected graph.
44 Returns
45 -------
46 iterator
47 An iterator over cliques, each of which is a list of nodes in
48 `G`. The cliques are ordered according to size.
50 Notes
51 -----
52 To obtain a list of all cliques, use
53 `list(enumerate_all_cliques(G))`. However, be aware that in the
54 worst-case, the length of this list can be exponential in the number
55 of nodes in the graph (for example, when the graph is the complete
56 graph). This function avoids storing all cliques in memory by only
57 keeping current candidate node lists in memory during its search.
59 The implementation is adapted from the algorithm by Zhang, et
60 al. (2005) [1]_ to output all cliques discovered.
62 This algorithm ignores self-loops and parallel edges, since cliques
63 are not conventionally defined with such edges.
65 References
66 ----------
67 .. [1] Yun Zhang, Abu-Khzam, F.N., Baldwin, N.E., Chesler, E.J.,
68 Langston, M.A., Samatova, N.F.,
69 "Genome-Scale Computational Approaches to Memory-Intensive
70 Applications in Systems Biology".
71 *Supercomputing*, 2005. Proceedings of the ACM/IEEE SC 2005
72 Conference, pp. 12, 12--18 Nov. 2005.
73 <https://doi.org/10.1109/SC.2005.29>.
75 """
76 index = {}
77 nbrs = {}
78 for u in G:
79 index[u] = len(index)
80 # Neighbors of u that appear after u in the iteration order of G.
81 nbrs[u] = {v for v in G[u] if v not in index}
83 queue = deque(([u], sorted(nbrs[u], key=index.__getitem__)) for u in G)
84 # Loop invariants:
85 # 1. len(base) is nondecreasing.
86 # 2. (base + cnbrs) is sorted with respect to the iteration order of G.
87 # 3. cnbrs is a set of common neighbors of nodes in base.
88 while queue:
89 base, cnbrs = map(list, queue.popleft())
90 yield base
91 for i, u in enumerate(cnbrs):
92 # Use generators to reduce memory consumption.
93 queue.append(
94 (
95 chain(base, [u]),
96 filter(nbrs[u].__contains__, islice(cnbrs, i + 1, None)),
97 )
98 )
101@not_implemented_for("directed")
102@nx._dispatchable
103def find_cliques(G, nodes=None):
104 """Returns all maximal cliques in an undirected graph.
106 For each node *n*, a *maximal clique for n* is a largest complete
107 subgraph containing *n*. The largest maximal clique is sometimes
108 called the *maximum clique*.
110 This function returns an iterator over cliques, each of which is a
111 list of nodes. It is an iterative implementation, so should not
112 suffer from recursion depth issues.
114 This function accepts a list of `nodes` and only the maximal cliques
115 containing all of these `nodes` are returned. It can considerably speed up
116 the running time if some specific cliques are desired.
118 Parameters
119 ----------
120 G : NetworkX graph
121 An undirected graph.
123 nodes : list, optional (default=None)
124 If provided, only yield *maximal cliques* containing all nodes in `nodes`.
125 If `nodes` isn't a clique itself, a ValueError is raised.
127 Returns
128 -------
129 iterator
130 An iterator over maximal cliques, each of which is a list of
131 nodes in `G`. If `nodes` is provided, only the maximal cliques
132 containing all the nodes in `nodes` are returned. The order of
133 cliques is arbitrary.
135 Raises
136 ------
137 ValueError
138 If `nodes` is not a clique.
140 Examples
141 --------
142 >>> from pprint import pprint # For nice dict formatting
143 >>> G = nx.karate_club_graph()
144 >>> sum(1 for c in nx.find_cliques(G)) # The number of maximal cliques in G
145 36
146 >>> max(nx.find_cliques(G), key=len) # The largest maximal clique in G
147 [0, 1, 2, 3, 13]
149 The size of the largest maximal clique is known as the *clique number* of
150 the graph, which can be found directly with:
152 >>> max(len(c) for c in nx.find_cliques(G))
153 5
155 One can also compute the number of maximal cliques in `G` that contain a given
156 node. The following produces a dictionary keyed by node whose
157 values are the number of maximal cliques in `G` that contain the node:
159 >>> from collections import Counter
160 >>> from itertools import chain
161 >>> counts = Counter(chain.from_iterable(nx.find_cliques(G)))
162 >>> pprint(dict(counts))
163 {0: 13,
164 1: 6,
165 2: 7,
166 3: 3,
167 4: 2,
168 5: 3,
169 6: 3,
170 7: 1,
171 8: 3,
172 9: 2,
173 10: 2,
174 11: 1,
175 12: 1,
176 13: 2,
177 14: 1,
178 15: 1,
179 16: 1,
180 17: 1,
181 18: 1,
182 19: 2,
183 20: 1,
184 21: 1,
185 22: 1,
186 23: 3,
187 24: 2,
188 25: 2,
189 26: 1,
190 27: 3,
191 28: 2,
192 29: 2,
193 30: 2,
194 31: 4,
195 32: 9,
196 33: 14}
198 Or, similarly, the maximal cliques in `G` that contain a given node.
199 For example, the 4 maximal cliques that contain node 31:
201 >>> [c for c in nx.find_cliques(G) if 31 in c]
202 [[0, 31], [33, 32, 31], [33, 28, 31], [24, 25, 31]]
204 See Also
205 --------
206 find_cliques_recursive
207 A recursive version of the same algorithm.
209 Notes
210 -----
211 To obtain a list of all maximal cliques, use
212 `list(find_cliques(G))`. However, be aware that in the worst-case,
213 the length of this list can be exponential in the number of nodes in
214 the graph. This function avoids storing all cliques in memory by
215 only keeping current candidate node lists in memory during its search.
217 This implementation is based on the algorithm published by Bron and
218 Kerbosch (1973) [1]_, as adapted by Tomita, Tanaka and Takahashi
219 (2006) [2]_ and discussed in Cazals and Karande (2008) [3]_. It
220 essentially unrolls the recursion used in the references to avoid
221 issues of recursion stack depth (for a recursive implementation, see
222 :func:`find_cliques_recursive`).
224 This algorithm ignores self-loops and parallel edges, since cliques
225 are not conventionally defined with such edges.
227 References
228 ----------
229 .. [1] Bron, C. and Kerbosch, J.
230 "Algorithm 457: finding all cliques of an undirected graph".
231 *Communications of the ACM* 16, 9 (Sep. 1973), 575--577.
232 <http://portal.acm.org/citation.cfm?doid=362342.362367>
234 .. [2] Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi,
235 "The worst-case time complexity for generating all maximal
236 cliques and computational experiments",
237 *Theoretical Computer Science*, Volume 363, Issue 1,
238 Computing and Combinatorics,
239 10th Annual International Conference on
240 Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28--42
241 <https://doi.org/10.1016/j.tcs.2006.06.015>
243 .. [3] F. Cazals, C. Karande,
244 "A note on the problem of reporting maximal cliques",
245 *Theoretical Computer Science*,
246 Volume 407, Issues 1--3, 6 November 2008, Pages 564--568,
247 <https://doi.org/10.1016/j.tcs.2008.05.010>
249 """
250 if len(G) == 0:
251 return
253 adj = {u: {v for v in G[u] if v != u} for u in G}
255 # Initialize Q with the given nodes and subg, cand with their nbrs
256 Q = nodes[:] if nodes is not None else []
257 cand = set(G)
258 for node in Q:
259 if node not in cand:
260 raise ValueError(f"The given `nodes` {nodes} do not form a clique")
261 cand &= adj[node]
263 if not cand:
264 yield Q[:]
265 return
267 subg = cand.copy()
268 stack = []
269 Q.append(None)
271 u = max(subg, key=lambda u: len(cand & adj[u]))
272 ext_u = cand - adj[u]
274 try:
275 while True:
276 if ext_u:
277 q = ext_u.pop()
278 cand.remove(q)
279 Q[-1] = q
280 adj_q = adj[q]
281 subg_q = subg & adj_q
282 if not subg_q:
283 yield Q[:]
284 else:
285 cand_q = cand & adj_q
286 if cand_q:
287 stack.append((subg, cand, ext_u))
288 Q.append(None)
289 subg = subg_q
290 cand = cand_q
291 u = max(subg, key=lambda u: len(cand & adj[u]))
292 ext_u = cand - adj[u]
293 else:
294 Q.pop()
295 subg, cand, ext_u = stack.pop()
296 except IndexError:
297 pass
300@not_implemented_for("directed")
301@nx._dispatchable
302def find_cliques_recursive(G, nodes=None):
303 """Returns all maximal cliques in a graph.
305 For each node *v*, a *maximal clique for v* is a largest complete
306 subgraph containing *v*. The largest maximal clique is sometimes
307 called the *maximum clique*.
309 This function returns an iterator over cliques, each of which is a
310 list of nodes. It is a recursive implementation, so may suffer from
311 recursion depth issues, but is included for pedagogical reasons.
312 For a non-recursive implementation, see :func:`find_cliques`.
314 This function accepts a list of `nodes` and only the maximal cliques
315 containing all of these `nodes` are returned. It can considerably speed up
316 the running time if some specific cliques are desired.
318 Parameters
319 ----------
320 G : NetworkX graph
321 An undirected graph.
323 nodes : list, optional (default=None)
324 If provided, only yield *maximal cliques* containing all nodes in `nodes`.
325 If `nodes` isn't a clique itself, a ValueError is raised.
327 Returns
328 -------
329 iterator
330 An iterator over maximal cliques, each of which is a list of
331 nodes in `G`. If `nodes` is provided, only the maximal cliques
332 containing all the nodes in `nodes` are yielded. The order of
333 cliques is arbitrary.
335 Raises
336 ------
337 NetworkXNotImplemented
338 If `G` is directed.
340 ValueError
341 If `nodes` is not a clique.
343 See Also
344 --------
345 find_cliques
346 An iterative version of the same algorithm. See docstring for examples.
348 Notes
349 -----
350 To obtain a list of all maximal cliques, use
351 `list(find_cliques_recursive(G))`. However, be aware that in the
352 worst-case, the length of this list can be exponential in the number
353 of nodes in the graph. This function avoids storing all cliques in memory
354 by only keeping current candidate node lists in memory during its search.
356 This implementation is based on the algorithm published by Bron and
357 Kerbosch (1973) [1]_, as adapted by Tomita, Tanaka and Takahashi
358 (2006) [2]_ and discussed in Cazals and Karande (2008) [3]_. For a
359 non-recursive implementation, see :func:`find_cliques`.
361 This algorithm ignores self-loops and parallel edges, since cliques
362 are not conventionally defined with such edges.
364 References
365 ----------
366 .. [1] Bron, C. and Kerbosch, J.
367 "Algorithm 457: finding all cliques of an undirected graph".
368 *Communications of the ACM* 16, 9 (Sep. 1973), 575--577.
369 <http://portal.acm.org/citation.cfm?doid=362342.362367>
371 .. [2] Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi,
372 "The worst-case time complexity for generating all maximal
373 cliques and computational experiments",
374 *Theoretical Computer Science*, Volume 363, Issue 1,
375 Computing and Combinatorics,
376 10th Annual International Conference on
377 Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28--42
378 <https://doi.org/10.1016/j.tcs.2006.06.015>
380 .. [3] F. Cazals, C. Karande,
381 "A note on the problem of reporting maximal cliques",
382 *Theoretical Computer Science*,
383 Volume 407, Issues 1--3, 6 November 2008, Pages 564--568,
384 <https://doi.org/10.1016/j.tcs.2008.05.010>
386 """
387 if len(G) == 0:
388 return iter([])
390 adj = {u: {v for v in G[u] if v != u} for u in G}
392 # Initialize Q with the given nodes and subg, cand with their nbrs
393 Q = nodes[:] if nodes is not None else []
394 cand_init = set(G)
395 for node in Q:
396 if node not in cand_init:
397 raise ValueError(f"The given `nodes` {nodes} do not form a clique")
398 cand_init &= adj[node]
400 if not cand_init:
401 return iter([Q])
403 subg_init = cand_init.copy()
405 def expand(subg, cand):
406 u = max(subg, key=lambda u: len(cand & adj[u]))
407 for q in cand - adj[u]:
408 cand.remove(q)
409 Q.append(q)
410 adj_q = adj[q]
411 subg_q = subg & adj_q
412 if not subg_q:
413 yield Q[:]
414 else:
415 cand_q = cand & adj_q
416 if cand_q:
417 yield from expand(subg_q, cand_q)
418 Q.pop()
420 return expand(subg_init, cand_init)
423@nx._dispatchable(returns_graph=True)
424def make_max_clique_graph(G, create_using=None):
425 """Returns the maximal clique graph of the given graph.
427 The nodes of the maximal clique graph of `G` are the cliques of
428 `G` and an edge joins two cliques if the cliques are not disjoint.
430 Parameters
431 ----------
432 G : NetworkX graph
434 create_using : NetworkX graph constructor, optional (default=nx.Graph)
435 Graph type to create. If graph instance, then cleared before populated.
437 Returns
438 -------
439 NetworkX graph
440 A graph whose nodes are the cliques of `G` and whose edges
441 join two cliques if they are not disjoint.
443 Notes
444 -----
445 This function behaves like the following code::
447 import networkx as nx
449 G = nx.make_clique_bipartite(G)
450 cliques = [v for v in G.nodes() if G.nodes[v]["bipartite"] == 0]
451 G = nx.bipartite.projected_graph(G, cliques)
452 G = nx.relabel_nodes(G, {-v: v - 1 for v in G})
454 It should be faster, though, since it skips all the intermediate
455 steps.
457 """
458 if create_using is None:
459 B = G.__class__()
460 else:
461 B = nx.empty_graph(0, create_using)
462 cliques = list(enumerate(set(c) for c in find_cliques(G)))
463 # Add a numbered node for each clique.
464 B.add_nodes_from(i for i, c in cliques)
465 # Join cliques by an edge if they share a node.
466 clique_pairs = combinations(cliques, 2)
467 B.add_edges_from((i, j) for (i, c1), (j, c2) in clique_pairs if c1 & c2)
468 return B
471@nx._dispatchable(returns_graph=True)
472def make_clique_bipartite(G, fpos=None, create_using=None, name=None):
473 """Returns the bipartite clique graph corresponding to `G`.
475 In the returned bipartite graph, the "bottom" nodes are the nodes of
476 `G` and the "top" nodes represent the maximal cliques of `G`.
477 There is an edge from node *v* to clique *C* in the returned graph
478 if and only if *v* is an element of *C*.
480 Parameters
481 ----------
482 G : NetworkX graph
483 An undirected graph.
485 fpos : bool
486 If True or not None, the returned graph will have an
487 additional attribute, `pos`, a dictionary mapping node to
488 position in the Euclidean plane.
490 create_using : NetworkX graph constructor, optional (default=nx.Graph)
491 Graph type to create. If graph instance, then cleared before populated.
493 Returns
494 -------
495 NetworkX graph
496 A bipartite graph whose "bottom" set is the nodes of the graph
497 `G`, whose "top" set is the cliques of `G`, and whose edges
498 join nodes of `G` to the cliques that contain them.
500 The nodes of the graph `G` have the node attribute
501 'bipartite' set to 1 and the nodes representing cliques
502 have the node attribute 'bipartite' set to 0, as is the
503 convention for bipartite graphs in NetworkX.
505 """
506 B = nx.empty_graph(0, create_using)
507 B.clear()
508 # The "bottom" nodes in the bipartite graph are the nodes of the
509 # original graph, G.
510 B.add_nodes_from(G, bipartite=1)
511 for i, cl in enumerate(find_cliques(G)):
512 # The "top" nodes in the bipartite graph are the cliques. These
513 # nodes get negative numbers as labels.
514 name = -i - 1
515 B.add_node(name, bipartite=0)
516 B.add_edges_from((v, name) for v in cl)
517 return B
520@nx._dispatchable
521def node_clique_number(G, nodes=None, cliques=None, separate_nodes=False):
522 """Returns the size of the largest maximal clique containing each given node.
524 Returns a single or list depending on input nodes.
525 An optional list of cliques can be input if already computed.
527 Parameters
528 ----------
529 G : NetworkX graph
530 An undirected graph.
532 cliques : list, optional (default=None)
533 A list of cliques, each of which is itself a list of nodes.
534 If not specified, the list of all cliques will be computed
535 using :func:`find_cliques`.
537 Returns
538 -------
539 int or dict
540 If `nodes` is a single node, returns the size of the
541 largest maximal clique in `G` containing that node.
542 Otherwise return a dict keyed by node to the size
543 of the largest maximal clique containing that node.
545 See Also
546 --------
547 find_cliques
548 find_cliques yields the maximal cliques of G.
549 It accepts a `nodes` argument which restricts consideration to
550 maximal cliques containing all the given `nodes`.
551 The search for the cliques is optimized for `nodes`.
552 number_of_cliques
553 """
554 if cliques is None:
555 if nodes is not None:
556 # Use ego_graph to decrease size of graph
557 # check for single node
558 if nodes in G:
559 return max(len(c) for c in find_cliques(nx.ego_graph(G, nodes)))
560 # handle multiple nodes
561 return {
562 n: max(len(c) for c in find_cliques(nx.ego_graph(G, n))) for n in nodes
563 }
565 # nodes is None--find all cliques
566 cliques = list(find_cliques(G))
568 # single node requested
569 if nodes in G:
570 return max(len(c) for c in cliques if nodes in c)
572 # multiple nodes requested
573 # preprocess all nodes (faster than one at a time for even 2 nodes)
574 size_for_n = defaultdict(int)
575 for c in cliques:
576 size_of_c = len(c)
577 for n in c:
578 if size_for_n[n] < size_of_c:
579 size_for_n[n] = size_of_c
580 if nodes is None:
581 return size_for_n
582 return {n: size_for_n[n] for n in nodes}
585def number_of_cliques(G, nodes=None, cliques=None):
586 """Return the number of maximal cliques each node is part of.
588 Output is a single value or dict depending on `nodes`.
589 Optional list of cliques can be input if already computed.
591 Parameters
592 ----------
593 G : NetworkX graph
594 An undirected graph.
596 nodes : list or None, optional (default=None)
597 A list of nodes to return the number of maximal cliques for.
598 If `None`, return the number of maximal cliques for all nodes.
600 cliques : list or None, optional (default=None)
601 A precomputed list of maximal cliques to use for the calculation.
603 Returns
604 -------
605 int or dict
606 If `nodes` is a single node, return the number of maximal cliques it is
607 part of. If `nodes` is a list, return a dictionary keyed by node to the
608 number of maximal cliques it is part of.
610 Raises
611 ------
612 NetworkXNotImplemented
613 If `G` is directed.
615 See Also
616 --------
617 find_cliques
618 node_clique_number
620 Examples
621 --------
622 Compute the number of maximal cliques a node is part of:
624 >>> G = nx.complete_graph(3)
625 >>> nx.add_cycle(G, [0, 3, 4])
626 >>> nx.number_of_cliques(G, nodes=0)
627 2
628 >>> nx.number_of_cliques(G, nodes=1)
629 1
631 Or, for a list of nodes:
633 >>> nx.number_of_cliques(G, nodes=[0, 1])
634 {0: 2, 1: 1}
636 If no explicit `nodes` are provided, all nodes are considered:
638 >>> nx.number_of_cliques(G)
639 {0: 2, 1: 1, 2: 1, 3: 1, 4: 1}
641 The list of maximal cliques can also be precomputed:
643 >>> cl = list(nx.find_cliques(G))
644 >>> nx.number_of_cliques(G, cliques=cl)
645 {0: 2, 1: 1, 2: 1, 3: 1, 4: 1}
646 """
647 if cliques is None:
648 cliques = find_cliques(G)
650 if nodes is None:
651 nodes = list(G.nodes()) # none, get entire graph
653 if not isinstance(nodes, list): # check for a list
654 v = nodes
655 # assume it is a single value
656 numcliq = sum(1 for c in cliques if v in c)
657 else:
658 numcliq = Counter(chain.from_iterable(cliques))
659 numcliq = {v: numcliq[v] for v in nodes} # return a dict
660 return numcliq
663class MaxWeightClique:
664 """A class for the maximum weight clique algorithm.
666 This class is a helper for the `max_weight_clique` function. The class
667 should not normally be used directly.
669 Parameters
670 ----------
671 G : NetworkX graph
672 The undirected graph for which a maximum weight clique is sought
673 weight : string or None, optional (default='weight')
674 The node attribute that holds the integer value used as a weight.
675 If None, then each node has weight 1.
677 Attributes
678 ----------
679 G : NetworkX graph
680 The undirected graph for which a maximum weight clique is sought
681 node_weights: dict
682 The weight of each node
683 incumbent_nodes : list
684 The nodes of the incumbent clique (the best clique found so far)
685 incumbent_weight: int
686 The weight of the incumbent clique
687 """
689 def __init__(self, G, weight):
690 self.G = G
691 self.incumbent_nodes = []
692 self.incumbent_weight = 0
694 if weight is None:
695 self.node_weights = {v: 1 for v in G.nodes()}
696 else:
697 for v in G.nodes():
698 if weight not in G.nodes[v]:
699 errmsg = f"Node {v!r} does not have the requested weight field."
700 raise KeyError(errmsg)
701 if not isinstance(G.nodes[v][weight], int):
702 errmsg = f"The {weight!r} field of node {v!r} is not an integer."
703 raise ValueError(errmsg)
704 self.node_weights = {v: G.nodes[v][weight] for v in G.nodes()}
706 def update_incumbent_if_improved(self, C, C_weight):
707 """Update the incumbent if the node set C has greater weight.
709 C is assumed to be a clique.
710 """
711 if C_weight > self.incumbent_weight:
712 self.incumbent_nodes = C[:]
713 self.incumbent_weight = C_weight
715 def greedily_find_independent_set(self, P):
716 """Greedily find an independent set of nodes from a set of
717 nodes P."""
718 independent_set = []
719 P = P[:]
720 while P:
721 v = P[0]
722 independent_set.append(v)
723 P = [w for w in P if v != w and not self.G.has_edge(v, w)]
724 return independent_set
726 def find_branching_nodes(self, P, target):
727 """Find a set of nodes to branch on."""
728 residual_wt = {v: self.node_weights[v] for v in P}
729 total_wt = 0
730 P = P[:]
731 while P:
732 independent_set = self.greedily_find_independent_set(P)
733 min_wt_in_class = min(residual_wt[v] for v in independent_set)
734 total_wt += min_wt_in_class
735 if total_wt > target:
736 break
737 for v in independent_set:
738 residual_wt[v] -= min_wt_in_class
739 P = [v for v in P if residual_wt[v] != 0]
740 return P
742 def expand(self, C, C_weight, P):
743 """Look for the best clique that contains all the nodes in C and zero or
744 more of the nodes in P, backtracking if it can be shown that no such
745 clique has greater weight than the incumbent.
746 """
747 self.update_incumbent_if_improved(C, C_weight)
748 branching_nodes = self.find_branching_nodes(P, self.incumbent_weight - C_weight)
749 while branching_nodes:
750 v = branching_nodes.pop()
751 P.remove(v)
752 new_C = C + [v]
753 new_C_weight = C_weight + self.node_weights[v]
754 new_P = [w for w in P if self.G.has_edge(v, w)]
755 self.expand(new_C, new_C_weight, new_P)
757 def find_max_weight_clique(self):
758 """Find a maximum weight clique."""
759 # Sort nodes in reverse order of degree for speed
760 nodes = sorted(self.G.nodes(), key=lambda v: self.G.degree(v), reverse=True)
761 nodes = [v for v in nodes if self.node_weights[v] > 0]
762 self.expand([], 0, nodes)
765@not_implemented_for("directed")
766@nx._dispatchable(node_attrs="weight")
767def max_weight_clique(G, weight="weight"):
768 """Find a maximum weight clique in G.
770 A *clique* in a graph is a set of nodes such that every two distinct nodes
771 are adjacent. The *weight* of a clique is the sum of the weights of its
772 nodes. A *maximum weight clique* of graph G is a clique C in G such that
773 no clique in G has weight greater than the weight of C.
775 Parameters
776 ----------
777 G : NetworkX graph
778 Undirected graph
779 weight : string or None, optional (default='weight')
780 The node attribute that holds the integer value used as a weight.
781 If None, then each node has weight 1.
783 Returns
784 -------
785 clique : list
786 the nodes of a maximum weight clique
787 weight : int
788 the weight of a maximum weight clique
790 Notes
791 -----
792 The implementation is recursive, and therefore it may run into recursion
793 depth issues if G contains a clique whose number of nodes is close to the
794 recursion depth limit.
796 At each search node, the algorithm greedily constructs a weighted
797 independent set cover of part of the graph in order to find a small set of
798 nodes on which to branch. The algorithm is very similar to the algorithm
799 of Tavares et al. [1]_, other than the fact that the NetworkX version does
800 not use bitsets. This style of algorithm for maximum weight clique (and
801 maximum weight independent set, which is the same problem but on the
802 complement graph) has a decades-long history. See Algorithm B of Warren
803 and Hicks [2]_ and the references in that paper.
805 References
806 ----------
807 .. [1] Tavares, W.A., Neto, M.B.C., Rodrigues, C.D., Michelon, P.: Um
808 algoritmo de branch and bound para o problema da clique máxima
809 ponderada. Proceedings of XLVII SBPO 1 (2015).
811 .. [2] Warren, Jeffrey S, Hicks, Illya V.: Combinatorial Branch-and-Bound
812 for the Maximum Weight Independent Set Problem. Technical Report,
813 Texas A&M University (2016).
814 """
816 mwc = MaxWeightClique(G, weight)
817 mwc.find_max_weight_clique()
818 return mwc.incumbent_nodes, mwc.incumbent_weight