Source code for networkx.algorithms.connectivity.utils

"""
连接性包的实用工具
"""

import networkx as nx

__all__ = ["build_auxiliary_node_connectivity", "build_auxiliary_edge_connectivity"]




@nx._dispatchable(returns_graph=True)
def build_auxiliary_node_connectivity(G):
    r"""从无向图 G 创建有向图 D 以计算基于流量的节点连通性。

对于具有 `n` 个节点和 `m` 条边的无向图 G，我们通过将每个原始节点 `v` 替换为两个节点 `vA` 和 `vB` ，并在 D 中通过一条（内部）弧连接它们，从而得到具有 `2n` 个节点和 `2m+n` 条弧的有向图 D。然后，对于 G 中的每条边 ( `u` , `v` )，我们在 D 中添加两条弧 ( `uB` , `vA` ) 和 ( `vB` , `uA` )。最后，我们将 D 中每条弧的属性 capacity 设置为 1 [1]。

对于具有 `n` 个节点和 `m` 条弧的有向图，我们通过将每个原始节点 `v` 替换为两个节点 `vA` 和 `vB` ，并在 D 中通过一条（内部）弧 ( `vA` , `vB` ) 连接它们，从而得到具有 `2n` 个节点和 `m+n` 条弧的有向图 D。然后，对于 G 中的每条弧 ( `u` , `v` )，我们在 D 中添加一条弧 ( `uB` , `vA` )。最后，我们将 D 中每条弧的属性 capacity 设置为 1。

一个包含原始图中节点与辅助有向图之间映射关系的字典作为图属性存储：D.graph['mapping']。

References
----------
.. [1] Kammer, Frank 和 Hanjo Taubig。图连通性。在 Brandes 和 Erlebach 的 '网络分析：方法论基础' 中，计算机科学讲义，第 3418 卷，Springer-Verlag，2005 年。
    https://doi.org/10.1007/978-3-540-31955-9_7
"""
    directed = G.is_directed()

    mapping = {}
    H = nx.DiGraph()

    for i, node in enumerate(G):
        mapping[node] = i
        H.add_node(f"{i}A", id=node)
        H.add_node(f"{i}B", id=node)
        H.add_edge(f"{i}A", f"{i}B", capacity=1)

    edges = []
    for source, target in G.edges():
        edges.append((f"{mapping[source]}B", f"{mapping[target]}A"))
        if not directed:
            edges.append((f"{mapping[target]}B", f"{mapping[source]}A"))
    H.add_edges_from(edges, capacity=1)

    # Store mapping as graph attribute
    H.graph["mapping"] = mapping
    return H





@nx._dispatchable(returns_graph=True)
def build_auxiliary_edge_connectivity(G):
    """辅助有向图用于计算基于流边的连通性

如果输入图是无向的，我们将每条边 ( `u` , `v` ) 替换为两条互反弧 ( `u` , `v` ) 和 ( `v` , `u` )，并为每条弧设置属性 'capacity' 为 1。如果输入图是有向的，我们只需添加 'capacity' 属性。这是[1]中算法1的一部分。

References
----------
.. [1] Abdol-Hossein Esfahanian. 连通性算法。（这是一个章节，查找书籍的参考文献）。
    http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
"""
    if G.is_directed():
        H = nx.DiGraph()
        H.add_nodes_from(G.nodes())
        H.add_edges_from(G.edges(), capacity=1)
        return H
    else:
        H = nx.DiGraph()
        H.add_nodes_from(G.nodes())
        for source, target in G.edges():
            H.add_edges_from([(source, target), (target, source)], capacity=1)
        return H