список всех путей из источника для впитывания направленного графа без петель [дубликат]
2 ответа
Это основано на ответе Алекса Мартелли, но он должен работать. Это зависит от выражения source_node.children , дающего итерацию, которая будет перебирать все дочерние элементы source_node . Он также полагается на то, что для оператора == существует рабочий способ сравнения двух узлов, чтобы убедиться, что они одинаковы. Использование - может быть лучшим выбором. По-видимому, в используемой вами библиотеке синтаксис для получения итерации по всем дочерним элементам - 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
Это также позволяет вам сохранять словарь мемоизации между вызовами, поэтому, если вам нужно вычислить ответ для нескольких узлов источника и приемника, вы можете избежать больших дополнительных усилий.
Я не уверен, доступны ли какие-либо специальные оптимизации - прежде чем искать какую-либо из них, я бы сделал простое рекурсивное решение, что-то вроде (использование 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
Это должно быть доказуемо правильным (но я я не собираюсь проводить доказательство, потому что уже очень поздно, я устал и неуверен ;-) и могу использовать для проверки любых дальнейших оптимизаций ;-).
Первая оптимизация, которую я бы попробовал, была бы своего рода простым запоминанием: если бы я уже вычислил набор путей от некоторого узла N к любому целевому узлу (независимо от префикса, ведущего к N, когда я выполнял это вычисление), Я могу спрятать это в dict под ключом N и избежать дальнейших перерасчетов, если и когда я снова доберусь до N другим маршрутом ;-).