Networkx圖：查找給定節點集合中的任何節點與另一組節點之間是否存在路徑

我有一個包含數十萬個節點和數萬個邊的大型無向圖。我有兩個單獨的問題：對於一組節點N =（節點[1]，節點[2]，節點[3]，節點[4]，節點[5]），並且比方說M =（節點[1001]，節點[1002]，節點[1003]，節點[1004]，節點[1005]）是否存在N中的任何節點與M中的任何節點之間的路徑？Networkx圖：查找給定節點集合中的任何節點與另一組節點之間是否存在路徑

我知道存在nx.path.bidirectional_dijkstra（）函數，但要使用，我必須測試所有組合N * M是多餘的（因爲許多節點將被多次查詢），並且因爲在實踐中N/M的長度可能在幾千，這是不實際的。

2）一個稍微單獨的問題，但有沒有辦法從N到M獲得所有路徑的列表？

我對如何「滾動我自己的」解決方案有一個大致的想法，但我想它會比如果有人已經這樣做了很多倍，但沒有圖論中的背景我不'甚至不知道我需要尋找什麼！謝謝。

來源

2013-05-02 Matthew

像這樣的東西應該工作：

def is_there_a_path(_from, _to): 
    visited = set() # remember what you visited 
    while _from: 
     from_node = _from.pop(0) # get a new unvisited node 
     if from_node in _to: 
      # went the path 
      return True 
     # you need to implement get_nodes_referenced_by(node) 
     for neighbor_node in get_nodes_referenced_by(from_node): 
      # iterate over all the nodes the from_node points to 
      if neighbor_node not in visited: 
       # expand only unvisited nodes to avoid circles 
       visited.add(neighbor_node) 
       _from.append(neighbor_node) 
    return False

您可以從功能，從1.建立這個通過附加的路徑，而不是neighbor_node但它需要更多的時間和可能發生的圈子。使用yield，而不是return得到的路徑源源不斷然後做for path in is_there_a_path(_from, _to):

時，這一個是算法從上面穿過的紅寶石對象圖，並從自我發現到另一個對象的路徑，返回路徑：

class Object 
    # 
    # breadth first search for references from the given object to self 
    # 
    def reference_path_to(to_object, length, trace = false) 
    paths = [[to_object]] 
    traversed = IdentitySet.new 
    traversed.add(to_object) 
    start_size = 1 if trace 
    while not paths.empty? and paths.first.size <= length 
     references = paths[0][0].find_references_in_memory 
     # if we print here a SecurityError mey occur 
     references.each{ |reference| 
     return [reference] + paths[0] if reference.equal?(self) 
     unless traversed.include?(reference) or paths.any?{ |path| reference.equal?(path)} 
      paths.push([reference] + paths[0]) 
      traversed.add(reference) 
     end 
     } 
     if trace and start_size != paths[0].size 
     puts "reference_path_length: #{paths[0].size}" 
     start_size = paths[0].size 
     end 
     paths.delete_at(0) 
    end 
    return nil 
    end 
end # from https://github.com/knub/maglevrecord/blob/60082fd8c16fa7974166b96e5243fc0a176d172e/lib/maglev_record/tools/object_reference.rb

Python算法應該與我認爲的紅寶石算法大致相同。

來源

2013-05-02 13:59:02 User

謝謝，這看起來會很好！你知道圖論中是否有這種問題/算法的名稱，或者它不是經常出現的東西嗎？ – Matthew 2013-05-02 21:10:48

想想看，如果我只是在N中的所有節點和M中的所有節點之間創建邊，那麼nx.has_path（）應該直接給出答案。除非有什麼我失蹤。嗯... – Matthew 2013-05-02 22:32:35

這是http://en.wikipedia.org/wiki/Breadth-first_search的組合，並將點標記爲已訪問以實現更低的複雜度 – User 2013-05-03 06:58:13

1）的邊緣在N和一個節點y與邊緣添加一個節點x到每個節點的每一個節點在M。然後檢查是否有x - y路徑。注意 - 確保x和y不是節點。

G.add_edges_from([('x',node) for node in N]) 
G.add_edges_from([(node,'y') for node in M]) 
nx.has_path(N,M) #true if there was an M to N path

2）

augmented_paths = nx.all_simple_paths(G,source=x,target=y)

（這將產生一個發電機）。

for augmentedpath in nx.all_simple_paths(G, source=x, target=y): 
    path = augmentedpath[1:-1] #don't want the x and y included 
    print path

來源

2015-12-08 10:36:23 Joel

Networkx圖：查找給定節點集合中的任何節點與另一組節點之間是否存在路徑

回答

相關問題