C++ Program to Create a Random Linear Extension for a DAG

This is a C++ Program to find random linear extension of DAG. Linear extension is another term for finding topological sort of a graph.

Here is source code of the C++ Program to Create a Random Linear Extension for a DAG. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // A C++ program to print topological sorting of a DAG
  2. #include<iostream>
  3. #include <list>
  4. #include <stack>
  5. using namespace std;
  6.  
  7. // Class to represent a graph
  8. class Graph
  9. {
  10.         int V; // No. of vertices'
  11.  
  12.         // Pointer to an array containing adjacency listsList
  13.         list<int> *adj;
  14.  
  15.         // A function used by topologicalSort
  16.         void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
  17.     public:
  18.         Graph(int V); // Constructor
  19.  
  20.         // function to add an edge to graph
  21.         void addEdge(int v, int w);
  22.  
  23.         // prints a Topological Sort of the complete graph
  24.         void topologicalSort();
  25. };
  26.  
  27. Graph::Graph(int V)
  28. {
  29.     this->V = V;
  30.     adj = new list<int> [V];
  31. }
  32.  
  33. void Graph::addEdge(int v, int w)
  34. {
  35.     adj[v].push_back(w); // Add w to v’s list.
  36. }
  37.  
  38. // A recursive function used by topologicalSort
  39. void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
  40. {
  41.     // Mark the current node as visited.
  42.     visited[v] = true;
  43.  
  44.     // Recur for all the vertices adjacent to this vertex
  45.     list<int>::iterator i;
  46.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  47.         if (!visited[*i])
  48.             topologicalSortUtil(*i, visited, Stack);
  49.  
  50.     // Push current vertex to stack which stores result
  51.     Stack.push(v);
  52. }
  53.  
  54. // The function to do Topological Sort. It uses recursive topologicalSortUtil()
  55. void Graph::topologicalSort()
  56. {
  57.     stack<int> Stack;
  58.  
  59.     // Mark all the vertices as not visited
  60.     bool *visited = new bool[V];
  61.     for (int i = 0; i < V; i++)
  62.         visited[i] = false;
  63.  
  64.     // Call the recursive helper function to store Topological Sort
  65.     // starting from all vertices one by one
  66.     for (int i = 0; i < V; i++)
  67.         if (visited[i] == false)
  68.             topologicalSortUtil(i, visited, Stack);
  69.  
  70.     // Print contents of stack
  71.     while (Stack.empty() == false)
  72.     {
  73.         cout << Stack.top() << " ";
  74.         Stack.pop();
  75.     }
  76. }
  77.  
  78. // Driver program to test above functions
  79. int main()
  80. {
  81.     // Create a graph given in the above diagram
  82.     Graph g(6);
  83.     g.addEdge(5, 2);
  84.     g.addEdge(5, 0);
  85.     g.addEdge(4, 0);
  86.     g.addEdge(4, 1);
  87.     g.addEdge(2, 3);
  88.     g.addEdge(3, 0);
  89.  
  90.     cout << "Following is a Topological Sort of the given graph \n";
  91.     g.topologicalSort();
  92.  
  93.     return 0;
  94. }

Output:

$ g++ RandomLinearExtensionOfDAG.cpp
$ a.out
 
Following is a Topological Sort of the given graph 
5 4 2 3 1 0
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.