Список всех путей от источника до приемника в ориентированном ациклическом графе

Question

Возможный дубликат:
[python]: путь между двумя узлами

Может кто-нибудь указать мне некоторые ресурсы о том, как это сделать? я использую networkx как моя библиотека Python.

Спасибо!

Answer 1

Это основано на ответе Алекса Мартелли, но это должно сработать. Это зависит от выражения source_node.children давая итеративный, который будет перебирать всех детей source_node, Это также зависит от того, есть ли рабочий путь для == Оператор для сравнения двух узлов, чтобы увидеть, если они одинаковы. С помощью is может быть лучшим выбором По-видимому, в используемой вами библиотеке синтаксис для получения итерации для всех дочерних graph[source_node], так что вам нужно будет соответствующим образом скорректировать код.

def allpaths(source_node, sink_node):
    if source_node == sink_node: # Handle trivial case
        return frozenset([(source_node,)])
    else:
        result = set()
        for new_source in source_node.children:
            paths = allpaths(new_source, sink_node, memo_dict)
            for path in paths:
                path = (source_node,) + path
                result.add(path)
        result = frozenset(result)
        return result

Мое главное беспокойство заключается в том, что это делает поиск в глубину, тратит впустую усилия, когда есть несколько путей от источника к узлу, который является внуком, правнуком и т. Д. Весь источник, но не обязательно родительский элемент приемника. Если бы он запомнил ответ для заданного узла источника и приемника, можно было бы избежать дополнительных усилий.

Вот пример того, как это будет работать:

def allpaths(source_node, sink_node, memo_dict = None):
    if memo_dict is None:
        # putting {}, or any other mutable object
        # as the default argument is wrong 
        memo_dict = dict()

    if source_node == sink_node: # Don't memoize trivial case
        return frozenset([(source_node,)])
    else:
        pair = (source_node, sink_node)
        if pair in memo_dict: # Is answer memoized already?
            return memo_dict[pair]
        else:
            result = set()
            for new_source in source_node.children:
                paths = allpaths(new_source, sink_node, memo_dict)
                for path in paths:
                    path = (source_node,) + path
                    result.add(path)
            result = frozenset(result)
            # Memoize answer
            memo_dict[(source_node, sink_node)] = result
            return result

Это также позволяет вам сохранять словарь запоминания между вызовами, поэтому, если вам нужно вычислить ответ для нескольких узлов источника и приемника, вы можете избежать больших дополнительных усилий.

Answer 2

На самом деле этот работает с networkx, и он не рекурсивный, что может быть хорошо для больших графов.

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths

Answer 3

Я не уверен, есть ли специальные оптимизации, доступные - прежде чем искать какую-либо из них, я бы сделал простое рекурсивное решение, что-то вроде (использование только функции networkx, которая индексирует граф с помощью узла, дает итеративную выдачу его соседние узлы [[дикт, в случае networkx, но я не использую это в частности]])...:

def allpaths(G, source_nodes, set_of_sink_nodes, path_prefix=()):
  set_of_result_paths = set()
  for n in source_nodes:
    next_from_n = []
    for an in G[n]:
      if an in set_of_sink_nodes:
        set_of_result_paths.add(path_prefix + (n, an))
      else:
        next_from_n.append(an)
    if next_from_n:
      set_of_result_paths.update(
          allpaths(G, next_from_n, set_of_sink_nodes, path_prefix + (n,)))
  return set_of_result_paths

Это должно быть доказуемо правильно (но я не собираюсь делать доказательство, потому что очень поздно, и я устал, и нечеткий;-) и пригодный для проверки любых дальнейших оптимизаций;-).

Первой оптимизацией, которую я бы попробовал, было бы какое-то простое запоминание: если я уже вычислил набор путей от некоторого узла N к любому целевому узлу (каким бы ни был префикс, ведущий к N, когда я делал это вычисление), я могу спрятать это далеко от слова под ключом N и избежать дальнейших пересчетов, если и когда я снова доберусь до N другим путем;-).