Information ausblenden
Willkommen im Forum für alle Datenbanken! Registriere Dich kostenlos und diskutiere über DBs wie Mysql, MariaDB, Oracle, Sql-Server, Postgres, Access uvm

Starke Zusammenhangskomponente eines Graphen mit SQL erkennen

Dieses Thema im Forum "MySQL und MariaDB" wurde erstellt von GShadow, 4 Mai 2012.

  1. GShadow

    GShadow Neuer Benutzer

    Ich besitze leider nur grundlegende SQL Kenntnisse und irgendwie reicht bei mir der RAM im Kopf nicht aus um das Problem per SQL Abfrage zu lösen.

    Ein Starke Zusammenhangskomponente in einem gerichten Graphen bedeutet eigentlich nix anderes als, dat es zu jedem Punkt der zu so einer Komponente gehört sowohl einen Hin- als auch einen Rückweg zu jeden beliebigen anderen Punkt aus der Komponente gibt.

    Beispiel
    Startknoten|Zielknoten
    A->B
    B->C
    C->A
    A->D
    C->B
    E->F

    A,B,C wären in der starken Zusammenhangskomponete D,E,F nicht. Leider enthält der Graph in der Datenbank ca 500.000 solcher Verbindungen und ich würde gerne wissen wie groß die größten/die jeweiligen starken Zusammenhangskomponenten sind.

    Ist sowas überhaupt mit SQL möglich oder muss ich mich da anderweitig umschauen?

    Viele Grüße
     
  2. ukulele

    ukulele Datenbank-Guru

    Das müsste eigentlich in SQL und so gut wie jeder anderen Scriptsprache zu realisieren sein. Allerdings ist das nicht ganz einfach, wenn die Länge der Verbindungen variiert. Als was liegen die Knoten vor, als Buchstaben wie im Beispiel oder als Schlüssel? Gibt es eine eindeutige Zeilen ID (ist diese fortlaufend)? Kommt eine Knotenbezeichnung in mehreren Verbindungen vor? Eventuell brauchen wir eine Hilfstabelle.
     
  3. GShadow

    GShadow Neuer Benutzer

    Die Knoten haben haben eine Eindeutige Bezeichnung von Char(16) in der DB. Real sind es 16 Zeichen in Hex. Sie sind nicht fortlaufend.
    Die Einträge sehen so aus:
    000056874A2A9000 - 303DF4F1E6569019
    000056874A2A9000 - F1938F0A97E64FD9
    000069263735EE6D - C165365B5802F7DD
    00008898832D6D08 - 5AFE51FA22B94D0A
    00008898832D6D08 - 9493707725D1559B
    0000B371C688F8C6 - 15BD0F3F12EF0B6F
    0000B371C688F8C6 - 5F72BADC78BAD808
    0000B371C688F8C6 - B6CB26A8719AA2FE
    0000B9DC0F74243D - C9B9C91A0208BEF6
    000102EA47340487 - 6EA97EFB26358570
    000102EA47340487 - 9F8BE8733378F579
    000102EA47340487 - C802644D4A77234E

    Root-Rechte auf der Maschiene, die es berechnen soll, sind vorhanden.
     
  4. ukulele

    ukulele Datenbank-Guru

    Kommt eine Knotenbezeichnung in mehreren Verbindungen vor? Also kann es sein das ein Knoten in mehreren Verbindungen vorkommt?

    z.B.

    A->B
    B->C
    C->D
    C->E

    würde die Kombination A,B,C,D und A,B,C,E erlauben. Das macht die ganze Sache aber schwiriger.
     
  5. GShadow

    GShadow Neuer Benutzer

    ja , siehe Beispiel im ersten post. Bei deinem Beispiel, würde es allerdings keine starke Zusammenhangkomponente geben, da es keine Rückwege gibt. Allerdings wäre die (nicht starke) Zusammenhangskomponente : ABCDE, weil alle fünf Knoten miteinander irgendwie verbunden wären.

    Ein wenig mathematischer:
    Wenn es also möglich ist, aus einer Gruppen g von Knoten, die mindestens einen Knoten enhält, einen Pfad zu einem weiteren Gruppe g' von Knoten, die mindestens einen Knoten enthält, zu finden, so gehören beide Gruppen g und g' zu einer Zusammenhangskomponente. Gibt es zusätzlich noch einen Pfad (zurück) von g' zu g, so gehören beide Gruppen zu einer starke Zusammenhangskomponente.
     
  6. ukulele

    ukulele Datenbank-Guru

    Das sieht spannend aus aber ist auch verdammt schwer, ich werd mich mal nachher versuchen da rein zu denken. Kannst du mir noch ein paar Testdaten (also die Schlüssel so wie oben) zur Verfügung stellen, in denen alle Fälle, sprich mehrere Kombinationen vorkommen und mir dann sagen, auf wieviel starke Zusammenhangskomponenten ich kommen muss?
     
  7. GShadow

    GShadow Neuer Benutzer

    hier eine Testdatei. Sie ist vollständig. Ich kann dir nur sagen dat die größte starke Zusammenhangskomponente bei ca 50.000 mitgliedern liegt. Wenn ich die Ergebnisse kennen würde müsse ich es ja nicht mehr in sql packen :D
    ca 26MB
    http://www.dateiupload.com/files/G1VhD6euDG.7z
     
  8. ukulele

    ukulele Datenbank-Guru

    Dann wird auch meine Idee scheitern es wie bei meiner Ordnerstruktur zu lösen, 50.000 sind ja schon verdammt viel^^ Vieleicht fällt mir noch was ein.
     

Diese Seite empfehlen

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies.
    Information ausblenden