Anzahl der Nachkommen jedes Knotens in einer DAG

8

1) Gibt es einen besseren Algorithmus als das naive O (| E |. | V |), um die Anzahl der Nachkommen jedes Scheitelpunkts in einer DAG zu berechnen?

2) Gibt es einen Online-Algorithmus, der davon ausgeht, dass Knoten einzeln hinzugefügt werden und eine Verbindung zu einer nicht leeren Teilmenge der vorhandenen Knoten herstellen?

Kontext: Ich interessiere mich für den Fall, dass m = O (n), typischerweise Millionen von Eckpunkten, zig Millionen von Kanten. Alternativ wäre es nützlich, die Anzahl der Nachkommen zu zählen, die auch Senken sind.

Ein probabilistischer Ansatz wäre Min-Hashing, um die Menge der Nachkommen jedes Knotens darzustellen. Die Vereinigung der Min-Hash-Struktur ist trivial, und die Kardinalität der Vereinigung kann aus der Anzahl der Zufälle in den Min-Hashes geschätzt werden.

Ich bin mir jedoch nicht sicher, wie gut sich das bei der Verbreitung der DAG verhalten würde. Intuitiv sieht es so aus, als würden sich Fehler ziemlich schnell verstärken.

Sehr verwandt: /cstheory/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag Und tatsächlich ein Duplikat von: https: // cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability

graph-theory Arthur B.
quelle
Sie haben Ihre Frage geändert. Würde Ihnen O (n ^ 2 + m) für Szenario 1 helfen?
Niklas B.
Es wäre nicht schnell genug, aber ich würde gerne hören, wie Sie es machen.
Arthur B
Ist der Grad Ihrer Knoten begrenzt? Oder haben Sie im Allgemeinen eine Eigenschaft des Diagramms, mit deren Hilfe Sie einen schnelleren Algorithmus entwerfen können? Intuitiv ist eine DAG hier nicht einfacher als ein allgemeiner Graph, da Sie einen allgemeinen Graphen in SCCs zerlegen können, die eine DAG bilden
Niklas B.
1
Ich entschuldige mich für meine vorherige Antwort - das war definitiv falsch!
Templatetypedef
2
Ich würde vorschlagen, dass Sie dies auf CS.stackexchange.com fragen. Meine Intuition ist, dass es ein schwierigeres Problem ist, als es aussieht. Wenn Sie es auf das Problem verallgemeinern, bei dem Sie Knotengewichte haben und für jeden Knoten das erreichbare Gesamtgewicht wissen möchten, ist es durch die von mir erwähnte SCC-Reduzierung mindestens so schwierig wie das gleiche Problem für allgemeine Diagramme. Aber es könnte einige Techniken geben, um die Berechnung für die Art der Graphen zu beschleunigen, mit denen Sie konfrontiert sind
Niklas B.

Antworten:

4
  1. Sortieren Sie die Knoten in Ihrer DAG topologisch .
  2. Stellen Sie für jeden Knoten Nein N.QueryCount = 0.
  3. Für jeden Knoten Nin umgekehrter topologischer Reihenfolge:
    • Stellen Sie ein N.Descendants = {N} U {C.Descendants | C in N.Children}.
    • Ausbeute (N, N.Descendants.Count)aus dem Algorithmus.
    • Wenn N.Parentsleer, können Sie entsorgen N.Descendants.
    • Inkrementieren Sie für jedes CIn . Wenn ja, können Sie entsorgen .N.ChildrenC.QueryCountC.QueryCount == C.Parents.CountC.Descendants

Dies ist natürlich teuer, wenn Ihre Knotengrade groß sind. Die Worst-Case-Komplexität ist möglicherweise nicht wesentlich besser als Ihr nicht spezifizierter "naiver Algorithmus".

Das Problem ist, dass dies ein sehr schwer zu lösendes Problem ist. Angenommen, es gibt eine DAG mit Millionen von Knoten, Millionen von Kanten usw. Ich zeige Ihnen diesen Teil des Diagramms:

A--> B
 \-> C

Wie viele Nachkommen hat A? Die Anzahl der Nachkommen von Bplus die Anzahl der Nachkommen von Cminus der Anzahl der gemeinsamen Nachkommen von Bund C. Es ist der dritte Begriff, der die Schwierigkeit schafft. Sie können nicht nur die Anzahl der Nachkommen von Bund kennen C- Sie müssen auch wissen, was die Nachkommen sind.

Timothy Shields
quelle
1
Das scheint mindestens O (n * m) zu sein
Niklas B.
1
Und der naive Algorithmus würde nur die Erreichbarkeit (DFS oder BFS) von jedem Knoten aus durchführen
Niklas B.
@ NiklasB. Wenn die eingestellte Vereinigung O (1) ist, ist dies O (n + m). Set Union ist dies natürlich nicht, aber wenn die Knotengrade relativ niedrig sind, sollte dies hinsichtlich der CPU- und RAM-Nutzung eine gute Leistung bringen. EDIT: Dies ist nicht richtig, bitte ignorieren.
Timothy Shields
1
Ich bin mir nicht so sicher, selbst wenn die Grade niedrig sind, kann es vorkommen, dass viele Eckpunkte viele Nachfolger haben. Für einen unausgeglichenen Binärbaum (zum Beispiel eine Knotenkette) wäre es O (n ^ 2), es sei denn, Sie verwenden Union-by-Weight (aber ich denke, das gibt Ihnen für den allgemeinen Fall nicht viel)
Niklas B. .
@ NiklasB. Oh, richtig, denn die DescendantsMengen werden gegen Ende nahe an O (n) sein.
Timothy Shields
1

Das Auflisten aller Nachkommen aller Scheitelpunkte kann eine Ausgabe der Größe erzeugen. O(n²)Wenn das Diagramm beispielsweise ein lineares Diagramm ist, hat der Scheitelpunkt ohne eingehende Kante n - 1Nachkommen, den folgenden Scheitelpunkt n - 2usw.

Dies lässt die Frage offen, ob Sie die Anzahl der Nachkommen bestimmen können, ohne sie aufzuzählen. Ich kann keinen Beweis liefern, aber ich bin ziemlich sicher, dass die Antwort nein ist. Angenommen, ein Scheitelpunkt xhat untergeordnete Elemente, uund vdann müssen Sie die Kardinalität des Schnittpunkts der Nachkommen von uund ermitteln. vSie wissen jedoch nichts über diese Gruppe - uund vteilen möglicherweise keinen einzelnen Nachkommen, oder sie haben möglicherweise dieselbe Gruppe von Nachkommen .


quelle