Ablauf Algorithmus

alx3400

Hallo,
ich muss einen Graphen-Algorithmus implementieren, der verinfacht folgendes beinhaltet:

Initialisierung aller Variablen
Suche einen Knoten x, der Bed. 1 erfüllt. Wenn es keinen gibt, ist der Alg. fertig.
Suche Nachbarn y dieses Knoten, der Bed. 2 erfüllt. Falls es keinen gibt, goto 2.
4)Falls y Bed. 3 erfüllt, führe Funktion grow() aus und gehe danach zu 3.

Das ist stark vereinfacht und die Bedingungen sollen nur andeuten, dass dort mit if irgendwelche mathematischen Ausdrücke geprüft werden.

Mein Problem ist, ich weiss nicht wirklich, wie ich dieses ganze Hin und Her zwischen den Schritten hinbekomme. Ich hatte erst gedacht, am Ende eines der Schritte, die ich jeweils als eigene Funktion schreibe, die Funktion auszurufen, die danach kommen soll (also am ende der Funktion, die Schritt 4 bescreibt, dann wieder die Funktion für Schritt 3 aufzurufen). Aber dann springt man ja nach Ausführen einer Funktion wieder in die zurück, aus der man die neue aufgerufen hat, und das scheint ja nicht ganz das zu sein, was man will.

Das Ganze ist sehr schwer zu erklären, ich hoffe, jemand versteht, was ich meine, sonst versuche ich, es nochmal besser zu erklären.

Danke schonmal

Dasd

Lässt sich das nicht einfach mit Hilfe verschachtelter Schleifen realisieren? Hängt allerdings davon ab, was grow() machen soll.

_matze

Eigentlich ist der Ablauf ja schon ganz gut beschrieben. Am besten, du zeigst mal, was du bislang hast, und dann sehen wir weiter.

alx3400

void findy(int x){
	for(int i=0;i<graph[x].degree;++i){
		y=graph[x].neighbours[i];
		if( outofforest(y) or (outer(y) and roh[y]!=roh[x]) ){
			if (outofforest(y))
				grow(x,y);
			else if (vdisjoint(x,y))
				augment(x,y);
			     else
				shrink(x,y);
		}

	}
	scanned[x]=true;
	findx();
}

int findx(){
	for(int i=0;i<n;++i){
		if(outer(i)){
			if(!scanned[i]){

				findy(i);

				break;
			}
			else
				continue;
		}
		else
			continue;
	}
	return -1;
}

also findx() wird aus main() aufgerufen und soll einen Knoten x finden, der "outer" ist (wird durch die Funktion outer() gecheckt) und "nicht scanned".Gibt es den nicht, wird -1 zurückgegeben. Falls er einen findet, wird findy()aufgerufen, die einen Nachbarn y von x sucht. Je nachdem welche Eigenschaften y hat, werden die Funktionen "grow","shrink" oder "augment" aufgerufen. Wurden grow oder shrink aufgerufen, suche ich mir danach nur ein neues y, wenn augment aufgerufen wurde, muss ich "ganz vorne" anfangen und auch ein neues x suchen.

Mein Problem ist irgendwie diese Verschachtelung. Angenommen, augment wird ausgeführt, dann müsste am ende von augment wieder ein Aufruf der Funktion findx stehen. Ich würde aber lieber von da aus wiede an die Stelle zurück, wo ich zu Anfang findx aufgerufen hab, nur mit den veränderten Werten des Graphen.

Ich weiss immer noch nicht, ob man auch nur ansatzweise verstehen kann, was ich meine.

EDIT: Nochmal zur Erklärung. Ich hätte vielleicht gern in main(), an der Stelle, an der findx() aufgerufen, sowas wie nen Rückkehrpunkt, an den ich wieder springen kann, wenn die Funktion augment aufgerufen wurde und ihren Dienst getan hat. Genauso hätte ich gern einen Punkt in findx(), direkt vor dem Aufruf von findy(), an den ich zurückspringe, wenn shrink oder grow aufgerufen wurde.

alx3400

int findy(int x){
	for(int i=0;i<graph[x].degree;++i){
		y=graph[x].neighbours[i];
		if( outofforest(y) or (outer(y) and roh[y]!=roh[x]) )
			return i;
	}
	scanned[x]=true;
	return -1;
}

int findx(){
	for(int i=0;i<n;++i){
		if(outer(i)){
			if(!scanned[i])
				return i;
			else
				continue;
		}
		else
			continue;
	}
	return -1;
}

int main(){

while(findx()!=-1){
		x=findx();
		while(findy(x)!=-1){
			y=findy(x);
			if (outofforest(y)){
				grow(x,y);
				continue;
			}
			else{
				if(vdisjoint(x,y)){
					augment(x,y);
					break;
				}
				else{
					shrink(x,y);
					continue;
				}
			}
		}
}
//Hier kommt die Ausgabe des Ergebnisses hin
return 0;
}

Bin das Ganze jetzt mal etwas anders angegangen. Werde erstmal versuchen ob es so geht und sich meine eigentlich Frage damit erledigt hat.
Ich hoffe, ich habe break und continue richtig eingesetzt. Jedenfalls müsste doch, nachdem grow oder shrink aufgerufen wurde als nächstes wieder geprüft werden, ob findy(x) -1 ergibt und es damit keinen in Frage kommenden Nachbarn von x mehr gibt. Falls augment aufgerufen wird, wird die while-Schleife, die in Zeile 29 beginnt, verlassen und es wird erneut die Bedingung der while-Schleife aus Zeile 27 gecheckt und mit einem neuem x, falls vorhanden, weitergearbeitet.

Vielleicht kann mir ja jemand sagen, ob mein Gedankengang so richtig ist.

Danke

_matze

Hab jetzt nicht die Zeit, mir das im Detail anzusehen, aber wenn du wissen willst, ob der Ablauf in Ordnung ist, dann gehe schrittweise mit dem Debugger durch!