1
Я использую функцию от here:NetworkX/Python_igraph: Все пути между двумя узлами, ограниченный списком узлов
def find_all_paths(graph, start, end, mode = 'OUT', maxlen = None):
def find_all_paths_aux(adjlist, start, end, path, maxlen = None):
path = path + [start]
if start == end:
return [path]
paths = []
if maxlen is None or len(path) <= maxlen:
for node in adjlist[start] - set(path):
paths.extend(find_all_paths_aux(adjlist, node, end, path, maxlen))
return paths
adjlist = [set(graph.neighbors(node, mode = mode)) \
for node in xrange(graph.vcount())]
all_paths = []
start = start if type(start) is list else [start]
end = end if type(end) is list else [end]
for s in start:
for e in end:
all_paths.extend(find_all_paths_aux(adjlist, s, e, [], maxlen))
return all_paths
найти все пути между двумя узлами.
Альтернативная функция является один here:
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
Я хотел бы выразить одну из функций, чтобы сделать еще один аргумент, который будет список «via_nodes».
Если путь имеет один из этих сквозных путей между его концом и стартовым узлом, его не следует возвращать.
Было бы легко сначала вычислить все пути с помощью функции, как она есть сейчас, а затем исключить пути, встречающиеся выше условия, но для того, чтобы сделать его более эффективным, я хотел бы, чтобы он остановил поиск пути, как только он встретится via_node на более раннем этапе.
Любые идеи?