2sat-korrektur: Programm schmiert ab

[gast6677]

Hallo cpp-Forum,

ich habe ein Problemchen ;-). Ich habe hierr einen fremden Code, den ich berichtigen will.
Ich habe bereits die Fehlerquelle gefunden, jedoch wundere ich mich, dass es nicht funktioniert.
Seht selbst:

Der Fehler liegt hier (weil er nur bis dahin kommt; Zeile 188):

Graph *temp = new Graph(2*variablen);

Hier der ganze Code:

#include <iostream>
#include <stdlib.h>

// zusaetzliche libs
#include <string>
#include <fstream>
#include <map>
#include <vector>

using namespace std;

///////////////////////////////////////////////
//map wird verwendet, damit schneller nach Elementen gesucht werden kann

typedef map<long,long> Komp;

class Adjazenzkante {

	public:
	Adjazenzkante(long ziel);
	~Adjazenzkante();

	void setzeNaechste(Adjazenzkante *a);

        Adjazenzkante *gebeNaechste(void);

	long gebeZiel(void);

	private:
	long ziel;
	Adjazenzkante *naechste;

};

typedef Adjazenzkante* p_Adjazenzkante;
typedef p_Adjazenzkante* pp_Adjazenzkante;

Adjazenzkante::Adjazenzkante(long ziel) {
	this->ziel = ziel;
	this->naechste = 0;

}

Adjazenzkante::~Adjazenzkante() {
	if (naechste != 0) delete naechste;
}

void Adjazenzkante::setzeNaechste(Adjazenzkante *a) {
	naechste = a;
}

Adjazenzkante *Adjazenzkante::gebeNaechste(){
	return naechste;
}

long Adjazenzkante::gebeZiel(void) {
	return ziel;
}

//////////////////////// 

class Graph{

	public:
	Graph(long Knoten);
	~Graph();

	void entfernen(long k);
	bool neueKante (long start, long ziel);
//	Graph *gebeUngerichteten Graphen(); // f1
	Graph *gebeUngerichteten;
	Graph *gebeAntiGraph();	
	Adjazenzkante **gebeKanten();
	long gebeKnotenanzahl();

	//Die Algorithmen
	void scc(vector<Komp> &Komponenten);
//	void gerichteterKreis(vector<Komp> Komponenten, bool +kreis);
	void gerichteterKreis(vector<Komp> Komponenten, bool *kreis);
	bool* erfuellendeBelegung();

	private:
	Adjazenzkante **Kanten;
	long Knotenanzahl;
	void besuche1(long a, long labell[], long relable[], bool besuchte[],
	long* zaehler, Komp &Komponente1);
	void besuche2 (long a, long label[], long relabel[], bool besuchte[],
	Adjazenzkante **Knoten, Komp &Komponente);

};

typedef Graph* p_Graph;

void Graph::entfernen (long k){
	Kanten[k]=0;
}

Graph::Graph(long Knoten){
	Knotenanzahl=Knoten;
	Kanten = new p_Adjazenzkante[Knotenanzahl];
	for(long i = 0; 1<Knoten; i++){
		Kanten[i] = 0;
	}
}

Graph::~Graph() {
	for (long i=0; i<Knotenanzahl; i++){
		if(Kanten[i]!= NULL) delete Kanten[i]; // f3
	}
	delete[] Kanten;
}

bool Graph::neueKante(long start, long ziel){
	p_Adjazenzkante laeufer;
	p_Adjazenzkante davor;
	laeufer = Kanten[start];
	if (laeufer==NULL){
		Kanten[start] = new Adjazenzkante(ziel);
		return true;
	}

	while(laeufer !=NULL){
		davor = laeufer;
		laeufer= laeufer->gebeNaechste();
	}

	davor-> setzeNaechste(new Adjazenzkante(ziel));
	return true;
}

pp_Adjazenzkante Graph::gebeKanten(){
	return Kanten;
}

p_Graph Graph::gebeAntiGraph(){
	p_Graph temp = new Graph(Knotenanzahl);
	for(int i=0; i<Knotenanzahl; i++) {
		p_Adjazenzkante aktKante = Kanten[i];
		while(aktKante !=NULL){
			temp->neueKante(aktKante->gebeZiel(),i);
			aktKante=aktKante->gebeNaechste();
		}
	}
	return temp;
}

long Graph::gebeKnotenanzahl(){ // f4 zusammengeschrieben
	return Knotenanzahl;
}

Graph *parseDatei (string dateiname){
	long variablen, kanten;
	char startnegiert, zielnegiert, x;
	long start, ziel;
	char negiert;
	ifstream datei;

	datei.open(dateiname.c_str(), ifstream::in);
	if (datei==0) {
		cerr<<"Datei nicht gefunden"<< endl;
		return 0;
    	}	

	datei >> variablen;
	Graph *temp = new Graph(2*variablen);
	while ( !datei.eof() ) { 
		datei >> startnegiert;  // f5 falschgeschrieben
 		datei >> x;                     // x einlesen 
		datei >> start; 
		datei >> zielnegiert; 
		datei >> x;                    //x einlesen 
		datei >> ziel;
		if (startnegiert =='+' && zielnegiert == '+') {  // nicht `` sondern ''
			temp->neueKante(start+variablen,ziel);
			temp->neueKante(ziel+variablen, start); 
			continue;
		}	
		if(startnegiert == '+'	&& zielnegiert == '~') { // nicht `` sondern ''
			temp->neueKante(ziel,start);
			temp->neueKante(start+variablen, ziel+variablen); 
			continue;
		}

		if(startnegiert == '~'  &&  zielnegiert == '+') { // nicht `` sondern ''
			temp->neueKante(start,ziel);
         temp->neueKante(ziel+variablen,start+variablen);
			continue;
		}

		if(startnegiert == '~' && zielnegiert == '~') {// nicht `` sondern ''
			temp->neueKante(start,ziel+variablen);
			temp->neueKante(ziel,start+variablen);
			continue;
		}
	}
	return temp;
}

void Graph::scc(vector<Komp> &Komponenten) { 
	p_Graph antigraph = gebeAntiGraph();
	long anzkomponente = 0;
//	long *zaeh1er = new long; // fehler siehe unten
	long *zaehler = new long;
	long label[Knotenanzahl]; // f10 falschgeschrieben
	bool besuchte [Knotenanzahl]; 
	long relabel[Knotenanzahl]; // f11 falschgeschrieben
	vector<Komp> Komponenten1;
	for(long i = 0; i<Knotenanzahl; i++){ // f12 i vergessen
		besuchte[i]=false;
		label[i]=-1;
		relabel[i]=-1;
	}
	*zaehler = -1; // fehler mit zeile davor (Rechtschreibfehler f13
	for(long i=0; i<Knotenanzahl;i++){
		Komp Komponente1;
		if(besuchte[i] == false){
			besuche1(i, label,relabel,besuchte,zaehler,Komponente1);
		}
	}

	for(long i=0; i<Knotenanzahl; i++) besuchte[i] = false;

	for(long i=Knotenanzahl-1; i>=0; i--){
		if(besuchte[label[i]]==false){
			anzkomponente++;
			Komp Komponente;
			cout<<"Starke Zusammenhangskomponente" << anzkomponente<< ":"<<endl;
			besuche2(label[i],label,relabel,besuchte,antigraph->gebeKanten(),Komponente);

			cout<<endl;

			Komponenten.push_back(Komponente);
		}
	}
	delete antigraph;
}

	void Graph::besuche1(long a, long label[], long relabel[], bool besuchte[],long*zaehler, Komp &Komponente1){

		besuchte[a]=true;
		p_Adjazenzkante aktKante = Kanten[a];

		while (aktKante !=NULL){
			if(besuchte[aktKante->gebeZiel()]==false){
				besuche1(aktKante->gebeZiel(),label, relabel, besuchte, zaehler, Komponente1);
			}
			aktKante = aktKante->gebeNaechste();
		}

		(*zaehler)++;
		label[*zaehler] = a;
		relabel[a] = *zaehler;
		Komponente1[a] = a;
	}

	void Graph::besuche2(long a, long label[], long relabel[], bool besuchte[], Adjazenzkante **AntiKanten, Komp &Komponente){
		besuchte[a]= true;
		p_Adjazenzkante aktKante = AntiKanten[a];
		while (aktKante != NULL) {
			if (besuchte[aktKante->gebeZiel()]==false) besuche2(aktKante->gebeZiel(), label,relabel,besuchte,AntiKanten,Komponente); // rechtschreibfehler relabel
			aktKante=aktKante->gebeNaechste();
		}

		Komponente[a]= a;
		cout << "" << a;        
	}

void Graph::gerichteterKreis(vector<Komp> Komponenten, bool *kreis) { // rechtschreibfehler

	vector<Komp>::iterator iterkomponenten;
	map<long,long>::iterator itermap; // diese zeile vergessen f15
	map<long,long>::iterator iter;
	long test;

	for(iterkomponenten=Komponenten.begin(); iterkomponenten!=Komponenten.end();iterkomponenten++) {
		for(itermap =(*iterkomponenten).begin(); itermap !=(*iterkomponenten).end(); itermap++){
			if((*itermap).first < (Knotenanzahl/2)){
				test=(*itermap).first+Knotenanzahl/2;
				if((*iterkomponenten).find(test)!=(*iterkomponenten).end()){ // inahlt von iterkompenenten end ==> * !!! fehler 16
					*kreis=true;
					//return; // falsch geht nicht funktion ist ehe void FEHLER auch in musterlösung!!! f17
				}
			}
		}	
	}
	*kreis=false;
}

bool* Graph::erfuellendeBelegung(){
	bool gesetzt[Knotenanzahl];
	bool*wert= new bool[Knotenanzahl];
	long angesetzt =0; // wieder ANZGESETZT? fehler 23 AHA : einmal angesetzt statt anzgesetzt (== anzahl der gesetzten?) folge fehler
	long i=0;
	long label[Knotenanzahl];

	//bool *besuchte =new bool[Knotenanzahl];

	bool besuchte[Knotenanzahl];
	long relabel[Knotenanzahl];	
	long *zaehler =new long;
	Komp Komponente1;
	long test;

	for(long j=0; j < Knotenanzahl; j++) {
		besuchte[j] = false;
		label[j]=-1;
		relabel[j]=-1;
		gesetzt[j] = false;
	}

	*zaehler = -1;

	while(angesetzt != Knotenanzahl) { // folge fehler mit anzgesetzt ; wir machen jetzt draus angesetzt
		while(gesetzt[i]==true){
			if(i==Knotenanzahl) {
				cout << "Fehler beim Finden einer zulaessigen Belegung" << endl;
				exit(1);
			}
			i++;
		}
		besuche1 (i,label,relabel,besuchte,zaehler,Komponente1); // fehler nicht relable sondern relabel /f18
		if(i < (Knotenanzahl/2)) test = i +Knotenanzahl/2;
		else test= i - Knotenanzahl/2;

		if(Komponente1.find(test)==Komponente1.end()) {
			//negiertes nicht in Komponente enthalten
			for(long j=0; j<Knotenanzahl;j++){
			//to do: mit Komponenten
				if(besuchte[j]==true) {
					gesetzt[j] = true;
					angesetzt++; // fehler f22 FALSCHGESCHRIEBEN
					wert[j] = true;
					entfernen(j);
					if(j < (Knotenanzahl/2)) { // VARIABLENNAMEN IMMER SO SCHREIBEN WIE SIE DEKLARIERT WORDEN SIND! hier Knotenanzahl //f19
						gesetzt[j+Knotenanzahl/2]=true;
						angesetzt++; // wieder der tolle folgefehler (das kommt uebrigens davon, wenn man den code nicht dokumentiert) Kritik auch hier an die Assi-Frau!!!!
						entfernen(j+Knotenanzahl/2);
					}
					else{
						gesetzt[j-Knotenanzahl/2] = true; // schreibfehler: gesetzt NICHT gesezt!// f20
						angesetzt++; // schonwieder .. fuck!
						wert[j-Knotenanzahl/2]=false;
						entfernen(j-Knotenanzahl/2);
					}
				}
			}
		}
		else{
			long temp;
			for(long j=0; j<Knotenanzahl;j++)
				besuchte[j] = gesetzt[j]; // Wieder rechtschreibfehler (siehe fehler f20)
				temp = i;
				i = test;
				test = temp;
				besuche1(i,label, relabel, besuchte, zaehler,Komponente1);
			for(long j=0; j<Knotenanzahl;j++){
			//to do: mit Komponenten
				if(besuchte[j]==true){
					gesetzt[j] = true; 
					angesetzt++; // fehler f22
					wert[j] = true;
					entfernen(j);
					if(j < (Knotenanzahl/2)){
						gesetzt[j+Knotenanzahl/2] = true;
						angesetzt++;
						wert[j-Knotenanzahl/2] = false;
						entfernen(j+Knotenanzahl/2);
					}

					else {
						gesetzt[j-Knotenanzahl/2] = true; // wieder ein rechtschreibfehler 't' vergessen
						angesetzt++; // bla wieder fehler
						wert[j-Knotenanzahl/2] = false;
						entfernen(j-Knotenanzahl/2);
					}
				}
			}	
		}
	}
	return wert;
}

void ausgabe (bool *belegung, long Knotenanzahl){
	cout << endl << "Erfuellende Belegung für 2SAT-Instanz:" << endl;
	for(int i=0; i< Knotenanzahl/2; i++) {
		cout << "x"<< i << "=" << belegung[i] << endl;
	}
}
///////////////////////////////////////////////

int main(int argc, char *argv[])
{
  	bool kreis;
	bool *belegung;
	vector<Komp> Komponenten;

	if (argc != 2){
		cout << "Benutzung: zusammenhang <Dateiname>" << endl;
		return -1;
	}

	string dateiname(argv[1]);
	Graph *arbeiter;

	arbeiter = parseDatei(dateiname);

	if (arbeiter == 0) return -1;

	arbeiter->scc(Komponenten);

	arbeiter->gerichteterKreis(Komponenten, &kreis);

	if(kreis == true){cout << "Keine erfuellende Belegung für diese 2SAT-Instanz moeglich" << endl;
		return 0;
	}									

	belegung= (bool*) malloc((arbeiter->gebeKnotenanzahl())*sizeof(bool));
	belegung = arbeiter->erfuellendeBelegung();
	ausgabe(belegung,arbeiter->gebeKnotenanzahl());

  system("PAUSE");	
  return 0;
}

Die 2SAT.TXT sieht so aus:

4
+x0 +x1
+x1 -x0
-x1 -x0
+x1 +x2
+x2 +x3
-x3 +x0

Ich verwende Dev-cpp 4.9. Der hat keine Fehler angezeigt.

Vielen Dank für die Hilfe
gast6677

[CStoll]

gast6677 schrieb:

Der Fehler liegt hier (weil er nur bis dahin kommt; Zeile 188):

Graph *temp = new Graph(2*variablen);

Zwischenfrage: Wie äußert sich denn der Fehler?

Ansonsten solltest du mal einen Debugger einschalten und nachsehen, was dein Programm dort macht.

(was mir schon auffällt: im Programm prüfst du auf '~', aber in der Datei steht '-' für negative Werte, könnte es daran liegen?)