C++ Programming Code Examples C++ > Sorting Searching Code Examples Generate a Random Directed Acyclic Graph DAC for a Given Number of Edges Generate a Random Directed Acyclic Graph DAC for a Given Number of Edges - This algorithm generates a random directed acyclic graph for the given edges 'e'. - The time complexity of this algorithm is O(e*v*e). - This algorithm takes the input of the number of edges 'e' in the random DAG. - It connects two random vertexes and checks for any cycle generated due to this edge. - If yes discard this edge and generate random vertex pair again. - Exit. #include<iostream> #include<stdlib.h> // The maximum number of the vertex for the sample random graph. #define NOV 20 using namespace std; // A function to check for the cycle, on addition of a new edge in the random graph. bool CheckAcyclic(int edge[][2], int ed, bool check[], int v) { int i; bool value; // If the current vertex is visited already, then the graph contains cycle. if(check[v] == true) { return false; } else { check[v] = true; // For each vertex, go for all the vertex connected to it. for(i = ed; i >= 0; i--) { if(edge[i][0] == v) { return CheckAcyclic(edge, ed, check, edge[i][1]); } } } // In case, if the path ends then reassign the vertexes visited in that path to false again. check[v] = false; if(i == 0) return true; } // A function to generate random graph. void GenerateRandGraphs(int e) { int i, j, edge[e][2], count; bool check[21]; // Build a connection between two random vertex. i = 0; while(i < e) { edge[i][0] = rand()%NOV+1; edge[i][1] = rand()%NOV+1; for(j = 1; j <= 20; j++)check[j] = false; if(CheckAcyclic(edge, i, check, edge[i][0]) == true) i++; } // Print the random graph. cout<<"\nThe generated random random graph is: "; for(i = 0; i < NOV; i++) { count = 0; cout<<"\n\t"<<i+1<<"-> { "; for(j = 0; j < e; j++) { if(edge[j][0] == i+1) { cout<<edge[j][1]<<" "; count++; } else if(edge[j][1] == i+1) { count++; } else if(j == e-1 && count == 0) cout<<"Isolated Vertex!"; } cout<<" }"; } } int main() { int e; cout<<"Enter the number of edges for the random graphs: "; cin>>e; // A function to generate a random undirected graph with e edges. GenerateRandGraphs(e); }