NetworkX DiGraph按節點創建子圖（DiGraph）

我想按節點獲取子圖（紅色區域）：子圖由從輸入節點可到達的所有節點組成。NetworkX DiGraph按節點創建子圖（DiGraph）

像G.subgraph（3）從紅色區域返回一個新的DiGraph。

例如我創建一個有向圖，因爲這：

import networkx as nx 
G = nx.DiGraph() 

G.add_path([1,2,3,4]) 
G.add_path([3,'a','b']) 

A = nx.to_agraph(G) 
A.layout() 
A.draw('graph.png')

我看着https://networkx.github.io/documentation/latest/reference/generated/networkx.Graph.subgraph.html並將其轉換爲單向的。我測試了out_egdes，strong/weak_connected_component，但它從未工作過。我也看了How to find subgraphs in a directed graph without converting to undirected graph?和Networkx: extract the connected component containing a given node (directed graph)。

我知道Subgraph在DiGraph中不起作用。

有人可以告訴我如何做到這一點？如果生成的Graph也是一個DiGraph

來源

2015-10-04 svenhornberg

你澄清你怎麼想生成子圖。這是否是從給定輸入節點可以到達的所有節點？ –

是的，這就是我正在尋找。對不起，我沒有澄清這一點。順便說一句很有效 – svenhornberg

根據我的理解，創建子圖的標準取決於從輸入節點可到達的節點。那麼下面的遞歸函數應該足以完成工作。

def create_subgraph(G,sub_G,start_node): 
    for n in G.successors_iter(start_node): 
     sub_G.add_path([start_node,n]) 
     create_subgraph(G,sub_G,n)

我複製你的代碼來創建圖形，初始化一個空的有向圖和調用的函數如下：

G = nx.DiGraph() 
G.add_path([1,2,3,4]) 
G.add_path([3,'a','b']) 
sub_G = nx.DiGraph() 
create_subgraph(G, sub_G,3)

的結果有向圖的圖示。

來源

2015-10-06 13:02:41

使用內置遍歷算法可以獲得更好的性能，支持雙向選項，並避免遞歸深度限制。

def create_subgraph(G, node): 
    edges = nx.dfs_successors(G, node) 
    nodes = [] 
    for k,v in edges.items(): 
     nodes.extend([k]) 
     nodes.extend(v) 
    return G.subgraph(nodes)

或者簡潔的版本，單向性：

def create_subgraph(G, node): 
    nodes = nx.single_source_shortest_path(G,node).keys() 
    return G.subgraph(nodes)

的內置的版本是3倍以上的遞歸一個在我的案件快。它子3000從5000個節點：

In [1]: %timeit -n10 use_built_in('O_CONTRACT_PRODUCT') 
10 loops, best of 3: 102 ms per loop 

In [2]: %timeit -n10 use_recursive('O_CONTRACT_PRODUCT') 
10 loops, best of 3: 341 ms per loop

create_subgraph的（G，3）結果如圖所示：

來源

2017-08-14 16:26:49 Jesse

NetworkX DiGraph按節點創建子圖（DiGraph）

回答

相關問題