获取包含其间所有节点的 networkx 子图

Question

我有一个 networkx 有向图，我想通过传入节点列表从中提取一个子图。然而，子图可以包含所有可能位于我已经传递的节点之间的节点。我检查了 nx.subgraph() 但它没有像我想要的那样工作。至于一个小例子：

import networkx as nx

G = nx.DiGraph()
edges = [(7, 4), (3, 8), (3, 2), (3, 0), (3, 1), (7, 5), (7, 6), (7, 8)]
G.add_edges_from(edges)
H = get_subgraph(G, [0,6,7,8])

如何编写函数 get_subgraph() 使 H 具有边 [(3, 8), (3, 0), (7, 6), (7, 8)]？我需要的子图包含我在 get_subgraph() 函数中传递的节点之间的传出和传入路径中的所有节点。

Answer 1

一种方法可以是找到指定节点集之间的最长路径长度，然后找到包含路径中所有节点的相应导出子图。但是，作为有向图，节点 3 和 7 之间没有直接路径。所以我们需要在图的无向副本中找到路径。让我们设置问题：

G = nx.DiGraph()
edges = [(7, 4), (3, 8), (3, 2), (3, 0), (3, 1), (7, 5), (7, 6), (7, 8)]
G.add_edges_from(edges)

plt.figure(figsize=(10,6))
pos = nx.spring_layout(G, scale=20, k=3/np.sqrt(G.order()))
nx.draw(G, pos, node_color='lightblue', 
        with_labels=True, 
        node_size=1500,
        arrowsize=20)

现在我们可以为指定节点获取具有 nx.to_undirected and find all nx.shortest_path_length 的图的无向副本：

from itertools import combinations

H = nx.to_undirected(G)

nodelist = [0,6,7,8]
paths = {}
for nodes in combinations(nodelist, r=2):
    paths[nodes] = nx.shortest_path_length(H, *nodes)

print(paths)
# {(0, 6): 4, (0, 7): 3, (0, 8): 2, (6, 7): 1, (6, 8): 2, (7, 8): 1}

我们可以在无向图中找到最长的路径：

max_path = max(paths.items(), key=lambda x: x[1])[0]
longest_induced_path = nx.shortest_path(H, *max_path)

对应的导出子图可以用Graph.subgraph得到：

sG = nx.subgraph(G, longest_induced_path)

pos = nx.spring_layout(sG, scale=20, k=3/np.sqrt(G.order()))
nx.draw(sG, pos, node_color='lightblue', 
        with_labels=True, 
        node_size=1500,
        arrowsize=20)

Answer 2

我从问题中了解到这一点：您需要一条路径中的所有节点，但提供该路径的一些节点，算法应该给出该路径的所有节点，然后您可以将这些节点传递给一个图并制作一个新图。它应该是你想要的： 1. 您必须使用此方法遍历所有节点对：

from itertools import combinations
b= combinations('ABCD', 2)
print(list(b))  --> [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

你必须用这个获取所有路径： https://networkx.github.io/documentation/stable/reference/algorithms/simple_paths.html
您必须 select 具有最大节点数的路径，这就是您的解决方案。

获取包含其间所有节点的 networkx 子图

Get networkx subgraph containing all nodes in between

python

graph-theory

graph

networkx