BlackBoard (http://www.black-board.net/index.php)
- Design, Programmierung & Entwicklung (http://www.black-board.net/board.php?boardid=55)
-- Programmieren (http://www.black-board.net/board.php?boardid=4)
--- Layoutalgorithmen (http://www.black-board.net/thread.php?threadid=23360)
Geschrieben von phlox81 am 17.05.2008 um 12:53:
Layoutalgorithmen
Hallo,
beschäftige mich gerade mit Layoutalgorithmen, für z.b. Graphen.
Hat jemand mit diesem Thema Erfahrung? Es geht quasi um das Anordnen von Fenstern.
Ich habe verschiedene Rechecke, welche wiederum zu anderen Rechtecken Verbindungen halten können (aber nicht müssen).
Am Anfang sind diese Verbindungen hierarchisch, d.h. aus einzelnen Rechtecken ließe sich ein Baum formen z.B.(A -> B , B -> C, B -> D, A -> E).
Wobei jedes Recheckt seine Verbindungen kennt. In beide Hierarchierichtungen.
Ich habe eine Liste, in der alle Rechtecke liegen, und kann ebenfalls für jedes Rechteck mir die Verbindungen zu anderen Rechtecken holen.
Ich will nun diese Rechecke am geschicktesten in einem Fenster anordnen.
Und dafür suche ich nach Ideen, wie man das am geschicktesten macht, ohne das all zu viel freiraum bleibt, und sich möglichst wenige Verbindungen überkreuzen.
Meine bisherige Idee:
| code: |
1:
2:
3:
4:
5:
|
liste rechtecke = GetShapeList(), rechtecke_ohne_verbindungen = filter(no_conncections,rechtecke);
liste rechtecke_mit_kindern = filter(haschildren,rechtecke);
liste rechtecke_mit_eltern_und_kindern = filter(combine(haschildren, hasparent),rechtecke);
|
|
Problem ist hierbei jedoch die Hierarchie, die ich auch als top down darstellen will.
Ich müsste mir also irgendwie einen Layout graphen basteln, muss jedoch dann beachten, das ich möglichst sinnvoll entstehende Zwischenräume fülle.
Hat jemand eine Idee, wie ich am geschicktesten dieses Problem lösen kann?
phlox
Geschrieben von Xcryon am 17.05.2008 um 21:19:
Hi,
ich vermute ich habe nicht richtig verstanden was genau du machen willst.
Du hast einen Graphen (Mit einem Root-Element?), wobei jeder Knotenpunkt ein Rechteck representiert. Diese Rechtecke möchtest du nun (möglichst kompakt) graphisch darstellen, so das die Herachie der Rechtecke erhalten bleibt. Außerdem sollen die Verbindungen zwischen den Rechtecken dargestellt werden!?
Geschrieben von phlox81 am 17.05.2008 um 21:27:
| Zitat: |
Original von Xcryon
Hi,
ich vermute ich habe nicht richtig verstanden was genau du machen willst.
Du hast einen Graphen (Mit einem Root-Element?), wobei jeder Knotenpunkt ein Rechteck representiert. Diese Rechtecke möchtest du nun (möglichst kompakt) graphisch darstellen, so das die Herachie der Rechtecke erhalten bleibt. Außerdem sollen die Verbindungen zwischen den Rechtecken dargestellt werden!? |
Es gibt kein Rootelement. Mit Root wäre es ja einfach, einfach jede Ebene in die Breite ziehen.
Ansonsten hast du korrekt verstanden, in meiner Datenstruktur habe ich eine Art graph, dessen Knoten durch Rechtecke dargestellt werden sollen.
Die Verbindungen dazwischen sind dann die Kanten.
Wo bei es 4 Verschiedene Knoten gibt:
- Knoten ohne Kante(n).
- Knoten mit Kante(n) nach oben und unten
- Knoten mit Kante(n) nach oben
- Knoten mit Kante(n) nach unten
Die Kanten haben also jeweils eine Richtung.
Das Ganze will ich möglichst effektiv und gut darstellen.
phlox
Geschrieben von Xcryon am 17.05.2008 um 21:48:
| Zitat: |
Wo bei es 4 Verschiedene Knoten gibt:
- Knoten ohne Kante(n).
- Knoten mit Kante(n) nach oben und unten
- Knoten mit Kante(n) nach oben
- Knoten mit Kante(n) nach unten
|
Knoten ohne Kanten würde bedeuten das es Knotengibt die garnicht zu dem Graphen gehören!?
Die anderen 3 Punkte sind Optional, sprich es könnte auch sein das der Graph wie folgt aussieht!?:
[A->B, B->C, C->A]
Wie will man solche ungerichteten Graphen darstellen? Ich könnte mir nur vorstellen das man mit irgend einem Element beginnt und dieses als (Pseudo)Root-Element deklariert. Dann kann man die restlichen Knoten wie einen gerichteten Graphen aufbauen. Stößt man auf einen Knoten welcher auf das (Pseudo)Root-Element verweist muss man halt eine Kant zurück zeichnen.
Ich denke aber das solche Graphen ab einem gewissen Verzwigungsgrad nicht mehr vernünftig visuallisiert werden können.
Wie ist denn die konkrete Aufgabenstellung wenn man fragen darf?
[Edit]
Achso, du meinst wahrscehinlich keine Ebenen-Darstellung, sondern eher sowas:
Geschrieben von phlox81 am 17.05.2008 um 22:11:
| Zitat: |
Original von Xcryon
| Zitat: |
Wo bei es 4 Verschiedene Knoten gibt:
- Knoten ohne Kante(n).
- Knoten mit Kante(n) nach oben und unten
- Knoten mit Kante(n) nach oben
- Knoten mit Kante(n) nach unten
|
Knoten ohne Kanten würde bedeuten das es Knotengibt die garnicht zu dem Graphen gehören!?
Die anderen 3 Punkte sind Optional, sprich es könnte auch sein das der Graph wie folgt aussieht!?:
[A->B, B->C, C->A]
Wie will man solche ungerichteten Graphen darstellen? Ich könnte mir nur vorstellen das man mit irgend einem Element beginnt und dieses als (Pseudo)Root-Element deklariert. Dann kann man die restlichen Knoten wie einen gerichteten Graphen aufbauen. Stößt man auf einen Knoten welcher auf das (Pseudo)Root-Element verweist muss man halt eine Kant zurück zeichnen.
Ich denke aber das solche Graphen ab einem gewissen Verzwigungsgrad nicht mehr vernünftig visuallisiert werden können.
Wie ist denn die konkrete Aufgabenstellung wenn man fragen darf? |
Nein, Ringe und ähnliche spielerreien gibt es nicht.
Eigentlich ist es momentan eher eine Ansammlung von Bäumen, könnte man sagen.
A-F
A -> B, A-> C, B-> D, E -> F z.b.
Ich hänge mal einen Screenshot an. Ich habe jetzt erstmal nach den 4 Sorten gefiltert, und sie dann jeweils in eine Ebene geschmissen. Was sicher nicht optimal ist
Vielleicht sollte ich die Bäume mit Kindern trennen, und jeweils auf ihre Roots die Freien Objekte aufteilen.
phlox
Geschrieben von phlox81 am 18.05.2008 um 14:57:
So, jetzt bin ich etwas weiter, zumindest in der Theorie.
Ich teile zu erst die Liste der Knoten in Knoten die nur Eltern sind (Rootelement damit),
und die restlichen Auf.
| code: |
1:
2:
|
parent (A,B)
C-J |
|
Jetzt verteile ich die Elemente auf die Rootknoten, so das ein Baum ensteht.
| code: |
1:
2:
|
parent (A -> (C, D -> E),B->(F -> H))
G-J |
|
Nun habe ich 2 Bäume (ACDE,BFH), und 3 "Freie" Knoten.
Wenn ich nun den Tiefsten Baum ermittle, weiss ich schon mal wieviele "Etagen" ich in meinem Diagramm abbilden muss (mindestens).
Und in diesen Etagen kann ich nun nach Platz für freie Elemente oder andere Bäume suchen.
Ergebnis könnte dann sein:
| code: |
1:
2:
3:
4:
|
A B I
C D F
E H G
J |
|
Forensoftware: Burning Board 2.3.6, entwickelt von WoltLab GmbH