Mercurial > repos > shellac > sam_consensus_v3
view 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 |
line wrap: on
line source
""" Ramsey numbers. """ import networkx as nx from ...utils import arbitrary_element __all__ = ["ramsey_R2"] def ramsey_R2(G): r"""Compute the largest clique and largest independent set in `G`. This can be used to estimate bounds for the 2-color Ramsey number `R(2;s,t)` for `G`. This is a recursive implementation which could run into trouble for large recursions. Note that self-loop edges are ignored. Parameters ---------- G : NetworkX graph Undirected graph Returns ------- max_pair : (set, set) tuple Maximum clique, Maximum independent set. """ if not G: return set(), set() node = arbitrary_element(G) nbrs = (nbr for nbr in nx.all_neighbors(G, node) if nbr != node) nnbrs = nx.non_neighbors(G, node) c_1, i_1 = ramsey_R2(G.subgraph(nbrs).copy()) c_2, i_2 = ramsey_R2(G.subgraph(nnbrs).copy()) c_1.add(node) i_2.add(node) # Choose the larger of the two cliques and the larger of the two # independent sets, according to cardinality. return max(c_1, c_2, key=len), max(i_1, i_2, key=len)