Caminho entre dois nós

Question

Estou usando o networkx para trabalhar com gráficos.Eu tenho um gráfico bem grande (tem quase 200 nós) e tento encontrar todos os caminhos possíveis entre dois nós.Mas, pelo que entendi, o networkx só consegue encontrar o caminho mais curto.Como posso obter não apenas o caminho mais curto, mas todos os caminhos possíveis?

Atualização:path pode conter cada nó apenas uma vez.

UPD2:Preciso de algo como a função find_all_paths(), descrita aqui:python.org/doc/essays/graphs.html Mas esta função não funciona bem com grande número de nós e arestas =(

Answer 1

gráfico, outro módulo gráfico para Python pode calcular todos os mais curto caminhos entre um determinado par de nós.Calcular todos os caminhos não faz sentido, pois você tem infinitos caminhos desse tipo.

Um exemplo para calcular todos os caminhos mais curtos do vértice 0:

>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]

Se você possui o igraph 0.6 ou posterior (esta é a versão de desenvolvimento no momento em que este artigo foi escrito), você pode restringir o resultado de get_all_shortest_paths para um determinado vértice final também:

>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
 [0, 1, 2, 12, 13, 14, 15],
 [0, 10, 11, 12, 13, 14, 15],
 [0, 1, 11, 12, 13, 14, 15],
 [0, 1, 2, 3, 13, 14, 15],
 [0, 1, 2, 3, 4, 5, 15]]

Claro que você precisa ter cuidado;por exemplo, suponha que você tenha um gráfico de grade de 100 x 100 (que pode ser facilmente gerado por Graph.Lattice([100, 100], circular=False) no igraph).O número de caminhos mais curtos que vão do nó superior esquerdo ao nó inferior direito é igual ao número de possibilidades de escolher 100 elementos entre 200 (prova:o comprimento do caminho mais curto tem 200 arestas, 100 das quais irão "horizontalmente" na grade e 100 das quais irão "verticalmente").Provavelmente isso não cabe na sua memória, portanto mesmo calculando todos os mais curto caminhos entre esses dois nós não é realmente viável aqui.

Se você realmente precisa de todos os caminhos entre dois nós, você pode reescrever a função fornecida na página mencionada usando o igraph, o que provavelmente será mais rápido que uma solução Python pura, já que o núcleo do igraph é implementado em C:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in set(graph.neighbors(start)) - set(path):
        paths.extend(find_all_paths(graph, node, end, path))
    return paths

Ele pode ser mais otimizado convertendo primeiro o gráfico em uma representação de lista de adjacências, pois isso pouparia chamadas repetidas para graph.neighbors:

def find_all_paths(graph, start, end):
    def find_all_paths_aux(adjlist, start, end, path):
        path = path + [start]
        if start == end:
            return [path]
        paths = []
        for node in adjlist[start] - set(path):
            paths.extend(find_all_paths_aux(adjlist, node, end, path))
        return paths

    adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
    return find_all_paths_aux(adjlist, start, end, [])

Editar:corrigi o primeiro exemplo para funcionar no igraph 0.5.3 também, não apenas no igraph 0.6.

Answer 2

Na verdade, este funciona com o NetworkX e não é recursivo, o que pode ser bom para gráficos grandes.

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

O algoritmo de Dijkstra encontrará o caminho mais curto de uma maneira semelhante a uma primeira pesquisa de largura (substitui uma fila de prioridade ponderada por profundidade no gráfico para a fila ingênua de um BFS). Você pode estendê -lo de maneira bastante trivial para produzir os caminhos mais curtos 'n' se precisar de algum número de alternativas, embora se você precisar dos caminhos para ser substancialmente diferente (por exemplo, agendando as rotas das vans de segurança), talvez seja necessário ser mais inteligente em selecionar caminhos que são significativamente diferentes um do outro.