Optimierung von Graphen

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Optimierung von Graphen

    Hallo Community,

    ich würde gerne gerichtete Graphen (z. B. - aber nicht nur - DB-Modelle) mit PHP verschönern. Mein erster Schritt bestand darin, die Knoten (z. B. Tabellen) spaltenweise so anzuordnen, dass alle gerichteten Kanten (z. B. Fremdschlüsselbeziehungen) nach links zeigen. Ganz links stehen im Falle eines DB-Modells nur Tabellen, die gar keine Fremdschlüssel haben und im Falle eines Klassendiagramms nur Klassen, die von keiner anderen abgeleitet sind. Das funktioniert bis dahin auch wunderbar.

    Schritt 2 soll nun sein, Überschneidungen von Kanten zu vermeiden (komplett verhindern lassen sie sich sowieso nicht in jedem Falle), indem die Knoten innerhalb jeder Spalte (man könnte auch "Abhängigkeitsebene" sagen) umsortiert werden. Im Falle von Klassendiagrammen ist das recht einfach, solange es keine Mehrfachvererbung ist, weil der Graph dann einfach ein Multi-Baum ist, dessen Wurzeln in der Spalte ganz links liegen. Im Falle von DB-Modellen allerdings wird das etwas schwieriger, weil jede Tabelle einen Fremdschlüssel auf mehrere andere haben kann, gleichzeitig aber auch von mehreren anderen referenziert werden kann.

    Jetzt könnte ich die erste Spalte so lassen, wie sie ist und für die zweite alle möglichen Anordnungen durchiterieren und die Anzahl der Kantenüberschneidungen berechnen. Die Reihenfolge mit den wenigsten wird angewandt und dann wird die nächste Spalte sortiert und so weiter. Das halte ich aber für ziemlich unperformant, da es n! Sortierungsmöglichkeiten gibt und man bei 10 Knoten pro Spalte schon mehrere Millionen Möglichkeiten berechnen müsste. Davon abgesehen würde das Ergebnis nicht zwangsläufig das Optimum darstellen, weil es ja eventuell noch überschneidungsärmer gegangen wäre, wenn ich die erste Spalte anders sortiert hätte (was ich aber zu dem Zeitpunkt noch nicht hätte feststellen können). Es sind also im Idealfall auch noch Rückkopplungen zu beachten.

    Kennt jemand einen effizienteren Algorithmus, mit dem man solche Überschneidungen auf ein Minimum reduzieren kann?

    Gruß,

    Amica
    [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
    Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
    Super, danke!
    [/COLOR]

  • #2
    Das Problem ist ja nicht neu. Für Eclipse gibt es zum Beispiel viele grafische Editoren und Visualisierer für UML, DB-Schemata, OO-Hierarchien, Prozesse, Netzwerkdiagramme, etc. Die meisten Plugins benutzen dafür das GEF, welches eine Layout-Komponente mitbringt. Da könnte man sich eventuell einen geeigneten Algorithmus abgucken ...

    gef-layout: Useful Links

    Kommentar


    • #3
      Dankeschön! Über den Link habe ich http://www.graphviz.org/Documentation/TSE93.pdf gefunden, wo das ziemlich gut beschrieben wird.
      [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
      Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
      Super, danke!
      [/COLOR]

      Kommentar

      Lädt...
      X