"""与图覆盖相关的函数。"""
from functools import partial
from itertools import chain
import networkx as nx
from networkx.utils import arbitrary_element, not_implemented_for
__all__ = ["min_edge_cover", "is_edge_cover"]
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def min_edge_cover(G, matching_algorithm=None):
"""返回图的最小基数边覆盖，以边集合的形式表示。
通过找到一个最大匹配并贪婪地扩展它以覆盖所有节点，可以在多项式时间内找到最小的边覆盖。此函数遵循该过程。可以为算法的第一个步骤指定一个最大匹配算法。结果集可能返回每个边的一个2元组（通常情况），或者对于每个边返回两个2元组 `(u, v)` 和 `(v, u)` 。后者仅在指定了二分匹配算法时才会执行。
Parameters
----------
G : NetworkX图
一个无向图。
matching_algorithm : 函数
一个返回 `G` 的最大基数匹配的函数。该函数必须接受一个输入，即图 `G` ，并返回一个边集合（仅包含节点对的一个方向）或一个将每个节点映射到其匹配节点的字典。如果未指定，则使用 :func:`~networkx.algorithms.matching.max_weight_matching` 。常见的二分匹配函数包括 :func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching` 或 :func:`~networkx.algorithms.bipartite.matching.eppstein_matching` 。
Returns
-------
min_cover : 集合
一个包含最小边覆盖中边的集合，以元组形式表示。它仅包含每个边的等效2元组 `(u, v)` 和 `(v, u)` 中的一个。如果使用二分方法计算匹配，则返回的集合包含每个边的最小边覆盖的两个2元组 `(u, v)` 和 `(v, u)` 。
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> sorted(nx.min_edge_cover(G))
[(2, 1), (3, 0)]
Notes
-----
图的边覆盖是一个边集合，使得图的每个节点至少与集合中的一条边相关联。最小边覆盖是具有最小基数的边覆盖。
由于其实现方式，此算法的 worst-case 运行时间受限于 ``matching_algorithm`` 函数的 worst-case 运行时间。
`G` 的最小边覆盖也可以使用 :mod:`networkx.algorithms.bipartite.covering` 模块中的 `min_edge_covering` 函数找到，该函数仅是此函数，默认匹配算法为 :func:`~networkx.algorithms.bipartite.matching.hopcraft_karp_matching` 。
"""
if len(G) == 0:
return set()
if nx.number_of_isolates(G) > 0:
# ``min_cover`` does not exist as there is an isolated node
raise nx.NetworkXException(
"Graph has a node with no edge incident on it, so no edge cover exists."
)
if matching_algorithm is None:
matching_algorithm = partial(nx.max_weight_matching, maxcardinality=True)
maximum_matching = matching_algorithm(G)
# ``min_cover`` is superset of ``maximum_matching``
try:
# bipartite matching algs return dict so convert if needed
min_cover = set(maximum_matching.items())
bipartite_cover = True
except AttributeError:
min_cover = maximum_matching
bipartite_cover = False
# iterate for uncovered nodes
uncovered_nodes = set(G) - {v for u, v in min_cover} - {u for u, v in min_cover}
for v in uncovered_nodes:
# Since `v` is uncovered, each edge incident to `v` will join it
# with a covered node (otherwise, if there were an edge joining
# uncovered nodes `u` and `v`, the maximum matching algorithm
# would have found it), so we can choose an arbitrary edge
# incident to `v`. (This applies only in a simple graph, not a
# multigraph.)
u = arbitrary_element(G[v])
min_cover.add((u, v))
if bipartite_cover:
min_cover.add((v, u))
return min_cover
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def is_edge_cover(G, cover):
"""确定一组边是否是图的有效边覆盖。
给定一组边，我们可以通过检查图的所有节点是否都有来自该集合的边与之相邻来确定它是否是边覆盖。
Parameters
----------
G : NetworkX 图
一个无向二分图。
cover : 集合
待检查的边集合。
Returns
-------
bool
该组边是否是图的有效边覆盖。
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> cover = {(2, 1), (3, 0)}
>>> nx.is_edge_cover(G, cover)
True
Notes
-----
图的边覆盖是一个边集合，使得图的每个节点都至少与集合中的一条边相邻。
"""
return set(G) <= set(chain.from_iterable(cover))
