Kreise verbinden

Hi Leute
folgender Sachverhalt :

Es gibt überschaubar viele Kreise(max etwa 250) und viele davon haben Verbindungen(max etwa 35) zu anderen Kreisen( auch koherente).

Nun Suche ich einen Algorithmus der die Kreise möglichst übersichtlich Platziert und mit einen Polygonzug verbindet.

Übersichtlichkeit ist natürlich subjektiv aber ich denke man könnte sich auf einige punkte festlegen:
-keine überlappungen von Kreisen
-möglichst wenig Kreuzungen der Verbindungen
-keine Verbindungen die durch Kreise hindurch gehen

Ich denke es gibt dafür viele "gute" Ansätze, die abhängig von der Struktur der jeweiligen Daten sind, deswegen freue ich mich auch über jeden Ansatz zu Diskutieren, für welche Daten er am besten geeignet sein könnte.

Gruß A Circle

ps: Mir geht es also hier mehr im die Idee, die Exsistenz von selbstverständlichen Funktionen wie Intersect( Kreis1, Kreis2) , kann als gegeben angenommen werden.

Meine erste Idee :

Man Nimmt den ersten Kreis und schaut zu welchen Kreisen es verbindet werden soll,
und Platziert alle Kreise Rechts vom ersten Kreis Untereinander und macht dies mit jeden Platzierten Kreis wieder, usw.

Praktisch Für Hierarchisch angeordnete Strukturen, aber jemehr es davon abweicht desto unübersichtlicher wird es.

SeppJ

Noch 2 (edit: sind 3 geworden ) Fragen:
1. Was ist ein koherente Verbindung?
2. Irgendwelche sonstigen Einschränkungen? Sonst könnte man die unverbundenen Kreise einfach weit Weg packen.
3. Ist es wichtig, dass es ein Polygonzug ist oder war das nur so gesagt?

Das klingt irgendwie nach einem Standardproblem, einen Graphen so anzuordnen, dass es möglichst wenige Kantenüberschneidungen gibt. Leider kenne ich mich mit Graphentheorie nur sehr oberflächlich aus .

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

SeppJ schrieb:

Noch 2 (edit: sind 3 geworden ) Fragen:
1. Was ist ein koherente Verbindung?
2. Irgendwelche sonstigen Einschränkungen? Sonst könnte man die unverbundenen Kreise einfach weit Weg packen.
3. Ist es wichtig, dass es ein Polygonzug ist oder war das nur so gesagt?

Das klingt irgendwie nach einem Standardproblem, einen Graphen so anzuordnen, dass es möglichst wenige Kantenüberschneidungen gibt. Leider kenne ich mich mit Graphentheorie nur sehr oberflächlich aus .

ups, keine Ahnung wie ich das Reingepackt habe, vergesst mal das Wort
nein, ja man kann die kreise einfach (weit) wegpacken, das endresultat sollte halt übersichtlich sein
Ist es nicht, von mir aus kannst du auch bezierkurven oder splines( oder weis der geier was verwenden, aber Polygonzüge sind einfach zu implementieren.

Meine 2te Idee:
Mann Ordnet alle Kreise kreisförmig an.

Sieht gut aus, wenn es nur wenige Verbindungen gibt, weil sonst man ein risieges wirwar bekommt. Man könnte auch ein bisschen mit der anordnung der Kreise Spielen, einige Verbindungen auserhalb des Kreises(der Kreise) setzen, aber ich denke da stößt man schnell an der Grenze der Übersichtlichkeit.

Das Problem erinnert mich an früher wo ich Große UML-Klassendiagramme machen musste, denke da und zb bei Visualisierung von Neuronalen Netzwerken könnte sowas Anwendung finden

CStoll

Wie sind denn die Verbindungen über deine Kreise verteilt? Gibt es große Gruppen, die miteinander verbunden sind - oder sind es bestenfalls kleine Grüppchen von zwei bis drei Kreisen? Im letzteren Fall kannst du jede Gruppe für sich nehmen und auf einen freien Teil des Bildschirms verteilen.

(bei kleinen Teilgraphen (ca. bis 4 Knoten) ist das Problem eigentlich trivial, ab einer gewissen Graphengröße gibt es Fälle, wo du sie überhaupt nicht ohne Kantenkreuzungen zeichnen kannst)

CStoll schrieb:

Wie sind denn die Verbindungen über deine Kreise verteilt? Gibt es große Gruppen, die miteinander verbunden sind - oder sind es bestenfalls kleine Grüppchen von zwei bis drei Kreisen? Im letzteren Fall kannst du jede Gruppe für sich nehmen und auf einen freien Teil des Bildschirms verteilen.

(bei kleinen Teilgraphen (ca. bis 4 Knoten) ist das Problem eigentlich trivial, ab einer gewissen Graphengröße gibt es Fälle, wo du sie überhaupt nicht ohne Kantenkreuzungen zeichnen kannst)

Sowohl als auch, allerdings ist größer seltener.
Dass es ab einer bestimmten größe Kantenkreuzungen unvermeindlich sind, ist mir bewusst. Ich suche Ideen für intelligente Algorythmen...
Ich denke man kommt bei diesem Problem weiter, wenn man verschiedene spezielle Strukturen Klassifiziert und einen Algo zum findet und lösen entwickelt.

Aber auch allgemeinere Algos kommen, man findet bestimmt zu jeden Algorithmus Best- und worst cases.

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".