Algorithmus Sucht zu invertieren (? Reverse Spiegel dreht inside-out) ein DAG

Question

Ich suche nach einem Algorithmus auf "Invert" (? Rückwärtsdrehung inside-out) eine DAG:

 A*  # I can't ascii-art the arrows, so just 
    /\  # pretend the slashes are all pointing 
    B C  # "down" (south-east or south-west) 
    //\ # e.g. 
    G E D # A -> (B -> G, C -> (E -> F, D -> F)) 
     \/
     F 

Die Darstellung, die ich benutze, ist unveränderlich eine echte DAG (es gibt keine "Eltern" -Zeiger). Ich würde gerne den Graph in irgendeiner Weise durchqueren während der Erstellung eines "Spiegelbild" Graph mit äquivalenten Knoten, aber mit die Richtung der Beziehungen zwischen Knoten invertiert.

  F* 
     /\ 
    G* E D # F -> (E -> C -> A, D -> C -> A), G -> B -> A 
    \ \/ # 
    B C  # Again, arrows point "down" 
     \/ # 
     A  # 

Also die Eingabe ist eine Menge von "Wurzeln" (hier, {A}). Die Ausgabe sollte eine Menge von "Wurzeln" in der Ergebnisgrafik sein: {G, F}. (Root meine ich einen Knoten ohne eingehende Referenzen. Ein Blatt ist ein Knoten ohne abgehenden Referenzen.)

Die Wurzeln des Eingangs der Blätter des Ausgangs und Visum wurden versa. Die Transformation sollte eine Umkehrung von sich selbst sein.

(Für die Neugierigen, würde Ich mag eine Funktion zu einer Bibliothek hinzufügen Ich verwende zu XML darstellen für strukturelle Abfrage-, mit dem ich jeden Knoten in der erste Baum zu seinem „Spiegelbild“ Karte kann in der zweite Baum (und zurück wieder) mehr Navigations Flexibilität für meine Abfrage Regeln zur Verfügung zu stellen)

Answer 1

Durchlaufen Sie das Diagramm und erstellen Sie eine Reihe von umgekehrten Kanten und eine Liste von Blattknoten.

Führen Sie eine topologische Sortierung der umgekehrten Kanten durch, indem Sie die Knoten (die jetzt Wurzelknoten sind) als Anfang verwenden.

Konstruieren Sie den umgekehrten Graph basierend auf den umgekehrten Kanten, beginnend am Ende der sortierten Liste. Da die Knoten in umgekehrter topologischer Reihenfolge aufgebaut sind, haben Sie garantiert die Kinder eines bestimmten Knotens vor dem Konstruieren des Knotens konstruiert, so dass eine unveränderliche Darstellung möglich ist.

Dies ist entweder O (N), wenn Sie Strukturen für Ihre Zwischenrepräsentation verwenden, die alle Links in beide Richtungen eines Knotens verfolgen, oder O (NlnN), wenn Sie mithilfe der Sortierung alle Verbindungen eines Knotens finden. Für kleine Graphen oder Sprachen, die nicht unter Stack-Überläufen leiden, können Sie den Graphen nur träge konstruieren, anstatt explizit die topologische Sortierung durchzuführen. Es hängt also ein wenig davon ab, was Sie alles implementieren, wie anders dies wäre.

A -> (B -> G, C -> (E -> F, D -> F)) 

original roots: [ A ] 
original links: [ AB, BG, AC, CE, EF, CD, DF ] 
reversed links: [ BA, GB, CA, EC, FE, DC, FD ] 
reversed roots: [ G, F ] 
reversed links: [ BA, CA, DC, EC, FE, FD, GB ] (in order of source) 
topologically sorted: [ G, B, F, E, D, C, A ] 
construction order : A, C->A, D->C, E->C, F->(D,E), B->A, G->B 

Answer 2

Depth-first search könnte in der Lage sein, zu erzeugen, was Sie nach. Ihr Weg durch den Baum Hinweis und jedes Mal, wenn Sie die Rückseite durchqueren hinzufügen zum resultierenden DAG (Blätter sind Wurzeln).

Answer 3

Führen Sie einfach eine Tiefensuche durch, wo Sie bereits waren, und jedes Mal, wenn Sie einen Pfeil durchlaufen, fügen Sie das umgekehrte Ergebnis zu Ihrem Ergebnis DAG hinzu. Fügen Sie die Blätter als Wurzeln hinzu.

Answer 4

Mein intuitiver Vorschlag wäre, eine Tiefen-Traversierung Ihres Graphen durchzuführen und gleichzeitig Ihren gespiegelten Graphen zu konstruieren.

Wenn Sie jeden Knoten durchlaufen, erstellen Sie einen neuen Knoten im gespiegelten Diagramm und erstellen Sie eine Kante zwischen ihm und seinem Vorgänger im neuen Diagramm.

Wenn Sie an einem beliebigen Punkt einen Knoten erreichen, der keine Kinder enthält, markieren Sie ihn als Root.

Answer 5

Ich löste dies mit einem einfachen Graph Traversal. Beachten Sie, dass die topologische Sortierung nur für gerichtete azyklische Graphen nützlich ist.

Ich habe eine Adjazenzliste verwendet, aber Sie können eine ähnliche Sache mit einer Adjazenzmatrix machen.

In Python sieht es so aus:

# Basic Graph Structure 
g = {} 
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges 

Um alle Kanten für v zu finden, überqueren Sie dann die Liste g [v] und das wird Ihnen alle (v, u) Kanten.

das umgekehrte Diagramm, um den Bau eines neuen Wörterbuch machen und es so etwas wie dieses bauen:

reversed = {} 
    for v in g: 
     for e in g[v]: 
      if e not in reversed: 
       reversed[e] = [] 
      reversed[e].append(v) 

Diese für große Graphen sehr speicherintensiv ist (die Speicherauslastung zu verdoppeln), aber es ist eine sehr einfache Möglichkeit, arbeite mit ihnen und ziemlich schnell. Es gibt vielleicht cleverere Lösungen, die den Aufbau eines Generators und die Verwendung eines dfs-Algorithmus beinhalten, aber ich habe nicht viel darüber nachgedacht.