修剪不在networkx簡單路徑中的節點？

我有一個DiGrraph，我想修剪任何不包含在我指定的兩個節點之間的simple paths中的節點。（另一種想法是節點不能達到都start和end點應該修剪）。修剪不在networkx簡單路徑中的節點？

我發現要做到這一點的最好方法是獲得all_simple_paths，然後使用這些重建一個新圖形，但我希望有一個更優雅，更容易出錯的解決方案。例如，有沒有辦法確定什麼是不在簡單路徑上，然後刪除這些節點？

來源

2015-11-07 mlissner

我不知道如何。但'all_simple_paths'返回一個生成器，所以你只需要用next（..）來查詢它。那麼如果你的圖不在節點上存儲數據，那麼得到一個子圖就是單線圖。 – Kikohs

你可以擴展嗎？我沒有在節點上存儲數據，但我不確定你想要的是什麼。聽起來很有希望！ – mlissner

然後我會做出迴應。 – Kikohs

您可以使用方法all_simple_paths，它返回一個生成器，但只需要第一個路徑。然後，您可以使用G.subgraph(nbunch)從您的路徑返回誘導圖。

編輯：返回由所有簡單路徑引發的子圖只是連接由all_simple_paths返回的唯一節點。

import networkx as nx 
import itertools 

G = nx.complete_graph(10) # or DiGraph, MultiGraph, MultiDiGraph, etc 
# Concatenate all the paths and keep unique nodes (in one line) 
all_path_nodes = set(itertools.chain(*list(nx.all_simple_paths(G, source=0, target=3)))) 
# Extract the induced subgraph from a given list of nodes 
H = G.subgraph(all_path_nodes) 
print(nx.info(H))

輸出：

Name: complete_graph(10) 
Type: Graph 
Number of nodes: 10 
Number of edges: 45 
Average degree: 9.0000

來源

2015-11-07 18:51:33 Kikohs

好的，我明白你的意思了，儘管我需要我的最終圖來包含任何簡單路徑中的所有節點。不過，我不知道'subgraph'函數，所以這很有用，但我認爲它不會幫助我解決這個問題。 – mlissner

你的問題並不清楚，因爲你在* a *簡單的路徑中說過。 – Kikohs

對不起，覺得很清楚。我會更新它。 – mlissner

我沒有就這個而@kikohs一些進展正在努力理解我的問題，並提供他的回答，所以我張貼這個作爲一種替代解決問題的辦法。我認爲他的答案雖然優越！

def _trim_branches(self, g, start, end): 
    """Find all the paths from start to finish, and nuke any nodes that 
    aren't in those paths. 
    """ 
    good_nodes = set() 
    for path in networkx.all_simple_paths(
      g, 
      source=start, 
      target=end): 
     [good_nodes.add(n) for n in path] 

    for node in g.nodes: 
     if node not in good_nodes: 
      g.remove_node(node) 

    return g

使用subgraph做第二個循環是清楚越好，因爲是使用itertools.chain他需要一行代碼。今天圍繞這些部件的好東西！

來源

2015-11-07 19:11:36 mlissner

修剪不在networkx簡單路徑中的節點？

回答

相關問題