Нашёл на просторах интернета функцию для поиска в глубину. Она работает, но при большом количестве путей время обхода слишком большое. Предполагаю, что единственный способ - это расширение на C. Но с C я вообще не знаком. Подскажите как минимальной кровью ускорить этот модуль. Смотрю в сторону cython, но опять же сложно понять как переписать алгоритм для повышения скорости.
Или поскажите готовые библиотеки с python интерфэйсом для работы с графами под Windows.
#!/usr/bin/env python # -*- coding: utf-8 -*- import time graph = {'begin': {'L1'}, 'L1' : {'BL2'}, 'BL2' : {'L2', 'EL2'}, 'L2' : {'EL2'}, 'EL2' : {'BL5'}, } n = 20 for i in range(3,n): graph['EL'+str(i-1)] = {'BL'+str(i)} graph['BL'+str(i)] = {'EL'+str(i), 'L'+str(i)} graph['L'+str(i)] = {'EL'+str(i)} if i == n-1: graph['EL'+str(i)] = {'end'} def dfs_paths(graph, start, goal): stack = [(start, [start])] while stack: (vertex, path) = stack.pop() for next in graph[vertex] - set(path): if next == goal: yield path + [next] else: stack.append((next, path + [next])) begin = time.time() print u'Обход всех путей...' for path in dfs_paths(graph, 'begin', 'end'): pass print u'Обход завершён...' end = time.time() print end-begin