Topological sorting for Directed Acyclic Graph (DAG) - ist steht auf dem Schlauch

Ich versuche gerade einem Kollegen zu erklären das man mit einer Topologie-Sortierung *doch* ein Ausführungs-Reihenfolgen-Problem lösen kann - und nicht komisch mit wilden Sortierungen um sich schlagen muss

Ich nutze zur Anschauung den Algorithmus von dieser Seite:

http://www.geeksforgeeks.org/topological-sorting/

das Python-Beispiel laesst sich so direkt Online ausführen
http://code.geeksforgeeks.org/AsN3Mw

mein Testgraph sieht so aus

Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(1, 4);
g.addEdge(4, 5);

also Vertex:
0 => {1,2}
1 => {2,3,4}
3 => {4}
4 => {5}

als Ergebnis kommt

Following is a Topological Sort of the given graph
[6, 0, 1, 3, 4, 5, 2]

soweit ich das verstehe sind das die Edge-Indizes (nicht zu verwechseln mit Vertex-Indize - es gibt auch keinen Vertex 6) aber jetzt bin
ich mir absolut nicht sicher wie ich damit auf meine Vertex-Reihenfolge komme

eine korrekte(Variante) der Sortierung meiner Vertexe ist

2
5
4
3
1
0

ich habe aber nur die Edge-Indizes und die 6 am Ende irritiert mich

kann mich jemand ein wenig erleuchten

den Link auf die Online-Python Implementation nur damit man spielen kann - ich will das ganze dann in ein C++ Projekt integrieren

am liebsten würde ich Boost Graph verwenden - aber Boost ist in dem Projekt nicht erlaubt

Gast3 schrieb:

am liebsten würde ich Boost Graph verwenden - aber Boost ist in dem Projekt nicht erlaubt

So etwas habe ich noch nie verstanden. Was genau ist die Argumentation dahinter?

muss auf WinCE VS2008 und GCC 3.4.x usw laufen - ist im std. Testsystem so drinn - und damit ist die Argumentationskette zu Ende - schon öfters probiert - hier gilt auch nicht C++11 ist böse - am besten weniger als C++03... alte Herren

kannst du mir bei meinem Unverständnis helfen?

nach ein bisschen längere Suche habe ich jetzt das gefunden:

http://www.jiuzhang.com/solutions/topological-sorting

relativ klein, macht was es soll, fertig

Danke

Hallo,

du hast ja nur 6 Vertices im tatsächlichen Graphen, initialisierst den Graphen im Programmcode aber mit 7 Vertices.

Graph g(7); // <-- hier nur 6 Vertices (0...5)
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(1, 4);
g.addEdge(4, 5);

muss auf WinCE VS2008 und GCC 3.4.x usw laufen - ist im std. Testsystem so drinn - und damit ist die Argumentationskette zu Ende - schon öfters probiert - hier gilt auch nicht C++11 ist böse - am besten weniger als C++03... alte Herren

gleiches hier - vergiss es. Die wollen nichts neues (C++11) und wollen auch nicht irgendwelche Ergebnisse aus der Informatik verwenden. Stattdessen lieber irgendwelche Bastellösungen die seit 20 Jahren in den meisten Fällen funktionieren, manchmal halt doch nicht, aber das lässt sich sicher lösen mit noch einer weiteren Spezialbehandlung.
Ich rede inzwischen garnicht mehr drüber sondern mach es einfach.

soweit ich das verstehe sind das die Edge-Indizes (nicht zu verwechseln mit Vertex-Indize - es gibt auch keinen Vertex 6) aber jetzt bin
ich mir absolut nicht sicher wie ich damit auf meine Vertex-Reihenfolge komme

das sind keine Edge Indizes, sondern die Vertices, siehe Code:

Der Stack wird mit den Vertices befüllt

// Push current vertex to stack which stores result
    Stack.push(v);

Und bei der Ausgabe werden auch nur die Vertices aus dem Stack ausgegeben:

// Print contents of stack
    while (Stack.empty() == false)
    {
        cout << Stack.top() << " ";
        Stack.pop();
    }

Und die Ausgabe [0, 1, 3, 4, 5, 2] entspricht ja genau dem, was du erwartest (bis auf die verkehrte Reihenfolge).

Nachmittagsblindheit hat zugeschlagen - Danke