Bestimmen der Konnektivität für ein vollständig dynamisches Diagramm mit Einfügen und Löschen von Scheitelpunkten / Untergraphen

8

Ich suche nach einer Lösung für das folgende Problem und frage mich, ob mich jemand auf eine bestehende Forschung zu diesem Thema hinweisen könnte. Ich komme aus einer realen Anwendung von Graphen. Nehmen Sie also Kontakt mit mir auf, wenn meine Terminologie nicht genau stimmt.

Ich habe ein Datenbanksystem, in dem Benutzer Objekte hinzufügen / entfernen / verschieben können, indem sie Beziehungen erstellen / löschen und ändern. Als solches kann ich die Objekte als Eckpunkte in einem Diagramm sehen und die Beziehungen als Kanten und Kanten können abhängig von der Art der Beziehungen (entweder Zusammensetzung, Assoziation oder Aggregation) gewichtet werden.

Aus Sicht des Benutzers kann das Hinzufügen eines neuen Elements mit einem einzigen Klick erfolgen. Unter der Haube erstellt das Programm ein Diagramm mit Objekten, die durch Beziehungen verknüpft sind. Dieses Diagramm wird dann dem Hauptdiagramm hinzugefügt, das die gesamte Datenbank definiert. Das Entfernen eines Elements ist umgekehrt, wenn Verknüpfungen / Kanten getrennt werden und der Graph zu zwei disjunkten Graphen wird, wobei 1 die Datenbank ist und der andere aus Eckpunkten besteht, die vom Element und seinen Unterelementen gebildet werden.

Ich brauche einen sehr schnellen Weg, um festzustellen, wann ich disjunkte Graphen habe und wann 2 disjunkte Graphen wieder zu 1 werden. Ich habe einen kurzen Blick auf Holm, de Lichtenberg und Thorup ( 2001 ; pdf ) geworfen . Es scheint der richtige Weg zu sein, aber der Autor hat erwähnt, dass nur ein Diagramm mit einer festen Anzahl von Eckpunkten in Betracht gezogen wird. Fragen Sie sich nur, ob sich Algorithmen normalerweise auf das Hinzufügen / Entfernen von Scheitelpunkten erstrecken, indem Sie das Hinzufügen von Kanten nur schrittweise durchführen? Oder gab es Arbeiten, die speziell auf ein solches Szenario zugeschnitten waren?

ds.algorithms graph-theory dynamic-algorithms Thuan Seah Tan
quelle

Antworten:

4

Dies ist überhaupt keine triviale Frage. Eines der Probleme, bei denen Sie Algorithmen dafür finden, ist die Unterbrechung (Wortspiel beabsichtigt) der Arbeit an dynamischen Graphen. Die Arbeit von Thorup et al. (Die, die Sie erwähnen) ist wahrscheinlich der beste Anfang für die Art von Dingen, die Sie suchen.

Sie können auch Bhadra & Ferreira ausprobieren. Wahrscheinlich werden sie für das, was Sie wollen, etwas vom Thema abweichen, aber sie haben Verweise auf anderes Material, das nützlich sein könnte.

Luke Mathieson
quelle
1

Die Vertex-Aktualisierungen können mithilfe von Kantenaktualisierungen wie folgt behandelt werden (obwohl sie etwas ineffizient sind, da deg (u) die Kantenaktualisierungsfunktion aufruft):

AddVertex(G,u,Adj(u)):- 
  /* Adj(u) is the vertices adjacent to u after adding u */  
  For each v in Adj(u) do 
    AddEdge(G, (u,v))

DeleteVertex(G,u):- 
  For each v in Adj(u) do
    DeleteEdge(G, (u,v))

Thorup et. Die Laufzeitanalyse von Al besagt, dass die Aktualisierungszeit die Amortisationszeit pro Kantenaktualisierung ist. Es impliziert also keine Poly direkt. Ergebnis der logarithmischen Aktualisierungszeit unter Scheitelpunktaktualisierungen.

Es gibt einige Arbeiten, bei denen der Aktualisierungsvorgang auch das Löschen von Scheitelpunkten / Hinzufügungen unterstützt. In [1] für das Problem "Dynamisch alle Paare kürzeste Pfade" ermöglichen sie grundsätzlich die Aktualisierung von Kanten, die auf einen Scheitelpunkt fallen, indem sie die neuen Gewichte angeben. Wir können sie alle auf + unendlich aktualisieren, um einen Scheitelpunkt zu löschen und auf ähnliche Weise einen Scheitelpunkt hinzuzufügen.

Die Referenzen [2] und [3] sind möglicherweise hilfreich, wenn Sie gerade erst mit dynamischen Diagrammalgorithmen beginnen. [2] gibt einen guten Überblick über aktuelle Ansätze für dynamische Konnektivitätsprobleme.

Verweise

  1. Ein neuer Ansatz zur Dynamik Alle Paare kürzeste Wege, Demetrescu. et. Al, JACM 2004 Voume 51, Ausgabe 6, 2004

  2. Folie des Vortrags über dynamische Graph-Algorithmen von Dr. Surender Baswana im Workshop "Jüngste Fortschritte bei Datenstrukturen und Algorithmen" am IMSc in Chennai.

  3. Camil Demetrescu und Pino Italiano, Dynamische Graphen, Handbuch zu Datenstrukturen und -anwendungen, Kapitel 36. Dinesh Mehta und Sartaj Sahni (Hrsg.), CRC Press Series, in Computer and Information Science, Januar 2005. [Entwurf (pdf)]

Rizwanhudda
quelle