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?

Mittlerweile bin ich meine Grafik eine networkx.Graph-Instanz, aber ich interessiere mich nicht wirklich, wenn zB igraph empfohlen wird.

Danke vielmals!

  • Python: list index außerhalb des bereichs fehler
  • Bestimmen, was tkinter Fenster ist derzeit oben
  • Multi-Versions-Unterstützung für Python-Doctests
  • Fall-Unempfindlichkeit in Python-Strings
  • Verwenden von Sublisten, um neue Listen zu erstellen, in denen sich die Zahlen nicht wiederholen
  • Wie kann man PYTHONPATH-Einstellung eines Eclipse-Pydev-Projekts fortsetzen?
  • Tkinter Entry Widget bleibt in größeren Programmen leer (Python 2)
  • Wie erfasse ich die Passwort-Eingabeaufforderung
  • 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.