Moderatorin
Tweet
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
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
Dankeschön! Über den Link habe ich
Kommentar