Wie mit modifizierten DFS-Algorithmus

Question

ÜBERBLICK

Ich versuche, herauszufinden, zyklische gerichteten Graphen zu durchqueren, wie gerichtet zyklischen Graphen mit irgendeiner Art von DFS iterativen Algorithmus zu durchlaufen. Hier ist eine kleine MCVE Version von dem, was ich zur Zeit umgesetzt wurde (es funktioniert nicht mit Zyklen beschäftigen):

class Node(object): 

    def __init__(self, name): 
     self.name = name 

    def start(self): 
     print '{}_start'.format(self) 

    def middle(self): 
     print '{}_middle'.format(self) 

    def end(self): 
     print '{}_end'.format(self) 

    def __str__(self): 
     return "{0}".format(self.name) 


class NodeRepeat(Node): 

    def __init__(self, name, num_repeats=1): 
     super(NodeRepeat, self).__init__(name) 
     self.num_repeats = num_repeats 


def dfs(graph, start): 
    """Traverse graph from start node using DFS with reversed childs""" 

    visited = {} 
    stack = [(start, "")] 
    while stack: 
     # To convert dfs -> bfs 
     # a) rename stack to queue 
     # b) pop becomes pop(0) 
     node, parent = stack.pop() 
     if parent is None: 
      if visited[node] < 3: 
       node.end() 
      visited[node] = 3 
     elif node not in visited: 
      if visited.get(parent) == 2: 
       parent.middle() 
      elif visited.get(parent) == 1: 
       visited[parent] = 2 

      node.start() 
      visited[node] = 1 

      stack.append((node, None)) 

      # Maybe you want a different order, if it's so, don't use reversed 
      childs = reversed(graph.get(node, [])) 
      for child in childs: 
       if child not in visited: 
        stack.append((child, node)) 


if __name__ == "__main__": 
    Sequence1 = Node('Sequence1') 
    MtxPushPop1 = Node('MtxPushPop1') 
    Rotate1 = Node('Rotate1') 
    Repeat1 = NodeRepeat('Repeat1', num_repeats=2) 

    Sequence2 = Node('Sequence2') 
    MtxPushPop2 = Node('MtxPushPop2') 
    Translate = Node('Translate') 
    Rotate2 = Node('Rotate2') 
    Rotate3 = Node('Rotate3') 
    Scale = Node('Scale') 
    Repeat2 = NodeRepeat('Repeat2', num_repeats=3) 
    Mesh = Node('Mesh') 

    cyclic_graph = { 
     Sequence1: [MtxPushPop1, Rotate1], 
     MtxPushPop1: [Sequence2], 
     Rotate1: [Repeat1], 
     Sequence2: [MtxPushPop2, Translate], 
     Repeat1: [Sequence1], 
     MtxPushPop2: [Rotate2], 
     Translate: [Rotate3], 
     Rotate2: [Scale], 
     Rotate3: [Repeat2], 
     Scale: [Mesh], 
     Repeat2: [Sequence2] 
    } 

    dfs(cyclic_graph, Sequence1) 

    print '-'*80 

    a = Node('a') 
    b = Node('b') 
    dfs({ 
     a : [b], 
     b : [a] 
    }, a) 

Der obige Code ist ein paar Fälle zu testen, wäre die erste eine Art von Darstellung des unten Graph :

das zweite ist der einfachste Fall einer Kurve, die ein "unendlich" loop {a->b, b->a}

ANFORDERUNGEN, die

• Es wird nicht so etwas wie „unendliche Zyklen“, lassen Sie uns existieren sagen, wenn man „unendlichen Zyklus“ gefunden wird, wird es eine maximale Schwelle (global var), um anzuzeigen, wenn sie um diejenigen Looping zu stoppen " pseudo-unendliche Zyklen“
• Alle Graphknoten sind in der Lage Zyklen zu schaffen, aber es wird einen speziellen Knoten Repeat genannt existieren, wo Sie, wie viele Iterationen Schleife um den Zyklus anzeigen kann
• die oben MCVE ich geschrieben habe, ist ein iterativer Version des Traversalalgorithmus, der nicht weiß, wie man mit zyklischen Graphen umgehen kann. Idealerweise würde die Lösung auch iterativ sein, aber wenn es eine viel bessere rekursive Lösung gibt, wäre das großartig.
• Die Datenstruktur, über die wir hier sprechen, sollte nicht "gerichtete azyklische Graphen" genannt werden, weil in diesem Fall jeder Knoten hat seine Kinder bestellt, und in Graphen Knotenverbindungen haben keine Reihenfolge.
• Alles kann mit irgendetwas im Editor verbunden werden. Sie können eine beliebige Blockkombination ausführen, und die einzige Einschränkung ist der Ausführungszähler, der überläuft, wenn Sie eine unendliche Schleife oder zu viele Iterationen ausführen.
• Der Algorithmus wird Anfang/Mitte/nach Knoten Methode Ausführung ähnlich als das obige Snippet

FRAGE

Könnte jemand bieten irgendeine Art von Lösung zu erhalten, die weiß, wie unendlich/endlich Zyklen zu durchqueren?

LITERATUR

Falls die Frage zu diesem Zeitpunkt noch nicht klar ist, können Sie diese mehr über dieses Problem auf diesen article lesen können, wird die ganze Idee, den Traversierungsalgorithmus sein mit einem ähnlichen Werkzeug wie das gezeigt zu implementieren in diesem Artikel.

Hier ist ein Screenshot die ganze Kraft dieser Art von Datenstruktur zeigt, bis ich herausfinden wollen, wie & Lauf zu durchqueren:

Answer 1

Bevor ich beginne, Run the code on CodeSkulptor! Ich hoffe auch, dass die Kommentare aufwendige was ich genug getan habe. Wenn Sie mehr Erklärung benötigen, sehen Sie sich meine Erklärung des rekursiven Ansatzes unter dem Code an.

# If you don't want global variables, remove the indentation procedures 
indent = -1 

MAX_THRESHOLD = 10 
INF = 1 << 63 

def whitespace(): 
    global indent 
    return '| ' * (indent) 

class Node: 
    def __init__(self, name, num_repeats=INF): 
     self.name = name 
     self.num_repeats = num_repeats 

    def start(self): 
     global indent 
     if self.name.find('Sequence') != -1: 
      print whitespace() 
      indent += 1 
     print whitespace() + '%s_start' % self.name 

    def middle(self): 
     print whitespace() + '%s_middle' % self.name 

    def end(self): 
     global indent 
     print whitespace() + '%s_end' % self.name 
     if self.name.find('Sequence') != -1: 
      indent -= 1 
      print whitespace() 

def dfs(graph, start): 
    visits = {} 
    frontier = [] # The stack that keeps track of nodes to visit 

    # Whenever we "visit" a node, increase its visit count 
    frontier.append((start, start.num_repeats)) 
    visits[start] = visits.get(start, 0) + 1 

    while frontier: 
     # parent_repeat_count usually contains vertex.repeat_count 
     # But, it may contain a higher value if a repeat node is its ancestor 
     vertex, parent_repeat_count = frontier.pop() 

     # Special case which signifies the end 
     if parent_repeat_count == -1: 
      vertex.end() 
      # We're done with this vertex, clear visits so that 
      # if any other node calls us, we're still able to be called 
      visits[vertex] = 0 
      continue 

     # Special case which signifies the middle 
     if parent_repeat_count == -2: 
      vertex.middle() 
      continue 

     # Send the start message 
     vertex.start() 

     # Add the node's end state to the stack first 
     # So that it is executed last 
     frontier.append((vertex, -1)) 

     # No more children, continue 
     # Because of the above line, the end method will 
     # still be executed 
     if vertex not in graph: 
      continue 

     ## Uncomment the following line if you want to go left to right neighbor 
     #### graph[vertex].reverse() 

     for i, neighbor in enumerate(graph[vertex]): 
      # The repeat count should propagate amongst neighbors 
      # That is if the parent had a higher repeat count, use that instead 
      repeat_count = max(1, parent_repeat_count) 
      if neighbor.num_repeats != INF: 
       repeat_count = neighbor.num_repeats 

      # We've gone through at least one neighbor node 
      # Append this vertex's middle state to the stack 
      if i >= 1: 
       frontier.append((vertex, -2)) 

      # If we've not visited the neighbor more times than we have to, visit it 
      if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count: 
       frontier.append((neighbor, repeat_count)) 
       visits[neighbor] = visits.get(neighbor, 0) + 1 

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}): 
    visits[node] = visits.get(node, 0) + 1 

    node.start() 

    if node not in graph: 
     node.end() 
     return 

    for i, neighbor in enumerate(graph[node][::-1]): 
     repeat_count = max(1, parent_repeat_count) 
     if neighbor.num_repeats != INF: 
      repeat_count = neighbor.num_repeats 

     if i >= 1: 
      node.middle() 

     if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count: 
      dfs_rec(graph, neighbor, repeat_count, visits) 

    node.end() 
    visits[node] = 0 

Sequence1 = Node('Sequence1') 
MtxPushPop1 = Node('MtxPushPop1') 
Rotate1 = Node('Rotate1') 
Repeat1 = Node('Repeat1', 2) 

Sequence2 = Node('Sequence2') 
MtxPushPop2 = Node('MtxPushPop2') 
Translate = Node('Translate') 
Rotate2 = Node('Rotate2') 
Rotate3 = Node('Rotate3') 
Scale = Node('Scale') 
Repeat2 = Node('Repeat2', 3) 
Mesh = Node('Mesh') 

cyclic_graph = { 
     Sequence1: [MtxPushPop1, Rotate1], 
     MtxPushPop1: [Sequence2], 
     Rotate1: [Repeat1], 
     Sequence2: [MtxPushPop2, Translate], 
     Repeat1: [Sequence1], 
     MtxPushPop2: [Rotate2], 
     Translate: [Rotate3], 
     Rotate2: [Scale], 
     Rotate3: [Repeat2], 
     Scale: [Mesh], 
     Repeat2: [Sequence2] 
    } 

dfs(cyclic_graph, Sequence1) 

print '-'*40 

dfs_rec(cyclic_graph, Sequence1) 

print '-'*40 

dfs({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1) 

print '-'*40 

dfs_rec({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1) 

Der Eingang und der (gut formatiert und eingekerbte) Ausgang kann here gefunden werden. Wenn Sie sehen möchten, wie formatierte ich die Ausgabe, beziehen Sie sich bitte auf den Code, der auch found on CodeSkulptor sein kann.

---

Richtig, auf die Erklärung. Je einfacher, aber viel ineffizienter rekursive Lösung zu verstehen, was ich erklären zu helfen, verwenden werden, folgt:

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}): 
    visits[node] = visits.get(node, 0) + 1 

    node.start() 

    if node not in graph: 
     node.end() 
     return 

    for i, neighbor in enumerate(graph[node][::-1]): 
     repeat_count = max(1, parent_repeat_count) 
     if neighbor.num_repeats != INF: 
      repeat_count = neighbor.num_repeats 

     if i >= 1: 
      node.middle() 

     if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count: 
      dfs_rec(graph, neighbor, repeat_count, visits) 

    node.end() 
    visits[node] = 0 

1. Das erste, was wir tun, ist, den Knoten besuchen. Dazu erhöhen wir die Anzahl der Besuche des Knotens im Wörterbuch.
2. Wir heben dann das start Ereignis des Knotens.
3. Wir überprüfen einfach, ob der Knoten ein kinderloser (Blatt-) Knoten ist oder nicht. Wenn dies der Fall ist, erhöhen wir das Ereignis end und kehren zurück.
4. Nun, da wir festgestellt haben, dass der Knoten Nachbarn hat, durchlaufen wir jeden Nachbarn. Side Note: Ich reverse die Nachbarliste (mit graph[node][::-1]) in der rekursiven Version, um die gleiche Reihenfolge (rechts nach links) der Traversierung von Nachbarn wie in der iterativen Version beizubehalten.
   1. Für jeden Nachbarn berechnen wir zuerst die Wiederholungszahl. Die Anzahl der Wiederholungen wird von den Vorfahrenknoten übernommen (geerbt), sodass die Anzahl der vererbten Wiederholungen verwendet wird, es sei denn, der Nachbar enthält einen Wiederholungszählwert.
   2. Wir erhöhen das middle Ereignis des aktuellen Knotens (nicht der Nachbar), wenn der zweite (oder größere) Nachbar verarbeitet wird.
   3. Wenn der Nachbar besucht werden kann, wird der Nachbar besucht. Die Sichtbarkeitsprüfung wird durchgeführt, indem überprüft wird, ob der Nachbar weniger als a) MAX_THRESHOLD mal (für pseudo-unendliche Zyklen) und b) die oben berechneten wiederholten Zählzeiten besucht wurde.
5. Wir sind jetzt mit diesem Knoten fertig; Erhebe das end Ereignis und lösche seine Besuche in der Hashtabelle. Dies geschieht, damit, wenn ein anderer Knoten es erneut aufruft, die Visitability-Prüfung nicht fehlschlägt und/oder für weniger als die erforderliche Anzahl ausgeführt wird.

Answer 2

Per comment66244567 - Verringerung der Grafik auf einem Baum durch Links zu besuchten Knoten zu ignorieren und eine Breitensuche durchzuführen, da dies eine natürlich wirkende (und wahrscheinlich ausgeglichener) Baum produzieren würde:

def traverse(graph,node,process): 
    seen={node} 
    current_level=[node] 
    while current_level: 
     next_level=[] 
     for node in current_level: 
      process(node) 
      for child in (link for link in graph.get(node,[]) if link not in seen): 
       next_level.append(child) 
       seen.add(child) 
     current_level=next_level 

Mit Ihrem Diagramm und def process(node): print node, dies erzeugt:

In [24]: traverse(cyclic_graph,Sequence1,process) 
Sequence1 
MtxPushPop1 
Rotate1 
Sequence2 
Repeat1 
MtxPushPop2 
Translate 
Rotate2 
Rotate3 
Scale 
Repeat2 
Mesh 

der andere BFS-Algorithmus, iterative deepening DFS (weniger Speicher auf Kosten der Geschwindigkeit verwendet) wird nicht gewinnen Sie irgendetwas in diesem Fall: Da Sie Referenzen zu besuchten Knoten speichern müssen, verbrauchen Sie bereits O (n) Speicher. Weder müssen Sie Zwischenergebnisse produzieren (aber Sie können sowieso - z. B. yield etwas nach der Verarbeitung eines Levels).