Tiefensuche, Wie erkennt man Diamantabhängigkeiten?

Question

Ich frage mich, ob jemand einige Hinweise geben kann, wie Diamantenabhängigkeiten überprüft werden, während eine Tiefensuche über ein Diagramm durchgeführt wird ... Ich habe das folgende Diagramm A -> B, A -> F, B -> C, B-> E, C -> D, E -> D.

Ich versuche eine Mietordnung von Containern zu konstruieren, die die angegebene Grafik darstellen, aber wenn ich eine Diamantenabhängigkeit erreiche, bin ich mir nicht sicher, was ich tun soll. Zum Beispiel, in meinem Diagramm, C und E sind beide untergeordnete Container von B, wenn ich auflösen, muss ich C und E verweisen. Kann ich eine Diamantabhängigkeit erkennen und C und E in einem einzigen Container kombinieren?

Answer 1

Ich finde es am einfachsten, Grafikalgorithmen mit Farben zu denken.

Alle Knoten beginnen weiß.

Ein Knoten, der gerade verarbeitet wird, ist grau dargestellt.

Sobald ein Knoten verarbeitet wurde, wird er schwarz dargestellt.

Sie färben einen Knoten grau, sobald Sie darauf stoßen.

Sie färben einen Knoten schwarz, sobald Sie die Verarbeitung der untergeordneten Elemente abgeschlossen haben.

Wenn Sie einen schwarzen Knoten treffen, dann haben Sie eine Diamantabhängigkeit getroffen.

Answer 2

Ich weiß nicht, wie Sie die Knoten des Graphen definieren. Lässt einen Weg sagen um den Knoten zu repräsentieren, wie unten ist -

public interface Node { 
      int getValue(); 
      List<Node> getChildren(); 
     } 

Das Problem bei einer solchen Umsetzung ist - wir haben die Eltern von einem Knoten nicht kennen. Wenn wir eine Möglichkeit haben zu wissen, wer der Paretent eines Knotens ist, können wir die Diamantabhängigkeit herausfinden. In Ihrem Fall sollten wir von der Unterseite des Baumes aus beginnen, und wir können sehen, dass D zwei Parenets hat und sie von B kommen. Also würde ich sagen Build your graph, das kümmert sich nicht nur Kinder, aber auch Eltern. Finde dann in einem Durchgang heraus, welche Knoten mehr als ein Elternteil haben (wie D) und ob diese Parenets (C und E) das gleiche Elternteil (B) haben.

Answer 3

Die Graphentheorie ist ein sehr großes und komplexes Gebiet der Mathematik. Es ist eines dieser Dinge, bei denen ein wenig Wissen eine gefährliche Sache sein kann. Es kann auch schwierig sein, einfache Erklärungen für selbst grundlegende Anwendungen der Graphentheorie zu finden. Die Chancen stehen gut, dass alles, was Sie wahrscheinlich mit Grafiken zu tun haben, zu Tode geprügelt wurde und 5 Mal mehr Fallstricke und Fehler hat, als Sie sich vorgestellt haben, als Sie das Problem gelöst haben.

Ich schätze, Sie werden einige sehr vernünftige Vorschläge hier und dann ein wenig später werden sie als teilweise oder sogar meistens falsch identifiziert werden. Schritt vorsichtig.

Answer 4

Ich bin nicht wirklich sicher, was Sie versuchen zu tun, aber spätestens, wenn Ihr Diagramm Zyklen enthält, müssen Sie wirklich Knoten finden, die Sie während Ihrer Suche wiederholt finden. Normalerweise geschieht dies, indem Sie die Knoten in irgendeiner Weise markieren, während Sie sie bearbeiten, so dass Sie später sehen können, ob Sie sie bereits vorher besucht haben. Wie gut das in Ihrem Fall funktioniert, hängt von Ihrer Implementierung und davon ab, wie diese Knoten aussehen ...

Answer 5

Rohan, da ich manchmal Algorithmen und Datenstrukturen lehre kann ich voreingenommen sein, aber ich vermute, dass Sie in ein Graphalgorithmus-Buch schauen müssen. Es gibt viele verschiedene Möglichkeiten, Dinge zu tun, die dies zu suggerieren scheint, aber es ist nicht ganz klar, was Sie wirklich versuchen, tun. Ja, in diesem Fall haben Sie zwei Knoten mit den eingehenden Kanten und ausgehenden Kanten zu/von denselben Knoten (hier, (B, E), (B, C) (C, D), (E, D)) Es wäre legitim, die beiden Knoten C und E zu einem "C, E" -Knoten zu kombinieren. Es wäre auch legitim, D in D und D zu zerlegen, machen Sie dies zu einem Baum anstelle eines DAG.

Das heißt, es wäre berechtigt, dies zu tun je auf das Problem.

Answer 6

Mit Rohan können Sie die Tiefensuche verwenden, um "Diamantabdrücke" zu erkennen, indem Sie nach Kreuz- oder Vorwärtskanten suchen. Wenn Sie sich die Pseudocode-Implementierung von depth-first-search auf der boost-graph-library-Homepage ansehen.

... else if (Farbe [v] = BLACK) (u, v) ist eine Quer oder Vorderkante ...