如何在圖中分離這些（包含圖像）路徑？

Question

我有一個圖表，並希望從它隔離不同的路徑。既然不能這句話很容易地在圖中的行話，這裏是一個草圖：

在左側是我的源圖的高度簡化的表示。該圖具有僅具有2個鄰居的節點（顯示爲藍色方塊）。然後它與兩個以上的鄰居或恰好一個鄰居（顯示爲紅點）的交叉點和末端節點。

在右側，用三種不同的顏色編碼，是我想隔離的路徑。我想隔離所有連接紅點的路徑。由此產生的路徑不得越過（穿過）任何紅點。每條邊可能只是一條不同結果路徑的一部分。不應留有邊緣（最短路徑長度爲1）。

我相信這是圖形世界中已知的任務。我在第一次使用的NetworkX中對該圖進行了建模，但無法找到正確的方法來執行此操作。我確信我可以用艱難的方式編寫代碼，但如果它存在，會很樂意使用一種簡單而快速的方法。謝謝！

編輯：在隨機瀏覽NetworkX文檔後，我遇到了all_simple_paths方法。我現在的想法是

1. 迭代的所有節點，並確定了紅點（鄰號！= 2）
2. 使用all_simple_paths（）成對的紅點，收集生成的路徑
3. 刪除重複產生路徑，扔掉一切包含一個紅點，除了作爲開始和結束節點

第2步，當然，將不會很好地擴展。有了〜2000個相交節點，這似乎仍然有可能。

編輯2： all_simple_paths似乎也是這樣慢地使用它的方式。

Answer 1

我建議找到所有直節點（即，恰好有兩個鄰居節點），並從這些名單由隨機挑選一條直線節點和下面的兩個建立所有直線路徑列表導致其兩端（第一個非直線節點）。

在代碼：

def eachStraightPath(g): 
    straightNodes = { node for node in g.node if len(g.edge[node]) == 2 } 
    print straightNodes 
    while straightNodes: 
    straightNode = straightNodes.pop() 
    straightPath = [ straightNode ] 
    neighborA, neighborB = g.edge[straightNode].keys() 
    while True: # break out later if node is not straight 
     straightPath.insert(0, neighborA) 
     if neighborA not in straightNodes: 
     break 
     newNeighborA = (set(g.edge[neighborA])^{ straightPath[1] }).pop() 
     straightNodes.remove(neighborA) 
     neighborA = newNeighborA 
    while True: # break out later if node is not straight 
     straightPath.append(neighborB) 
     if neighborB not in straightNodes: 
     break 
     newNeighborB = (set(g.edge[neighborB])^{ straightPath[-2] }).pop() 
     straightNodes.remove(neighborB) 
     neighborB = newNeighborB 
    yield straightPath 

g = nx.lollipop_graph(5, 7) 

for straightPath in eachStraightPath(g): 
    print straightPath 

如果你的圖形是非常大的，你不想持有一組內存中的所有直節點，那麼你可以遍歷它們代替，但檢查是否下一個鄰居是直的會變得不太可讀（儘管可能更快）。這種方法的真正問題是你必須引入一個檢查來防止直接路徑被多次出現。