Kreise verbinden

Hängt davon ab, wie oft die Kreise mit anderen verbunden sind. Wenn es nicht allzu lange Ketten sind geht folgendes.
Kreise mit den meisten Verbindungen in die Mitte. Kreise mit weniger Verbindungen darum verteilen, so dass Linien vom inneren zu den äußeren gehen.

darf man mal nach dem nutzen fragen? wozu soll das ganze gut sein?
und wie soll man sich die verbindungen der kreise vorstellen, von mittelpunkt zu mittelpunkt oda watt?

SeppJ

häh bahnhof schrieb:

darf man mal nach dem nutzen fragen? wozu soll das ganze gut sein?
und wie soll man sich die verbindungen der kreise vorstellen, von mittelpunkt zu mittelpunkt oda watt?

Er möchte ein Netz aus Knoten und Verbindungen auf eine 2D-Ebene projizieren und dabei möglichst wenige Überschneidungen haben. Nun ist dir Frage, was ist die günstigste topologische Anordnung. Die Kreise und ihre Größe spielen erst hinterher für die Ästhetik eine Rolle.

Jester

Letztlich ist das ein Problem aus dem Bereich Graph drawing. Am einfachsten wäre vielleicht für den Einstieg sowas wie ein Spring-Embedder. Wenn das nicht gut funktioniert muß man evtl. Nochmal genauer hinschaun.

Jester schrieb:

Letztlich ist das ein Problem aus dem Bereich Graph drawing. Am einfachsten wäre vielleicht für den Einstieg sowas wie ein Spring-Embedder. Wenn das nicht gut funktioniert muß man evtl. Nochmal genauer hinschaun.

Danke, werd ich mal nachgucken.
Aber mein Sachverhalt ist eher theoretischer Natur.
Kannst du mir deswegen sagen, wann ein Spring-Embedder besonderst gut geeignet bzw ungeeignet ist?

gruß A Circle

volkard

Was sagen die Kreise und Striche aus?

Eher sowas http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Lattice_of_the_divisibility_of_60.svg/313px-Lattice_of_the_divisibility_of_60.svg.png ? Also es liegt starke Bedeutung irgendwo und man kapiert sie besser, wenn das Bilchen hübsch ist?

Dann ist das grafische hübsche Darstellen von Graphen ein richtig geil unzugängliches ungelöstes spannendes Problem.
Für ein paar Sorten von Graphen gint es gute Lösungen. Meine erste (abgebrochen) Diplomarbeit war, für 10 Klassen von Graphen Hübsche-Bildchen-Mal-Prozeduren zu schreiben. Es gibt ein paar Faustregeln, wie daß Parallelogramme geil sind und man gerne welche macht, auch wenn es mehr Kreuzungen bedeutet. Und natürlich daß man sonst Kreuzungen meidet.

Oder eher sowas?

http://www.google.de/search?um=1&hl=de&biw=896&bih=452&sa=3&q=midmap&btnG=Bilder+suchen&tbm=isch

Die krasse Anzahl der verschiedenen Ansichten, was Übersichtlich ist, erschlägt mich.

Jester

A Circle schrieb:

Danke, werd ich mal nachgucken.
Aber mein Sachverhalt ist eher theoretischer Natur.
Kannst du mir deswegen sagen, wann ein Spring-Embedder besonderst gut geeignet bzw ungeeignet ist?

Spring-Embedder sind oft erstaunlich gut darin, unterschiedliche dichte stellen im Graphen voneinander zu trennen. Leider hat man relativ wenig Kontrolle darüber wie der Graph dann letztlich gelayoutet ist, insbesondere garantiert einem keiner, dass die Anzahl der Kreuzungen in irgendeiner Weise klein ist oder Mindestabstände eingehalten werden.

Wenn das nicht reicht bzw. du an der theoretischen Fragestellung interessiert bist, solltest Du genauer spezifizieren was Du eigentlich suchst. Es gibt tausende von verschiedenen Zeichenstilen und sie eignen sich alle unterschiedlich gut für verschiedene Arten von Informationen. In volkards Beispiel-Bild geht es ja um die Teilbarkeit und um das Diagramm zu verstehen, ist es wichtig, dass alle Knoten mit größeren Zahlen weiter oben liegen als die mit kleineren Zahlen, damit die Teilbarkeit immer schön aufwärts gerichtet ist. Wäre derselbe Graph mit einer anderen Bedeutung versehen (oder ganz ohne Bedeuting), würde man das vielleicht eher sein lassen und stattdessen versuchen eine Zeichnung ohne Kreuzungen zu finden. Es kommt also massiv drauf an was man genau haben möchte.

volkard

Jester schrieb:

In volkards Beispiel-Bild geht es ja um die Teilbarkeit und um das Diagramm zu verstehen, ist es wichtig, dass alle Knoten mit größeren Zahlen weiter oben liegen als die mit kleineren Zahlen, damit die Teilbarkeit immer schön aufwärts gerichtet ist.

Und das ist nur die halbe Wahrheit. Gleiche Multiplikationsfaktoren zeigen in die selbe Richting! einself!
Es kommt vor, daß man das man sowas und die Parallelität und die Inhaltsgleichheit erst kapiert, nachdem man den Graphen zurechtgerückt hat, bis er hübsch ist. Durchaus per Hand uns Maus. Hübsch halt, das kann ein Mensch, wenn er viel Zeit hat. Und wenn es wenige Knoten sind.
Hier sind die Richtungen eigentlich Dimensionen und man kann sich locker 20-dimensionale Teilerverbände vorstellen und damit operieren, nachdem man das gesehen hat. Die verschiedenen Richtungen und Längen sind nur Projektionen auf das Zeichenpapier. Wie sagte noch der Mathematiker zum Physiker, der im Symposion den Faden verlor? Ich stelle mit den 26-dimensionalen Raum ganz einfach vor, indem ich mir einen unendlichdimensionalen nehme und auf 26 reduziere. Hübsche Bildchen halte ich für ein wichtiges Werkzeug zum Erkenntnisgewinn. Ganz am Ende ist Verhübschen von Graphen vielleicht wie mathematischer Fortschritt: genauso bitter und zugleich süß, für Rechner prinzipiell völlig unzugänglich.

Jester

volkard schrieb:

Ganz am Ende ist Verhübschen von Graphen vielleicht wie mathematischer Fortschritt: genauso bitter und zugleich süß, für Rechner prinzipiell völlig unzugänglich.

Graph Drawing ist mathematischer Fortschritt: http://en.wikipedia.org/wiki/Graph_drawing
Es gibt einige sehr gute Verfahren zum Zeichnen von Graphen, aber man muß schon festlegen was man haben möchte, einen Algorithmus "Zeichnung machma_huebsch(Graph)" gibt's natürlich nicht.

berniebutt

Bei mir scheitert das Verständnis schon bei der Frage 'Kreise verbinden'. Jeder Kreis hat einen Mittelpunkt und einen Radius und ist damit eindeutig definiert. Was soll da jetzt wie verbunden werden oder nicht verbunden sein? Bitte genauer erklären!

berniebutt schrieb:

Bei mir scheitert das Verständnis schon bei der Frage 'Kreise verbinden'. Jeder Kreis hat einen Mittelpunkt und einen Radius und ist damit eindeutig definiert. Was soll da jetzt wie verbunden werden oder nicht verbunden sein? Bitte genauer erklären!

Ok, da habe ich mich villeicht etwas undeutlich ausgedrückt...
Also ich habe Daten die in Beziehung stehen:

class Data
{
  /*Data*/
  Vector<Data*> RelatedData;
};

Nun möchte ich die Daten mithilfe von Kreisen mit einen anhand der Daten berechneten Radius(wobei dieser eine Untergeordnete rolle spielt) und der Assoziationen RelatedData, mithilfe von Polygonzügen(oder was anderem) verbinden.
Das Endergebnis sind viele Kreise mit vielen Strichen von Kreisrändern zu anderen Kreisrändern.
Was ich nun suche, sind intelligente Algos die, die Kreise möglichst günstig Topoligisch anordnen und möglichst geschiekt die geforderten verbindungen(-slinien) berechnet um Übersichtlichkeit in diese "abstrakte" struktur "Data" zu schaffen.

berniebutt

A Circle schrieb:

Ok, da habe ich mich villeicht etwas undeutlich ausgedrückt...
Also ich habe Daten die in Beziehung stehen:
class Data
{
  /*Data*/
  Vector<Data*> RelatedData;
};

Sich klar ausdrücken, ist oft schon die halbe Lösung! :p Jetzt musst du nur noch erklären, was die 'Beziehung' der Daten untereinander sein soll! Mir fallen da nur Abstände und Winkel ein.

SeppJ

berniebutt schrieb:

Sich klar ausdrücken, ist oft schon die halbe Lösung! :p Jetzt musst du nur noch erklären, was die 'Beziehung' der Daten untereinander sein soll! Mir fallen da nur Abstände und Winkel ein.

Wenn ich das recht verstanden habe, ist die Beziehung "verbunden" und "unverbunden".

Jester

@berniebutt: siehste, wir sind noch mitten in schritt 1.

berniebutt

Jester schrieb:

@berniebutt: siehste, wir sind noch mitten in schritt 1.

Stimmt Schritt 1: Problem erst einmal klar beschreiben und gewünschte Ziele verständlich benennen. Wer ist nun aber 'wir'? Ich kann hier nur rätseln. Und deswegen stellte weitere Fragen bevor ich antworten wollte. Schnelle Lösungen für ein nicht voll verstandenes Problem erscheinen mir unsinnig!

@Fragesteller: Du bist wieder dran!

berniebutt schrieb:

A Circle schrieb:
Ok, da habe ich mich villeicht etwas undeutlich ausgedrückt...
Also ich habe Daten die in Beziehung stehen:
class Data
{
  /*Data*/
  Vector<Data*> RelatedData;
};
Sich klar ausdrücken, ist oft schon die halbe Lösung! :p Jetzt musst du nur noch erklären, was die 'Beziehung' der Daten untereinander sein soll! Mir fallen da nur Abstände und Winkel ein.

SeppJ hat es richtig erkannt :

SeppJ schrieb:

Wenn ich das recht verstanden habe, ist die Beziehung "verbunden" und "unverbunden".

Leider kann ich keine Informationen geben, die die Vielzahl an möglichen Strukturen dieses Netzwerkes einschränken würde.

volkard schrieb:

Was sagen die Kreise und Striche aus?

Eher sowas http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Lattice_of_the_divisibility_of_60.svg/313px-Lattice_of_the_divisibility_of_60.svg.png ? Also es liegt starke Bedeutung irgendwo und man kapiert sie besser, wenn das Bilchen hübsch ist?

Ja

volkard schrieb:

http://www.google.de/search?um=1&hl=de&biw=896&bih=452&sa=3&q=midmap&btnG=Bilder+suchen&tbm=isch

Die krasse Anzahl der verschiedenen Ansichten, was Übersichtlich ist, erschlägt mich.

Leider tauchen in meinem Problem, Hierarchische Beziehungen zu selten auf, aber ab und an trifft man auch auf sowas. Für diese Struktur habe ich ein Lösungsansatz in meinem zweiten Post beschrieben und wird auch momentan als "Fallback"-Routine wenn die Daten ähnlichkeit(momentan werden nur die zurückgehenden und lateraren Verbindungen gezählt und durch die anzahl der "Hierarchischen Kanten" geteilt und mit einem Schwellenwert verglichen,
naja wie auch immer "große"-ähnlichkeit ist selten und viele alternative Topologien habe ich nicht implementiert(mir fehlen Ideen) deswegen ist der Schwellenwert noch relativ groß) Hierarchische Struktur besitzt.

Gruss A Circle

ps:

Ich finde es interessant das solche Probleme ein Mensch theoretisch lösen könnte, aber für einen Computer ein unzugängliches Problem darstellt. Gibt es Erkenntnisse in diesem bereich, mit versuchen einem Neuronalen Netz das schöne anordnen von Graphen beizubringen? - Hat jemand die mittel das zu testen?

CStoll

Kannst du denn wenigstens einen Hinweis geben, was diese "verbunden/nicht verbunden" Beziehung eigentlich darstellen soll? Eventuell hilft das Verständnis der dahinterliegenden Struktur bei der Auswahl eines geeigneten Verfahrens.

CStoll schrieb:

Kannst du denn wenigstens einen Hinweis geben, was diese "verbunden/nicht verbunden" Beziehung eigentlich darstellen soll? Eventuell hilft das Verständnis der dahinterliegenden Struktur bei der Auswahl eines geeigneten Verfahrens.

Leider nicht, die "verbunden/nicht verbunden" Beziehung wird vom User bestimmt und das Programm wird mit Daten gefüttert und ich darf die Daten Visualisieren.
Je nach Problemstellung kann das Programm für Mindmaps, UML-Diagramme, Künstliche Neuronale Netze oder einfach abstrakte Graphen zur Auswertung verwendet werden.

Die Lösung für Mindmaps und künstliche Neuronale Netzte sind die einfachsten da die anzahl der klassifizierbaren Strukturen überschaubar ist.
Wobei es bei Neuronalen Netzwerken auch mal paar schwierige "ausreiser" vorkommen...
UML-Diagramme sind auch noch machbar, wenn man die unterschiedlichen Verbindungen(Assoziationen[lateral], Vererbung[hierarchisch]) getrennt analysiert und anschliesend die ergebnisse zusammenträgt(und den einen oder anderen Kompromiss eingeht(wegen den []-annahmen).

Aber bei den allgemeinen Graphen oder anderen, nicht von mir genannten Netzwerken, versagt mein Programm zu wenige Netzwerke klassifiziert und schön-zeichnen-Prozeduren kennt.

volkard

A Circle schrieb:

Ich finde es interessant das solche Probleme ein Mensch theoretisch lösen könnte, aber für einen Computer ein unzugängliches Problem darstellt.

Ein Mensch kann leider auch nicht das hübschere Graphenbildchen des K4 zwischen http://mathestuff.de/files/k4kl.png und http://upload.wikimedia.org/wikipedia/commons/thumb/5/59/Complete_graph_K4.svg/210px-Complete_graph_K4.svg.png herausfinden, wenn er nichts über die dargestellten Daten erfahren darf!
Das eine ist kreuzngsfrei. Das andere betont, daß keine der vier Ecken eine besondere Lage hat. Jede dieser Eigenschaften kann je nach Anwendung wichtiger sein.

Was ich mit der mathematischen Forschung meinte, war: Könnte der Computer es schaffen, beliebige Graphenbildchen zu zurechtzurücken, daß sie hübsch sind, dann könnte er automatisiert mathematische Forschung betreiben. Und das ist möglicherweise prinzipiell nicht möglich.

Wenn Dein Programm den Zweck hat, den Menschen beim Überlegen zu unterstützen, mußt Du wohl dem Benutzer viele Knöpfe anbieten. Zum Beispiel beim neuronalen Netz Eingangs- und Ausgangsknoten definieren zu können (könnte mir voestellen, daß der Rechner versuchen soll, die an entgegengesetze Ränder zu legen), bei anderen Graphen definieren zu können, daß die Beziehung transitiv ist, auch wenn das nicht dargestellt wird (woraufhin der Rechner vielleicht versucht, durchgehende Richtungen länger beizubehalten), oder bestimmte Kreise als unwichtig zu kennzeichnen (zum Beispiel, damit der Rechner erkennt, daß das (bis auf den einen störenden Knoten) ein Baum ist).

berniebutt

Aha Neuronale Netze - immerhin eine neue Erkenntnis zur Fragestellung! Sind dafür 250 Punkte nicht viel zu wenig?
Für ein zu schreibendes Programm kommt man um klare Festlegungen und Rechenvorschriften nicht herum. Was nicht vorgedacht ist, kann das Programm nicht leisten.

1. Punkt = neuronaler Knoten --> Welche Eigenschaften besitzt ein Punkt (x,y,...)?
2. Benutzer legt Beziehungen fest, aus denen sich Strukturen ergeben --> welche Eingaben sind möglich?
3. Für welche Punkte gelten diese Beziehungen?
4. Sind die Strukturen auf die Punkte oder auf die Beziehungen bezogen?

Jester hat recht: Schritt 1 = Beschreibung des Problems.
Ich fürchte, dass dies nicht gelingt und es somit keine programmierbare Lösung gibt!