1

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

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

我知道存在 nx.path.bidirectional_dijkstra() 函数，但要使用它，我必须测试所有组合 N*M 这是冗余的（因为许多节点将被多次查询），因为实际上 N 的长度/M 可能是数千，这是不切实际的。

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

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

4

2 回答 2

2

  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. 您可以通过附加路径而不是neighbor_node 从函数中构建它，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​​ 算法差不多。

于 2013-05-02T13:59:02.317 回答
0

1) 为 中的每个节点添加一个x带边的节点，为 中的每个节点N添加一个带边y的节点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-08T10:36:23.457 回答