"""
算法用于寻找 k-边增广
k-边增广是一组边，一旦添加到图中，就能确保图是 k-边连通的；即除非移除 k 条或更多边，否则图不会断开连接。通常，目标是找到具有最小权重的增广。一般来说，不能保证存在 k-边增广。
See Also
--------
:mod:`edge_kcomponents` : 用于寻找 k-边连通分量的算法
:mod:`connectivity` : 用于确定边连通性的算法
"""
import itertools as it
import math
from collections import defaultdict, namedtuple
import networkx as nx
from networkx.utils import not_implemented_for, py_random_state
__all__ = ["k_edge_augmentation", "is_k_edge_connected", "is_locally_k_edge_connected"]
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def is_k_edge_connected(G, k):
"""测试一个图是否为k边连通图。
是否不可能通过移除少于k条边来断开图？
如果是，那么G是k边连通图。
Parameters
----------
G : NetworkX图
一个无向图。
k : 整数
要测试的边连通性
Returns
-------
布尔值
如果G是k边连通图，则返回True。
See Also
--------
:func:`is_locally_k_edge_connected`
Examples
--------
>>> G = nx.barbell_graph(10, 0)
>>> nx.is_k_edge_connected(G, k=1)
True
>>> nx.is_k_edge_connected(G, k=2)
False
"""
if k < 1:
raise ValueError(f"k must be positive, not {k}")
# First try to quickly determine if G is not k-edge-connected
if G.number_of_nodes() < k + 1:
return False
elif any(d < k for n, d in G.degree()):
return False
else:
# Otherwise perform the full check
if k == 1:
return nx.is_connected(G)
elif k == 2:
return nx.is_connected(G) and not nx.has_bridges(G)
else:
return nx.edge_connectivity(G, cutoff=k) >= k
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def is_locally_k_edge_connected(G, s, t, k):
"""测试图中的一个边是否是局部k边连通的。
是否不可能通过移除少于k条边来断开s和t？
如果是，那么s和t在G中是局部k边连通的。
Parameters
----------
G : NetworkX图
一个无向图。
s : 节点
源节点
t : 节点
目标节点
k : 整数
s和t节点的局部边连通性
Returns
-------
布尔值
如果s和t在G中是局部k边连通的，则返回True。
See Also
--------
:func:`is_k_edge_connected`
Examples
--------
>>> from networkx.algorithms.connectivity import is_locally_k_edge_connected
>>> G = nx.barbell_graph(10, 0)
>>> is_locally_k_edge_connected(G, 5, 15, k=1)
True
>>> is_locally_k_edge_connected(G, 5, 15, k=2)
False
>>> is_locally_k_edge_connected(G, 1, 5, k=2)
True
"""
if k < 1:
raise ValueError(f"k must be positive, not {k}")
# First try to quickly determine s, t is not k-locally-edge-connected in G
if G.degree(s) < k or G.degree(t) < k:
return False
else:
# Otherwise perform the full check
if k == 1:
return nx.has_path(G, s, t)
else:
localk = nx.connectivity.local_edge_connectivity(G, s, t, cutoff=k)
return localk >= k
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def k_edge_augmentation(G, k, avail=None, weight=None, partial=False):
"""查找使G成为k边连通图的一组边。
向G中添加这些增广边后，除非移除k条或更多边，否则无法断开G。此函数使用最有效的可用函数（取决于k值以及问题是否加权）来搜索可用边的最小权重子集，以使G成为k边连通图。一般来说，寻找k边增广问题是NP难的，因此不能保证解是最小的。此外，可能不存在k边增广。
Parameters
----------
G : NetworkX图
一个无向图。
k : 整数
期望的边连通度
avail : 字典或2或3元组集合
可用于增广的边。
如果未指定，则G的补图中的所有边都可用。否则，每个项是一条可用边（可选带权重）。
在无权重情况下，每个项是一条边 ``(u, v)`` 。
在加权情况下，每个项是一个3元组 ``(u, v, d)`` 或一个字典，键值对为 ``(u, v): d`` 。第三个项 ``d`` 可以是一个字典或一个实数。如果 ``d`` 是一个字典， ``d[weight]`` 对应于权重。
weight : 字符串
如果 ``avail`` 是一个包含字典的3元组集合，用于查找权重的键。
partial : 布尔值
如果partial为True且不存在可行的k边增广，则生成一个部分k边增广。将部分增广中的边添加到G中，最小化k边连通分量的数量，并最大化这些分量之间的边连通度。详细信息请参阅:func:`partial_k_edge_augmentation` 。
Yields
------
edge : 元组
一旦添加到G中，将使G成为k边连通的边。如果partial为False且无法实现，则会引发错误。否则，生成的边形成一个部分增广，尽可能地k边连通G的任何部分，并最大限度地连接剩余部分。
Raises
------
NetworkXUnfeasible
如果partial为False且不存在k边增广。
NetworkXNotImplemented
如果输入图是有向图或多重图。
ValueError:
如果k小于1
Notes
-----
当k=1时，返回一个最优解。
当k=2且 ``avail`` 为None时，返回一个最优解。否则当k=2时，返回一个最优解的2近似。
对于k>3，此问题是NP难的，使用随机算法生成一个可行解，但不保证解的权重。
Examples
--------
>>> # 无权重情况
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> sorted(nx.k_edge_augmentation(G, k=1))
[(1, 5)]
>>> sorted(nx.k_edge_augmentation(G, k=2))
[(1, 5), (5, 4)]
>>> sorted(nx.k_edge_augmentation(G, k=3))
[(1, 4), (1, 5), (2, 5), (3, 5), (4, 5)]
>>> complement = list(nx.k_edge_augmentation(G, k=5, partial=True))
>>> G.add_edges_from(complement)
>>> nx.edge_connectivity(G)
4
>>> # 加权情况
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> # avail可以是一个包含字典的元组
>>> avail = [(1, 5, {"weight": 11}), (2, 5, {"weight": 10})]
>>> sorted(nx.k_edge_augmentation(G, k=1, avail=avail, weight="weight"))
[(2, 5)]
>>> # 或者avail可以是一个包含实数的3元组
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # 或者avail可以是一个字典
>>> avail = {(1, 5): 11, (2, 5): 10, (4, 3): 1, (4, 5): 51}
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # 如果增广不可行，则可以找到一个部分解
>>> avail = {(1, 5): 11}
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True))
[(1, 5)]
"""
try:
if k <= 0:
raise ValueError(f"k must be a positive integer, not {k}")
elif G.number_of_nodes() < k + 1:
msg = f"impossible to {k} connect in graph with less than {k + 1} nodes"
raise nx.NetworkXUnfeasible(msg)
elif avail is not None and len(avail) == 0:
if not nx.is_k_edge_connected(G, k):
raise nx.NetworkXUnfeasible("no available edges")
aug_edges = []
elif k == 1:
aug_edges = one_edge_augmentation(
G, avail=avail, weight=weight, partial=partial
)
elif k == 2:
aug_edges = bridge_augmentation(G, avail=avail, weight=weight)
else:
# raise NotImplementedError(f'not implemented for k>2. k={k}')
aug_edges = greedy_k_edge_augmentation(
G, k=k, avail=avail, weight=weight, seed=0
)
# Do eager evaluation so we can catch any exceptions
# Before executing partial code.
yield from list(aug_edges)
except nx.NetworkXUnfeasible:
if partial:
# Return all available edges
if avail is None:
aug_edges = complement_edges(G)
else:
# If we can't k-edge-connect the entire graph, try to
# k-edge-connect as much as possible
aug_edges = partial_k_edge_augmentation(
G, k=k, avail=avail, weight=weight
)
yield from aug_edges
else:
raise
@nx._dispatchable
def partial_k_edge_augmentation(G, k, avail, weight=None):
"""找到能够尽可能多地k边连接图的增强。
当无法实现k边增强时，我们仍然可以尝试找到一组小的边，尽可能多地部分k边连接图。在剩余部分之间生成所有可能的边。这最小化了结果图中k边连通子图的数量，并最大化这些子图之间的边连通性。
Parameters
----------
G : NetworkX图
一个无向图。
k : 整数
期望的边连通性
avail : 字典或2或3元组的集合
更多详情，请参阅 :func:`k_edge_augmentation` 。
weight : 字符串
如果 ``avail`` 是3元组的集合，用于查找权重的键。
更多详情，请参阅 :func:`k_edge_augmentation` 。
Yields
------
edge : 元组
部分增强G中的边。这些边k边连接G中任何可能的部分，并最大限度地连接剩余部分。换句话说，生成avail中的所有边，除了那些已经在k边连通子图中的边。
Notes
-----
构建H，用avail中的所有边增强G。
找到H的k边子图。
对于每个k边子图，如果节点数大于k，则找到该图的k边增强并将其添加到解决方案中。然后在k边子图之间添加avail中的所有边到解决方案中。
See Also
--------
:func:`k_edge_augmentation`
Examples
--------
>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> G.add_node(8)
>>> avail = [(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (1, 8)]
>>> sorted(partial_k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (1, 8)]
"""
def _edges_between_disjoint(H, only1, only2):
"""找到不相交节点之间的边缘"""
only1_adj = {u: set(H.adj[u]) for u in only1}
for u, neighbs in only1_adj.items():
# Find the neighbors of u in only1 that are also in only2
neighbs12 = neighbs.intersection(only2)
for v in neighbs12:
yield (u, v)
avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G)
# Find which parts of the graph can be k-edge-connected
H = G.copy()
H.add_edges_from(
(
(u, v, {"weight": w, "generator": (u, v)})
for (u, v), w in zip(avail, avail_w)
)
)
k_edge_subgraphs = list(nx.k_edge_subgraphs(H, k=k))
# Generate edges to k-edge-connect internal subgraphs
for nodes in k_edge_subgraphs:
if len(nodes) > 1:
# Get the k-edge-connected subgraph
C = H.subgraph(nodes).copy()
# Find the internal edges that were available
sub_avail = {
d["generator"]: d["weight"]
for (u, v, d) in C.edges(data=True)
if "generator" in d
}
# Remove potential augmenting edges
C.remove_edges_from(sub_avail.keys())
# Find a subset of these edges that makes the component
# k-edge-connected and ignore the rest
yield from nx.k_edge_augmentation(C, k=k, avail=sub_avail)
# Generate all edges between CCs that could not be k-edge-connected
for cc1, cc2 in it.combinations(k_edge_subgraphs, 2):
for u, v in _edges_between_disjoint(H, cc1, cc2):
d = H.get_edge_data(u, v)
edge = d.get("generator", None)
if edge is not None:
yield edge
@not_implemented_for("multigraph")
@not_implemented_for("directed")
@nx._dispatchable
def one_edge_augmentation(G, avail=None, weight=None, partial=False):
"""找到连接图G的最小权重边集。
等价于当k=1时的 :func:`k_edge_augmentation` 。将结果边添加到G中将使其成为1-边连通的。该解决方案对加权和非加权变体都是最优的。
Parameters
----------
G : NetworkX图
一个无向图。
avail : 字典或2或3元组集合
更多详情，参见 :func:`k_edge_augmentation` 。
weight : 字符串
如果 ``avail`` 是3元组集合，用于查找权重的键。
更多详情，参见 :func:`k_edge_augmentation` 。
partial : 布尔值
如果partial为True且不存在可行的k-边增广，则增广边最小化连通分量的数量。
Yields
------
edge : 元组
G的1-增广中的边
Raises
------
NetworkXUnfeasible
如果partial为False且不存在1-边增广。
Notes
-----
根据是否指定 ``avail`` ，使用 :func:`unconstrained_one_edge_augmentation` 或 :func:`weighted_one_edge_augmentation` 。两种算法都基于寻找最小生成树。因此，两种算法都找到最优解并在线性时间内运行。
See Also
--------
:func:`k_edge_augmentation`
"""
if avail is None:
return unconstrained_one_edge_augmentation(G)
else:
return weighted_one_edge_augmentation(
G, avail=avail, weight=weight, partial=partial
)
@not_implemented_for("multigraph")
@not_implemented_for("directed")
@nx._dispatchable
def bridge_augmentation(G, avail=None, weight=None):
"""找到一组连接G的桥接边。
等价于当k=2且partial=False时的:func:`k_edge_augmentation` 。将结果边添加到G中将使其成为2边连通的。如果没有指定约束条件，返回的边集是最小且最优的，否则解决方案是近似的。
Parameters
----------
G : NetworkX图
一个无向图。
avail : 字典或一组2或3元组
更多详情，参见:func:`k_edge_augmentation` 。
weight : 字符串
如果 ``avail`` 是一组3元组，用于查找权重的键。
更多详情，参见:func:`k_edge_augmentation` 。
Yields
------
edge : 元组
G的桥接增强中的边
Raises
------
NetworkXUnfeasible
如果不存在桥接增强。
Notes
-----
如果没有约束条件，可以使用:func:`unconstrained_bridge_augmentation` 在
线性时间内计算解决方案。否则，问题变为NP-hard，解决方案由
:func:`weighted_bridge_augmentation` 近似计算。
See Also
--------
:func:`k_edge_augmentation`
"""
if G.number_of_nodes() < 3:
raise nx.NetworkXUnfeasible("impossible to bridge connect less than 3 nodes")
if avail is None:
return unconstrained_bridge_augmentation(G)
else:
return weighted_bridge_augmentation(G, avail, weight=weight)
# --- Algorithms and Helpers ---
def _ordered(u, v):
"""返回无向边中的节点，按下三角顺序排列"""
return (u, v) if u < v else (v, u)
def _unpack_available_edges(avail, weight=None, G=None):
"""辅助函数，用于将可用边及其对应权重分离"""
if weight is None:
weight = "weight"
if isinstance(avail, dict):
avail_uv = list(avail.keys())
avail_w = list(avail.values())
else:
def _try_getitem(d):
try:
return d[weight]
except TypeError:
return d
avail_uv = [tup[0:2] for tup in avail]
avail_w = [1 if len(tup) == 2 else _try_getitem(tup[-1]) for tup in avail]
if G is not None:
# Edges already in the graph are filtered
flags = [not G.has_edge(u, v) for u, v in avail_uv]
avail_uv = list(it.compress(avail_uv, flags))
avail_w = list(it.compress(avail_w, flags))
return avail_uv, avail_w
MetaEdge = namedtuple("MetaEdge", ("meta_uv", "uv", "w"))
def _lightest_meta_edges(mapping, avail_uv, avail_w):
"""将原始图中的可用边映射到元图中的边。
Parameters
----------
mapping : dict
由 :func:`collapse` 生成的映射，将原始图中的每个节点映射到元图中的一个节点
avail_uv : list
边列表
avail_w : list
边权重列表
Notes
-----
元图中的每个节点是原始图中的一个 k-边连通分量。我们不关心同一 k-边连通分量内的任何边，因此忽略自环边。我们还只对连接每个 k-边连通分量的最小权重边感兴趣，因此我们按元边分组并取每组中最轻的边。
Examples
--------
>>> # 每个组代表一个元节点
>>> groups = ([1, 2, 3], [4, 5], [6])
>>> mapping = {n: meta_n for meta_n, ns in enumerate(groups) for n in ns}
>>> avail_uv = [(1, 2), (3, 6), (1, 4), (5, 2), (6, 1), (2, 6), (3, 1)]
>>> avail_w = [20, 99, 20, 15, 50, 99, 20]
>>> sorted(_lightest_meta_edges(mapping, avail_uv, avail_w))
[MetaEdge(meta_uv=(0, 1), uv=(5, 2), w=15), MetaEdge(meta_uv=(0, 2), uv=(6, 1), w=50)]
"""
grouped_wuv = defaultdict(list)
for w, (u, v) in zip(avail_w, avail_uv):
# Order the meta-edge so it can be used as a dict key
meta_uv = _ordered(mapping[u], mapping[v])
# Group each available edge using the meta-edge as a key
grouped_wuv[meta_uv].append((w, u, v))
# Now that all available edges are grouped, choose one per group
for (mu, mv), choices_wuv in grouped_wuv.items():
# Ignore available edges within the same meta-node
if mu != mv:
# Choose the lightest available edge belonging to each meta-edge
w, u, v = min(choices_wuv)
yield MetaEdge((mu, mv), (u, v), w)
@nx._dispatchable
def unconstrained_one_edge_augmentation(G):
"""找到连接G的最小边集。
这是无权最小生成树问题的一个变种。
如果G不为空，总是存在一个可行解。
Parameters
----------
G : NetworkX图
一个无向图。
Yields
------
edge : 元组
G的一边增广中的边
See Also
--------
:func:`one_edge_augmentation`
:func:`k_edge_augmentation`
Examples
--------
>>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
>>> G.add_nodes_from([6, 7, 8])
>>> sorted(unconstrained_one_edge_augmentation(G))
[(1, 4), (4, 6), (6, 7), (7, 8)]
"""
ccs1 = list(nx.connected_components(G))
C = collapse(G, ccs1)
# When we are not constrained, we can just make a meta graph tree.
meta_nodes = list(C.nodes())
# build a path in the metagraph
meta_aug = list(zip(meta_nodes, meta_nodes[1:]))
# map that path to the original graph
inverse = defaultdict(list)
for k, v in C.graph["mapping"].items():
inverse[v].append(k)
for mu, mv in meta_aug:
yield (inverse[mu][0], inverse[mv][0])
@nx._dispatchable
def weighted_one_edge_augmentation(G, avail, weight=None, partial=False):
"""找到连接图G的最小权重边集（如果存在）。
这是加权最小生成树问题的一个变种。
Parameters
----------
G : NetworkX图
一个无向图。
avail : 字典或2或3元组集合
更多细节请参见 :func:`k_edge_augmentation` 。
weight : 字符串
如果 ``avail`` 是3元组集合，用于查找权重的键。
更多细节请参见 :func:`k_edge_augmentation` 。
partial : 布尔值
如果partial为True且不存在可行的k边增强，则增强边最小化连通分量的数量。
Yields
------
edge : 元组
选自avail的用于连接G的边子集中的边。
See Also
--------
:func:`one_edge_augmentation`
:func:`k_edge_augmentation`
Examples
--------
>>> G = nx.Graph([(1, 2), (2, 3), (4, 5)])
>>> G.add_nodes_from([6, 7, 8])
>>> # 不在avail中的边隐含权重为无穷大
>>> avail = [(1, 3), (1, 5), (4, 7), (4, 8), (6, 1), (8, 1), (8, 2)]
>>> sorted(weighted_one_edge_augmentation(G, avail))
[(1, 5), (4, 7), (6, 1), (8, 1)]
>>> # 通过给前一个解决方案中的边赋予大权重来找到另一个解决方案（注意必须使用一些旧边）
>>> avail = [(1, 3), (1, 5, 99), (4, 7, 9), (6, 1, 99), (8, 1, 99), (8, 2)]
>>> sorted(weighted_one_edge_augmentation(G, avail))
[(1, 5), (4, 7), (6, 1), (8, 2)]
"""
avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G)
# Collapse CCs in the original graph into nodes in a metagraph
# Then find an MST of the metagraph instead of the original graph
C = collapse(G, nx.connected_components(G))
mapping = C.graph["mapping"]
# Assign each available edge to an edge in the metagraph
candidate_mapping = _lightest_meta_edges(mapping, avail_uv, avail_w)
# nx.set_edge_attributes(C, name='weight', values=0)
C.add_edges_from(
(mu, mv, {"weight": w, "generator": uv})
for (mu, mv), uv, w in candidate_mapping
)
# Find MST of the meta graph
meta_mst = nx.minimum_spanning_tree(C)
if not partial and not nx.is_connected(meta_mst):
raise nx.NetworkXUnfeasible("Not possible to connect G with available edges")
# Yield the edge that generated the meta-edge
for mu, mv, d in meta_mst.edges(data=True):
if "generator" in d:
edge = d["generator"]
yield edge
@nx._dispatchable
def unconstrained_bridge_augmentation(G):
"""找到使用最少边的G的最优2边增广。
这是[1]中详细算法的实现。基本思想是构建桥连通分量的元图，连接树的叶节点以连接整个图，最后按深度优先搜索前序连接树的叶节点以桥接整个图。
Parameters
----------
G : NetworkX图
一个无向图。
Yields
------
edge : 元组
G的桥增广中的边
Notes
-----
输入：一个图G。
首先找到G的桥连通分量并将每个桥连通分量折叠成元图C的一个节点，C保证是一片树的森林。
C包含p个“叶节点”——恰好有一条入边的节点。
C包含q个“孤立节点”——没有入边的节点。
定理：如果p + q > 1，则至少需要 :math:`ceil(p / 2) + q` 条边来桥接C。该算法实现了这个最小数量。
该方法首先添加足够的边使G变成一棵树，然后简单地配对叶节点。
设n为C中树的数量。设v(i)为第i棵树中的一个孤立顶点（如果存在），否则为第i棵树中的一对不同叶节点。从这些集合中交替添加边（例如，添加边A1 = [(v(i)[0], v(i + 1)[1]), v(i + 1)[0], v(i + 2)[1])...])将C连接成一棵树T。这棵树有p' = p + 2q - 2(n -1)个叶节点且没有孤立顶点。A1有n - 1条边。下一步找到ceil(p' / 2)条边来双连通任何有p'个叶节点的树。
通过选择一个度数 >= 2 的任意根节点并将所有边指向远离根的方向，将T转换为树状图T'。注意实现隐式构造了T'。
T的叶节点是T'中没有现有边的节点。
按深度优先搜索前序对T'的叶节点进行排序。然后将这个列表分成两半并添加拉链对到A2。
集合A = A1 + A2是元图中的最小增广。
将其转换为原始图中的边
References
----------
.. [1] Eswaran, Kapali P., and R. Endre Tarjan. (1975) Augmentation problems.
http://epubs.siam.org/doi/abs/10.1137/0205044
See Also
--------
:func:`bridge_augmentation`
:func:`k_edge_augmentation`
Examples
--------
>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> sorted(unconstrained_bridge_augmentation(G))
[(1, 7)]
>>> G = nx.path_graph((1, 2, 3, 2, 4, 5, 6, 7))
>>> sorted(unconstrained_bridge_augmentation(G))
[(1, 3), (3, 7)]
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
>>> G.add_node(4)
>>> sorted(unconstrained_bridge_augmentation(G))
[(1, 4), (4, 0)]
"""
# -----
# Mapping of terms from (Eswaran and Tarjan):
# G = G_0 - the input graph
# C = G_0' - the bridge condensation of G. (This is a forest of trees)
# A1 = A_1 - the edges to connect the forest into a tree
# leaf = pendant - a node with degree of 1
# alpha(v) = maps the node v in G to its meta-node in C
# beta(x) = maps the meta-node x in C to any node in the bridge
# component of G corresponding to x.
# find the 2-edge-connected components of G
bridge_ccs = list(nx.connectivity.bridge_components(G))
# condense G into an forest C
C = collapse(G, bridge_ccs)
# Choose pairs of distinct leaf nodes in each tree. If this is not
# possible then make a pair using the single isolated node in the tree.
vset1 = [
tuple(cc) * 2 # case1: an isolated node
if len(cc) == 1
else sorted(cc, key=C.degree)[0:2] # case2: pair of leaf nodes
for cc in nx.connected_components(C)
]
if len(vset1) > 1:
# Use this set to construct edges that connect C into a tree.
nodes1 = [vs[0] for vs in vset1]
nodes2 = [vs[1] for vs in vset1]
A1 = list(zip(nodes1[1:], nodes2))
else:
A1 = []
# Connect each tree in the forest to construct an arborescence
T = C.copy()
T.add_edges_from(A1)
# If there are only two leaf nodes, we simply connect them.
leafs = [n for n, d in T.degree() if d == 1]
if len(leafs) == 1:
A2 = []
if len(leafs) == 2:
A2 = [tuple(leafs)]
else:
# Choose an arbitrary non-leaf root
try:
root = next(n for n, d in T.degree() if d > 1)
except StopIteration: # no nodes found with degree > 1
return
# order the leaves of C by (induced directed) preorder
v2 = [n for n in nx.dfs_preorder_nodes(T, root) if T.degree(n) == 1]
# connecting first half of the leafs in pre-order to the second
# half will bridge connect the tree with the fewest edges.
half = math.ceil(len(v2) / 2)
A2 = list(zip(v2[:half], v2[-half:]))
# collect the edges used to augment the original forest
aug_tree_edges = A1 + A2
# Construct the mapping (beta) from meta-nodes to regular nodes
inverse = defaultdict(list)
for k, v in C.graph["mapping"].items():
inverse[v].append(k)
# sort so we choose minimum degree nodes first
inverse = {
mu: sorted(mapped, key=lambda u: (G.degree(u), u))
for mu, mapped in inverse.items()
}
# For each meta-edge, map back to an arbitrary pair in the original graph
G2 = G.copy()
for mu, mv in aug_tree_edges:
# Find the first available edge that doesn't exist and return it
for u, v in it.product(inverse[mu], inverse[mv]):
if not G2.has_edge(u, v):
G2.add_edge(u, v)
yield u, v
break
@nx._dispatchable
def weighted_bridge_augmentation(G, avail, weight=None):
"""找到G的一个近似最小权重2边增广。
这是[1]中详细介绍的近似算法的实现。它从avail中选择一组边添加到G中，使其成为2边连通的（如果存在这样的子集）。这是通过找到一个特殊构造的元图的最小生成树来完成的。
Parameters
----------
G : NetworkX图
一个无向图。
avail : 2或3元组的集合
候选边（可选带权重）以供选择
weight : 字符串
如果avail是3元组的集合，其中每个元组的第三个项是字典，则使用此键来查找权重。
Yields
------
edge : 元组
avail中选择的子集中的边，用于桥接增广G。
Notes
-----
找到加权2边增广是NP难问题。
任何不在 ``avail`` 中的边都被认为具有无穷大的权重。
如果 ``G`` 是连通的，近似因子为2；如果不是，则为3。
运行时间为 :math:`O(m + n log(n))`
References
----------
.. [1] Khuller, Samir, and Ramakrishna Thurimella. (1993) Approximation
algorithms for graph augmentation.
http://www.sciencedirect.com/science/article/pii/S0196677483710102
See Also
--------
:func:`bridge_augmentation`
:func:`k_edge_augmentation`
Examples
--------
>>> G = nx.path_graph((1, 2, 3, 4))
>>> # 当权重相等时，(1, 4) 是最好的
>>> avail = [(1, 4, 1), (1, 3, 1), (2, 4, 1)]
>>> sorted(weighted_bridge_augmentation(G, avail))
[(1, 4)]
>>> # 给 (1, 4) 一个高权重使得两条边的解决方案成为最佳。
>>> avail = [(1, 4, 1000), (1, 3, 1), (2, 4, 1)]
>>> sorted(weighted_bridge_augmentation(G, avail))
[(1, 3), (2, 4)]
>>> # ------
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 1)]
>>> sorted(weighted_bridge_augmentation(G, avail=avail))
[(1, 5), (4, 5)]
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
>>> sorted(weighted_bridge_augmentation(G, avail=avail))
[(1, 5), (2, 5), (4, 5)]
"""
if weight is None:
weight = "weight"
# If input G is not connected the approximation factor increases to 3
if not nx.is_connected(G):
H = G.copy()
connectors = list(one_edge_augmentation(H, avail=avail, weight=weight))
H.add_edges_from(connectors)
yield from connectors
else:
connectors = []
H = G
if len(avail) == 0:
if nx.has_bridges(H):
raise nx.NetworkXUnfeasible("no augmentation possible")
avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=H)
# Collapse input into a metagraph. Meta nodes are bridge-ccs
bridge_ccs = nx.connectivity.bridge_components(H)
C = collapse(H, bridge_ccs)
# Use the meta graph to shrink avail to a small feasible subset
mapping = C.graph["mapping"]
# Choose the minimum weight feasible edge in each group
meta_to_wuv = {
(mu, mv): (w, uv)
for (mu, mv), uv, w in _lightest_meta_edges(mapping, avail_uv, avail_w)
}
# Mapping of terms from (Khuller and Thurimella):
# C : G_0 = (V, E^0)
# This is the metagraph where each node is a 2-edge-cc in G.
# The edges in C represent bridges in the original graph.
# (mu, mv) : E - E^0 # they group both avail and given edges in E
# T : \Gamma
# D : G^D = (V, E_D)
# The paper uses ancestor because children point to parents, which is
# contrary to networkx standards. So, we actually need to run
# nx.least_common_ancestor on the reversed Tree.
# Pick an arbitrary leaf from C as the root
try:
root = next(n for n, d in C.degree() if d == 1)
except StopIteration: # no nodes found with degree == 1
return
# Root C into a tree TR by directing all edges away from the root
# Note in their paper T directs edges towards the root
TR = nx.dfs_tree(C, root)
# Add to D the directed edges of T and set their weight to zero
# This indicates that it costs nothing to use edges that were given.
D = nx.reverse(TR).copy()
nx.set_edge_attributes(D, name="weight", values=0)
# The LCA of mu and mv in T is the shared ancestor of mu and mv that is
# located farthest from the root.
lca_gen = nx.tree_all_pairs_lowest_common_ancestor(
TR, root=root, pairs=meta_to_wuv.keys()
)
for (mu, mv), lca in lca_gen:
w, uv = meta_to_wuv[(mu, mv)]
if lca == mu:
# If u is an ancestor of v in TR, then add edge u->v to D
D.add_edge(lca, mv, weight=w, generator=uv)
elif lca == mv:
# If v is an ancestor of u in TR, then add edge v->u to D
D.add_edge(lca, mu, weight=w, generator=uv)
else:
# If neither u nor v is a ancestor of the other in TR
# let t = lca(TR, u, v) and add edges t->u and t->v
# Track the original edge that GENERATED these edges.
D.add_edge(lca, mu, weight=w, generator=uv)
D.add_edge(lca, mv, weight=w, generator=uv)
# Then compute a minimum rooted branching
try:
# Note the original edges must be directed towards to root for the
# branching to give us a bridge-augmentation.
A = _minimum_rooted_branching(D, root)
except nx.NetworkXException as err:
# If there is no branching then augmentation is not possible
raise nx.NetworkXUnfeasible("no 2-edge-augmentation possible") from err
# For each edge e, in the branching that did not belong to the directed
# tree T, add the corresponding edge that **GENERATED** it (this is not
# necessarily e itself!)
# ensure the third case does not generate edges twice
bridge_connectors = set()
for mu, mv in A.edges():
data = D.get_edge_data(mu, mv)
if "generator" in data:
# Add the avail edge that generated the branching edge.
edge = data["generator"]
bridge_connectors.add(edge)
yield from bridge_connectors
def _minimum_rooted_branching(D, root):
"""辅助函数，用于计算最小根分支（又称根树形图）
在计算分支之前，必须通过移除根的前驱节点使有向图成为根图。
根图G的分支/树形图是一个子图，包含从根到每个其他顶点的有向路径。它是最小生成树问题的有向图对应问题。
References
----------
[1] Khuller, Samir (2002) 高级算法讲义24笔记。
https://web.archive.org/web/20121030033722/https://www.cs.umd.edu/class/spring2011/cmsc651/lec07.pdf
"""
rooted = D.copy()
# root the graph by removing all predecessors to `root`.
rooted.remove_edges_from([(u, root) for u in D.predecessors(root)])
# Then compute the branching / arborescence.
A = nx.minimum_spanning_arborescence(rooted)
return A
@nx._dispatchable(returns_graph=True)
def collapse(G, grouped_nodes):
"""将每组节点折叠成一个单一节点。
这类似于凝聚，但适用于无向图。
Parameters
----------
G : NetworkX 图
grouped_nodes: 列表或生成器
要折叠的节点分组。分组必须是互斥的。
如果 grouped_nodes 是强连通分量，则这等效于 :func:`condensation` 。
Returns
-------
C : NetworkX 图
根据节点分组折叠的图 C。节点标签是分组列表中组件索引的整数。
C 具有名为 'mapping' 的图属性，该属性是一个字典，将原始节点映射到它们所属的 C 中的节点。
C 中的每个节点还具有一个节点属性 'members'，其中包含形成该节点所代表的组的原始节点集合。
Examples
--------
>>> # 使用互斥组折叠图，但不一定是连通的
>>> G = nx.Graph([(1, 0), (2, 3), (3, 1), (3, 4), (4, 5), (5, 6), (5, 7)])
>>> G.add_node("A")
>>> grouped_nodes = [{0, 1, 2, 3}, {5, 6, 7}]
>>> C = collapse(G, grouped_nodes)
>>> members = nx.get_node_attributes(C, "members")
>>> sorted(members.keys())
[0, 1, 2, 3]
>>> member_values = set(map(frozenset, members.values()))
>>> assert {0, 1, 2, 3} in member_values
>>> assert {4} in member_values
>>> assert {5, 6, 7} in member_values
>>> assert {"A"} in member_values
"""
mapping = {}
members = {}
C = G.__class__()
i = 0 # required if G is empty
remaining = set(G.nodes())
for i, group in enumerate(grouped_nodes):
group = set(group)
assert remaining.issuperset(
group
), "grouped nodes must exist in G and be disjoint"
remaining.difference_update(group)
members[i] = group
mapping.update((n, i) for n in group)
# remaining nodes are in their own group
for i, node in enumerate(remaining, start=i + 1):
group = {node}
members[i] = group
mapping.update((n, i) for n in group)
number_of_groups = i + 1
C.add_nodes_from(range(number_of_groups))
C.add_edges_from(
(mapping[u], mapping[v]) for u, v in G.edges() if mapping[u] != mapping[v]
)
# Add a list of members (ie original nodes) to each node (ie scc) in C.
nx.set_node_attributes(C, name="members", values=members)
# Add mapping dict as graph attribute
C.graph["mapping"] = mapping
return C
@nx._dispatchable
def complement_edges(G):
"""返回仅在图G的补集中的边
Parameters
----------
G : NetworkX图
Yields
------
edge : 元组
在G的补集中的边
Examples
--------
>>> G = nx.path_graph((1, 2, 3, 4))
>>> sorted(complement_edges(G))
[(1, 3), (1, 4), (2, 4)]
>>> G = nx.path_graph((1, 2, 3, 4), nx.DiGraph())
>>> sorted(complement_edges(G))
[(1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)]
>>> G = nx.complete_graph(1000)
>>> sorted(complement_edges(G))
[]
"""
G_adj = G._adj # Store as a variable to eliminate attribute lookup
if G.is_directed():
for u, v in it.combinations(G.nodes(), 2):
if v not in G_adj[u]:
yield (u, v)
if u not in G_adj[v]:
yield (v, u)
else:
for u, v in it.combinations(G.nodes(), 2):
if v not in G_adj[u]:
yield (u, v)
def _compat_shuffle(rng, input):
"""用于Python 2兼容性的rng.shuffle包装器"""
rng.shuffle(input)
@not_implemented_for("multigraph")
@not_implemented_for("directed")
@py_random_state(4)
@nx._dispatchable
def greedy_k_edge_augmentation(G, k, avail=None, weight=None, seed=None):
"""贪婪算法用于寻找 k-边增广
Parameters
----------
G : NetworkX 图
一个无向图。
k : 整数
期望的边连通性
avail : 字典或一组 2 或 3 元组
更多详情，参见 :func:`k_edge_augmentation` 。
weight : 字符串
如果 ``avail`` 是一组 3 元组，用于查找权重的键。
更多详情，参见 :func:`k_edge_augmentation` 。
seed : 整数，random_state，或 None（默认）
随机数生成状态的指示器。
参见 :ref:`Randomness<randomness>` 。
Yields
------
edge : 元组
G 的贪婪增广中的边
Notes
-----
该算法很简单。边逐渐添加在图中尚未局部 k-边连通的部分之间。然后从增广集中修剪边，只要不破坏局部边连通性。
该算法是贪婪的，不提供最优性保证。它仅用于为 :func:`k_edge_augmentation` 提供生成任意 k 的可行解的能力。
See Also
--------
:func:`k_edge_augmentation`
Examples
--------
>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> sorted(greedy_k_edge_augmentation(G, k=2))
[(1, 7)]
>>> sorted(greedy_k_edge_augmentation(G, k=1, avail=[]))
[]
>>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7))
>>> avail = {(u, v): 1 for (u, v) in complement_edges(G)}
>>> # 随机修剪过程可能产生不同的解决方案
>>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=2))
[(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 4), (2, 6), (3, 7), (5, 7)]
>>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=3))
[(1, 3), (1, 5), (1, 6), (2, 4), (2, 6), (3, 7), (4, 7), (5, 7)]
"""
# Result set
aug_edges = []
done = is_k_edge_connected(G, k)
if done:
return
if avail is None:
# all edges are available
avail_uv = list(complement_edges(G))
avail_w = [1] * len(avail_uv)
else:
# Get the unique set of unweighted edges
avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G)
# Greedy: order lightest edges. Use degree sum to tie-break
tiebreaker = [sum(map(G.degree, uv)) for uv in avail_uv]
avail_wduv = sorted(zip(avail_w, tiebreaker, avail_uv))
avail_uv = [uv for w, d, uv in avail_wduv]
# Incrementally add edges in until we are k-connected
H = G.copy()
for u, v in avail_uv:
done = False
if not is_locally_k_edge_connected(H, u, v, k=k):
# Only add edges in parts that are not yet locally k-edge-connected
aug_edges.append((u, v))
H.add_edge(u, v)
# Did adding this edge help?
if H.degree(u) >= k and H.degree(v) >= k:
done = is_k_edge_connected(H, k)
if done:
break
# Check for feasibility
if not done:
raise nx.NetworkXUnfeasible("not able to k-edge-connect with available edges")
# Randomized attempt to reduce the size of the solution
_compat_shuffle(seed, aug_edges)
for u, v in list(aug_edges):
# Don't remove if we know it would break connectivity
if H.degree(u) <= k or H.degree(v) <= k:
continue
H.remove_edge(u, v)
aug_edges.remove((u, v))
if not is_k_edge_connected(H, k=k):
# If removing this edge breaks feasibility, undo
H.add_edge(u, v)
aug_edges.append((u, v))
# Generate results
yield from aug_edges
