Test case generator for Tree using Disjoint-Set Union
In this article, we will generate test cases such that given set edges form a Tree. Below are the two conditions of the Tree:
- It should have one less edge than the number of vertices.
- There should be no cycle in it.
Approach: The idea is to run a loop and add one edge each time that is generated randomly, and for adding each edge we will check whether it is forming cycle or not. We can ensure that cycle is present or not with the help of Disjoint-Set Union. If adding any edges form cycle then ignore the current edges and generate the new set of edges. Else print the edges with randomly generated weight. Below is the implementation of the above approach:
C++
// C++ implementation to generate// test-case for the Tree#include <bits/stdc++.h>using namespace std;typedef long long int ll;#define fast ios_base::sync_with_stdio(false);#define MOD 1000000007// Maximum Number Of Nodes#define MAXNODE 10;// Maximum Number Of testCases#define MAXT 10;// Maximum weight#define MAXWEIGHT 100;// Function for the path// compression techniquell find(ll parent[], ll x){ // If parent found if (parent[x] == x) return x; // Find parent recursively parent[x] = find(parent, parent[x]); // Return the parent node of x return parent[x];}// Function to compute the union// by rankvoid merge(ll parent[], ll size[], ll x, ll y){ ll r1 = find(parent, x); ll r2 = find(parent, y); if (size[r1] < size[r2]) { parent[r1] = r2; size[r2] += size[r1]; } else { parent[r2] = r1; size[r1] += size[r2]; }}// Function to generate the// test-cases for the treevoid generate(){ ll t; t = 1 + rand() % MAXT; // Number of testcases cout << t << "\n"; while (t--) { // for 2<=Number of Nodes<=MAXNODE // Randomly generate number of edges ll n = 2 + rand() % MAXNODE; ll i; cout << n << "\n"; ll parent[n + 1]; ll size[n + 1]; // Initialise parent and // size arrays for (i = 1; i <= n; i++) { parent[i] = i; size[i] = 1; } vector<pair<ll, ll> > Edges; vector<ll> weights; // Now We have add N-1 edges for (i = 1; i <= n - 1; i++) { ll x = 1 + rand() % n; ll y = 1 + rand() % n; // Find edges till it does not // forms a cycle while (find(parent, x) == find(parent, y)) { x = 1 + rand() % n; y = 1 + rand() % n; } // Merge the nodes in tree merge(parent, size, x, y); // Store the current edge and weight Edges.push_back(make_pair(x, y)); ll w = 1 + rand() % MAXWEIGHT; weights.push_back(w); } // Print the set of edges // with weight for (i = 0; i < Edges.size(); i++) { cout << Edges[i].first << " " << Edges[i].second; cout << " " << weights[i]; cout << "\n"; } }}// Driver Codeint main(){ // Uncomment the below line to store // the test data in a file // freopen ("output.txt", "w", stdout); // For random values every time srand(time(NULL)); fast; generate();} |
Java
import java.util.*;public class TreeTestCases { // Maximum Number Of Nodes static final int MAXNODE = 10; // Maximum Number Of testCases static final int MAXT = 10; // Maximum weight static final int MAXWEIGHT = 100; // Function for the path compression technique static int find(int[] parent, int x) { // If parent found if (parent[x] == x) { return x; } // Find parent recursively parent[x] = find(parent, parent[x]); // Return the parent node of x return parent[x]; } // Function to compute the union by rank static void merge(int[] parent, int[] size, int x, int y) { int r1 = find(parent, x); int r2 = find(parent, y); if (size[r1] < size[r2]) { parent[r1] = r2; size[r2] += size[r1]; } else { parent[r2] = r1; size[r1] += size[r2]; } } // Function to generate the test-cases for the tree static void generate() { Random rand = new Random(); // Number of testcases int t = rand.nextInt(MAXT) + 1; System.out.println(t); for (int i = 0; i < t; i++) { // for 2<=Number of Nodes<=MAXNODE // Randomly generate number of edges int n = rand.nextInt(MAXNODE - 1) + 2; System.out.println(n); int[] parent = new int[n + 1]; int[] size = new int[n + 1]; for (int j = 1; j <= n; j++) { parent[j] = j; size[j] = 1; } List<int[]> edges = new ArrayList<>(); List<Integer> weights = new ArrayList<>(); // Now We have to add N-1 edges for (int j = 0; j < n - 1; j++) { int x = rand.nextInt(n) + 1; int y = rand.nextInt(n) + 1; // Find edges till it does not forms a cycle while (find(parent, x) == find(parent, y)) { x = rand.nextInt(n) + 1; y = rand.nextInt(n) + 1; } // Merge the nodes in tree merge(parent, size, x, y); // Store the current edge and weight edges.add(new int[] {x, y}); int w = rand.nextInt(MAXWEIGHT) + 1; weights.add(w); } // Print the set of edges with weight for (int j = 0; j < edges.size(); j++) { int[] edge = edges.get(j); System.out.println(edge[0] + " " + edge[1] + " " + weights.get(j)); } } } // Driver Code public static void main(String[] args) { // For random values every time Random rand = new Random(); rand.setSeed(System.currentTimeMillis()); generate(); }} |
Python3
# Python3 implementation to generate# test-case for the Treeimport random# Maximum Number Of NodesMAXNODE = 10# Maximum Number Of testCasesMAXT = 10# Maximum weightMAXWEIGHT = 100# Function for the path# compression techniquedef find(parent, x): # If parent found if parent[x] == x: return x # Find parent recursively parent[x] = find(parent, parent[x]) # Return the parent node of x return parent[x]# Function to compute the union# by rankdef merge(parent, size, x, y): r1 = find(parent, x) r2 = find(parent, y) if size[r1] < size[r2]: parent[r1] = r2 size[r2] += size[r1] else: parent[r2] = r1 size[r1] += size[r2]# Function to generate the# test-cases for the treedef generate(): # Number of testcases t = random.randint(1, MAXT) print(t) for _ in range(t): # for 2<=Number of Nodes<=MAXNODE # Randomly generate number of edges n = random.randint(2, MAXNODE) print(n) parent = [i for i in range(n + 1)] size = [1 for _ in range(n + 1)] Edges = [] weights = [] # Now We have add N-1 edges for i in range(n - 1): x = random.randint(1, n) y = random.randint(1, n) # Find edges till it does not # forms a cycle while find(parent, x) == find(parent, y): x = random.randint(1, n) y = random.randint(1, n) # Merge the nodes in tree merge(parent, size, x, y) # Store the current edge and weight Edges.append((x, y)) w = random.randint(1, MAXWEIGHT) weights.append(w) # Print the set of edges # with weight for i in range(len(Edges)): print(Edges[i][0], Edges[i][1], weights[i])# Driver Codeif __name__ == "__main__": # Uncomment the below line to store # the test data in a file # open("output.txt", "w").close() # open("output.txt", "w").write(generate()) # For random values every time random.seed(None) generate() # This code is contributed by Potta Lokesh |
C#
// C# implementation to generate// test-case for the Treeusing System;using System.Collections.Generic;class GFG { static int MAXNODE = 10; static int MAXT = 10; static int MAXWEIGHT = 100; static int[] parent = new int[MAXNODE + 1]; static int[] size = new int[MAXNODE + 1]; // Function for the path // compression technique static int find(int[] parent, int x) { // If parent found if (parent[x] == x) return x; // Find parent recursively parent[x] = find(parent, parent[x]); // Return the parent node of x return parent[x]; } // Function to compute the union // by rank static void merge(int[] parent, int[] size, int x, int y) { int r1 = find(parent, x); int r2 = find(parent, y); if (size[r1] < size[r2]) { parent[r1] = r2; size[r2] += size[r1]; } else { parent[r2] = r1; size[r1] += size[r2]; } } // Function to generate the // test-cases for the tree static void generate() { Random rand = new Random(); int t = 1 + rand.Next() % MAXT; // Number of testcases Console.WriteLine(t); while (t-- > 0) { // for 2<=Number of Nodes<=MAXNODE // Randomly generate number of edges int n = 2 + rand.Next() % MAXNODE; int i; Console.WriteLine(n); // Initialise parent and // size arrays for (i = 1; i <= n; i++) { parent[i] = i; size[i] = 1; } List<Tuple<int, int> > Edges = new List<Tuple<int, int> >(); List<int> weights = new List<int>(); // Now We have add N-1 edges for (i = 1; i <= n - 1; i++) { int x = 1 + rand.Next() % n; int y = 1 + rand.Next() % n; // Find edges till it does not // forms a cycle while (find(parent, x) == find(parent, y)) { x = 1 + rand.Next() % n; y = 1 + rand.Next() % n; } // Merge the nodes in tree merge(parent, size, x, y); // Store the current edge and weight Edges.Add(new Tuple<int, int>(x, y)); int w = 1 + rand.Next() % MAXWEIGHT; weights.Add(w); } // Print the set of edges // with weight for (i = 0; i < Edges.Count; i++) { Console.WriteLine(Edges[i].Item1 + " " + Edges[i].Item2 + " " + weights[i]); } } } // Driver Code static void Main() { // Uncomment the below line to store // the test data in a file // System.setOut(new PrintStream(new // File("output.txt"))); // For random values every time Random rand = new Random(); generate(); }} |
Javascript
// JavaScript implementation to generate// test-case for the Treeconst MAXNODE = 10;const MAXT = 10;const MAXWEIGHT = 100;const parent = new Array(MAXNODE + 1);const size = new Array(MAXNODE + 1);// Function for the path// compression techniquefunction find(parent, x) { // If parent found if (parent[x] == x) return x; // Find parent recursively parent[x] = find(parent, parent[x]); // Return the parent node of x return parent[x];}// Function to compute the union// by rankfunction merge(parent, size, x, y) { let r1 = find(parent, x); let r2 = find(parent, y); if (size[r1] < size[r2]) { parent[r1] = r2; size[r2] += size[r1]; } else { parent[r2] = r1; size[r1] += size[r2]; }}// Function to generate the// test-cases for the treefunction generate() { let t = 1 + Math.floor(Math.random() * MAXT); // Number of testcases console.log(t); while (t-- > 0) { // for 2<=Number of Nodes<=MAXNODE // Randomly generate number of edges let n = 2 + Math.floor(Math.random() * MAXNODE); let i; console.log(n); // Initialise parent and // size arrays for (i = 1; i <= n; i++) { parent[i] = i; size[i] = 1; } const Edges = []; const weights = []; // Now We have add N-1 edges for (i = 1; i <= n - 1; i++) { let x = 1 + Math.floor(Math.random() * n); let y = 1 + Math.floor(Math.random() * n); // Find edges till it does not // forms a cycle while (find(parent, x) == find(parent, y)) { x = 1 + Math.floor(Math.random() * n); y = 1 + Math.floor(Math.random() * n); } // Merge the nodes in tree merge(parent, size, x, y); // Store the current edge and weight Edges.push([x, y]); let w = 1 + Math.floor(Math.random() * MAXWEIGHT); weights.push(w); } // Print the set of edges // with weight for (i = 0; i < Edges.length; i++) { console.log(`${Edges[i][0]} ${Edges[i][1]} ${weights[i]}`); } }}// Driver Codegenerate(); |
Output:
1 10 4 2 67 8 3 64 6 5 31 7 6 77 8 2 64 9 2 44 5 9 10 1 6 71 10 7 32
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
