http://www.geeksforgeeks.org/topological-sorting/
Topogica sort can be applied only to directed acyclic graph - (DAG)
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.
Time Complexity: The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).
In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
1. Make an empty list L and an empty list S;
2. Put all the vertices with no predecessors in L;
3. While L has items in it;
3.1. Pop an item from L – n, and push it to S;
3.2. For each vertex m adjacent to n;
3.2.1. Remove (n, m);
3.2.2. If m has no predecessors – push it to L;
Store both incoming and outgoing edges and slightly modify the adjacency lists.
1. Represent the graph with two lists on each vertex (incoming edges and outgoing edges)
2. Make an empty queue Q;
3. Make an empty topologically sorted list T;
4. Push all items with no predecessors in Q;
5. While Q is not empty
a. Dequeue from Q into u;
b. Push u in T;
c. Remove all outgoing edges from u;
6. Return T;
This approach will give us a better performance than the “brute force” approach. The running time complexity is O(|V| + |E|). The problem is that we need additional space and an operational queue, but this approach is a perfect example of how by using additional space you can get a better performing algorithm.
Use Modified DFS
From http://www.geeksforgeeks.org/topological-sorting/
We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
Java Code https://sites.google.com/site/indy256/algo/topological_sorting
http://algs4.cs.princeton.edu/44sp/Topological.java.html
static void dfs(List<Integer>[] graph, boolean[] used, List<Integer> res, int u) {
used[u] = true;
for (int v : graph[u])
if (!used[v])
dfs(graph, used, res, v);
res.add(u);
}
public static List<Integer> topologicalSort(List<Integer>[] graph) {
int n = graph.length;
boolean[] used = new boolean[n];
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++)
if (!used[i])
dfs(graph, used, res, i);
Collections.reverse(res);
return res;
}
http://www.drdobbs.com/database/topological-sorting/184410262
Also check http://www.sanfoundry.com/java-program-topological-sorting-graphs/
Read full article from Algorithm of the Week: Topological Sort of a Graph | Architects Zone
Topogica sort can be applied only to directed acyclic graph - (DAG)
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.
Time Complexity: The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).
In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
1. Make an empty list L and an empty list S;
2. Put all the vertices with no predecessors in L;
3. While L has items in it;
3.1. Pop an item from L – n, and push it to S;
3.2. For each vertex m adjacent to n;
3.2.1. Remove (n, m);
3.2.2. If m has no predecessors – push it to L;
public function __construct()
{
$this->_len = count($this->_g);
// finds the vertices with no predecessors
$sum = 0;
for ($i = 0; $i < $this->_len; $i++) {
for ($j = 0; $j < $this->_len; $j++) {
$sum += $this->_g[$j][$i];
}
if (!$sum) {
// append to list
array_push($this->_list, $i);
}
$sum = 0;
}
}
public function topologicalSort()
{
while ($this->_list) {
$t = array_shift($this->_list);
array_push($this->_ts, $t);
foreach ($this->_g[$t] as $key => $vertex) {
if ($vertex == 1) {
$this->_g[$t][$key] = 0;
$sum = 0;
for ($i = 0; $i < $this->_len; $i++) {
$sum += $this->_g[$i][$key];
}
if (!$sum) {
array_push($this->_list, $key);
}
}
$sum = 0;
}
}
print_r($this->_ts);
}
Computer Algorithms: Topological Sort RevisitedStore both incoming and outgoing edges and slightly modify the adjacency lists.
1. Represent the graph with two lists on each vertex (incoming edges and outgoing edges)
2. Make an empty queue Q;
3. Make an empty topologically sorted list T;
4. Push all items with no predecessors in Q;
5. While Q is not empty
a. Dequeue from Q into u;
b. Push u in T;
c. Remove all outgoing edges from u;
6. Return T;
This approach will give us a better performance than the “brute force” approach. The running time complexity is O(|V| + |E|). The problem is that we need additional space and an operational queue, but this approach is a perfect example of how by using additional space you can get a better performing algorithm.
Use Modified DFS
From http://www.geeksforgeeks.org/topological-sorting/
We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
Java Code https://sites.google.com/site/indy256/algo/topological_sorting
http://algs4.cs.princeton.edu/44sp/Topological.java.html
static void dfs(List<Integer>[] graph, boolean[] used, List<Integer> res, int u) {
used[u] = true;
for (int v : graph[u])
if (!used[v])
dfs(graph, used, res, v);
res.add(u);
}
public static List<Integer> topologicalSort(List<Integer>[] graph) {
int n = graph.length;
boolean[] used = new boolean[n];
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++)
if (!used[i])
dfs(graph, used, res, i);
Collections.reverse(res);
return res;
}
private int V; // No. of vertices private LinkedList<Integer> adj[]; // Adjacency List //Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList(); } // Function to add an edge into the graph void addEdge(int v,int w) { adj[v].add(w); } // A recursive function used by topologicalSort void topologicalSortUtil(int v, Boolean visited[],Stack stack) { // Mark the current node as visited. visited[v] = true; Integer i; // Recur for all the vertices adjacent to this vertex Iterator<Integer> it = adj[v].iterator(); while (it.hasNext()) { i = it.next(); if (!visited[i]) topologicalSortUtil(i, visited, stack); } // Push current vertex to stack which stores result stack.push(new Integer(v)); } // The function to do Topological Sort. It uses recursive // topologicalSortUtil() void topologicalSort() { Stack stack = new Stack(); // Mark all the vertices as not visited Boolean visited[] = new Boolean[V]; // use boolean[] for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to store Topological // Sort starting from all vertices one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, stack); // Print contents of stack while (stack.empty()==false) System.out.print(stack.pop() + " "); }
The overall time complexity of this basic algorithm is O(n+m). The O(n) comes from the number of times that the while loop (and initial for loop) is executed, and the O(m) from the nested for loop.
Although there is no way to calculate how many times the inner loop will be executed on any one iteration of the outer loop, it will only be executed once for each successor of each member, which means that the total number of times that it will be executed is the total number of successors of all the members -- or the total number of relations.
Space complexity is also O(n+m). The O(n) component comes from the predecessor count information stored for each member, and the maximum length of the auxiliary queue. The O(m) comes from storing the successors for each member; once again, the total number of successors is the number of relations, so O(m).
Cycles
The basic algorithm's usefulness may be limited because of its inability to give detailed information about cycles. In practice, there are often one or more cycles in real-world problems. In program analysis, mutually recursive functions cause cycles.
In The Design and Analysis of Computer Algorithms (Addison Wesley, 1974), Aho, Hopcroft, and Ullman present a complete -- and efficient -- algorithm for identifying strongly connected components in a graph, which we can use for finding cycles.
The basic approach is to iterate through all the members of the set and perform a depth-first search of the relations from each. As we visit each member for the first time, we number it (Aho et al. refer to this as the "depth-first number") and push it onto a stack.
For each member, we also keep a record of the lowest-numbered potential root of a cycle involving that member. Initially, this is simply the member itself; when we are done with the depth-first search from a member, if any of its successors has a lower-numbered potential root, we update the member's potential root.
A member is potentially the base of a cycle if its lowest-numbered potential root is itself. Because the search is depth-first, any cycle will end up at the end of the stack, so we can find the cycle by popping the stack repeatedly until we get to the base node. (Unlike the Aho et al. algorithm, we ignore members that do not have any members following them on the stack; these members are not in any cycle.) Since each member is popped off the stack only once, it is in at most one cycle. The file topsort.h (available electronically; see "Availability," page 3) implements this algorithm.
https://en.wikipedia.org/wiki/Topological_sortingKahn's algorithm
choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty acyclic graph. Then:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
If the graph is a DAG, a solution will be contained in the list L (the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sorting is impossible.
Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created. A variation of Kahn's algorithm that breaks ties lexicographically forms a key component of the Coffman–Graham algorithm for parallel scheduling and layered graph drawing.
DFS
An alternative algorithm for topological sorting is based on depth-first search. The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node):
L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)
function visit(node n)
if n has a temporary mark then stop (not a DAG)
if n is not marked (i.e. has not been visited yet) then
mark n temporarily
for each node m with an edge from n to m do
visit(m)
mark n permanently
unmark n temporarily
add n to head of L
Also check http://www.sanfoundry.com/java-program-topological-sorting-graphs/
Read full article from Algorithm of the Week: Topological Sort of a Graph | Architects Zone
