Algorithmus zum Zeichnen eines Komponentendiagramms

[Oli (Gast)]

Hallo zusammen,

folgendes Problem liegt mir vor:

- Gegeben ist ein Komponentendiagramm einer Modellbasierten Software.
- Dieses enthält Komponenten mit beliebig vielen (>0) Schnittstellen.
- Eine Komponente wird im Diagramm dargestellt durch ein Rechteck.
- Schnittstellen sind Sender, Receiver, Server und Clients.
- Sender und Clients befinden sich am rechten Rand der Komponente.
- Receiver und Server befinden sich am Linken Rand der Komponente.
(Minimalbeispiel siehe Bild im Anhang)
- Abhängigkeiten bestehen zwischen Sendern und Receivern oder Servern 
und Clients. Diese werden durch gerichtete Kanten (gestrichelte Pfeile) 
dargestellt.

Ich suche nun einen Algorithmus, der mir ein Diagramm erzeugt, in 
welchem die Komponenten möglichst geschickt angeordnet sind (geschickt 
im Sinn von möglichst kurze Kanten mit möglichst wenig Kreuzungen) und 
der mir die Kanten so zeichnet, dass diese nicht über die Komponenten 
gezeichnet werden (wie im Minimalbeispiel) sondern daneben und wenn es 
Knicke gibt, so sollen diese rechtwinklig sein.

Im Moment ist mein Ansatz, das Ganze wie einen Graphen mit Knoten (= 
Komponenten) und Kanten (= Abhängigkeiten) zu behandeln und einen 
optimalen Graphen zu finden.

Als Problem dabei sehe ich allerdings noch folgende Dinge:

- Ich habe bei meinen Knoten (= Komponenten) ja mehrere, verschiedene 
Schnittstellen, d.h. nicht alle Abhängigkeiten verlaufen direkt in den 
Knoten sondern in eine bestimmte Schnittstelle.
- Meine Knoten (= Schnittstellen) haben ja eine gewisse räumliche 
Ausdehnung.

Ich hab mir schon gewisse Materialien zum Thema Graphenzeichnen 
durchgelesen, allerdings bin mir grad bzgl. der Auswahl des 
Optimierungsalgorithmus zur Positionierung der Knoten und weiterhin zu 
den o.a. Problemen noch unsicher.

Hat vllt. jemand von euch ein paar Tipps für mich?

Vielen Dank im Voraus!

Freundlicher Gruß
Oli

Ps: Ich hab das Ganze jetzte mal in dieses Forum gepostet, da ich mit C# 
programmiere. Aber das ist ja, denke ich, erst mal gar nicht so wichtig.

[Noch einer (Gast)]

Ist doch letztendlich das selbe Problem, wie ein Autorouter eines 
Platinenlayouts. Die Kollegen im Platinen-Forum vertreten die Meinung, 
keiner der Algorithmen liefert da ein zufriedenstellendes Ergebnis.

[Vlad T. (vlad_tepesch)]

such mal nach der Software "graphviz dot" die erzeugt aus strukturierten 
Textinputs diagramme.
Aber perfekt kann das keine Software.

[Ed (Gast)]

Inspiration evtl. von "yEd"?