Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/clique.py: 15%
200 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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"""
10from collections import defaultdict, deque
11from itertools import chain, combinations, islice
13import networkx as nx
14from networkx.utils import not_implemented_for
16__all__ = [
17 "find_cliques",
18 "find_cliques_recursive",
19 "make_max_clique_graph",
20 "make_clique_bipartite",
21 "node_clique_number",
22 "number_of_cliques",
23 "enumerate_all_cliques",
24 "max_weight_clique",
25]
28@not_implemented_for("directed")
29@nx._dispatch
30def enumerate_all_cliques(G):
31 """Returns all cliques in an undirected graph.
33 This function returns an iterator over cliques, each of which is a
34 list of nodes. The iteration is ordered by cardinality of the
35 cliques: first all cliques of size one, then all cliques of size
36 two, etc.
38 Parameters
39 ----------
40 G : NetworkX graph
41 An undirected graph.
43 Returns
44 -------
45 iterator
46 An iterator over cliques, each of which is a list of nodes in
47 `G`. The cliques are ordered according to size.
49 Notes
50 -----
51 To obtain a list of all cliques, use
52 `list(enumerate_all_cliques(G))`. However, be aware that in the
53 worst-case, the length of this list can be exponential in the number
54 of nodes in the graph (for example, when the graph is the complete
55 graph). This function avoids storing all cliques in memory by only
56 keeping current candidate node lists in memory during its search.
58 The implementation is adapted from the algorithm by Zhang, et
59 al. (2005) [1]_ to output all cliques discovered.
61 This algorithm ignores self-loops and parallel edges, since cliques
62 are not conventionally defined with such edges.
64 References
65 ----------
66 .. [1] Yun Zhang, Abu-Khzam, F.N., Baldwin, N.E., Chesler, E.J.,
67 Langston, M.A., Samatova, N.F.,
68 "Genome-Scale Computational Approaches to Memory-Intensive
69 Applications in Systems Biology".
70 *Supercomputing*, 2005. Proceedings of the ACM/IEEE SC 2005
71 Conference, pp. 12, 12--18 Nov. 2005.
72 <https://doi.org/10.1109/SC.2005.29>.
74 """
75 index = {}
76 nbrs = {}
77 for u in G:
78 index[u] = len(index)
79 # Neighbors of u that appear after u in the iteration order of G.
80 nbrs[u] = {v for v in G[u] if v not in index}
82 queue = deque(([u], sorted(nbrs[u], key=index.__getitem__)) for u in G)
83 # Loop invariants:
84 # 1. len(base) is nondecreasing.
85 # 2. (base + cnbrs) is sorted with respect to the iteration order of G.
86 # 3. cnbrs is a set of common neighbors of nodes in base.
87 while queue:
88 base, cnbrs = map(list, queue.popleft())
89 yield base
90 for i, u in enumerate(cnbrs):
91 # Use generators to reduce memory consumption.
92 queue.append(
93 (
94 chain(base, [u]),
95 filter(nbrs[u].__contains__, islice(cnbrs, i + 1, None)),
96 )
97 )
100@not_implemented_for("directed")
101@nx._dispatch
102def find_cliques(G, nodes=None):
103 """Returns all maximal cliques in an undirected graph.
105 For each node *n*, a *maximal clique for n* is a largest complete
106 subgraph containing *n*. The largest maximal clique is sometimes
107 called the *maximum clique*.
109 This function returns an iterator over cliques, each of which is a
110 list of nodes. It is an iterative implementation, so should not
111 suffer from recursion depth issues.
113 This function accepts a list of `nodes` and only the maximal cliques
114 containing all of these `nodes` are returned. It can considerably speed up
115 the running time if some specific cliques are desired.
117 Parameters
118 ----------
119 G : NetworkX graph
120 An undirected graph.
122 nodes : list, optional (default=None)
123 If provided, only yield *maximal cliques* containing all nodes in `nodes`.
124 If `nodes` isn't a clique itself, a ValueError is raised.
126 Returns
127 -------
128 iterator
129 An iterator over maximal cliques, each of which is a list of
130 nodes in `G`. If `nodes` is provided, only the maximal cliques
131 containing all the nodes in `nodes` are returned. The order of
132 cliques is arbitrary.
134 Raises
135 ------
136 ValueError
137 If `nodes` is not a clique.
139 Examples
140 --------
141 >>> from pprint import pprint # For nice dict formatting
142 >>> G = nx.karate_club_graph()
143 >>> sum(1 for c in nx.find_cliques(G)) # The number of maximal cliques in G
144 36
145 >>> max(nx.find_cliques(G), key=len) # The largest maximal clique in G
146 [0, 1, 2, 3, 13]
148 The size of the largest maximal clique is known as the *clique number* of
149 the graph, which can be found directly with:
151 >>> max(len(c) for c in nx.find_cliques(G))
152 5
154 One can also compute the number of maximal cliques in `G` that contain a given
155 node. The following produces a dictionary keyed by node whose
156 values are the number of maximal cliques in `G` that contain the node:
158 >>> pprint({n: sum(1 for c in nx.find_cliques(G) if n in c) for n in G})
159 {0: 13,
160 1: 6,
161 2: 7,
162 3: 3,
163 4: 2,
164 5: 3,
165 6: 3,
166 7: 1,
167 8: 3,
168 9: 2,
169 10: 2,
170 11: 1,
171 12: 1,
172 13: 2,
173 14: 1,
174 15: 1,
175 16: 1,
176 17: 1,
177 18: 1,
178 19: 2,
179 20: 1,
180 21: 1,
181 22: 1,
182 23: 3,
183 24: 2,
184 25: 2,
185 26: 1,
186 27: 3,
187 28: 2,
188 29: 2,
189 30: 2,
190 31: 4,
191 32: 9,
192 33: 14}
194 Or, similarly, the maximal cliques in `G` that contain a given node.
195 For example, the 4 maximal cliques that contain node 31:
197 >>> [c for c in nx.find_cliques(G) if 31 in c]
198 [[0, 31], [33, 32, 31], [33, 28, 31], [24, 25, 31]]
200 See Also
201 --------
202 find_cliques_recursive
203 A recursive version of the same algorithm.
205 Notes
206 -----
207 To obtain a list of all maximal cliques, use
208 `list(find_cliques(G))`. However, be aware that in the worst-case,
209 the length of this list can be exponential in the number of nodes in
210 the graph. This function avoids storing all cliques in memory by
211 only keeping current candidate node lists in memory during its search.
213 This implementation is based on the algorithm published by Bron and
214 Kerbosch (1973) [1]_, as adapted by Tomita, Tanaka and Takahashi
215 (2006) [2]_ and discussed in Cazals and Karande (2008) [3]_. It
216 essentially unrolls the recursion used in the references to avoid
217 issues of recursion stack depth (for a recursive implementation, see
218 :func:`find_cliques_recursive`).
220 This algorithm ignores self-loops and parallel edges, since cliques
221 are not conventionally defined with such edges.
223 References
224 ----------
225 .. [1] Bron, C. and Kerbosch, J.
226 "Algorithm 457: finding all cliques of an undirected graph".
227 *Communications of the ACM* 16, 9 (Sep. 1973), 575--577.
228 <http://portal.acm.org/citation.cfm?doid=362342.362367>
230 .. [2] Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi,
231 "The worst-case time complexity for generating all maximal
232 cliques and computational experiments",
233 *Theoretical Computer Science*, Volume 363, Issue 1,
234 Computing and Combinatorics,
235 10th Annual International Conference on
236 Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28--42
237 <https://doi.org/10.1016/j.tcs.2006.06.015>
239 .. [3] F. Cazals, C. Karande,
240 "A note on the problem of reporting maximal cliques",
241 *Theoretical Computer Science*,
242 Volume 407, Issues 1--3, 6 November 2008, Pages 564--568,
243 <https://doi.org/10.1016/j.tcs.2008.05.010>
245 """
246 if len(G) == 0:
247 return
249 adj = {u: {v for v in G[u] if v != u} for u in G}
251 # Initialize Q with the given nodes and subg, cand with their nbrs
252 Q = nodes[:] if nodes is not None else []
253 cand = set(G)
254 for node in Q:
255 if node not in cand:
256 raise ValueError(f"The given `nodes` {nodes} do not form a clique")
257 cand &= adj[node]
259 if not cand:
260 yield Q[:]
261 return
263 subg = cand.copy()
264 stack = []
265 Q.append(None)
267 u = max(subg, key=lambda u: len(cand & adj[u]))
268 ext_u = cand - adj[u]
270 try:
271 while True:
272 if ext_u:
273 q = ext_u.pop()
274 cand.remove(q)
275 Q[-1] = q
276 adj_q = adj[q]
277 subg_q = subg & adj_q
278 if not subg_q:
279 yield Q[:]
280 else:
281 cand_q = cand & adj_q
282 if cand_q:
283 stack.append((subg, cand, ext_u))
284 Q.append(None)
285 subg = subg_q
286 cand = cand_q
287 u = max(subg, key=lambda u: len(cand & adj[u]))
288 ext_u = cand - adj[u]
289 else:
290 Q.pop()
291 subg, cand, ext_u = stack.pop()
292 except IndexError:
293 pass
296# TODO Should this also be not implemented for directed graphs?
297@nx._dispatch
298def find_cliques_recursive(G, nodes=None):
299 """Returns all maximal cliques in a graph.
301 For each node *v*, a *maximal clique for v* is a largest complete
302 subgraph containing *v*. The largest maximal clique is sometimes
303 called the *maximum clique*.
305 This function returns an iterator over cliques, each of which is a
306 list of nodes. It is a recursive implementation, so may suffer from
307 recursion depth issues, but is included for pedagogical reasons.
308 For a non-recursive implementation, see :func:`find_cliques`.
310 This function accepts a list of `nodes` and only the maximal cliques
311 containing all of these `nodes` are returned. It can considerably speed up
312 the running time if some specific cliques are desired.
314 Parameters
315 ----------
316 G : NetworkX graph
318 nodes : list, optional (default=None)
319 If provided, only yield *maximal cliques* containing all nodes in `nodes`.
320 If `nodes` isn't a clique itself, a ValueError is raised.
322 Returns
323 -------
324 iterator
325 An iterator over maximal cliques, each of which is a list of
326 nodes in `G`. If `nodes` is provided, only the maximal cliques
327 containing all the nodes in `nodes` are yielded. The order of
328 cliques is arbitrary.
330 Raises
331 ------
332 ValueError
333 If `nodes` is not a clique.
335 See Also
336 --------
337 find_cliques
338 An iterative version of the same algorithm. See docstring for examples.
340 Notes
341 -----
342 To obtain a list of all maximal cliques, use
343 `list(find_cliques_recursive(G))`. However, be aware that in the
344 worst-case, the length of this list can be exponential in the number
345 of nodes in the graph. This function avoids storing all cliques in memory
346 by only keeping current candidate node lists in memory during its search.
348 This implementation is based on the algorithm published by Bron and
349 Kerbosch (1973) [1]_, as adapted by Tomita, Tanaka and Takahashi
350 (2006) [2]_ and discussed in Cazals and Karande (2008) [3]_. For a
351 non-recursive implementation, see :func:`find_cliques`.
353 This algorithm ignores self-loops and parallel edges, since cliques
354 are not conventionally defined with such edges.
356 References
357 ----------
358 .. [1] Bron, C. and Kerbosch, J.
359 "Algorithm 457: finding all cliques of an undirected graph".
360 *Communications of the ACM* 16, 9 (Sep. 1973), 575--577.
361 <http://portal.acm.org/citation.cfm?doid=362342.362367>
363 .. [2] Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi,
364 "The worst-case time complexity for generating all maximal
365 cliques and computational experiments",
366 *Theoretical Computer Science*, Volume 363, Issue 1,
367 Computing and Combinatorics,
368 10th Annual International Conference on
369 Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28--42
370 <https://doi.org/10.1016/j.tcs.2006.06.015>
372 .. [3] F. Cazals, C. Karande,
373 "A note on the problem of reporting maximal cliques",
374 *Theoretical Computer Science*,
375 Volume 407, Issues 1--3, 6 November 2008, Pages 564--568,
376 <https://doi.org/10.1016/j.tcs.2008.05.010>
378 """
379 if len(G) == 0:
380 return iter([])
382 adj = {u: {v for v in G[u] if v != u} for u in G}
384 # Initialize Q with the given nodes and subg, cand with their nbrs
385 Q = nodes[:] if nodes is not None else []
386 cand_init = set(G)
387 for node in Q:
388 if node not in cand_init:
389 raise ValueError(f"The given `nodes` {nodes} do not form a clique")
390 cand_init &= adj[node]
392 if not cand_init:
393 return iter([Q])
395 subg_init = cand_init.copy()
397 def expand(subg, cand):
398 u = max(subg, key=lambda u: len(cand & adj[u]))
399 for q in cand - adj[u]:
400 cand.remove(q)
401 Q.append(q)
402 adj_q = adj[q]
403 subg_q = subg & adj_q
404 if not subg_q:
405 yield Q[:]
406 else:
407 cand_q = cand & adj_q
408 if cand_q:
409 yield from expand(subg_q, cand_q)
410 Q.pop()
412 return expand(subg_init, cand_init)
415@nx._dispatch
416def make_max_clique_graph(G, create_using=None):
417 """Returns the maximal clique graph of the given graph.
419 The nodes of the maximal clique graph of `G` are the cliques of
420 `G` and an edge joins two cliques if the cliques are not disjoint.
422 Parameters
423 ----------
424 G : NetworkX graph
426 create_using : NetworkX graph constructor, optional (default=nx.Graph)
427 Graph type to create. If graph instance, then cleared before populated.
429 Returns
430 -------
431 NetworkX graph
432 A graph whose nodes are the cliques of `G` and whose edges
433 join two cliques if they are not disjoint.
435 Notes
436 -----
437 This function behaves like the following code::
439 import networkx as nx
440 G = nx.make_clique_bipartite(G)
441 cliques = [v for v in G.nodes() if G.nodes[v]['bipartite'] == 0]
442 G = nx.bipartite.projected_graph(G, cliques)
443 G = nx.relabel_nodes(G, {-v: v - 1 for v in G})
445 It should be faster, though, since it skips all the intermediate
446 steps.
448 """
449 if create_using is None:
450 B = G.__class__()
451 else:
452 B = nx.empty_graph(0, create_using)
453 cliques = list(enumerate(set(c) for c in find_cliques(G)))
454 # Add a numbered node for each clique.
455 B.add_nodes_from(i for i, c in cliques)
456 # Join cliques by an edge if they share a node.
457 clique_pairs = combinations(cliques, 2)
458 B.add_edges_from((i, j) for (i, c1), (j, c2) in clique_pairs if c1 & c2)
459 return B
462@nx._dispatch
463def make_clique_bipartite(G, fpos=None, create_using=None, name=None):
464 """Returns the bipartite clique graph corresponding to `G`.
466 In the returned bipartite graph, the "bottom" nodes are the nodes of
467 `G` and the "top" nodes represent the maximal cliques of `G`.
468 There is an edge from node *v* to clique *C* in the returned graph
469 if and only if *v* is an element of *C*.
471 Parameters
472 ----------
473 G : NetworkX graph
474 An undirected graph.
476 fpos : bool
477 If True or not None, the returned graph will have an
478 additional attribute, `pos`, a dictionary mapping node to
479 position in the Euclidean plane.
481 create_using : NetworkX graph constructor, optional (default=nx.Graph)
482 Graph type to create. If graph instance, then cleared before populated.
484 Returns
485 -------
486 NetworkX graph
487 A bipartite graph whose "bottom" set is the nodes of the graph
488 `G`, whose "top" set is the cliques of `G`, and whose edges
489 join nodes of `G` to the cliques that contain them.
491 The nodes of the graph `G` have the node attribute
492 'bipartite' set to 1 and the nodes representing cliques
493 have the node attribute 'bipartite' set to 0, as is the
494 convention for bipartite graphs in NetworkX.
496 """
497 B = nx.empty_graph(0, create_using)
498 B.clear()
499 # The "bottom" nodes in the bipartite graph are the nodes of the
500 # original graph, G.
501 B.add_nodes_from(G, bipartite=1)
502 for i, cl in enumerate(find_cliques(G)):
503 # The "top" nodes in the bipartite graph are the cliques. These
504 # nodes get negative numbers as labels.
505 name = -i - 1
506 B.add_node(name, bipartite=0)
507 B.add_edges_from((v, name) for v in cl)
508 return B
511@nx._dispatch
512def node_clique_number(G, nodes=None, cliques=None, separate_nodes=False):
513 """Returns the size of the largest maximal clique containing each given node.
515 Returns a single or list depending on input nodes.
516 An optional list of cliques can be input if already computed.
518 Parameters
519 ----------
520 G : NetworkX graph
521 An undirected graph.
523 cliques : list, optional (default=None)
524 A list of cliques, each of which is itself a list of nodes.
525 If not specified, the list of all cliques will be computed
526 using :func:`find_cliques`.
528 Returns
529 -------
530 int or dict
531 If `nodes` is a single node, returns the size of the
532 largest maximal clique in `G` containing that node.
533 Otherwise return a dict keyed by node to the size
534 of the largest maximal clique containing that node.
536 See Also
537 --------
538 find_cliques
539 find_cliques yields the maximal cliques of G.
540 It accepts a `nodes` argument which restricts consideration to
541 maximal cliques containing all the given `nodes`.
542 The search for the cliques is optimized for `nodes`.
543 """
544 if cliques is None:
545 if nodes is not None:
546 # Use ego_graph to decrease size of graph
547 # check for single node
548 if nodes in G:
549 return max(len(c) for c in find_cliques(nx.ego_graph(G, nodes)))
550 # handle multiple nodes
551 return {
552 n: max(len(c) for c in find_cliques(nx.ego_graph(G, n))) for n in nodes
553 }
555 # nodes is None--find all cliques
556 cliques = list(find_cliques(G))
558 # single node requested
559 if nodes in G:
560 return max(len(c) for c in cliques if nodes in c)
562 # multiple nodes requested
563 # preprocess all nodes (faster than one at a time for even 2 nodes)
564 size_for_n = defaultdict(int)
565 for c in cliques:
566 size_of_c = len(c)
567 for n in c:
568 if size_for_n[n] < size_of_c:
569 size_for_n[n] = size_of_c
570 if nodes is None:
571 return size_for_n
572 return {n: size_for_n[n] for n in nodes}
575def number_of_cliques(G, nodes=None, cliques=None):
576 """Returns the number of maximal cliques for each node.
578 Returns a single or list depending on input nodes.
579 Optional list of cliques can be input if already computed.
580 """
581 if cliques is None:
582 cliques = list(find_cliques(G))
584 if nodes is None:
585 nodes = list(G.nodes()) # none, get entire graph
587 if not isinstance(nodes, list): # check for a list
588 v = nodes
589 # assume it is a single value
590 numcliq = len([1 for c in cliques if v in c])
591 else:
592 numcliq = {}
593 for v in nodes:
594 numcliq[v] = len([1 for c in cliques if v in c])
595 return numcliq
598class MaxWeightClique:
599 """A class for the maximum weight clique algorithm.
601 This class is a helper for the `max_weight_clique` function. The class
602 should not normally be used directly.
604 Parameters
605 ----------
606 G : NetworkX graph
607 The undirected graph for which a maximum weight clique is sought
608 weight : string or None, optional (default='weight')
609 The node attribute that holds the integer value used as a weight.
610 If None, then each node has weight 1.
612 Attributes
613 ----------
614 G : NetworkX graph
615 The undirected graph for which a maximum weight clique is sought
616 node_weights: dict
617 The weight of each node
618 incumbent_nodes : list
619 The nodes of the incumbent clique (the best clique found so far)
620 incumbent_weight: int
621 The weight of the incumbent clique
622 """
624 def __init__(self, G, weight):
625 self.G = G
626 self.incumbent_nodes = []
627 self.incumbent_weight = 0
629 if weight is None:
630 self.node_weights = {v: 1 for v in G.nodes()}
631 else:
632 for v in G.nodes():
633 if weight not in G.nodes[v]:
634 errmsg = f"Node {v!r} does not have the requested weight field."
635 raise KeyError(errmsg)
636 if not isinstance(G.nodes[v][weight], int):
637 errmsg = f"The {weight!r} field of node {v!r} is not an integer."
638 raise ValueError(errmsg)
639 self.node_weights = {v: G.nodes[v][weight] for v in G.nodes()}
641 def update_incumbent_if_improved(self, C, C_weight):
642 """Update the incumbent if the node set C has greater weight.
644 C is assumed to be a clique.
645 """
646 if C_weight > self.incumbent_weight:
647 self.incumbent_nodes = C[:]
648 self.incumbent_weight = C_weight
650 def greedily_find_independent_set(self, P):
651 """Greedily find an independent set of nodes from a set of
652 nodes P."""
653 independent_set = []
654 P = P[:]
655 while P:
656 v = P[0]
657 independent_set.append(v)
658 P = [w for w in P if v != w and not self.G.has_edge(v, w)]
659 return independent_set
661 def find_branching_nodes(self, P, target):
662 """Find a set of nodes to branch on."""
663 residual_wt = {v: self.node_weights[v] for v in P}
664 total_wt = 0
665 P = P[:]
666 while P:
667 independent_set = self.greedily_find_independent_set(P)
668 min_wt_in_class = min(residual_wt[v] for v in independent_set)
669 total_wt += min_wt_in_class
670 if total_wt > target:
671 break
672 for v in independent_set:
673 residual_wt[v] -= min_wt_in_class
674 P = [v for v in P if residual_wt[v] != 0]
675 return P
677 def expand(self, C, C_weight, P):
678 """Look for the best clique that contains all the nodes in C and zero or
679 more of the nodes in P, backtracking if it can be shown that no such
680 clique has greater weight than the incumbent.
681 """
682 self.update_incumbent_if_improved(C, C_weight)
683 branching_nodes = self.find_branching_nodes(P, self.incumbent_weight - C_weight)
684 while branching_nodes:
685 v = branching_nodes.pop()
686 P.remove(v)
687 new_C = C + [v]
688 new_C_weight = C_weight + self.node_weights[v]
689 new_P = [w for w in P if self.G.has_edge(v, w)]
690 self.expand(new_C, new_C_weight, new_P)
692 def find_max_weight_clique(self):
693 """Find a maximum weight clique."""
694 # Sort nodes in reverse order of degree for speed
695 nodes = sorted(self.G.nodes(), key=lambda v: self.G.degree(v), reverse=True)
696 nodes = [v for v in nodes if self.node_weights[v] > 0]
697 self.expand([], 0, nodes)
700@not_implemented_for("directed")
701@nx._dispatch(node_attrs="weight")
702def max_weight_clique(G, weight="weight"):
703 """Find a maximum weight clique in G.
705 A *clique* in a graph is a set of nodes such that every two distinct nodes
706 are adjacent. The *weight* of a clique is the sum of the weights of its
707 nodes. A *maximum weight clique* of graph G is a clique C in G such that
708 no clique in G has weight greater than the weight of C.
710 Parameters
711 ----------
712 G : NetworkX graph
713 Undirected graph
714 weight : string or None, optional (default='weight')
715 The node attribute that holds the integer value used as a weight.
716 If None, then each node has weight 1.
718 Returns
719 -------
720 clique : list
721 the nodes of a maximum weight clique
722 weight : int
723 the weight of a maximum weight clique
725 Notes
726 -----
727 The implementation is recursive, and therefore it may run into recursion
728 depth issues if G contains a clique whose number of nodes is close to the
729 recursion depth limit.
731 At each search node, the algorithm greedily constructs a weighted
732 independent set cover of part of the graph in order to find a small set of
733 nodes on which to branch. The algorithm is very similar to the algorithm
734 of Tavares et al. [1]_, other than the fact that the NetworkX version does
735 not use bitsets. This style of algorithm for maximum weight clique (and
736 maximum weight independent set, which is the same problem but on the
737 complement graph) has a decades-long history. See Algorithm B of Warren
738 and Hicks [2]_ and the references in that paper.
740 References
741 ----------
742 .. [1] Tavares, W.A., Neto, M.B.C., Rodrigues, C.D., Michelon, P.: Um
743 algoritmo de branch and bound para o problema da clique máxima
744 ponderada. Proceedings of XLVII SBPO 1 (2015).
746 .. [2] Warren, Jeffrey S, Hicks, Illya V.: Combinatorial Branch-and-Bound
747 for the Maximum Weight Independent Set Problem. Technical Report,
748 Texas A&M University (2016).
749 """
751 mwc = MaxWeightClique(G, weight)
752 mwc.find_max_weight_clique()
753 return mwc.incumbent_nodes, mwc.incumbent_weight