Wie kann ich alle Pfade durch eine Reihe von bestimmten Knoten in einem DAG finden?

Question

Ich habe eine Liste von Elementen (blaue Knoten unten), die von den Nutzern meiner Anwendung kategorisiert sind. Die Kategorien selbst gruppiert werden können und kategorisiert selbst.

Die resultierende Struktur kann als gerichteten azyklischen Graphen (DAG) dargestellt werden wo die Elemente Quellen sind Senken am unteren Rand der Topologie des Graphen und die oberen Kategorien. Beachten Sie, dass einige der Kategorien könnten gut definiert werden, viel wird definiert als Benutzer und könnte sehr chaotisch sein.

Beispiel:

_{(Quelle: theuprightape.net )}

Bei dieser Struktur möchte ich die folgenden Operationen ausführen:

• finden Sie alle Artikel (Senken) unter einem bestimmten Knoten (alle Elemente in Europa)
• finden alle Pfade (falls vorhanden), die durch alle von einem Satz von n Knoten (von example.com alle Einzelteile über SMTP gesendet) passieren
• finden Sie alle Knoten, die alle unten eine Menge von Knoten liegen (Kreuzung: goyish braun Lebensmittel)

Die erste scheint recht einfach: an dem Knoten starten, folgt allen möglichen Pfaden auf den Boden und die Gegenstände dort sammeln. Allerdings gibt es einen schnelleren Ansatz? In Erinnerung an die Knoten ich bereits bestanden wahrscheinlich durch unnötige Wiederholungen zu vermeiden hilft, aber gibt es mehr Optimierungen?

Wie gehe ich über die zweite? Es scheint, dass der erste Schritt, um die Höhe jedes Knotens in dem Satz zu bestimmen wäre, wie bei welche (s) zu bestimmen, zu starten und dann alle Pfade unterhalb finden, die den Rest des Satzes umfassen. Aber ist dies der beste (oder sogar ein guter) Ansatz?

Die Graph Traversal-Algorithmen bei Wikipedia aufgelistet alle besorgt zu sein scheinen entweder mit einem bestimmten finden Knoten oder die kürzeste oder anderweitig effektivste Route zwischen zwei Knoten. Ich denke, dass beide nicht, was ich will, oder habe ich nicht nur sehen, wie dies für mein Problem gilt? Wo sonst soll ich lesen?

Answer 1

Es scheint mir, dass seine im Wesentlichen den gleichen Vorgang für alle drei Fragen. Sie fragen immer „Hier finden Sie alle X unter dem Knoten (n) Y, wobei X vom Typ Z“. Alles, was Sie brauchen, ist ein allgemeiner Mechanismus für ‚finden Sie alle Knoten unter dem Knoten‘, (löst Q3) und dann können Sie die Ergebnisse für ‚nodetype = sink‘ (löst Q1) filtern. Für Q2, haben Sie den Ausgangspunkt (Ihr Knotensatz) und Ihren Endpunkt (jede Senke unter dem Ausgangspunkt), so dass Ihr Lösungssatz ist alle Pfade vom Knoten zur Senke angegeben starten. So würde ich vorschlagen, dass, was Sie im Grunde haben ein Baum ist, und grundlegende Baum Traversal-Algorithmen wäre der Weg zu gehen.

Answer 2

die Operationen, die Sie zitieren erinnern mich an ähnlichen Aspekten der Kontrollflussgraphen Analyse

Trotz der Tatsache, dass Ihr Graph azyklisch ist. Es gibt einen umfangreichen Satz von Algorithmen basierend auf Dominanz , die anwendbar sein können. Zum Beispiel erinnert Ihre dritte Operation mich seit der Berechnung Dominanz Grenzen; Ich glaube, dass Algorithmus würde direkt funktionieren, wenn Sie vorübergehend „Eintrag“ einführen und „exit“ Knoten. Der Eingangsknoten verbindet den „gegebenen Satz von Knoten“ und die Ausgangsknoten verbindet die Senken.

siehe

Auch Robert Tarjan der grundlegenden Algorithmen.