Alle Pfade der Länge L vom Knoten n mit Python

Bei einem Graphen G, einem Knoten n und einer Länge L, möchte ich alle (nicht-zyklischen) Pfade der Länge L sammeln, die von n abweichen.

Hast du eine Ahnung, wie du das nimmst?

  • Python äquivalent zu "halten" in Matlab
  • Brauchen Sie Hilfe bei NetworkX
  • Sparse Matrix aus einem dichten Tensorflow
  • Konstruieren Sie bipartite Graphen aus Spalten von Python-Dataframe
  • Animierte Grafikdiffusion mit NetworkX
  • NetworkX: Wie kann man eine Inzidenzmatrix eines gewichteten Graphen erstellen?
  • Mittlerweile bin ich meine Grafik eine networkx.Graph-Instanz, aber ich interessiere mich nicht wirklich, wenn zB igraph empfohlen wird.

    Danke vielmals!

  • Finden Sie den Index der N größten Elemente in Python Array / Liste effizient
  • Python Numpy Datentypen Leistung
  • Langsame Leistung von Pandas Zeitstempel vs datetime
  • Optimiere diese Funktion mit numpy (oder anderen Vektorisierungsmethoden)
  • Schlechte numpy.cross () Leistung
  • Python FAQ: "Wie schnell sind Ausnahmen?"
  • 5 Solutions collect form web for “Alle Pfade der Länge L vom Knoten n mit Python”

    Ich möchte nur auf die hervorragende Antwort von Lance Helsten erweitern:

    Die Tiefenbegrenzte Suche sucht nach einem bestimmten Knoten innerhalb einer bestimmten Tiefe (was du die Länge L nennst) und hört auf, wenn er sie findet. Wenn du einen Blick auf den Pseudocode im Wiki Link in seiner Antwort werdest, wirst du das verstehen:

    DLS(node, goal, depth) { if ( depth >= 0 ) { if ( node == goal ) return node for each child in expand(node) DLS(child, goal, depth-1) } } 

    In deinem Fall aber, wie du alle Pfade der Länge L von einem Knoten suchst, wirst du nicht überall aufhören. So muss der Pseudocode geändert werden an:

     DLS(node, depth) { for each child in expand(node) { record paths as [node, child] DLS(child, depth-1) } } 

    Nachdem Sie mit der Aufzeichnung aller Single-Link-Pfade aus aufeinanderfolgenden Nestern des DLS fertig sind, nehmen Sie einfach ein Produkt von ihnen, um den ganzen Weg zu bekommen. Die Anzahl dieser gibt Ihnen die Anzahl der Pfade der erforderlichen Tiefe ab dem Knoten.

    Ein ganz einfacher Weg, sich zu nähern (und ganz zu lösen) ist dieses Problem, die Nachbarschaftsmatrix A des Graphen zu verwenden. Das (i, j) -te Element von A ^ L ist die Anzahl der Pfade zwischen den Knoten i und j der Länge L. Also, wenn Sie diese über alle j halten, die ich bei n fixiert habe, bekommst du alle Pfade, die vom Knoten n der Länge L ausgehen .

    Das wird auch leider die zyklischen Wege zählen. Diese sind glücklicherweise aus dem Element A^L(n,n) , also einfach das zu subtrahieren.

    Also deine letzte Antwort lautet: Σj{A^L(n,j)} - A^L(n,n) .

    Wort der Vorsicht: Sagen Sie, dass Sie nach Pfaden der Länge 5 von Knoten 1 suchen: Diese Berechnung wird auch den Pfad mit kleinen Zyklen innerhalb wie 1-2-3-2-4 , deren Länge 5 oder 4 ist, je nachdem, wie Sie Wählen Sie es zu sehen, also seien Sie vorsichtig darüber.

    Verwenden Sie eine Tiefenbegrenzte Suche ( http://de.wikipedia.org/wiki/Depth-limited_search ), wo Sie eine Reihe von besuchten Knoten für die Erkennung eines Zyklus auf einem Pfad zu halten. Zum Beispiel kannst du einen Baum aus deinem Knoten n mit allen Knoten und Länge von L bauen, um den Baum zu beschneiden.

    Ich habe eine schnelle Suche nach Graphen-Algorithmen gemacht, um dies zu tun, aber fand nichts. Es gibt eine Liste von Graphenalgorithmen ( http://de.wikipedia.org/wiki/Kategorie:Graph_algorithmen ), die genau das haben können, was Sie suchen.

    Hier ist eine andere (eher naive) Implementierung, die ich nach dem Lesen der Antworten hierher komme:

     def findAllPaths(node, childrenFn, depth, _depth=0, _parents={}): if _depth == depth - 1: # path found with desired length, create path and stop traversing path = [] parent = node for i in xrange(depth): path.insert(0, parent) if not parent in _parents: continue parent = _parents[parent] if parent in path: return # this path is cyclic, forget yield path return for nb in childrenFn(node): _parents[nb] = node # keep track of where we came from for p in findAllPaths(nb, childrenFn, depth, _depth + 1, _parents): yield p graph = { 0: [1, 2], 1: [4, 5], 2: [3, 10], 3: [8, 9], 4: [6], 5: [6], 6: [7], 7: [], 8: [], 9: [], 10: [2] # cycle } for p in findAllPaths(0, lambda n: graph[n], depth=4): print(p) # [0, 1, 4, 6] # [0, 1, 5, 6] # [0, 2, 3, 8] # [0, 2, 3, 9] 

    Diese Lösung könnte in der Effizienz verbessert werden, aber es scheint sehr kurz und nutzt die Networkx-Funktionalität:

     G = nx.complete_graph(4) n = 0 L = 3 result = [] for paths in (nx.all_simple_paths(G, n, target, L) for target in G.nodes_iter()): print(paths) result+=paths 
    Python ist die beste Programmiersprache der Welt.