Ich möchte gerne Graphen darstellen. Ich habe mir selber einen verhältnismäßig stabilen Kreis-Layout Algorithmus gebaut (d.h. die Nachbarn werden in Orbitschalen um einen zentralen Knoten angeordnet). Der Algorithmus basiert auf ... öhm ... Bauernschleue. Was mathematisch korrektes würde mir gut gefallen.

Wie erreicht man unterschiedliche Layouts? (Kreis, Baum, Gleichmäßig verteiltes Netz) Was gibt es sonst noch für Layouts? Würde mich sehr dafür interessieren!

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Wollte nochmal auf meine Nachfrage hinweisen. Habt ihr Infos zu verschiedenen Layouts?

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ich weiß nicht, ob es das ist was du suchst, aber der oben genannte Artikel ist eine gute Anlaufstelle.


mfg

Hmm...Ich dachte eher an Graph-Layouting.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Habe meine Frage mal in einen extra Thread verschoben.

Falls jemanden was dazu einfällt bitte hier rein posten.

Hier hatte ich ein Tutorial dazu gefunden:
http://graphdrawing.org/literature/gd-constraints.pdf

Etwas mehr praxis wäre aber toll.

Hier sieht man verschiedene Layouts: http://www.graphviz.org/Gallery.php

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Hallo Flash,
Du fragst nach der Theorie von allem, deswegen ist es schwer, Dir zu antworten.


******************************************************************************
Was ist ein GRAPH? Wenn ich nicht irre, handelt es sich um zwei Elementmengen zusammen mit einer Zuordnungsvorschrift.

Wieviele Graphen gibt es? Ich denke mal: unendlich viele. Einige hast Du erwähnt: Polygone, Netze, Bäume. Um die Beispiele etwas zu erweitern, "brainstorme" ich jetzt mal:

* die Anordnung der Planeten in einem Sonnensystem
* die Schwingungen eines Pendels
* die Blütenblätter einer Sonnenblume
* der Passgang von Vierbeinern
* die Ordnungskriterien eines Sortierverfahrens
* jede mathematische Funktion (Kegelschnitte, die Mandelbrotmenge,......)
* die Löcher in einem schweizer Käse (mit sehr schwer zu bestimmender Zuordnungsvorschrift )
* .... alles was Dir einfällt, das eine bestimmte (erkennbare) Regelmäßigkeit aufweist, von der man hoffen kann, sie mathematisch in den Griff zu kriegen.


******************************************************************************
Und was ist ein LAYOUT - das ist etwas, was das menschliche Auge als solches erkennt, also jetzt mal nicht unbedingt etwas mathematisches. Aber wenn man es in die obige Definition einsetzt, das ist es ein Graph mit einer visuell erkennbaren (dem menschlichen Auge zugänglichen) Zuordnungsvorschrift.

Vermutlich sind einige von den oben erwähnten Graphen auch Layouts, zum Beispiel die Sonnenblumenblätter, möglicherweise auch die Pendelschwingung, sicherlich die Kegelschnitte, ganz bestimmt die Löcher im schweizer Käse.




Ich glaube, dass eine so allgemeine Formulierung nicht praktikabel sein kann. Wenn Du alle möglichen Layouts in Code umsetzen willst, wirst Du nicht alt genug, um sie alle implementieren zu können.

Und das mit der Bauernschläue nehme ich Dir nicht ab. Kreisförmige Orbitschalen kriegst Du nur, wenn Du eine Kreis-/Kugel-Funktion benutzt. Das ist doch auch mathematisch korrekt.
Traude

Ein Graph besteht aus einer Menge an Knoten/Punkten und einer Menge and Kanten(Verbindung zwischen 2 Punkten)
Die einzig sinnvolle Darstellung die bei allen Graphen funktioniert die mir einfällt ist ein konvexes Polygon.

Als Baum kannst du glaube ich alle nicht zirkulären Graphen darstellen. Bei welchem Knoten du anfängst ist egal, du erhältst immer einen Baum.

_________________

Der "Graph" einer Funktion kann auch eine Kurve sein, inklusive Unstetigkeitsstellen. Ist das keine sinnvolle Darstellung?

Edit: Ich meine, wenn man bedenkt aus welchen Thread dieser Thread ursprünglich herkam. Da ging es um Meshverformung. Du kannst ein Mesh kugelmäßig verformen, aber auch eine Paraboloid-Form benutzen, und eine Parabel ist eine nicht geschlossene Kurve und kann auch nicht als Baum angesehen werden.

Edit2: Ich habe mir schnell ein Mathebuch aus dem Regal geschnappt, darin gibts ein Kapitel "bemerkenswerte Kurven", da gibt es Kurven mit Rückschleifen ("Strophoide") und Schneckenhäuser ("Archimedische Spirale") und solche, die ein wenig an Blütenblätter erinnern (Epizykloide"). Das sind ganz normale Funktionen, teils offen, teils geschlossen. Die geschlossenen bilden zwar ein Polygon, aber kein konvexes.

Ich sagte ja nur dass das konvexe Polygon die einzige Darstellung ist die mir einfällt die für beliebige Graphen ein Sinnvolles Bild ergibt.
Für spezielle Graphen kann es natürlich andere praktischere Darstellung geben, z.B. einen Baum für nichtzirkuläre Graphen.
Der Graph einer funktion ist ja ein extremer Spezialfall eines Graphens, bei der jeder Knoten höchstens 2 Kanten hat. Dazu kommt dass da die Menge der Knoten dann meist unendlich ist, es somit nichteinmal ein Graph im eigentlichen Sinne mehr ist.
http://de.wikipedia.org/wiki/Graph_(Graphentheorie)


// Edit Lossy: Link korrigiert

_________________

@Flash: Du meinst Graphen nach der Graphen-Theorie? In der Wikipedia stehen noch gerichtete Graphen und Graphen mit Mehrfachkanten. Sonst sehe ich da nicht mehr soviel. Du hast von etwas "Praktischem" gesprochen. Wolltest Du eine Implementierung sehen?

Im konkreten geht es mir um ungerichtete Graphen und ja nach der Graphentheorie (Ich war etwas schockiert, was ihr glaubtet was ich will).

Nehmen wir mal den Fall an, dass wir die Nachbarn eines Knoten darstellen wollen. Eine schlichte methode wäre es, den Graph einfach als Netz anzuzeigen, fertig. Schicker wäre es den Graph Kreisförmig anzuzeigen ("zu layouten"), also den Wurzelknoten in die Mitte, die Nachbarn mit entfernung 1 in die erste Schale, die Nachbarn mit entfernung 2 in die zweite orbitschale etc.

Man könnte natürlich auch eine Baumform wählen indem man den Parenttree einer Breitensuche nutzt zum layouten und dann die zusätzlichen Kanten versucht noch dazwischen zu malen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Hallo,

bei den darzustellenden Graphen muss man noch zwischen planaren und nicht planaren Graphen unterscheiden.
Nur planare Graphen lassen sich so in die zweidimensionale Ebene einbetten, dass sich keine zwei Kanten überkreuzen ( aber man kann immerhin beliebige Graphen auf ähnliche Weise in den R^3 einbetten ).

Bäume sind auf jeden Fall schonmal planar, der K_5 ( Vollständiger Graph mit 5 Knoten ) ist ein Beispiel für einen nichtplanaren Graphen.

Die Schwierigkeit liegt dann sicherlich darin, eine möglichst 'schöne' ( am besten gleichverteilte ) Darstellung zu finden.
Bei der Netzstruktur muss man darauf achten, dass benachtbarte Knoten nah beiander liegen ( ist vielleicht garnicht so einfach wie man denkt ).

Ich würde erstmal bei einem bestimmten Knoten anfangen und dann alle Nachbarn gleichmässig auf einem Kreis um diesen Knoten verteilen.
Dann würde ich die Nachbarn so permutieren, dass benachbarte Nachbarknoten nebeneinander liegen, dann die nächste Nachbarschafts-Ebene einzeichnen usw.
Wenn drei dieser Nachbarknoten ein Dreieck bilden wird es allerdings etwas problematisch, dann müsste man den Abstand des mittleren Knotens zum ersten Knoten verkürzen.

Die kreisförmige Anordung funktioniert auch nicht immer, z.B. nicht beim K_4.


Viele Grüße
dj3hut1

Tschuldigung, schocken war nicht beabsichtigt, ich hab Dich offensichtlich nicht recht verstanden.

Wie Du das darstellst, hängt IMHO immer vom speziellen Anwendungfall ab. Ich weiss schon, dass das keine gute Antwort ist. Ich habe selbst so etwas noch nicht implementiert, aber schon oft Diagramme gezeichnet, mit denen ich jemandem etwas klarmachen wollte. Das war für mich immer Schwerarbeit, weil ich meist erst mit dem X-ten Etwurf zufrieden war. Man hat eigentlich immer nur ein DinA-4 Blättchen Papier und soll dort einen komplexen Workflow so darstellen, dass die Ansprechpartner auf Anhieb die wesentlichen Dinge erkennen und damit Entscheidungsgrundlagen haben.

Ich habe meine Zweifel, ob man das maschinell erzeugen kann. Zum Beispiel so ein UML-Diagramm auf automatische Weise. Jedenfalls braucht man dazu denk ich mir zusätzliche Parameter. Das was ich bisher gemacht habe, lief sich meist darauf hinaus, eine bestimmte "Fliess"-Richtung darzustellen, also eine Reihenfolge, wobei durchaus häufig vorkommt, dass indendrin in dem Gebilde eine Rückwärtsschlinge dargestellt werden muss, bevor es wieder seine ursprüngliche Richtung aufnimmt und schlussendlich einem "Ende" zugeführt wird. Das heißt, es wird sich wohl auf einen Graphen hinauslaufen.

Ein Baum ist was Schönes, aber er genügt nicht immer, denn nicht immer haben die Dinge so einen strengen Ablauf. Ein strukturloses Netzwerk ist glaub ich nicht so eine gute Wahl, well es genau das, was man mit so einem Diagramm erreichen willst, nicht tut: Strukturen und Richtungen hervorheben.

Welche art von Darstellung für ein Graph verwendet werden soll, hängt stark vom einsatzgebiet ab.
Es lohnen sich für SceneGraph z.B. baumartige darstellungen(wegen der bessereb Hierachie darstelung), Client/Serversysteme kann man durch Orbitale darstellung wesentlich besser darstellen, Shader/Materials sind Horizontal in Schritten sortiert besser dar zustellen(links der start und rechts das resultat) und KI(states) kann man in Gitterähnlichen anordnungen besser darstellen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Ich will auswählen können wie der Graph dargestellt wird. Ich will einmal sagen: "Jetzt als Netz" und danach "Jetzt mal als Kreis".

Es geht mir darum, ob schon jemand mal z.B. diese "Spring embedded nodes" (so hießen die glaub ich) programmiert hat. Dort wird das Layout über imaginäre Stahlfedern gelöst, die alle in ihren Idealzustand wollen und damit die Knoten zwischen denen sie gespannt sind, in die entsprechende Richtung ziehen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com