Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

absynth

Gründervater

  • "absynth" is male
  • "absynth" started this thread

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

1

Tuesday, February 25th 2003, 12:10pm

d&a: Graphentheorie oder so?

Hi,

ich habe eine Frage, die sich im weitesten Sinne auf d&a bezieht... Und zwar habe ich eine Anzahl Kanten und eine Anzahl Knoten, aus denen ein Graph erstellt werden soll. Die Verbindung und das ganze Gedöns sind ja klar, nur bräuchte ich einen Algorithmus (Perl, C, Pseudocode, you-name-it), der einen möglichst ästhetischen Graphen aus dieser Menge von Knoten und Kanten erstellt - also zeichnet.
Gibt es sowas? In den Übungen war das Zeichnen der Graphen ja eher "und jetzt zeichnen wir das"-Nebensache; aber da gibt es doch bestimmt irgendetwas, wo ich mich mal einlesen könnte, oder?

Hintergrund der Geschichte ist, daß ich eine gewichtete Sitemap für eines meiner Projekte erstellen will, die für jede Seite (Knoten) alle Links (Kanten) mit der Anzahl der Klicks auf die Links (Gewicht) anzeigt. Das Ganze soll eher Proof-of-Concept als wirkliche Anwendung werden.

--ck
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Tuesday, February 25th 2003, 12:33pm

Quoted

Original von absynth
ich habe eine Frage, die sich im weitesten Sinne auf d&a bezieht... Und zwar habe ich eine Anzahl Kanten und eine Anzahl Knoten, aus denen ein Graph erstellt werden soll. Die Verbindung und das ganze Gedöns sind ja klar, nur bräuchte ich einen Algorithmus (Perl, C, Pseudocode, you-name-it), der einen möglichst ästhetischen Graphen aus dieser Menge von Knoten und Kanten erstellt - also zeichnet.
Gibt es sowas? In den Übungen war das Zeichnen der Graphen ja eher "und jetzt zeichnen wir das"-Nebensache; aber da gibt es doch bestimmt irgendetwas, wo ich mich mal einlesen könnte, oder?
Das hier sieht ganz interessant aus:
http://www.infosun.fmi.uni-passau.de/br/…hl/Kurse/gd_02/
http://www.infosun.fmi.uni-passau.de/Graphlet/

Ansonsten:
http://www.google.com/search?q=Graph+zeichnen+Algorithmus
http://groups.google.com/groups?q=Graph+zeichnen+Algorithmus

Das Thema scheint aber andere als trivial zu sein, sonst würden da wohl keine Vorlesungen zu angeboten werden. Da kommt sicherlich noch einiges an Arbeit auf dich zu.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

3

Tuesday, February 25th 2003, 3:27pm

Das Stichwort heißt "Graphentflechtung" und ist eines der schwierigeren Probleme in der "angewandten" Graphentheorie... have fun.
  • Send private message

absynth

Gründervater

  • "absynth" is male
  • "absynth" started this thread

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

4

Tuesday, February 25th 2003, 4:55pm

Quoted

Original von np
Das Stichwort heißt "Graphentflechtung" und ist eines der schwierigeren Probleme in der "angewandten" Graphentheorie... have fun.


Oh, fein. Wäre ja auch zu einfach, sonst.

Ich würde da erstmal ganz doof rangehen. Ich habe N Knoten, also mache ich ein regelmäßiges N-Eck als Graph; die Linienstärke der Kanten möge mir als Veranschaulichung des Gewichtes dienen. Von da aus kann ich dann ja weiteriterieren oder es sein lassen (z.B. würden sich M geschachtelte N/M-Ecke ja irgendwie anbieten...

Naja, wenn ich mal Zeit habe... gibt's zu sowas ähnlichem vielleicht noch 'ne Vorlesung bei uns oder war's das mit D&A?

--ck
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

5

Wednesday, February 26th 2003, 8:29am

Quoted


Original von absynth
Ich würde da erstmal ganz doof rangehen. Ich habe N Knoten, also mache ich ein regelmäßiges N-Eck als Graph; die Linienstärke der Kanten möge mir als Veranschaulichung des Gewichtes dienen. Von da aus kann ich dann ja weiteriterieren oder es sein lassen (z.B. würden sich M geschachtelte N/M-Ecke ja irgendwie anbieten...

Das könnte in dem Fall sogar gehen, hängt ja sehr stark davon ab, was für Netztopologien man so hat. Vielleicht täte es in dem Fall auch etwas ähnliches wie ein hyperbolischer Baum.

Quoted


Naja, wenn ich mal Zeit habe... gibt's zu sowas ähnlichem vielleicht noch 'ne Vorlesung bei uns oder war's das mit D&A?

Wir machen in GDV I ganz am Anfang sehr oberflächlich etwas in der Richtung, aber nur im Überblickskapitel. Es gibt natürlich die (mathematische) Graphentheorie, aber dort wird Entflechtung allenfalls in den (darauf aufbauenden) Seminaren behandelt.

Vielleicht konzipiere ich einmal ein Labor dafür, wenn ich die Zeit finde; das wäre schon eine gute Idee.
  • Send private message