Berechnen Sie die relationale Zusammensetzung in

Definitionen: Sei eine DAG ohne Selbstschleifen, und und sind Graphen.$G=(V,E)$$X \subseteq G$$Y \subseteq G$

Input: . Ausgabe: Die relationale Zusammensetzung relationale Zusammensetzung in .$X,Y$ $X \circ Y$$\mathcal{O}(|E||V|)$

• Fall 1:. Zwei for-Schleifen über und : Runtime .$|E| \le |V|$$E(X)$$E(Y)$$\le \mathcal{O}(|E|^2) \le \mathcal{O}(|E||V|)$
• Fall 2:$|V| \le |E|$
  1. Zeichnen Sie den Graphen : . Wir nennen Kanten von schwarz und von rot.$(V(G),E(X) \cup E(Y))$$(O(|V|)+\mathcal{O}(|2E|)))$$E(X)$$E(Y)$
  2. Sortieren Sie es topologisch (Kahn: ). Die erste Ebene sei , und die Kanten wechseln von einer Ebene zu einer höheren Ebene.$\mathcal{O}(|V|) + \mathcal{O}(|E|)$$0$
  3. Zeichnen Sie dieses Diagramm zweimal.
  4. Entfernen Sie in der ersten Kopie jede rote Kante, die auf einer geraden Ebene beginnt, und jede schwarze Kante, die auf einer ungeraden Ebene beginnt: .$\mathcal{O}(E)$
  5. Entfernen Sie in der zweiten Kopie alle "schwarzen geraden" und "roten ungeraden": .$\mathcal{O}(E)$
  6. Für das erste Exemplar:
     • für alle Knoten auf Ebene$u$$2i$
     • für alle Knoten auf Ebene$v$$2i+1$
     • Berichtskante (Laufzeit ).$(u,v)$$\mathcal{O}(V^2) \le \mathcal{O}(EV)$
  7. Für die zweite Kopie: Gleiches gilt für " ".$2i+1$
  8. Vereinigen Sie die gemeldeten Knoten und werfen Sie Duplikate aus (ich hoffe, die Diagrammdarstellung erlaubt dies).$\mathcal{O}(V^2) <= \mathcal{O}(EV)$

Könnten einige von Ihnen bitte meinen Algorithmus überprüfen und prüfen, ob

• das ist richtig
• es ist in$\mathcal{O}(|E||V|)$

Wenn es korrekt ist, "existiert" mein Algorithmus bereits? Wenn nicht, könnten Sie eine Alternative anbieten? Ich werde die erste Antwort akzeptieren, aber positiv bewerten, wenn noch mehr Leute so freundlich sind, dies zu überprüfen.

BEARBEITEN: Schritt 6 Scheint manchmal in . Ich wünschte, das wäre nicht wahr. Hat jemand einen funktionierenden Algorithmus?$O(E^2)$

Das Problem ist in Schritt 6 (nach meinem Verständnis).

Im Wesentlichen sollten Sie nach Sequenzen ob und . Die topologische Sortierung ist korrekt, da in solchen Sequenzen die beiden Kanten nacheinander kommen müssen.$(u,w)(w,v)$$(u,w) \in E(X)$$(w,v) \in E(Y)$

Eine Kante ist schwarz, wenn sie zu . Eine Kante ist rot, wenn sie zu . Eine Kante kann in diesem Fall zwei Farben haben. $(u,w)$$E(X)$$(w,v)$$E(Y)$

Ein Knoten prüft jeden Nachbarn [st ist schwarz], wenn für einen seiner Nachbarn einen roten Rand . In diesem Fall:$u$$w$$(u,w)$$w$$(w,v)$$\sum _{u \in V} deg(u). \sum _{w \in N(x)} deg(w) = O(E^2)$

Soweit ich verstanden habe: Sie haben einige nicht benötigte Kanten gefiltert (Schritt 4,5) - es kann jedoch einen schlimmsten Fall geben, der zu einer höheren Komplexität als . $O(E^2)$

Satz 2.29 auf Seite 60 der Parsing-Theorie von Sippu und Soisalon-Soininen gibt einen Algorithmus zur Berechnung (unter anderem Operationen auf Beziehungen) der Zusammensetzung zweier Beziehungen an. Der Algorithmus läuft in der Zeit , wobei die Zeit ist, die benötigt wird, um Vereinigungs- oder Zuweisungsoperationen an Scheitelpunktsätzen durchzuführen. Das Ergebnis dieser Operation ist eine Menge von Scheitelpunkten pro Scheitelpunkt, die seine Nachbarn darstellen. Dieser Algorithmus arbeitet mit beliebigen Graphen, nicht nur mit azyklischen.$O(t(|V|+|E|))$$t$