Tarjans strongly connected components algoritme

kunne sikkert godt skrives bedre end det der, basalt set siger den bare at lowlink på en knude v er det mindste index på alle knuder v' som kan nås fra v.
Så alle knuder v i en component får det samme lowlink da du fra en knude i componenten kan komme til alle andre af en eller anden path.
Og den knude hvis index svarer til lowlink er roden i componenten.

og implementeringen er det nok lettest bare at tage pseudo koden og convertere den til c++ eller c

kunne sikkert godt skrives bedre end det der, basalt set siger den bare at lowlink på en knude v er det mindste index på alle knuder v' som kan nås fra v.
Så alle knuder v i en component får det samme lowlink da du fra en knude i componenten kan komme til alle andre af en eller anden path.
Og den knude hvis index svarer til lowlink er roden i componenten.

og implementeringen er det nok lettest bare at tage pseudo koden og convertere den til c++ eller c

Fint. så havde jeg forstået det rigtigt. Ja selve konverteringen er nok ikke så svær når bare man er sikker på at have forstået pseudo koden rigtigt.

Jeg vender tilbage hvis resultatet driller

Carsten

Jeg har virkelig problemer med at implementere algoritmen korrekt. Det kan nok være svært for jer der gerne vil hjælpe mig lige sådan at få mening ud af de nedenstående koder.
Jeg har en graf med knuder (vertex) og kanter (edge), via Sort kalder jeg Visit der rekursivt finder strongly connected components. Jeg har forsøgt at kommenterer min kode i forhold til eksemplet på wikipedia. Håber det giver mening.

Jeg tror jeg går galt i byen fra det punkt hvor jeg benytter Min() funktionen og så specielt den sidste del af Visit() funktionen. Hvor jeg udskriver SCC (hvilket jeg ikke gør endnu).

Ihvertfald får jeg en fejl i linien:
Vertex* vNext = (Vertex*) unsettled.back();

http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Håber meget på lidt hjælp
Mvh
Carsten

void Tarjan::Sort()
{
        //get First vertex/node in graph
	Vertex* vertex = graph->GetFirst();

        // Start a DFS at the start node
	Visit(vertex);    
}

void Tarjan::Visit(Vertex* v)
{
	Vertex* vertex = (Vertex*) v;

        // Set the depth index for v
	vertex->SetDepth(index);

        // Set the lowlink index for v
	vertex->SetLowlink(index);
	index++;

        //unsettled is a vector<Vertex*>
	unsettled.push_back(vertex);

        // Push v on the stack (kører jeg bagvendt pga. vector)
        // Consider successors of v 
        // Iterate all edges to v
	Edge* edge = (Edge*) vertex->GetEdges();
	while(edge)
	{
                // Was successor v' visited? 
                // int depth of vertices initialized to -1
		if(edge->GetEndVertex()->GetDepth() == -1)
		{
                        // Recurse
			Visit(edge->GetEndVertex());
			
//assign smallest int of lowlink this vertex and end vertex
vertex->SetLowlink(Min(vertex->GetLowlink(), edge->GetEndVertex()->GetLowlink()));
		}

                // Is v' on the stack?
		else if(FoundInStack(edge->GetEndVertex()))
		{
		//assign smallest int of this vertex lowlink and end vertex depth
	vertex->SetLowlink(Min(vertex->GetLowlink(), edge->GetEndVertex()->GetDepth()));
		}
		edge = edge->GetNext();
	}

         // Is v the root of an SCC?
	if(vertex->GetLowlink() == vertex->GetDepth())
	{
                //repeat untill v' equals v
		while(vertex->GetNext() != vertex)
		{
			Vertex* vNext = (Vertex*) unsettled.back();
			unsettled.pop_back();
		}
	}
}

bool Tarjan::FoundInStack(Vertex* vertex)
{
	for(int i = 0; i < unsettled.size(); i++)
	{
		if(vertex == unsettled.at(i))
			return true;
	}
	return false;
}

int Tarjan::Min(int m1, int m2)
{
	int m;
	m = (m1 < m2) ? m1 : m2;
	return m;
}

Tror faktisk jeg har løst det.
Skiftede den sidste løkke i Visit ud med:
PS: wxLogMessage er en wxWidgets specifik ting der udskriver data til et debug vindue, a la printf

[EDIT]: ØV DET HAVDE JEG IKKE

	if(vertex->GetLowlink() == vertex->GetDepth())
	{
		wxLogMessage("SCC:");
		while(vertex != unsettled.back())
		{
			wxLogMessage(wxT("%s"), unsettled.back()->GetData());
			unsettled.pop_back();
		}
		wxLogMessage(wxT("%s"), vertex->GetData());
	}

Er ikke god til c++, men:

//repeat until v' equals v
wxLogMessage("SCC:");
Vertex* vNext;
do{
  vNext = (Vertex*) unsettled.back();
  wxLogMessage(wxT("%s"), vNext->GetData());
  unsettled.pop_back();
}while(vNext!=vertex);

Er ikke helt sikker på om dine functioner tager referencer eller om det er kopier, det sidste ville klart være en fejl.

og din min kunne skæres ned til bare
return (m1<m2)?m1:m2;

eller evt. fjernes og bare skrive std::min(vertex->GetLowlink(),edge->GetEndVertex()->GetLowlink());
og include algorithm header filen, men der er vistnok et problem med std::min hvis du bruger visual studio

*** PANIK *** Vil det sige at det koncept jeg gentager mange steder i min kode er implementeret forkert?

Jeg har lavet en linked list af Vertex objekter, der alle har en Vertex* kaldet next, den sidste pointer peger på NULL. Disse Vertices er del af en graf, hvor jeg sætter en pointer til den første Vertex i grafen. Så grafen har en Vertex* first

Dermed kan jeg sige:

Vertex* vFirst = (Vertex*) graf->GetFirst();

Er vFirst linked videre kan jeg ydermere sige:

Vertex* vNew = (Vertex*) vFirst->GetNext();

Det jeg får tilbage er altså en Vertex pointer.

Er det fuldstændig forkert? Skulle jeg i virkeligheden modtage referencer fra GetFirst() og GetNext()?
Lidt træt af at starte 2 spørgsmål i samme tråd da jeg stadig har brug for hjælp med det originale spørgsmål. Men det her er måske list lettere at svare på uden at have mere kode tilgængeligt.

Hjælp en frustreret herre der nærmer sig deadline
Carsten