php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Entwicklung > PHP Developer Forum
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


PHP Developer Forum Hier habt ihr die Möglichkeit, eure Skriptprobleme mit anderen Anwendern zu diskutieren. Seid so fair und beantwortet auch Fragen von anderen Anwendern. Dieses Forum ist sowohl für ANFÄNGER als auch für PHP-Profis! Fragen zu Laravel, YII oder anderen PHP-Frameworks.

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 23-11-2009, 15:29
AmicaNoctis
  Moderatorin
Links : Onlinestatus : AmicaNoctis ist offline
Registriert seit: Jul 2009
Beiträge: 5.709
Blog-Einträge: 9
AmicaNoctis sorgt für eine eindrucksvolle AtmosphäreAmicaNoctis sorgt für eine eindrucksvolle Atmosphäre
Standard 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
Mit Zitat antworten
  #2 (permalink)  
Alt 23-11-2009, 16:41
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

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
Mit Zitat antworten
  #3 (permalink)  
Alt 23-11-2009, 16:55
AmicaNoctis
  Moderatorin
Links : Onlinestatus : AmicaNoctis ist offline
Registriert seit: Jul 2009
Beiträge: 5.709
Blog-Einträge: 9
AmicaNoctis sorgt für eine eindrucksvolle AtmosphäreAmicaNoctis sorgt für eine eindrucksvolle Atmosphäre
Standard

Dankeschön! Über den Link habe ich http://www.graphviz.org/Documentation/TSE93.pdf gefunden, wo das ziemlich gut beschrieben wird.
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
Dynamische Graphen (mit Graphviz?) calito PHP Developer Forum 1 27-05-2005 13:58
Optimierung von MySQL und PHP Sylvie SQL / Datenbanken 1 29-04-2005 15:10
Optimierung England maio SEO - Suchmaschinen Tricks und Tipps 2 06-04-2005 11:05
objektklasse für graphen Tschebel BRAINSTORMING PHP/SQL/HTML/JS/CSS 1 20-08-2004 22:31
Optimierung... Sky SQL / Datenbanken 2 17-01-2002 23:30

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

ADSMAN V3 - Werbe-Manager ansehen ADSMAN V3 - Werbe-Manager

ADSMAN V3 - mehr als nur ein Bannermanager! Banner, Textanzeigen und PagePeel Manager! Mit ADSMAN PRO haben Sie die Marketinglösung für eine effektive und effiziente Werbeschaltung mit messbaren Ergebnissen. Unterstützt werden Bannerformate in beliebi

25.10.2018 virtualsystem | Kategorie: PHP/ Bannerverwaltung
PHP News und Artikel Script V2

News schreiben, verwalten, veröffentlichen. Dies ist jetzt mit dem neuen PHP News & Artikel System von virtualsystem.de noch einfacher. Die integrierte Multi-User-Funktion und der WYSIWYG-Editor (MS-Office ähnliche Bedienung) ermöglichen...

25.10.2018 virtualsystem | Kategorie: PHP/ News
Top-Side Guestbook

Gästebuch auf Textbasis (kein MySQL nötig) mit Smilies, Ip Sperre (Zeit selbst einstellbar), Spamschutz, Captcha (Code-Eingabe), BB-Code, Hitcounter, Löschfunktion, Editierfunktion, Kommentarfunktion, Kürzung langer Wörter, Seiten- bzw. Blätterfunktion, V

22.10.2018 webmaster10 | Kategorie: PHP/ Gaestebuch
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 07:38 Uhr.