Graphenprogramm

Renzo

hallo zusammen

ich schreibe gerade an meiner Maturaarbeit (Matura=Abi) über Graphenalgorithmen, nun sollte noch ein praktischer Teil berücksichtig werden.
Dabei würde ich gerne ein Programm in C++ oder C#schreiben, in dem man Knoten (also Punkte) und Kanten (also "Pfeile" zwischen den Knoten) einzeichnen könnte, dann z.B. Dijkstra auswählen und dann würde der Computer den schnellsten Weg bestimmen und die Pfeile so färben, dass der kürzeste Weg ersichtlich wäre....

ich würde gerne so ein "Windows"-mässiges Programm schreiben, mit Fenster und Menu...

ich habe bereits ein wenig Programmierkenntnisse, aber nur in PHP, "Konsolen-C++" und ein wenig JAVA.

Könnt ihr mir irgend ein Buch oder Tutorial empfehlen, mit dem ich diese Aufgaben in "vernünftiger" Zeit (2-3 Monate) schaffen kann?

wäre euch sehr dankbar
mfg
renzo

C++ Forumbot

Dieser Thread wurde von Moderator/in pumuckl aus dem Forum C++ 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.

Blue-Tiger

Eine Grafikbibliothek wie SDL oder SFML koennten dich halbwegs schnell zum Ziel fuehren. Dokus & Tutorials dazu gibts im Internet, recht viel mehr brauchst du nicht. Damit erhaelst du allerdings "nur" ein Fenster zum Reinmalen, keine Buttons etc.

Dafuer braeuchtest du eine vollwertige GUI, sich da einzuarbeiten ist IMO schwieriger und dauert laenger. Im GUI-Forum gibts 'ne FAQ zu den verschiedenen Bibliotheken, die du waehlen koenntest, wenn du's doch versuchen willst.

Auch eine Moeglichkeit: machs mit Java, da gibts eine relativ nette Graphische Oberflaeche, und wenn du C++ und ein bisschen Java eh schon kennst, sollte das machbar sein. Tuts zu Swing (so heisst die GUI-Lib in Java) gibts wie Sand am Meer, ein gutes Buch mit dem man innerhalb von ~1 Monat Java + Swing lernen kann wenn man Vorkenntnisse hat, ist "das Handbuch der Java-Programmierung", gibts gratis im Internet, einfach mal googeln

Jester

Man muß ja auch nicht bei Null anfangen. Für Java gibt es zum Beispiel JUNG: http://jung.sourceforge.net/

Das enthält neben Graphdatenstrukturen und Algorithmen auch schon Komponenten zur Visualisierung.

nman

Ich würde das Tool einfach in ein Konsolenutility und evtl. ein GUI dafür aufteilen und Graphviz oä verwenden: http://graphviz.org/

Also eine Graphenklasse + Dijkstra kann man in Java an einem Nachmittag bequem implementieren. Das Zeichnen eines Graphes dagegen ist eine äußerst komplexe Angelegenheit, da würde ich dir zu einem fertigen Framework raten, denn das ist ein Forschungsgebiet für sich (und die Algorithmen zum Zeichnen sind weitaus komplexer als Dijkstra).

volkard

Graphiker schrieb:

Das Zeichnen eines Graphes dagegen ist eine äußerst komplexe Angelegenheit, da würde ich dir zu einem fertigen Framework raten, denn das ist ein Forschungsgebiet für sich (und die Algorithmen zum Zeichnen sind weitaus komplexer als Dijkstra).

Man zeichnet selber die Punkte und Pfeile mit der Maus ein, da ergibt sich das Problem nicht.

volkard schrieb:

Graphiker schrieb:

Das Zeichnen eines Graphes dagegen ist eine äußerst komplexe Angelegenheit, da würde ich dir zu einem fertigen Framework raten, denn das ist ein Forschungsgebiet für sich (und die Algorithmen zum Zeichnen sind weitaus komplexer als Dijkstra).

Man zeichnet selber die Punkte und Pfeile mit der Maus ein, da ergibt sich das Problem nicht.

Man könnte die Anzahl der Knoten auch einfach auf die nächste Quadratzahl n aufrunden, dann die Zeichenfläche in sqrt(n) x sqrt(n) Plätze unterteilen und in jeden einen Knoten malen. Anschließend die Kanten einfach als Linien von Platz (x,y) nach (x',y') zeichnen

Bashar

***

volkard

Lustiger Kerl schrieb:

Man könnte die Anzahl der Knoten auch einfach auf die nächste Quadratzahl n aufrunden, dann die Zeichenfläche in sqrt(n) x sqrt(n) Plätze unterteilen und in jeden einen Knoten malen. Anschließend die Kanten einfach als Linien von Platz (x,y) nach (x',y') zeichnen

Versuchen wir mal, daß die Kanten sich nicht kreuzen, was natürlich nicht immer geht.
Versuchen wir's mal als Mensch bei
http://www.flashgames.de/index.php?onlinespiele=8836&todo=play
und überlegen uns, wie man das als Programm machen würde.

THE_ONE

Schau dir mal das hier an:
http://farm3.static.flickr.com/2607/3864349687_d717f9fb2b_o.gif
hab das gerade zwecks meiner Diplomarbeit in C# geschrieben.
Sogar Breitensuche hätte ich schon eingebaut.
Dijkstra wäre ne Arbeit von 15min, plus etwas Zeit für die Visualisierung.
Könnte dir ja Codeausschnitte zukommen lassen,wennst möchtest.

Lg THE_ONE

Renzo

THE_ONE schrieb:

Schau dir mal das hier an:
http://farm3.static.flickr.com/2607/3864349687_d717f9fb2b_o.gif
hab das gerade zwecks meiner Diplomarbeit in C# geschrieben.
Sogar Breitensuche hätte ich schon eingebaut.
Dijkstra wäre ne Arbeit von 15min, plus etwas Zeit für die Visualisierung.
Könnte dir ja Codeausschnitte zukommen lassen,wennst möchtest.

Lg THE_ONE

Hallo THE_ONE

das wär für mich natürlich sehr hilfreich, schon alleine wegen der graphischen Implementierung.

eigentlich würde ich mir vorstellen, dass man "Knoten einfügen" auswählt, dann auf dem Fenster "herumklicken" kann und dann auf "Kanten einfügen" klickt und dann auf den Startknoten drückt und dann auf den Endknoten...
die Länge der Kanten müsste ja über die Mausposition einfach zu berechnen sein, dass heisst eigentlich muss ich es erstmal nur schaffen, im laufenden Prozess Bildchen und Linien zu zeichnen und die Maus zu "überwachen". Irgendwie hab ich das Gefühl, das müsste doch "relativ" einfach zu realisieren sein, aber ich komm irgendwie trotz 3 Tutorials nicht drauf, wie ich das machen muss (hab mich mal mit dem MFC versucht)

CPaintDC dc(this);
dc rectangle(x1, y1, x2, y2);

funktioniert ja nur bei CChildView::OnPaint() und das wiederum wird nur beim Fenster zeichnen oder neuzeichnen ausgeführt.
Wie kann ich in das Fenster zeichnen während das Fenster schon gezeichnet wurde?
lg renzo

Jester

nman schrieb:

Ich würde das Tool einfach in ein Konsolenutility und evtl. ein GUI dafür aufteilen und Graphviz oä verwenden: http://graphviz.org/

Sorry, aber graphviz ist von der Zeichenqualität für alles was größer ist als 10 Knoten sowas von unter aller Kanone. Das ist kein Ersatz für ein vernünftiges Framework wie JUNG, yFiles oder notfalls wenigstens die Hand voll Zeichen-Algorithmen in boost.

Jester

volkard schrieb:

Lustiger Kerl schrieb:

Man könnte die Anzahl der Knoten auch einfach auf die nächste Quadratzahl n aufrunden, dann die Zeichenfläche in sqrt(n) x sqrt(n) Plätze unterteilen und in jeden einen Knoten malen. Anschließend die Kanten einfach als Linien von Platz (x,y) nach (x',y') zeichnen

Versuchen wir mal, daß die Kanten sich nicht kreuzen, was natürlich nicht immer geht.
Versuchen wir's mal als Mensch bei
http://www.flashgames.de/index.php?onlinespiele=8836&todo=play
und überlegen uns, wie man das als Programm machen würde.

Obs kreuzungsfrei geht kann man leicht rausbekommen. Allerdings ist es NP-schwer möglichst wenige Knoten zu bewegen: http://arxiv.org/abs/0709.0170v5

nman

Jester schrieb:

Sorry, aber graphviz ist von der Zeichenqualität für alles was größer ist als 10 Knoten sowas von unter aller Kanone. Das ist kein Ersatz für ein vernünftiges Framework wie JUNG, yFiles oder notfalls wenigstens die Hand voll Zeichen-Algorithmen in boost.

Kein Grund, sich zu entschuldigen.
Ist mir bis jetzt noch nicht aufgefallen, weil ich (a) Graphviz typischerweise für kleinere Sachen (Mehr als 10 Knoten, aber offensichtlich nicht "genug".) verwendet habe und (b) keinen direkten Vergleich zu JUNG oä. habe.

Hast Du einen Vergleich parat?

Renzo

ich lass jetzt das Fenster einfach "updaten" also neuzeichnen, funktioniert eigentlich sehr gut, aber ist das ressourcentechnisch vertretbar?