graph theory

What is topological sort:


Reference:
https://www.youtube.com/watch?v=ddTC4Zovtbc
http://www.geeksforgeeks.org/topological-sorting/


Khan's algorithm for topological sorting:

http://connalle.blogspot.in/2013/10/topological-sortingkahn-algorithm.html

Topological sorting

Introduction:

A topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

The graph shown to the left has many valid topological sorts, including: 7, 5, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom) 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first) 3, 7, 8, 5, 11, 10, 2, 9 (because we can) 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first) 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first) 7, 5, 11, 2, 3, 8, 9, 10

Algorithms:

Kahn Algorithm:

        Initialize sorted list to be empty, and a counter to 0

        Compute the indegrees of all nodes

        Store all nodes with indegree 0 in a queue

        While the queue is not empty

                get a node U and put it in the sorted list. Increment the counter.

                For all edges (U,V) decrement the indegree of V, and put V in the queue if the updated indegree is 0.

        If counter is not equal to the number of nodes, there is a cycle.

Recursive DFS Algorithm:

For this algorithm, edges point in the opposite direction as the previous algorithm (and the opposite direction to that shown in the diagram in the Examples section above).

        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

                add n to head of L

Complexity:

The number of operations is O(|E| + |V|), |V| - number of vertices, |E| - number of edges.
How many operations are needed to compute the indegrees?
Depends on the representation:
Adjacency lists: O(|E|)
Matrix: O(|V|²)

Code Implementation:

Kahn Algorithm

//Input : adj_list ->Adjacency list; indegree : indegrees of all nodes .....

void top_sort(vector<list<int> > & adj_list, vector<int> &indegree) {

      queue<int> tsort_queue;

      vector<int> sorted;

     

      //If a node is not present in the graph , its indegree is -1.....

      for(int i = 0; i < (signed)indegree.size(); i++) {

            if(indegree[i] == -1)

                  continue;

            if(indegree[i] == 0)

            tsort_queue.push(i);

      }

     

      while(!tsort_queue.empty()) {

            int front = tsort_queue.front();

            tsort_queue.pop();

            sorted.push_back(front);

            list<int>::iterator it;

            for(it = adj_list[front].begin();

                        it != adj_list[front].end(); it++) {

                  indegree[*it] -= 1;

                  if(indegree[*it] == 0)

                        tsort_queue.push(*it);

            }

      }

      cout<<"Top Sorted Order : ";

      for(int i = 0; i < (signed)sorted.size(); i++)

            cout<<sorted[i]<<" ";

      cout<<endl;

}

DFS Algorithm:

//Top Sort using DFS .....

void top_sort_DFS_loop(vector<list<int> > adj_list,

            stack<int>& sorted, vector<bool>& visited, int node) {

      list<int>::iterator it;

      for(it = adj_list[node].begin(); it != adj_list[node].end(); it++) {

            if(visited[*it])

                  continue;

            visited[*it] = true;

            top_sort_DFS_loop(adj_list, sorted, visited, *it);

      }

      sorted.push(node);

}

void top_sort_DFS(vector<list<int> > adj_list) {

      stack<int> sorted;

      vector<bool> visited(adj_list.size(), false);

      for(int i = 0; i < (signed)adj_list.size(); i++) {

            if(visited[i])

                  continue;

            visited[i] = true;

            top_sort_DFS_loop(adj_list, sorted, visited, i);

      }

      cout<<"Top Sort Using DFS : ";

      while(!sorted.empty()) {

            cout<<sorted.top()<<" ";

            sorted.pop();

      }

      cout<<endl;

}

Note : The above codes only accepts DAG.


Applications : 

Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers.

Dijkstra's algorithm