Get networkx subgraph containing all nodes in between
我有一个 networkx DiGraph，我想通过传入一个节点列表从中提取一个子图。然而，子图可以包含可能位于我通过的节点之间的所有节点。我检查了 nx.subgraph() 但它不像我打算的那样工作。举个小例子：
| 1 2 3 4 5 6 |
import networkx as nx
G = nx. DiGraph ( ) |
如何编写函数 get_subgraph() 以使 H 具有边 [(3, 8), (3, 0), (7, 6), (7, 8)] ？
我需要的子图是这样的，它包含我在 get_subgraph() 函数中传递的节点之间的传出路径和传入路径中的所有节点。
一种方法可以是找到指定节点集之间的最长路径长度，然后找到包含路径中所有节点的相应诱导子图。但是，作为有向图，节点 3 和 7 之间将没有直接路径。所以我们需要在图的无向副本中找到路径。让我们设置问题：
| 1 2 3 4 5 6 7 8 9 10 |
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 ) ) |
现在我们可以使用 nx.to_undirected 获取图的无向副本，并找到指定节点的所有 nx.shortest_path_length ：
| 1 2 3 4 5 6 7 8 9 10 11 |
from itertools import combinations
H = nx. to_undirected (G ) nodelist = [ 0 , 6 , 7 , 8 ] print (paths ) |
我们可以在无向图中找到最长的路径：
| 1 2 |
max_path = max (paths. items ( ) , key = lambda x: x [ 1 ] ) [ 0 ] longest_induced_path = nx. shortest_path (H , *max_path ) |
而对应的诱导子图可以用 Graph.subgraph 得到：
| 1 2 3 4 5 6 7 |
sG = nx. subgraph (G , longest_induced_path )
pos = nx. spring_layout (sG , scale = 20 , k = 3/np. sqrt (G. order ( ) ) ) |
我从问题中理解这一点：
您需要路径中的所有节点，但提供该路径的一些节点，并且算法应该提供该路径的所有节点，然后您可以将这些节点传递给一个图并制作一个新图。
它应该是你想要的：
1.您必须使用此方法遍历所有节点对：
| 1 2 3 |
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
您必须选择具有最大节点的路径，这就是您的解决方案。
- 明白了。谢谢您的意见。这类似于 yatus 答案
评论(0)