OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
https://en.wikipedia.org/wiki/Topological_sorting
Sortowanie topologiczne polega na zanurzeniu porządku częściowego (~<) w porządku liniowym, tj. na utworzeniu takiego ciągu elementów a[], że jeśli a[j] ~< a[k], to j < k [Knuth].
Porządek częściowy można zapisać w grafie skierowanym acyklicznym (dagu), a wtedy mówimy o sortowaniu topologicznym grafu. Można sortować topologicznie tylko grafy skierowane bez cykli skierowanych.
Wierzchołki grafu mogą reprezentować zadania do wykonania. Krawędź (u,v) w grafie oznacza, że zadanie u musi być wykonane przed zadaniem v. Uporządkowanie topologiczne wierzchołków będzie dozwoloną kolejnością wykonywania zadań. Zwykle istnieje kilka możliwych uporządkowań topologicznych wierzchołków.
Na sortowanie topologiczne grafu można spojrzeć jak na umieszczanie jego wierzchołków na linii poziomej w taki sposób, żeby wszystkie krawędzie były skierowane od strony lewej do prawej [Cormen].
Zastosowania sortowania topologicznego:
wyznaczanie najkrótszych ścieżek z jednego źródła w dagu [DAGShortestPath],
zarządzanie projektami, wyznaczanie ścieżki krytycznej,
wyznaczanie kolejności obliczania formuł w komórkach arkusza kalkulacyjnego,
porządkowanie zadań w Makefile,
rozwiązywanie zależności między symbolami w linkerach.
Są dwa podstawowe algorytmy sortowania topologicznego,
działające w czasie liniowym O(n+m):
(1) sortowanie topologiczne na bazie DFS [1976 Tarjan],
(2) algorytm usuwania wierzchołków niezależnych [1962 Kahn].
| Przykład sortowania topologicznego dagu. | 0 --o 1 --o 2 uporządkowanie 1: 0 3 4 1 5 2 | | \ o o uporządkowanie 2: 0 3 4 5 1 2 | | \ | | | o o | | | 3 --o 4 --o 5 | | +----------+ +----------+ | | | | | | | o | o | 0 --o 3 --o 4 --o 1 5 --o 2 | | o | o | | | | | | +----------------+ +----------+
Graph G(n,true); // graf skierowany, macierz sąsiedztwa, T = int
Graph<char> G(true); // graf skierowany, lista sąsiedztwa, T = char
// dodawanie krawędzi grafu, wierzchołki grafu są typu T
std::vector<T> sorted_nodes;
std::unordered_map<T,int> idx;
for (int i = 0; i < G.v(); ++i)
idx[sorted_nodes[i]] = i;
for (auto it = G.edge_begin(); it != G.edge_end(); ++it)
assert( idx[(*it).source] < idx[(*it).target] );
Input: A directed acyclic graph G (dag).
Output: A sequence of vertices sorted topologically.
Algorithm TopologicalSortDFS(G):
let Color[] be an empty table for vertex colors
let L be an empty list that will contain sorted vertices
for each vertex u in V(G) do
set Color[u] to WHITE
for each vertex u in V(G) do
if Color[u] is WHITE then
call DFSVisit(G,u) # post_action(u) is L.append(u)
reverse L
return L
Łatwo sprawdzić, czy graf jest skierowany. Trudniej sprawdzić, czy graf jest acykliczny. Standardowe przeszukiwanie DFS nie raportuje cykli w grafie skierowanym. Prosta modyfikacja DFS pozwala wykryć cykl skierowany.
Algorithm DFSVisit(G,u):
set Color[u] to GREY
call pre_action(u)
for each edge (u,v) in E(G) do
if Color[v] is WHITE then # adjacency list
set Parent[v] to u
call DFSVisit(G,v)
else if Color[v] is GREY then
return error # back edge detected (not a dag)
set Color[u] to BLACK
call post_action(u)
Algorytm wykryje, że graf nie jest dagiem.
Input: A directed acyclic graph G (dag).
Output: A sequence of vertices sorted topologically.
Algorithm TopologicalSortKahn(G):
let L be an empty list that will contain sorted vertices
let S be a set of all vertices with no incoming edge
while S is not empty do
remove a vertex u from S
add u to L
for each edge (u,v) in E(G) do
remove edge (u,v) from G
if v has no other incoming edges then
insert v into S
if G has edges then # len(L) < |V(G)|
return error # G has at least one cycle (not a dag)
else
return L # a topologically sorted order
# Depending on the order that vertices u are removed from the set S,
# a different solution is created.
Klasyfikacja krawędzi grafu na bazie DFS [Cormen]:
(1) krawędzie drzewowe (tree edge)
[(u,v) to krawędź drzewowa, jeżeli v odwiedzamy w wyniku badania
krawędzi (u,v); czyli v jest biały],
(2) krawędzie powrotne (back edge)
[(u,v) to krawędź powrotna, jeżeli v jest przodkiem u w drzewie DFS;
czyli v jest szary, ale w grafie nieskierowanym v != Parent[u];
taka krawędź oznacza cykl w grafie],
(3) krawędzie w przód (forward edge)
[(u,v) to krawędź w przód, jeżeli v jest potomkiem u,
ale (u,v) to nie jest krawędź drzewowa; czyli v jest czarny i jest potomkiem,
a więc można dojść od v do u przez Parent;
u jest wcześniej niż v na liście Preorder],
(4) krawędzie poprzeczne (cross edge)
[to są wszystkie inne krawędzie (u,v);
krawędzie łączą wierzchołki z jednego drzewa DFS, jeżeli jeden nie jest
przodkiem drugiego;
krawędzie łączą też wierzchołki z różnych drzew DFS;
czyli v jest czarny i nie można dojść od v do u przez Parent;
u jest później niż v na liście Preorder].
Twierdzenie [Cormen].
W przeszukiwaniu DFS grafu nieskierowanego G każda krawędź jest albo
krawędzią drzewową, albo krawędzią powrotną.
Lemat [Cormen].
Graf skierowany jest acykliczny wtw, gdy nie posiada krawędzi powrotnych
w przeszukiwaniu DFS.
Algorytm klasyfikujący krawędzie w grafie skierowanym lub nieskierowanym wykorzystuje DFS i działa w czasie O(n+m) dla reprezentacji list sąsiedztwa. Istnienie krawędzi powrotnych jest oznaką istnienia cyklu w grafie.
Input: A graph G and a vertex u of G.
Output: Edge classification.
Algorithm DFSVisit(G,u):
set Color[u] to GREY # Preorder.append(u)
for each edge (u,v) in E(G) do # adjacency list
if Color[v] is WHITE then
set Parent[v] to u
print "(u,v) is a tree edge"
call DFSVisit(G,v)
else if Color[v] is GREY then
if (G is directed) or (v != Parent[u]) then
print "(u,v) is a back edge" # cycle detected
else # Color[v] is BLACK
if G is not directed then
continue # krawędź była już badana jako back edge
# ma być directed graph, cross or forward edge;
# forward edge, jeżeli v jest potomkiem u;
set w to v
set forward to false # ustawiam flagę
while Parent[w] is not None do # idziemy w kierunku korzenia
set w to Parent[w]
if w equals u then
print "(u,v) is a forward edge"
set forward to true
if forward is false then
print "(u,v) is a cross edge"
set Color[u] to BLACK # Postorder.append(u)
Zaimplementować algorytm Tarjana sortowania topologicznego dagu z użyciem DFS. Wygenerować przykładowy dag z n=10. Posortować topologicznie wierzchołki dagu.
// Proponowany interfejs algorytmu Tarjana (szablon funkcji). template <typename T, typename G> // node type, graph type std::vector<T> topsort_dfs(G& graph);
Zaimplementować algorytm Kahna sortowania topologicznego dagu przez usuwanie wierzchołków niezależnych. Wygenerować przykładowy dag z n=10. Posortować topologicznie wierzchołki dagu.
// Proponowany interfejs algorytmu Kahna (szablon funkcji). template <typename T, typename G> // node type, graph type std::vector<T> topsort_kahn(G& graph);
Zaimplementować algorytm wykrywający cykle w grafie skierowanym lub nieskierowanym. Wygenerować przykladowy graf z n=10. Sprawdzić, czy graf zawiera cykl.