1

数十万のノードと数万のエッジを持つ大きな無向グラフがあります。私は2つの別々の問題を抱えています:

1) ノード N = (ノード [1]、ノード [2]、ノード [3]、ノード [4]、ノード [5]) のセットの場合、M = (ノード [1001]、ノード [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 のオブジェクト グラフを調べて、self から別のオブジェクトへのパスを見つけ、そのパスを返します。

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のすべてのノードにエッジを持つ 1 つのノードを追加し、 のすべてのノードにエッジを持つ1Nつのノードを追加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 に答える