Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
26.12.2006, 22:06 Uhr
~TM
Gast

Hallo,

folgendes Programm. Ich habe eine Klasse erstellt die eine Methode "Metix_bel" besitzt. In ihr soll der Bellman-Ford-Algorithmus für die Graphentheorie abgearbeitet werden. Klappt auch wunderbar, wenn es um die einzelnen kürzesten Distanzen geht. Nun möchte ich aber die Wegstrecken der einzelnen Distanzen in einer String-Matrix speichern. Das Problem steckt dabei in:

C++:

outStream.str("");
outStream.clear();
outStream << Edge_source(Edge_pos2id(j)) << "->" << Edge_target(Edge_pos2id(j));
matrix_bel_way[kn_source][Node_id2pos(Edge_target(Edge_pos2id(j)))]+=outStream.str();

Kann mir dabei jemand helfen?

Hier der vollständige Code:

C++:

string graph::Matrix_bel(int a, int b, bool name, string t)
{
if (kn_count==0) throw(error(3));
if (!Node_exists(a)) throw(error(2));
if (!Node_exists(b)) throw(error(2));
Nodes_sorting();
string rueck;
//neue Matrix anlegen
float** matrix_bel;
matrix_bel = new float*[kn_count];
for (int i=0; i<kn_count ; i++) matrix_bel[i] = new float[kn_count];
string** matrix_bel_way;
matrix_bel_way = new string*[kn_count];
for (int i=0; i<kn_count ; i++) matrix_bel_way[i] = new string[kn_count];
//BELLMAN-FORD-ALGORITHM
ostringstream outStream;
for (int kn_source=0; kn_source<kn_count ; kn_source++)
  {
  for (int knoten=0; knoten<kn_count ; knoten++)
    {
    if (knoten==kn_source) matrix_bel[kn_source][knoten]=0; else matrix_bel[kn_source][knoten]=INFINITY;
    }
  for(int i=0; i<kn_count; i++)
    {
    for(int j=0; j<ka_count; j++)
      {
      if (matrix_bel[kn_source][Node_id2pos(Edge_target(Edge_pos2id(j)))] > matrix_bel[kn_source][Node_id2pos(Edge_source(Edge_pos2id(j)))] + Edge_gewicht(Edge_pos2id(j)))
        {
        matrix_bel[kn_source][Node_id2pos(Edge_target(Edge_pos2id(j)))] = matrix_bel[kn_source][Node_id2pos(Edge_source(Edge_pos2id(j)))] + Edge_gewicht(Edge_pos2id(j));
        outStream.str("");
        outStream.clear();
        outStream << Edge_source(Edge_pos2id(j)) << "->" << Edge_target(Edge_pos2id(j));
        matrix_bel_way[kn_source][Node_id2pos(Edge_target(Edge_pos2id(j)))]+=outStream.str();
        }
      /*if (!gr_gerichtet)
        {
        if (matrix_bel[kn_source][Node_id2pos(Edge_source(Edge_pos2id(j)))] > matrix_bel[kn_source][Node_id2pos(Edge_target(Edge_pos2id(j)))] + Edge_gewicht(Edge_pos2id(j)))
          {
          matrix_bel[kn_source][Node_id2pos(Edge_source(Edge_pos2id(j)))] = matrix_bel[kn_source][Node_id2pos(Edge_target(Edge_pos2id(j)))] + Edge_gewicht(Edge_pos2id(j));
          outStream.str("");
          outStream.clear();
          outStream << Edge_target(Edge_pos2id(j)) << "->" << Edge_source(Edge_pos2id(j));// << Node_pos2id(countB);
          matrix_bel_way[kn_source][Node_id2pos(Edge_target(Edge_pos2id(j)))]+=outStream.str();
          }
        }*/
      }
    }
  for (int kn_a=0; kn_a<kn_count ; kn_a++)
    {
    for (int kn_b=0; kn_b<kn_count ; kn_b++)
      {
      if (matrix_bel[kn_a][kn_b]==INFINITY) matrix_bel_way[kn_a][kn_b]=t;
      }
    }
  }
//Rückgabe aus Matrix erstellen
rueck = matrix_bel_way[Node_id2pos(a)][Node_id2pos(b)];
//Matrix loeschen
for (int i=0; i<kn_count; i++) delete[] matrix_bel[i];
delete[] matrix_bel;
for (int i=0; i<kn_count; i++) delete[] matrix_bel_way[i];
delete[] matrix_bel_way;
//Rückgabe
return(rueck);
}

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
27.12.2006, 11:07 Uhr
ao

(Operator)

1. Worin besteht denn das Problem?

2. Dein Code sieht übel aus. Viel zu viele geschachtelte Ausdrücke, sowas hier zum Beispiel:

C++:

matrix_bel[kn_source][Node_id2pos(Edge_source(Edge_pos2id(j)))]

Für Unbeteiligte nicht verstehbar, würde ich sagen, es sei denn, jemand kennt diesen Algorithmus genau.

ao

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
27.12.2006, 14:16 Uhr
~TM
Gast

Ähm, ja... Vorraussetzung ist leider die Kenntnis und das Verständnis des Algorithmus. Muss ehrlich zugeben, dass das jetzt den Rahmen sprengen würde, das zu erklären. Die Frage richtet sich sicherlich an jenige, die da auch nen Durchblick haben

Link:
http://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
27.12.2006, 14:42 Uhr
Guybrush Threepwood
Gefürchteter Pirat
(Operator)

Das ändert aber nichts daran das dein Code sehr schlecht aufgebaut ist.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
28.12.2006, 21:56 Uhr
~TM
Gast

Ok. Und warum? Bin für Kritik immer offen

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
28.12.2006, 22:16 Uhr
Blubber2063

Angefangen davon das du nicht alles eingerückt hast, ist es einfach schlecht alles in eine Funktion(Methode) zu packen. Das ist unleserlich. Generell merk dir einfach mal alles was irgendwie komplexer ist wird in eine Funktion ausgelagert, das steigert die Übersicht enorm.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
28.12.2006, 23:09 Uhr
ao

(Operator)

Nun ja, es spricht schon einiges dafür, den ganzen Algorithmus in einer Funktion zusammenzuhalten, zumal er nicht sehr lang ist.

Was mich viel mehr stört, ist diese enorme Schachtelungstiefe, siehe Posting 002. Das sind drei Funktionsaufrufe ineinander, d.h. das Ergebnis der einen Funktion ist Argument der nächsten, und das letzte Ergebnis wird benutzt, um ein Array zu indizieren. Es gibt keinerlei Plausibilitätsprüfungen, zumindest sehe ich keine. Hast du wirklich im Griff, was da am Ende der Kette rausfällt? Kannst du sicher sein, dass es keine Speicherfehler durch ungültige Indizes gibt? Wie debuggst du das?

BTW, ich kenne Bellman-Ford nicht, verstehe nichts von Graphentheorie, bin noch nicht mal Mathematiker und sollte deswegen, was den Algorithmus selber angeht, wohl besser mein Maul halten. Trotzdem, wenn ich das richtig überfliege, berechnest du die Distanzen von jedem Knoten zu jedem anderen (also m * n Stück) und gibst dann nur eine einzige dieser Distanzen zurück, richtig? Muss das so sein? Ist das nicht ne ziemliche Verschwendung, m*n Ergebnisse zu berechnen, wenn nur eins davon gefragt ist?

Und noch ne Frage: Warum ist das Ergebnis des Algorithmus ein String?

ao

Dieser Post wurde am 29.12.2006 um 01:11 Uhr von ao editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
30.12.2006, 13:33 Uhr
~TM
Gast

Nun ja. Ich habe da sowieso im Laufe der Zeit meinen eigenen "Stil" gefunden, wenn es um das Einrücken geht. Leider muss i hier kritisieren, dass das Forum keine horizontalen Scrollbalken zur Verfügung stellt, deswegen sind einige Zeilen an den Anfang der nächsten Zeile automatisch gerückt.

Für jeden Algorithmus habe ich eine Methode des Graphen. Kam mir am plausibelsten vor.

Das eigentliche Ziel war es einmal noch eine Klasse Matrix zu schreiben und das dann als Rückgabewert zu übergeben, wäre aber von der Zeit net zu schaffen, der Prof hat gesagt: Abgabetermin ist der 9.1. Da ist nichts zu rütteln. Die Algorithmen lasen sich aber am besten mit Matrizen berechnen, daher wird es so auch genuzt, während da nur der entsprechende Teilbereich der Matrix zurückgegeben wird.

Diese Verschachtelungen ... hm... naja. An und für sich sind das ja auch nur Methoden die gewisse IDs zurückgeben. Das Ganze arbeitet ja mit 2 doppelt verketteten Listen (1x für die Knoten, 1x für die Kanten des Graphen). Jeder Knoten un jede Kante besitzt einen Identifier.. so wie auch der Primärschlüssel in einer DB. Dafür sind eigentlich diese Verschachtelungen nötig. Diese Methoden funzen aber einwandfrei.

Der Rückgabewert ist ein String der am Ende so auszusehen hat:
Von Knoten von 1 zu Knoten 5, der kürzeste Weg lautet:
"1->3->4->5" //der String in der Matrix matrix_bel_way[x][y]

Wenn ich den float-Wert auf matrix_bel[x][y] herausnehme funktioniert das auch einwandfrei. Hier befindet sich nämlich die Distanz des kürzesten Weges zusammenaddiert. Beispielsweise:
Von Knooten 1 zu Knoten 5, die Distanz des kürzesten Weges lautet:
520

Die 520 hat er im Algorithmus zusammenaddiert mit den einzelnen Gewichten der Wegstrecken (Kanten) über die man laufen muss, wenn man von Knoten 1 zu 5 kommen will. An un für sich sollte es daher ja leicht sein die Knoten daher zu bestimmen und in die andere Matrix einzufügen. Leider ist dem nicht so

MfG

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: