python - Networkx图: finding if path exists between any node in a given set of nodes and another set of nodes

Question

我有一个大型无向图，包含数十万个节点和数万个边。我有两个不同的问题:

1) 对于一组节点 N = (node[1],node[2],node[3],node[4],node[5]) 并且 M = (node[1001],节点[1002]，节点[1003]，节点[1004]，节点[1005])N中的任意节点与M中的任意节点之间是否存在路径？

我知道存在 nx.path.biorient_dijkstra() 函数，但要使用它，我必须测试所有组合 N*M 这是多余的(因为许多节点会被查询多次)，并且由于在实践中N/M 的长度可能有数千，这是不切实际的。

2)一个稍微独立的问题，但是有没有办法获取从 N 到 M 的所有路径的列表？

我对如何“推出自己的”解决方案有一个粗略的想法，但我想它会比有人已经做到这一点要慢很多倍，但我没有图论背景甚至知道我需要寻找什么!谢谢。

Answer 1

1. 类似这样的东西应该有效:

   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
   

2. 您可以通过附加路径而不是邻居节点来从 1. 的函数中构建此函数，但这需要更多时间，并且可能会出现循环。使用 yield 而不是 return 来获取无尽的路径流，然后在执行 for path in is_there_a_path(_from, _to) 时:

这是上面的算法，它遍历 ruby​​ 中的对象图并找到从自身到另一个对象的路径，并返回路径:

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 算法应该与 ruby​​ 算法大致相同。