图缩减

Question

我一直在编写代码以减少一个图形。问题是有些分支我想要移除。一旦我移除了一个分支，我可以合并节点或不合并，这取决于分支连接的节点之间路径的数量。

也许以下示例说明了我的意思：

我拥有的代码如下：

from networkx import DiGraph, all_simple_paths, draw
from matplotlib import pyplot as plt

# data preparation
branches = [(2,1), (3,2), (4,3), (4,13), (7,6), (6,5), (5,4), 
            (8,7), (9,8), (9,10), (10,11), (11,12), (12,1), (13,9)]

branches_to_remove_idx = [11, 10, 9, 8, 6, 5, 3, 2, 0]
ft_dict = dict()
graph = DiGraph()

for i, br in enumerate(branches):
    graph.add_edge(br[0], br[1])
    ft_dict[i] = (br[0], br[1])

# Processing -----------------------------------------------------
for idx in branches_to_remove_idx:

    # get the nodes that define the edge to remove
    f, t = ft_dict[idx]

    # get the number of paths from 'f' to 't'
    n_paths = len(list(all_simple_paths(graph, f, t)))

    if n_paths == 1:
        # remove branch and merge the nodes 'f' and 't'
        #
        #       This is what I have no clue how to do
        #
        pass

    else:
        # remove the branch and that's it
        graph.remove_edge(f, t)
        print('Simple removal of', f, t)

# -----------------------------------------------------------------

draw(graph, with_labels=True)
plt.show()

我认为应该有一种更简单直接的方法，通过分支索引获取第一个数字的最后一个数字，但我毫无头绪。

- Santi Peñate-Vera

---

在“网络术语”中，你所谓的分支通常被称为“边缘”。 - Paul Brodersen

我应该改变它吗？ - Santi Peñate-Vera

如果您想要，可以只翻译以下相关编程内容。返回翻译的文本即可。 - Paul Brodersen

手头的问题是在阻抗接近于零的电网中删除分支（边缘）。这意味着，如果它们连接的两个节点被合并，那么这些分支不会显著改变计算结果。但是通过删除边缘并合并节点，电网仍然“相同”，但计算需求更低。在我所举的例子中，潜在的边缘减少量从4500个到700个。这些边缘是为了工程和维护原因而表示的，但对于计算来说是一个负担。 - Santi Peñate-Vera

谢谢，我会仔细审查它。 - Santi Peñate-Vera

Answer 1

我认为这大致符合您的要求。我将所有在链式结构中（度数为2的连通节点）的节点合并为一个超级节点。我返回新图和一个将超级节点映射到收缩节点的字典。

import networkx as nx

def contract(g):
    """
    Contract chains of neighbouring vertices with degree 2 into one hypernode.

    Arguments:
    ----------
    g -- networkx.Graph instance

    Returns:
    --------
    h -- networkx.Graph instance
        the contracted graph

    hypernode_to_nodes -- dict: int hypernode -> [v1, v2, ..., vn]
        dictionary mapping hypernodes to nodes

    """

    # create subgraph of all nodes with degree 2
    is_chain = [node for node, degree in g.degree_iter() if degree == 2]
    chains = g.subgraph(is_chain)

    # contract connected components (which should be chains of variable length) into single node
    components = list(nx.components.connected_component_subgraphs(chains))
    hypernode = max(g.nodes()) +1
    hypernodes = []
    hyperedges = []
    hypernode_to_nodes = dict()
    false_alarms = []
    for component in components:
        if component.number_of_nodes() > 1:

            hypernodes.append(hypernode)
            vs = [node for node in component.nodes()]
            hypernode_to_nodes[hypernode] = vs

            # create new edges from the neighbours of the chain ends to the hypernode
            component_edges = [e for e in component.edges()]
            for v, w in [e for e in g.edges(vs) if not ((e in component_edges) or (e[::-1] in component_edges))]:
                if v in component:
                    hyperedges.append([hypernode, w])
                else:
                    hyperedges.append([v, hypernode])

            hypernode += 1

        else: # nothing to collapse as there is only a single node in component:
            false_alarms.extend([node for node in component.nodes()])

    # initialise new graph with all other nodes
    not_chain = [node for node in g.nodes() if not node in is_chain]
    h = g.subgraph(not_chain + false_alarms)
    h.add_nodes_from(hypernodes)
    h.add_edges_from(hyperedges)

    return h, hypernode_to_nodes


edges = [(2, 1),
         (3, 2),
         (4, 3),
         (4, 13),
         (7, 6),
         (6, 5),
         (5, 4),
         (8, 7),
         (9, 8),
         (9, 10),
         (10, 11),
         (11, 12),
         (12, 1),
         (13, 9)]

g = nx.Graph(edges)

h, hypernode_to_nodes = contract(g)

print("Edges in contracted graph:")
print(h.edges())
print('')
print("Hypernodes:")
for hypernode, nodes in hypernode_to_nodes.items():
    print("{} : {}".format(hypernode, nodes))

这是你的示例返回结果：

Edges in contracted graph:
[(9, 13), (9, 14), (9, 15), (4, 13), (4, 14), (4, 15)]

Hypernodes:
14 : [1, 2, 3, 10, 11, 12]
15 : [8, 5, 6, 7]

- Paul Brodersen

Answer 2

我编写了这个函数，它可以更好地缩放，并且在处理更大的图形时运行速度更快：

def add_dicts(vector):
    l = list(map(lambda x: Counter(x),vector))
    return reduce(lambda x,y:x+y,l)

def consolidate_dup_edges(g):
    edges = pd.DataFrame(g.edges(data=True),columns=['start','end','weight'])
    edges_consolidated = edges.groupby(['start','end']).agg({'weight':add_dicts}).reset_index()
    return nx.from_edgelist(list(edges_consolidated.itertuples(index=False,name=None)))

def graph_reduce(g):
    g = consolidate_dup_edges(g)
    is_deg2 = [node for node, degree in g.degree() if degree == 2]
    is_deg2_descendents =list(map(lambda x: tuple(nx.descendants_at_distance(g,x,1)),is_deg2))
    edges_on_deg2= list(map(lambda x: list(map(lambda x:x[2],g.edges(x,data=True))),is_deg2))
    edges_on_deg2= list(map(lambda x: add_dicts(x),edges_on_deg2))
    new_edges = list(zip(is_deg2_descendents,edges_on_deg2))
    new_edges = [(a,b,c) for (a,b),c in new_edges]
    g.remove_nodes_from(is_deg2)
    g.add_edges_from(new_edges)
    g.remove_edges_from(nx.selfloop_edges(g))
    g.remove_nodes_from([node for node, degree in g.degree() if degree <= 1])
    return consolidate_dup_edges(g)
    

graph_reduce 函数基本上会删除度数为 1 的节点，并删除度数为 2 的中间节点，将度数为 2 的节点连接到其连接的节点。我们可以看到当我们迭代运行此代码直到节点数量稳定时，它的最佳影响。这仅适用于无向图。

- Rishan