Idee zur Sortierung von Knoten in einem Graphen[fertig]

[corpsman]

guten Morgen,

Ich hab mal wieder was Programmiert und nu gehen mir die Ideen aus.

Es geht um die Graphische Darstellung von Unit Abhängigkeiten eines Projektes.

Ich habe mir also ein kleines Tool gebastelt, welches aus den Units eines Projektes einen Graphen aufbaut (siehe Anhang ).

Rot bedeutet hierbei = Unit wurde unter Implementation eingebunden
Schwarz = Unit wurde über Implementation eingebunden

Beginnt die Bezierkurve unten an der Ellipse heist dies dass die Unit am anderen Ende von der Start Ellipse eingebunden wurde ( Pfeile werde ich noch machen ..)

Mein Problem ist nun, dass ich einfach nicht so recht weis, wie ich die Knoten zu Beginn "Vorsortieren" kann.

Mein bisheriger Ansatz scheitert komplett ( Ebenfalls Anhang )

Hat jemand von euch eine Idee wie ich den Graphen einigermaßen entwirren kann ?

Klar ist das ich ihn nur seltenst Planar kriege.

[Keifor]

Ich habe mich vor einiger Zeit mal mit verschiedenen Placement Engines wie bsp. in Graphviz befasst und muss sagen, das ist ein hartes Problem.

Die Layout Engines benutzen in der Regel irgendwelche kranken Graphenalgorithmen zur Bewertung, Sortierung und Anordnung, evt. auch noch zur Gruppierung von Clustern/Zyklen etc. D.h. dafür müßte man wahrscheinlich das ein oder andere Paper lesen um eine "wirklich" gute Lösung zu finden, oder einfach ein existierendes Packet wie Graphviz als backend/Bibliothek nutzen (bsp. für Graphviz könnte man DOT generieren, das ganze durch eine der Layout Engines jagen und XDOT genieren lassen. XDOT enthält dann Koordinaten (für knoten) und Kurvenbeschreibungen für Pfade ).

Eine oft genutzter Ansatz ist das 2-dimensionale Bewerten mittels Anzahl der Abhängigkeiten und respektive Anordnung/Gruppierung in Horizontaler und Vertikaler Richtung (z.B. auf einem Gitter, wobei Kurvenpunkte der Bezierkurven ebenfalls als Knoten im Gitter gesetzt werden können um möglichst das gruppieren/parallele überschneiden von Pfaden zu verhindern). Für diesen Ansatz ergeben sich bei deiner Beschreibung 3. Hauptprobleme:
1. Anordnung der Units (Untereinander in Abhängigkeit)
2. Anordnung so dass möglichst wenig Unit Knoten auf einem nicht zugehörigen Pfad liegen (wie in deinem 2ten Bild: Unit uncommenter liegt auf mehreren nicht zugehörigen Pfaden)
3. Anordnung von Zyklen (schweres Problem)

Vernachlässigt man das 3te Problem erstmal, dann könnte (ist jetzt nur ein Entwurf, müsste man alles Nachweisen) die Anordnung durch Abhängigkeitssortierung in der Vertikalen und Freiraumanordnung in der Horizontalen gelöst werden. Abhängigkeitssortierung ist wie gesagt wegen der Möglichkeit von Zyklen etwas Problematisch und wird daher auch vereinfacht.

Eine grobe Lösungsidee entsprechend:
1. Priorisieren einer Abhängigkeit (Interface oder Implementation, so das immer nur eine der Abhängigkeiten zur Anordnung genutzt wird). Vertikale Anordnung durch Zuweisung von y-Positionen in Abhängigkeit der Abhängigkeiten. Also Bspw. Breitensuche Durchlauf, Zyklen ignorieren, jede Unit in eine "y-Ebene" packen, so dass die Abhängigen Units über dieser Ebene liegen.
2. Erzeugen von Pseudo-Abhängigkeiten: bspw. Unit x liegt in Ebene y1, die Abhängigkeit Unit x2 liegt in Ebene y2 (zwangsläufig y1 > y2 nach erstem Schritt). wenn y1 > y2-1 dann liegt wenigstens eine Ebene "dazwischen" . Für diese Ebenen werden Zwischenabhängigkeiten eingefügt so das jede Unit mit Abhängigkeiten die Abhängigkeit in der Nächsten Ebene hat. (Zur Anordnung der Pfade, damit möglichst wenig Pfadüberschneidungen auftreten werden Pseudo Abhängigkeiten für die Horizontale Anordnung eingefügt)
3. Horizontale Anordnung: Start in Ebene 0, Sortieren der Ebene 1 so das möglichst wenig Überschneidungen zwischen den 2 Ebenen auftauchen (einfachste Lösung: Unitknoten in darüberliegender Ebene hat y1, Abhängigkeiten werden mit y1+ya angeordnet, wobei ya = y-positionsversatz der Unit a)
4. 3. für alle Ebenen durchführen, Pseudoabhängigkeiten entfernen und Kurven durch diese Punkte erzeugen, die restlichen Abhängigkeiten einfügen...

Resultierendes Ergebnis ist eine y/x Ebenenposition Pro Unit und eventuell auch Kurvenpunkte. Diese müssen dann entsprechend noch so umgerechnet werden das Knoten nicht übereinander Liegen etc. Bspw. durch Multiplikation der Maximalen Höhe/Breite.

Problem: das Resultat wird vermutlich sehr groß, sollte aber wenig/keine Überschneidungen liefern solange keine Zyklen enthalten sind. Hier und da muss dann etwas gefeilt werden um die Bildgröße zu verringern. Für Zyklen kann man dann knifflige Methoden wie Clustering (Gruppierung von Zyklen und Einbettung in die Ebenensortierung) nutzen..

Das wäre ein relativ einfacher Ansatz, der wahrscheinlich wenig schön aussieht. Aber das Thema der Anordnung ist nun mal sehr komplex.

[corpsman]

Irgendwie hatte ich befürchtet das es keine "Einfache" Lösung gibt.

Habe mich nun dazu entschieden, eine "Kreisförmige Anordnung und die Möglichkeit des Löschens einzelner Knoten ein zu bauen.

Sollte Tatsächlich jemand Interesse an meinem Tool haben, wird wohl noch eine Exportfunktion in ein entsprechendes Format folgen..

Danke Keifor für das bestätigen meiner Befürchtung, irgendwie hatte ich gehofft, dass irgend jemand ganz motiviertes schon eine entsprechende Komponente entwickelt hat..

[carli]

Also ein Weg, eine ordentliche Sortierung zu bekommen ist, dass man sich die verschiedenen Anordnungen (Exponentiell viele) als einen Graphen vorstellt (ein ziemlich großer), bei dem es solche Knoten gibt, die unfertig sind [es fehlen noch Kanten und Knoten] (Zwischenergebnisse) und solchen, die ein gültiger Abhängigkeitsgraph sind [enthalten alle Units und alle Abhängigkeiten] (die Zielknoten). Es besteht immer ein Pfad zu einem neuen Knoten (Knotentyp: Graph), wenn man durch die Hinzugabe einer Linie oder das Hinzufügen eines Knotens den Graph erweitern kann. Die Länge eines Pfades mit Kantenhinzufügung ist die Anzahl der Intersektionen mit anderen Linien, die Länge eines Pfades mit Knotenhinzufügung kann z.B. die "Ungünstigkeit" des Knotens sein.

Über den Graph von Graphen lässt man dann den optimierten Dijkstra-Algorithmus laufen und taddaaa.. sobald ein vollständiger Graph erreicht [betrachtet] wurde, ist der Algorithmus fertig und man hat die Beste Anordnung gefunden.

Noch was: Man sollte natürlich den Graph von Graphen nicht vollständig aufbauen, das sind ja exponentiell viel Möglichkeiten, sondern immer nur so weit generieren, wie man gerade betrachtet.

[corpsman]

@carli,

Der Ansatz ist interessant, aber für mein "kleines Tool" dann doch zu aufwendig. Ich denke ich werde es dem User überlassen die Knoten zu sortieren...

Trotzdem danke für die lebendige Beschreibung