График Networkx: обнаружение, существует ли путь между любым узлом в данном наборе узлов и другим набором узлов

Question

У меня большой неориентированный граф с сотнями тысяч узлов и десятками тысяч ребер. У меня есть две отдельные проблемы:

1) Для набора узлов N = (узел [1], узел [2], узел [3], узел [4], узел [5]) и, скажем, M = (узел [1001], узел [1002] ], узел [1003], узел [1004], узел [1005]) существует ли путь между любым узлом в N и любым узлом в M?

Я знаю, что существует функция nx.path.bidirectional_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, я думаю.

Answer 2

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