Topologisches Sortieren
-
Erstmal Hi an alle!
Ich bin ralitiv neu in der Programmiersprache C++ und stehe nun vor folgendem Problem.
Zur Bearbeitung der Aufgabe wurde eine Klasse gerichteterGraph, Knoten und Kante gegeben.
/* Grundstrukturen eines gerichteten Graphen 15.11.1997 */ /* die Klassen des Graphen 23.09.1999 */ /* Version f"ur zus"atzliche Algorithmen */ #ifndef _GERICHTETERGRAPH1 #define _GERICHTETERGRAPH1 #include <string> #include <vector> using namespace std; class Knoten; class Kante; class gerichteterGraph { protected: int n,m; // Anzahl Knoten, Kanten vector<Knoten*> alleKnoten; // Feld aller Knoten vector<Kante *> alleKanten; // Feld aller Kanten public: const static int MAXGRAD=10; gerichteterGraph(int nn=10, int maxgrad=4, bool mitkantenbewertung=false, bool kreisfrei=false); // zuf"allig gerichteterGraph(char *datei="daten/graph1.dat"); gerichteterGraph(const gerichteterGraph&); // tiefe Kopie ~gerichteterGraph(void); void ausgeben(char *datei="daten/graph0.dat"); //in Datei Knoten* nrKnoten(int knr)const;//der Knoten mit Nummer knr int Knotenzahl() const {return n;}; // Anzahl der Knoten void knotenausgabe(int bis=50); // sequentiell ausgeben int neuerKnoten(); int neueKante(int von, int nach, double we=1); /* bool topSort(gerichteterGraph *g); bool topSort_I(Knoten *kn, int suchnummer); */ private: // Zuweisung unterbunden // gerichteterGraph& operator=(gerichteterGraph&){} protected: // Hilfsfunktionen int Kantenindex(Kante *kante) const; // Index im Feld int Knotenindex(Knoten *knoten) const; // Index im Feld void neunummerieren(); // der Knoten im Feld void zuruecksetzen(void); // aller Hilfsfelder }; class Knoten { protected: int nr; // die Knotennummer, fortlaufend ab 1 Kante *nachbarn; // Liste der abgehenden Kanten ~Knoten(){}; // soll nur vom Graphen geloescht werden public: Knoten(int num); // au"ser x,y alles auf Null gesetzt friend class gerichteterGraph; int knr(void) const {return nr;} Kante *erste_Kante() const {return nachbarn;} public: // Hilfsfelder f"ur einige Algorithmen // und Anwendungen sowie zur Graphik bool markiert, markiert2; // zum Markieren Knoten *vorgaenger; int hnr; double hwert; // Hilfsnummer, Hilfswert string text; // Zur weiteren Bezeichnung des Knotens int x,y; // bei Graphik: Position des Knotens in der Ebene void zuruecksetzen(void); // einiger Hilfsfelder Kante* Nachbarn() const {return nachbarn;} // mu"s leider sein }; class Kante { protected: Knoten *von; Knoten *nach; Kante *naechste; // na"chste in der Nachbarliste double w; // der Wert bei Kantenbewertung ~Kante(){}; // soll nur vom Graphen geloescht werden public: Kante(Knoten *v, Knoten *n, double we=1): von(v), nach(n), w(we), naechste(0),markiert(0),markiert2(0), text("") {} friend class Knoten; friend class gerichteterGraph; Knoten *vonKnoten() const {return von;} Knoten *nachKnoten() const {return nach;} Kante *naechsteKante() const {return naechste;} void SetzeWert(double wert) { w = wert ;} // Wert der Kante setzen double Wert() const {return w;} // der Wert dieser Kante bool markiert, markiert2; // Hilfsfelder f"ur Anwendungen, string text; // Algorithmen und Graphik }; #endifDie Aufgabe ist eine Topologische Sortierung zu vollziehen, in iterativer weise.
Für die Lösung ist im Skript eine Pseudocode gegeben, dennoch weiß ich nicht ob ich diesen richtig umsetzte. Der Pesudo-Code sieht folgendermaßen aus:Topsort(Graph g)
foreach Knoten kn von g /* Initialisierung /
kn.suchnummer=0 / 0 bedeutet: Suchnummer /
kn.markiert=false / noch nicht vergeben /
SNR=0 / globaler Z"ahler f"ur */
/* die Suchnummer */
foreach Knoten kn von g{
/* jeder unmarkierte Knoten wird als Ausgang
fuer Tiefensuche genommen /
if(kn.markiert=false){
kreisfrei=TopsortI(kn, SNR) / SNR ist ein Rueckgabeparameter */
if(not kreisfrei) return "nicht kreisfrei"
}
}
Ordne Knoten absteigend nach Suchnummern
return "kreisfrei"TopsortI(Knoten kn, SNR) /* SNR ist Rueckgabeparameter /
richte Keller f"ur ein Paar aus Knoten und Kante ein
kn.markiert=true
push(kn, 1.abgehende Kante) / (Knoten, Kante) auf Keller /
while(top()!=0){
p=pop(&ka) / (Knoten, Kante) vom Keller /
if(ka!=0){ / noch Nachbarn zu besuchen /
na=ka.nach / der Nachbar /
ka=ka.naechste / naechste Kante auf Keller /
push(p,ka) / ka=0, falls letzte Kante durchlaufen*/
if(na.markiert=false){
na.markiert=true
push(na,(1.abgehende Kante von na))
}
else if(na.suchnummer=0)
return false /* nicht kreisfrei, da Rueckwaertskante /
}
else{
SNR=SNR+1 / Suchnummernz"ahler erh"ohen /
p.suchnummer=SNR
}
}
return true / also kreisfrei */Meine Umgesetzte Version sieht so aus (ist ja nicht so, als ob ich es nicht versucht hätte, hehe) :
#include <iostream> #include <stack> #include <string> #include <utility> #include "Xgraph.h" using namespace std; int suchnummer; Knoten* tiefensuche(gerichteterGraph *g, int start, int ziel) { Knoten *aktuell(0); Knoten *nachfolger(0); Kante *k(0); stack<Knoten*> keller; aktuell=g->nrKnoten(start); if(NULL==aktuell) { cout << "Knoten konnte nicht gefunden werden!" << endl; return NULL; } aktuell->markiert=true; aktuell->markiert2=true; keller.push(aktuell); while(!keller.empty()) { aktuell=keller.top(); keller.pop(); if(aktuell->knr()!=ziel) { k=aktuell->Nachbarn(); while(NULL!=k) { nachfolger=k->nachKnoten(); if(false==nachfolger->markiert) { nachfolger->markiert=true; k->markiert=true; nachfolger->vorgaenger=aktuell; keller.push(nachfolger); } k=k->naechsteKante(); } } else { Knoten *hilf=aktuell; cout << "Wert :" << endl; while(hilf->knr()!=start) { hilf->markiert2=true; k=hilf->vorgaenger->Nachbarn(); while(k->nachKnoten()!=hilf) { k=k->naechsteKante(); } k->markiert2=true; cout << hilf->knr() << endl; hilf=hilf->vorgaenger; } cout << hilf->knr() << endl; return aktuell; } } return NULL; } bool topSort_I(Knoten *kn,int suchnummer); bool topSort(gerichteterGraph *g) { bool kreisfrei; int i=1; int n=g->Knotenzahl(); for(Knoten* k=g->nrKnoten(i); k!=NULL; k=g->nrKnoten(++i)) { k->hnr=0; k->markiert=false; } i=1; for(Knoten *k=g->nrKnoten(i); k!=NULL; k=g->nrKnoten(++i)) { if(k->markiert=false) { kreisfrei=topSort_I(k,suchnummer); if(!kreisfrei) return false; } } i=1; for(Knoten *k=g->nrKnoten(i); k!=NULL; k=g->nrKnoten(++i)) while(i!=n+1-(k->hnr)) { Knoten *p=k; Knoten *a=g->nrKnoten(n+1-k->hnr); k=a; a=p; } return true; } bool topSort_I(Knoten *kn, int suchnummer) { pair<Knoten*,Kante*> p; stack< pair<Knoten*,Kante*> > keller; p=make_pair(kn,kn->Nachbarn()); keller.push(p); while(!keller.empty()) { p=keller.top(); keller.pop(); if(NULL!=p.second) { Knoten* na=(p.second)->nachKnoten(); p.second=p.second->naechsteKante(); keller.push(p); if(na->markiert==false) { na->markiert=true; keller.push(make_pair(na,na->Nachbarn())); } else if(na->hnr==0) { return false; } } else { suchnummer+=1; (p.first)->hnr=suchnummer; } } return true; } int main(void) { gerichteterGraph *g=new gerichteterGraph(20,5); if(!topSort(g)) cout << "TPS misslang!" << endl; g->knotenausgabe(); delete g; return 0; }Vielleicht könnt ihr mir ein paar Tipps geben bezüglich meiner Übersetzung.
Ich bedanke mich schonmal im Vorraus.
Lg Sfuccma
-
Ich weiß zwar nicht was die eigentliche Frage ist...
Aber du wolltest ja "Tipps".
Überleg mal was der folgende Code macht.gerichteterGraph g;
-
Ich hatte eher auf Tipps gehofft, die sich auf die Umsetzung des Pseudocodes beziehen, aber trotzdem danke.
Die eigentliche Aufgabe ist:
a) Implementieren Sie die iterative Version der Topologischen Sortierung aus der Vorle-
sung. Verwenden Sie dazu die bereitgestellte Klasse gerichteterGraph.
Falls die topologische Sortierung milingt, soll das Programm mit einer entsprechenden
Fehlermeldung enden. Andernfalls sollen die Knoten in der Reihenfolge ihrer topologischen
Sortierung umnumeriert4
und ausgegeben werden. Die Knotenausgabe soll zeilenweise
erfolgen: Zu jedem Knoten sollen dessen Knotennummer, sowie die Knotennummern seiner
Nachfolger ausgegeben werden. Erstellen Sie weiterhin eine Pr u unktion, die testet, ob
die Knoten eines gerichteten Graphen in Sortierreihenfolge vorliegen. Zusatz 5
: Speichern
Sie f ur jeden Knoten dessen alte Knotenummer6
, und geben Sie diese jeweils mit aus.
-
Ach und meines Wissens erzeuge ich durch
gerichteterGraph geine Instanz/Objekt der Klasse gerichteterGraph ^^
-
sfuccma schrieb:
...
eine Instanz/Objekt der Klasse gerichteterGraph ^^Und wird diese aus der Datei daten/graph1.dat geladen oder mit
int nn=10, int maxgrad=4, bool mitkantenbewertung=false, bool kreisfrei=falseinitialisiert?
Ansonsten solltest du schon mit einer konkreten Frage kommen, sonst wirst du hier wahrscheinlich nicht viel Hilfe finden.
-
das Objekt wird mit zufälligen werten gefüllt mit der zeile
gerichteterGraph *g = new gerichteterGraph(20,5)mit folgendem Konstruktor:
gerichteterGraph:: gerichteterGraph(int nn/*=10*/, int maxgrad/*=4*/, bool mitkantenbewertung/*=false*/, bool kreisfrei/*=false*/){ // zuf"allig int i,j,j1,j2,k,g; int e=15; int knr; // aktuelle Kantennummer Kante *nk; // eine neue Kante if(maxgrad>MAXGRAD) maxgrad=MAXGRAD; srand(5*maxgrad*maxgrad+nn); n=nn; m=0; alleKnoten.resize(n+1,NULL); // Z"ahlung ab 1 for(i=1;i<=n;++i) alleKnoten[i]= new Knoten(i); for(i=1;i<=n;++i){ // Konstruktoraufrufe g=rand()%(maxgrad+1); if(g>0) { if(kreisfrei) { j1=(i+1 <=n ? i+1 : n); j2= (i+2*g*e <=n ? i+2*g*e : n); } else { j1= (i-g*e > 0 ? i-g*e : 1); j2= (i+g*e <=n ? i+g*e : n); if(j1==i) j1++; } g=(j2-j1+1)/g; for(k=1;k<=maxgrad && j1<=j2 && g>0;++k) { nk = new Kante(alleKnoten[i],alleKnoten[j1]); if(mitkantenbewertung) nk->w=rand()/10000000.; nk->naechste=alleKnoten[i]->nachbarn; alleKnoten[i]->nachbarn=nk; m++; j1+=rand()%g+1; if(j1==alleKnoten[i]->nr) j1++; } } } alleKanten.resize(m+1,NULL); j=0; for(k=1;k<=n;++k) { nk=alleKnoten[k]->nachbarn; while(nk) { alleKanten[++j]=nk; nk=nk->naechste; } } if(kreisfrei) { // n zuf"allige Vertauschungen Knoten* hilf; for(i=1;i<=n;++i) { int j=rand()%n+1; if(i!=j) { hilf=alleKnoten[i]; alleKnoten[i]=alleKnoten[j]; alleKnoten[j]=hilf; alleKnoten[i]->nr=i; alleKnoten[j]->nr=j; } } } } // Ende zuf"allige ErzeugungDie Klassen und Funktionen waren gegeben. In der Aufgabe geht es lediglich um das topologische Sortieren.
Thx für die vielen Antworten.
-
Meine Frage sollte eigentlich darauf hinweisen, dass der Aufruf nicht eindeutig aufgelöst werden kann. Das sollte zumindest eine Warnung geben und spätestens beim Aufruf von
gerichteterGraph g;einen Fehler der art "Ambiguous call to overloaded function". Da der Code wohl auch noch Bestandteil der Aufgabenstellung ist kannst du natürlich nichts dafür.... macht es aber noch viel schlimmer.
Ansonsten musst du die Daumen drücken, dass jemandem so langweilig ist, dass er fremde Aufgaben löst.
-
Das versteh ich nicht ganz ich übergebe in der Klasse von gerichteterGraph dem Konstruktor doch default-Werte.
Da die Aufgabe, Aufgabe 2 ist und ich in der 1. Aufgabe diese Version ebenfalls benutze, kann das nicht falsch sein.
Darüberhinaus sagte unser Dozent, dass das Programm nur auf Linux laufbar sei.
Auch wird mit
-Wno-deprecated kompiliert.
Was für das Programm notwendig ist.
-
sfuccma schrieb:
Da die Aufgabe, Aufgabe 2 ist und ich in der 1. Aufgabe diese Version ebenfalls benutze, kann das nicht falsch sein.
Der Header (sofern er wirklich so vorgegeben wurde) ist jedenfalls kein gültiges C++, und enthält noch ein paar weitere Dinge, die man möglichst vermeiden sollte.
sfuccma schrieb:
Darüberhinaus sagte unser Dozent, dass das Programm nur auf Linux laufbar sei.
An dem Code selber ist jedenfalls nichts OS-Spezifisches, ich nehme mal an das er ein Programm hat, das die Implementation testet, und das Programm nur unter Linux läuft.
So nun kurz zum Header:
1. Müssen Konstruktoren eindeutig bestimmt werden können. Es gibt aber 2 Konstruktoren die auf beispielsweise "gerichteterGraph g;" passen würden.2. Möchte ich mal bitte wissen, was man sich bei diesen Defaultwert gedacht hat: "gerichteterGraph(char *datei="daten/graph1.dat")" (Hätte man statt des char* die string-Klasse verwendet, wäre es etwas anderes).
3. Hast du uns noch immer nicht dein Problem gesagt, oder konkrete Fragen gestellt, und ich bezweifel das der Compiler keine Fehler ausspuckt.
Kleinere Anmerkungen:
a) Es ist schön zu sehen, das Dozenten auch die STL kennen, ein "using namespace std;" sollte man dennoch im Header vermeiden. Dies solltest du dir jedenfalls nicht in eigenen Code angewöhnen.
b) "(void)" ist in C++ eigentlich unüblich [normalerweise verzichtet man auf die Typangabe], und eher unter C verbreitet.
c) Eine Variable sollte man so lokal wie möglich deklarieren, am besten erst wenn man sie das erste mal verwendet.