Chemin entre deux nœuds

Question

J'utilise NetworkX pour travailler avec des graphiques. J'ai assez grand graphique (il est près de 200 nœuds en elle) et je tente de trouver tous les chemins possibles entre deux nœuds. Mais, comme je comprends, NetworkX ne peut trouver que plus court chemin. Comment puis-je obtenir non seulement plus court chemin, mais tous les chemins possibles?

UPD. Chemin peut contenir chaque noeud une seule fois

UPD2: Je besoin de quelque chose comme la fonction find_all_paths (), décrit ici: python.org/doc/essays/graphs.html Mais cette fonction ne fonctionne pas bien avec un grand nombre de nœuds et TRANCHANT = (

Answer 1

igraph , un autre module graphique pour Python peut calculer tous les le plus court chemins entre une paire donnée de nœuds. Le calcul de tous les chemins n'a pas de sens que vous avez une infinité de ces chemins.

Un exemple pour le calcul de tous les chemins les plus courts de sommet 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...]

Si vous avez igraph 0.6 ou version ultérieure (c'est la version de développement au moment de l'écriture), vous pouvez limiter le résultat de get_all_shortest_paths à un sommet final donné ainsi:

>>> 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]]

Bien sûr, vous devez être prudent; par exemple, supposons que vous avez un graphique de grille 100 x 100 (qui peut facilement être généré par Graph.Lattice([100, 100], circular=False) dans igraph). Le nombre de chemins les plus courts menant du nœud supérieur gauche au nœud en bas à droite est égal au nombre de possibilités de choisir 100 éléments sur 200 (la preuve: la longueur du chemin le plus court, il a 200 arêtes, dont 100 iront « horizontalement » dans la grille et 100 qui ira « verticalement »). Cela ne correspond pas probablement dans votre mémoire, donc même calcul tous les le plus court chemins entre ces deux noeuds n'est pas vraiment possible ici.

Si vous avez vraiment besoin de tous les chemins entre deux nœuds, vous pouvez réécrire la fonction donnée sur la page Web que vous avez mentionné en utilisant igraph, qui sera probablement plus rapide qu'une solution pure Python comme noyau de igraph est implémenté en 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

Il peut être optimisé plus en convertissant le graphique à une représentation de liste de contiguïté d'abord comme il épargnerait à des appels répétés 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, [])

Modifier :. Premier exemple fixe et de travailler dans igraph 0.5.3, non seulement dans igraph 0,6

Answer 2

Celui-ci fonctionne en fait avec NetworkX, et il est non récurrent, ce qui peut être agréable pour les grands graphiques.

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

L'algorithme de Dijkstra trouvera le chemin le plus court d'une manière similaire à une première recherche étendue (il substitue une file d'attente prioritaire pondérée par la profondeur dans le graphique de la file d'attente naïve d'un BFS). Vous pouvez assez trivialement étendre pour produire les chemins les plus courts « N » si vous avez besoin certain nombre d'alternatives, mais si vous avez besoin des chemins pour être sensiblement différents (par exemple la planification des itinéraires de fourgons de sécurité), vous pourriez avoir besoin d'être plus intelligent sur la sélection les chemins qui sont sensiblement différents les uns des autres.