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

Question

Possible Duplicate:
[python]: path between two nodes

Может кто-нибудь мне точку на некоторые ресурсы о том, как это сделать? Я использую 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 только функция, которая индексирует граф узлом дает итератор уступая соседние узлы [[а Dict, в случае 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 

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

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

Answer 3

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