Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/ramsey.py: 44%

1""" 

2Ramsey numbers. 

3""" 

4import networkx as nx 

5from networkx.utils import not_implemented_for 

6 

7from ...utils import arbitrary_element 

8 

9__all__ = ["ramsey_R2"] 

10 

11 

12@not_implemented_for("directed") 

13@not_implemented_for("multigraph") 

14@nx._dispatch 

15def ramsey_R2(G): 

16 r"""Compute the largest clique and largest independent set in `G`. 

17 

18 This can be used to estimate bounds for the 2-color 

19 Ramsey number `R(2;s,t)` for `G`. 

20 

21 This is a recursive implementation which could run into trouble 

22 for large recursions. Note that self-loop edges are ignored. 

23 

24 Parameters 

25 ---------- 

26 G : NetworkX graph 

27 Undirected graph 

28 

29 Returns 

30 ------- 

31 max_pair : (set, set) tuple 

32 Maximum clique, Maximum independent set. 

33 

34 Raises 

35 ------ 

36 NetworkXNotImplemented 

37 If the graph is directed or is a multigraph. 

38 """ 

39 if not G: 

40 return set(), set() 

41 

42 node = arbitrary_element(G) 

43 nbrs = (nbr for nbr in nx.all_neighbors(G, node) if nbr != node) 

44 nnbrs = nx.non_neighbors(G, node) 

45 c_1, i_1 = ramsey_R2(G.subgraph(nbrs).copy()) 

46 c_2, i_2 = ramsey_R2(G.subgraph(nnbrs).copy()) 

47 

48 c_1.add(node) 

49 i_2.add(node) 

50 # Choose the larger of the two cliques and the larger of the two 

51 # independent sets, according to cardinality. 

52 return max(c_1, c_2, key=len), max(i_1, i_2, key=len)