Grafischer Algorithmus zur Anordnung von Statecharts
Stefan Schulze
Ich bin auf der Suche nach einem Algorithmus, oder auch nach einem Paper
über einen, um die einzelnen Zustände und Transitionen von Statecharts
optimal anzuordnen.
Ich habe ein Paper [1] gefunden, das einen Algorithmus beschreibt, der etwas
ähnliches macht. Leider ist der nur für "edgeless-Graphen" zu gebrauchen und
zielt leider auch eher darauf ab, die einzelnen "Blobs" gleichmäßig über den
vorhandenen Platz zu verteilen. Leider ist das bei Statecharts ja nicht
immer das Optimale.
Ich hoffe, mir kann da jemand irgendwleche Tips zu geben und seien es nur
Stichwörter, Links, Verweise auf andere Posts, Papers oder Literatur....
CU
Stefan
[1]
"An Algorithm for Blob Hierarchy Layout"
by David Harel and Gregory Yashchin
Dept. of Applied Mathematics and Computer Science
The Weizmann Institute of Science, Rehovot, Israel. April, 1999
Lutz Donnerhacke
> Ich bin auf der Suche nach einem Algorithmus, oder auch nach einem Paper
> über einen, um die einzelnen Zustände und Transitionen von Statecharts
> optimal anzuordnen.
Optimal in welche Hinsicht? Minimale Zustandszahl? Dann "Einführung in die
theroretische Informatik I", Autor beliebig, Verlag beliebig.
Ansonsten ist Sedgwick immer einen Blick wert, und bei Knuth soll der Band
ja nicht vor 2014 erscheinen.
Stefan Schulze
news:slrnavjqr...@taranis.iks-jena.de...
> * Stefan Schulze wrote:
> > Ich bin auf der Suche nach einem Algorithmus, oder auch nach einem Paper
> > über einen, um die einzelnen Zustände und Transitionen von Statecharts
> > optimal anzuordnen.
> Optimal in welche Hinsicht? Minimale Zustandszahl? Dann "Einführung in die
> theroretische Informatik I", Autor beliebig, Verlag beliebig.
Optimal in Hinsicht auf: (den Prioritäten nach sortiert)
- keine Transitionen kreuzen sich
- keine Zustände überlappen sich
- keine Transitionen überlappen sich mit Zuständen (außer wenn eine
Transition an direkt an einen
Zustand in einer anderen Hierarchieebene geht)
- kurze Transitionen
- gleichmäßige Anordnung der Zustände im Diagramm
- ausgewogenes Verhältniss der äußeren Abmessungen der Zustände
Diese Liste ist eine kurze Zusammenfassung dessen, was Harel und Yashchin in
ihrem Paper mit "aestetic drawing" eingehender beschrieben haben.
Ich vermute, du erwähnst die "Einführung in die theoretische Informatik" da
du mein Problem mit FSMs verwechselst? Mein Problem liegt bei den
UML-Statecharts. Daher sollten besser keine Zustände wegfallen... ;-)
CU
Stefan
Lutz Donnerhacke
> Diese Liste ist eine kurze Zusammenfassung dessen, was Harel und Yashchin in
> ihrem Paper mit "aestetic drawing" eingehender beschrieben haben.
Ah! Komplett anderes Problem.
> Ich vermute, du erwähnst die "Einführung in die theoretische Informatik" da
> du mein Problem mit FSMs verwechselst?
Es klang danach. "Statecharts" treten bei eben bei vielen Parsealgorithmen auf.
> Mein Problem liegt bei den UML-Statecharts. Daher sollten besser keine
> Zustände wegfallen... ;-)
Eben. Anderes Problem.
> Optimal in Hinsicht auf: (den Prioritäten nach sortiert)
> - keine Transitionen kreuzen sich
> - keine Zustände überlappen sich
> - keine Transitionen überlappen sich mit Zuständen (außer wenn eine
> Transition an direkt an einen
> Zustand in einer anderen Hierarchieebene geht)
> - kurze Transitionen
> - gleichmäßige Anordnung der Zustände im Diagramm
> - ausgewogenes Verhältniss der äußeren Abmessungen der Zustände
Das riecht nach einem heuristischem Algorithmus, der Positionen vertauschen
kann. So eine Art ganzzahlige lineare Programmierung.