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

1 人关注

我有一个networkx DiGraph，我想通过传入一个节点列表来提取其中的子图。然而，这个子图可以包含所有可能在我所传递的节点之间的节点。我检查了 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()函数中传递的节点之间的传出和传入路径上的节点。


         python


         graph


         networkx


         graph-theory


        
         
         
          Crazzay1903
         
        
        
         发布于
         
         2020-05-21


        2
        
        个回答


          已采纳


         0
         
         人赞同


          
           做到这一点的方法可以是找到指定节点集之间最长的路径长度，然后找到相应的包含路径中所有节点的诱导子图。然而，作为一个有向图，节点
           
            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并找到所有nx.shortest_path_length for the specified nodes:
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)


          
           
            
             
              
               
               
                M.qaemi Qaemi
               
              
              
               发布于
               
               2020-05-21


          
           
            
             
              
               我从问题中理解了这一点。
你需要一个路径中的所有节点，但要提供该路径的一些节点，而算法应该给出该路径的所有节点，然后你可以将这些节点传递给一个图，并形成一个新的图。
这应该是你想要的结果。
1.你必须用这个方法遍历所有的节点对。
              
              from itertools import combinations
b= combinations('ABCD', 2)
print(list(b))  --> [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]