Generating Random Unweighted Trees
- Since this is a tree, the test data generation plan is such that no cycle gets formed.
- The number of edges is one less than the number of vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUM-1 lines are of the form (a b) where a is the parent of b
CPP
// A C++ Program to generate test cases for// an unweighted tree#include<bits/stdc++.h>using namespace std;// Define the number of runs for the test data// generated#define RUN 5// Define the maximum number of nodes of the tree#define MAXNODE 20class Tree{ int V; // No. of vertices // Pointer to an array containing adjacency listss list<int> *adj; // used by isCyclic() bool isCyclicUtil(int v, bool visited[], bool *rs);public: Tree(int V); // Constructor void addEdge(int v, int w); // adds an edge void removeEdge(int v, int w); // removes an edge // returns true if there is a cycle in this graph bool isCyclic();};// ConstructorTree::Tree(int V){ this->V = V; adj = new list<int>[V];}void Tree::addEdge(int v, int w){ adj[v].push_back(w); // Add w to v’s list.}void Tree::removeEdge(int v, int w){ list<int>::iterator it; for (it=adj[v].begin(); it!=adj[v].end(); it++) { if (*it == w) { adj[v].erase(it); break; } } return;}// This function is a variation of DFSUytil() inbool Tree::isCyclicUtil(int v, bool visited[], bool *recStack){ if (visited[v] == false) { // Mark the current node as visited and part of // recursion stack visited[v] = true; recStack[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i] && isCyclicUtil(*i, visited, recStack)) return true; else if (recStack[*i]) return true; } } recStack[v] = false; // remove the vertex from recursion stack return false;}// Returns true if the graph contains a cycle, else false.// This function is a variation of DFS() inbool Tree::isCyclic(){ // Mark all the vertices as not visited and not part of recursion // stack bool *visited = new bool[V]; bool *recStack = new bool[V]; for(int i = 0; i < V; i++) { visited[i] = false; recStack[i] = false; } // Call the recursive helper function to detect cycle in different // DFS trees for (int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true; return false;}int main(){ set<pair<int, int>> container; set<pair<int, int>>::iterator it; // Uncomment the below line to store // the test data in a file // freopen ("Test_Cases_Unweighted_Tree.in", "w", stdout); //For random values every time srand(time(NULL)); int NUM; // Number of Vertices/Nodes for (int i=1; i<=RUN; i++) { NUM = 1 + rand() % MAXNODE; // First print the number of vertices/nodes printf("%d\n", NUM); Tree t(NUM); // Then print the edges of the form (a b) // where 'a' is parent of 'b' for (int j=1; j<=NUM-1; j++) { int a = rand() % NUM; int b = rand() % NUM; pair<int, int> p = make_pair(a, b); t.addEdge(a, b); // Search for a random "new" edge everytime while (container.find(p) != container.end() || t.isCyclic() == true) { t.removeEdge(a, b); a = rand() % NUM; b = rand() % NUM; p = make_pair(a, b); t.addEdge(a, b); } container.insert(p); } for (it=container.begin(); it!=container.end(); ++it) printf("%d %d\n", it->first, it->second); container.clear(); printf("\n"); } // Uncomment the below line to store // the test data in a file // fclose(stdout); return(0);} |
C#
using System;using System.Collections.Generic;namespace UnweightedTreeTestCasesGenerator{ class Program { const int RUN = 5; const int MAXNODE = 20; class Tree { int V; List<int>[] adj; bool isCyclicUtil(int v, bool[] visited, bool[] recStack) { if (!visited[v]) { visited[v] = true; recStack[v] = true; foreach (int i in adj[v]) { if (!visited[i] && isCyclicUtil(i, visited, recStack)) return true; else if (recStack[i]) return true; } } recStack[v] = false; return false; } public Tree(int V) { this.V = V; adj = new List<int>[V]; for (int i = 0; i < V; i++) adj[i] = new List<int>(); } public void addEdge(int v, int w) { adj[v].Add(w); } public void removeEdge(int v, int w) { adj[v].Remove(w); } public bool isCyclic() { bool[] visited = new bool[V]; bool[] recStack = new bool[V]; for (int i = 0; i < V; i++) { visited[i] = false; recStack[i] = false; } for (int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true; return false; } } static void Main(string[] args) { HashSet<Tuple<int, int>> container = new HashSet<Tuple<int, int>>(); Random rand = new Random(); for (int i = 1; i <= RUN; i++) { int NUM = rand.Next(1, MAXNODE + 1); Console.WriteLine(NUM); Tree t = new Tree(NUM); for (int j = 1; j <= NUM - 1; j++) { int a = rand.Next(NUM); int b = rand.Next(NUM); Tuple<int, int> p = Tuple.Create(a, b); t.addEdge(a, b); while (container.Contains(p) || t.isCyclic()) { t.removeEdge(a, b); a = rand.Next(NUM); b = rand.Next(NUM); p = Tuple.Create(a, b); t.addEdge(a, b); } container.Add(p); } foreach (Tuple<int, int> p in container) Console.WriteLine($"{p.Item1} {p.Item2}"); container.Clear(); Console.WriteLine(); } } }} |
Time Complexity : O(V + E)
Space Complexity : O(V)
Generating Random Weighted Trees
- Since this is a tree, the test data generation plan is such that no cycle gets formed.
- The number of edges is one less than the number of vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUM-1 lines are of the form (a b wt) where a is the parent of b and the edge has a weight of wt
CPP
// A C++ Program to generate test cases for// an unweighted tree#include<bits/stdc++.h>using namespace std;// Define the number of runs for the test data// generated#define RUN 5// Define the maximum number of nodes of the tree#define MAXNODE 20class Tree{ int V; // No. of vertices // Pointer to an array containing adjacency listss list<int> *adj; // used by isCyclic() bool isCyclicUtil(int v, bool visited[], bool *rs);public: Tree(int V); // Constructor void addEdge(int v, int w); // adds an edge void removeEdge(int v, int w); // removes an edge // returns true if there is a cycle in this graph bool isCyclic();};// ConstructorTree::Tree(int V){ this->V = V; adj = new list<int>[V];}void Tree::addEdge(int v, int w){ adj[v].push_back(w); // Add w to v’s list.}void Tree::removeEdge(int v, int w){ list<int>::iterator it; for (it=adj[v].begin(); it!=adj[v].end(); it++) { if (*it == w) { adj[v].erase(it); break; } } return;}// This function is a variation of DFSUytil() inbool Tree::isCyclicUtil(int v, bool visited[], bool *recStack){ if (visited[v] == false) { // Mark the current node as visited and part of // recursion stack visited[v] = true; recStack[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i] && isCyclicUtil(*i, visited, recStack)) return true; else if (recStack[*i]) return true; } } recStack[v] = false; // remove the vertex from recursion stack return false;}// Returns true if the graph contains a cycle, else false.// This function is a variation of DFS() inbool Tree::isCyclic(){ // Mark all the vertices as not visited and not part of recursion // stack bool *visited = new bool[V]; bool *recStack = new bool[V]; for(int i = 0; i < V; i++) { visited[i] = false; recStack[i] = false; } // Call the recursive helper function to detect cycle in different // DFS trees for (int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true; return false;}int main(){ set<pair<int, int>> container; set<pair<int, int>>::iterator it; // Uncomment the below line to store // the test data in a file // freopen ("Test_Cases_Unweighted_Tree.in", "w", stdout); //For random values every time srand(time(NULL)); int NUM; // Number of Vertices/Nodes for (int i=1; i<=RUN; i++) { NUM = 1 + rand() % MAXNODE; // First print the number of vertices/nodes printf("%d\n", NUM); Tree t(NUM); // Then print the edges of the form (a b) // where 'a' is parent of 'b' for (int j=1; j<=NUM-1; j++) { int a = rand() % NUM; int b = rand() % NUM; pair<int, int> p = make_pair(a, b); t.addEdge(a, b); // Search for a random "new" edge everytime while (container.find(p) != container.end() || t.isCyclic() == true) { t.removeEdge(a, b); a = rand() % NUM; b = rand() % NUM; p = make_pair(a, b); t.addEdge(a, b); } container.insert(p); } for (it=container.begin(); it!=container.end(); ++it) printf("%d %d\n", it->first, it->second); container.clear(); printf("\n"); } // Uncomment the below line to store // the test data in a file // fclose(stdout); return(0);} |
Python3
# A Python3 program to generate test cases for# an unweighted treeimport random# Define the number of runs for the test data# generatedRUN = 5# Define the maximum number of nodes of the treeMAXNODE = 20# Define the maximum weight of edgesMAXWEIGHT = 200class Tree: def __init__(self, V): self.V = V self.adj = [[] for i in range(V)] def addEdge(self, v, w): self.adj[v].append(w) def removeEdge(self, v, w): for i in self.adj[v]: if i == w: self.adj[v].remove(i) break return # This function is a variation of DFSUytil() in def isCyclicUtil(self, v, visited, recStack): visited[v] = True recStack[v] = True # Recur for all the vertices adjacent to this vertex for i in self.adj[v]: if visited[i] == False and self.isCyclicUtil(i, visited, recStack): return True elif recStack[i]: return True # remove the vertex from recursion stack recStack[v] = False return False # Returns true if the graph contains a cycle, else false. # This function is a variation of DFS() in def isCyclic(self): # Mark all the vertices as not visited and not part # of recursion stack visited = [False] * self.V recStack = [False] * self.V # Call the recursive helper function to detect cycle # in different DFS trees for i in range(self.V): if visited[i] == False: if self.isCyclicUtil(i, visited, recStack) == True: return True return Falsefor i in range(RUN): NUM = 1 + random.randint(0, MAXNODE-1) # First print the number of vertices/nodes print(NUM) t = Tree(NUM) # Then print the edges of the form (a b) # where 'a' is parent of 'b' for j in range(NUM-1): a = random.randint(0, NUM-1) b = random.randint(0, NUM-1) t.addEdge(a, b) # Search for a random "new" edge everytime while t.isCyclic() == True: t.removeEdge(a, b) a = random.randint(0, NUM-1) b = random.randint(0, NUM-1) t.addEdge(a, b) # Then print the weights of the form (a b wt) for j in range(NUM-1): a = random.randint(0, NUM-1) b = random.randint(0, NUM-1) wt = 1 + random.randint(0, MAXWEIGHT-1) print(f"{a} {b} {wt}") print() |
Time Complexity : O(V + E)
Space Complexity : O(V)
If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!