"""用于计算大型团和最大独立集的函数。"""
import networkx as nx
from networkx.algorithms.approximation import ramsey
from networkx.utils import not_implemented_for
__all__ = [
"clique_removal",
"max_clique",
"large_clique_size",
"maximum_independent_set",
]
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def maximum_independent_set(G):
"""返回一个近似最大独立集。
独立集或稳定集是图中的一个顶点集合，其中任意两个顶点都不相邻。也就是说，它是一个顶点集合 I，对于 I 中的任意两个顶点，它们之间没有边相连。等价地，图中的每条边在 I 中最多有一个端点。一个独立集的大小是它包含的顶点数 [1]。
最大独立集是给定图 G 中的一个最大独立集，其大小记为 $\alpha(G)$。寻找这样一个集合的问题被称为最大独立集问题，是一个 NP 难优化问题。因此，不太可能存在一个有效的算法来找到一个图的最大独立集。
独立集算法基于 [2]。
Parameters
----------
G : NetworkX 图
无向图
Returns
-------
iset : 集合
近似最大独立集
Examples
--------
>>> G = nx.path_graph(10)
>>> nx.approximation.maximum_independent_set(G)
{0, 2, 4, 6, 9}
Raises
------
NetworkXNotImplemented
如果图是有向的或是一个多重图。
Notes
-----
在最坏情况下找到 $O(|V|/(log|V|)^2)$ 的独立集近似。
References
----------
.. [1] `Wikipedia: 独立集
<https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_
.. [2] Boppana, R., & Halldórsson, M. M. (1992).
通过排除子图来近似最大独立集。
BIT 数值数学, 32(2), 180–196. Springer.
"""
iset, _ = clique_removal(G)
return iset
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def max_clique(G):
r"""寻找最大团
在最坏情况下，找到图的最大团/独立集的 $O(|V|/(log|V|)^2)$ 近似解。
Parameters
----------
G : NetworkX 图
无向图
Returns
-------
clique : 集合
图的近似最大团
Examples
--------
>>> G = nx.path_graph(10)
>>> nx.approximation.max_clique(G)
{8, 9}
Raises
------
NetworkXNotImplemented
如果图是有向的或多重图。
Notes
-----
无向图 G = (V, E) 中的团是顶点集的一个子集 `C \subseteq V` ，使得 C 中的每两个顶点之间都存在一条边。这等价于说由 C 诱导的子图是完全的（在某些情况下，术语“团”也可能指该子图）。
最大团是给定图中可能的最大团。图 G 的团数 `\omega(G)` 是 G 中最大团的顶点数。G 的交集数是覆盖 G 所有边的团的最小数量。
https://en.wikipedia.org/wiki/Maximum_clique
References
----------
.. [1] Boppana, R., & Halldórsson, M. M. (1992).
通过排除子图来近似最大独立集。
BIT Numerical Mathematics, 32(2), 180–196. Springer.
doi:10.1007/BF01994876
"""
# finding the maximum clique in a graph is equivalent to finding
# the independent set in the complementary graph
cgraph = nx.complement(G)
iset, _ = clique_removal(cgraph)
return iset
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def clique_removal(G):
r"""重复地从图中移除团。
结果得到一个 $O(|V|/(\log |V|)^2)$ 的最大团和独立集的近似解。返回找到的最大独立集以及找到的最大团。
Parameters
----------
G : NetworkX 图
无向图
Returns
-------
max_ind_cliques : (集合, 列表) 元组
最大独立集和最大团的列表（集合）的 2-元组。
Examples
--------
>>> G = nx.path_graph(10)
>>> nx.approximation.clique_removal(G)
({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])
Raises
------
NetworkXNotImplemented
如果图是有向的或是一个多重图。
References
----------
.. [1] Boppana, R., & Halldórsson, M. M. (1992).
通过排除子图来近似最大独立集。
BIT 数值数学, 32(2), 180–196. Springer.
"""
graph = G.copy()
c_i, i_i = ramsey.ramsey_R2(graph)
cliques = [c_i]
isets = [i_i]
while graph:
graph.remove_nodes_from(c_i)
c_i, i_i = ramsey.ramsey_R2(graph)
if c_i:
cliques.append(c_i)
if i_i:
isets.append(i_i)
# Determine the largest independent set as measured by cardinality.
maxiset = max(isets, key=len)
return maxiset, cliques
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def large_clique_size(G):
"""寻找图中的一个大型团的大小。
*团* 是图中节点的一个子集，其中每对节点都相邻。此函数是一种启发式方法，用于寻找图中一个大型团的大小。
Parameters
----------
G : NetworkX 图
Returns
-------
k: 整数
图中一个大型团的大小。
Examples
--------
>>> G = nx.path_graph(10)
>>> nx.approximation.large_clique_size(G)
2
Raises
------
NetworkXNotImplemented
如果图是有向的或是一个多重图。
Notes
-----
此实现来自 [1]。其最坏情况时间复杂度为 :math:`O(n d^2)` ，其中 *n* 是图中的节点数，*d* 是最大度数。
此函数是一种启发式方法，这意味着它在实践中可能表现良好，但对于返回的数字与图中实际最大团大小之间的比率，没有严格的数学保证。
References
----------
.. [1] Pattabiraman, Bharath, 等。
"大规模图上最大团问题的快速算法及其在重叠社区检测中的应用。"
*Internet Mathematics* 11.4-5 (2015): 421--448.
<https://doi.org/10.1080/15427951.2014.986778>
See Also
--------
:func:`networkx.algorithms.approximation.clique.max_clique`
返回具有近似比率保证的近似最大团的函数。
:mod:`networkx.algorithms.clique`
用于在图中寻找精确最大团的功能。
"""
degrees = G.degree
def _clique_heuristic(G, U, size, best_size):
if not U:
return max(best_size, size)
u = max(U, key=degrees)
U.remove(u)
N_prime = {v for v in G[u] if degrees[v] >= best_size}
return _clique_heuristic(G, U & N_prime, size + 1, best_size)
best_size = 0
nodes = (u for u in G if degrees[u] >= best_size)
for u in nodes:
neighbors = {v for v in G[u] if degrees[v] >= best_size}
best_size = _clique_heuristic(G, neighbors, 1, best_size)
return best_size
