Starke Zusammenhangskomponente eines Graphen mit SQL erkennen

[GShadow]

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

 

[ukulele]

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.

 

[GShadow]

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.

 

[ukulele]

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.

 

[GShadow]

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.

 

[ukulele]

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?

 

[GShadow]

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
ca 26MB
http://www.dateiupload.com/files/G1VhD6euDG.7z

 

[ukulele]

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.