Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/ramsey.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Ramsey numbers. | |
3 """ | |
4 import networkx as nx | |
5 from ...utils import arbitrary_element | |
6 | |
7 __all__ = ["ramsey_R2"] | |
8 | |
9 | |
10 def ramsey_R2(G): | |
11 r"""Compute the largest clique and largest independent set in `G`. | |
12 | |
13 This can be used to estimate bounds for the 2-color | |
14 Ramsey number `R(2;s,t)` for `G`. | |
15 | |
16 This is a recursive implementation which could run into trouble | |
17 for large recursions. Note that self-loop edges are ignored. | |
18 | |
19 Parameters | |
20 ---------- | |
21 G : NetworkX graph | |
22 Undirected graph | |
23 | |
24 Returns | |
25 ------- | |
26 max_pair : (set, set) tuple | |
27 Maximum clique, Maximum independent set. | |
28 """ | |
29 if not G: | |
30 return set(), set() | |
31 | |
32 node = arbitrary_element(G) | |
33 nbrs = (nbr for nbr in nx.all_neighbors(G, node) if nbr != node) | |
34 nnbrs = nx.non_neighbors(G, node) | |
35 c_1, i_1 = ramsey_R2(G.subgraph(nbrs).copy()) | |
36 c_2, i_2 = ramsey_R2(G.subgraph(nnbrs).copy()) | |
37 | |
38 c_1.add(node) | |
39 i_2.add(node) | |
40 # Choose the larger of the two cliques and the larger of the two | |
41 # independent sets, according to cardinality. | |
42 return max(c_1, c_2, key=len), max(i_1, i_2, key=len) |