Generating Random Directed Unweighted Graphs
- Since this is a graph, the test data generation plan doesn’t guarantee that a cycle gets formed or not.
- The number of edges – NUMEDGE is greater than zero and less than NUM*(NUM-1)/2, where NUM = Number of Vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUMEDGE lines are of the form (a b) where a is connected to b and the edge is directed from a to b (a->b)
- Each of the NUMEDGE lines will have distinct edges, for e.g – if (1, 2) is there in one of the NUMEDGE lines then it is guaranteed, that (1, 2) will not be there in the remaining NUMEDGE-1 lines as this is a directed graph.
Example
CPP
// A C++ Program to generate test cases for// an unweighted directed graph#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 vertices of the graph#define MAX_VERTICES 20// Define the maximum number of edges#define MAX_EDGES 200int 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_Directed_Unweighted_Graph.in", // "w", stdout); // For random values every time srand(time(NULL)); int NUM; // Number of Vertices int NUMEDGE; // Number of Edges for (int i = 1; i <= RUN; i++) { NUM = 1 + rand() % MAX_VERTICES; // Define the maximum number of edges of the graph // Since the most dense graph can have N*(N-1)/2 // edges where N = number of vertices in the graph NUMEDGE = 1 + rand() % MAX_EDGES; while (NUMEDGE > NUM * (NUM - 1) / 2) NUMEDGE = 1 + rand() % MAX_EDGES; // First print the number of vertices and edges printf("%d %d\n", NUM, NUMEDGE); // Then print the edges of the form (a b) // where 'a' is connected to 'b' for (int j = 1; j <= NUMEDGE; j++) { int a = 1 + rand() % NUM; int b = 1 + rand() % NUM; pair<int, int> p = make_pair(a, b); // Search for a random "new" edge everytime // Note - In a tree the edge (a, b) is same // as the edge (b, a) while (container.find(p) != container.end()) { a = 1 + rand() % NUM; b = 1 + rand() % NUM; p = make_pair(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);} |
Java
// Java code addition import java.util.*;public class Main { static class Pair<K, V> { K first; V second; Pair(K first, V second) { this.first = first; this.second = second; } } // Define the number of runs for the test data generated static final int RUN = 5; // Define the maximum number of vertices of the graph static final int MAX_VERTICES = 20; // Define the maximum number of edges static final int MAX_EDGES = 200; public static void main(String[] args) { Set<Pair<Integer, Integer>> container; Iterator<Pair<Integer, Integer>> it; // Uncomment the below line to store the test data in a file // System.setOut(new PrintStream(new FileOutputStream("Test_Cases_Directed_Unweighted_Graph.in"))); // For random values every time Random rand = new Random(); int NUM; // Number of vertices int NUMEDGE; // Number of edges for (int i = 1; i <= RUN; i++) { NUM = 1 + rand.nextInt(MAX_VERTICES); // Define the maximum number of edges of the graph // Since the most dense graph can have N*(N-1)/2 // edges where N = number of vertices in the graph NUMEDGE = 1 + rand.nextInt(MAX_EDGES); while (NUMEDGE > NUM * (NUM - 1) / 2) NUMEDGE = 1 + rand.nextInt(MAX_EDGES); // First print the number of vertices and edges System.out.println(NUM + " " + NUMEDGE); container = new HashSet<>(); // Then print the edges of the form (a b) where 'a' is connected to 'b' for (int j = 1; j <= NUMEDGE; j++) { int a = 1 + rand.nextInt(NUM); int b = 1 + rand.nextInt(NUM); Pair<Integer, Integer> p = new Pair<>(a, b); // Search for a random "new" edge everytime // Note - In a tree the edge (a, b) is same as the edge (b, a) while (container.contains(p)) { a = 1 + rand.nextInt(NUM); b = 1 + rand.nextInt(NUM); p = new Pair<>(a, b); } container.add(p); } for (it = container.iterator(); it.hasNext(); ) { Pair<Integer, Integer> p = it.next(); System.out.println(p.first + " " + p.second); } container.clear(); System.out.println(); } // Uncomment the below line to store the test data in a file // System.out.close(); }}// The code is contributed by Arushi Goel. |
Python3
import random# Define the number of runs for the test data generatedRUN = 5# Define the maximum number of vertices of the graphMAX_VERTICES = 20# Define the maximum number of edgesMAX_EDGES = 200for i in range(1, RUN+1): NUM = 1 + random.randint(0, MAX_VERTICES-1) # Define the maximum number of edges of the graph # Since the most dense graph can have N*(N-1)/2 edges # where N = number of vertices in the graph NUMEDGE = 1 + random.randint(0, MAX_EDGES-1) while NUMEDGE > NUM*(NUM-1)//2: NUMEDGE = 1 + random.randint(0, MAX_EDGES-1) # First print the number of vertices and edges print(f"{NUM} {NUMEDGE}") # Then print the edges of the form (a b) # where 'a' is connected to 'b' container = set() for j in range(1, NUMEDGE+1): a = 1 + random.randint(0, NUM-1) b = 1 + random.randint(0, NUM-1) p = (a, b) # Search for a random "new" edge everytime # Note - In a tree the edge (a, b) is same # as the edge (b, a) while p in container: a = 1 + random.randint(0, NUM-1) b = 1 + random.randint(0, NUM-1) p = (a, b) container.add(p) for a, b in container: print(f"{a} {b}") container.clear() print() |
C#
using System;using System.Collections.Generic;class Program { static void Main(string[] args) { // Define the number of runs for the test data // generated int RUN = 5; // Define the maximum number of vertices of the // graph int MAX_VERTICES = 20; // Define the maximum number of edges int MAX_EDGES = 200; Random random = new Random(); for (int i = 1; i <= RUN; i++) { int NUM = 1 + random.Next(0, MAX_VERTICES - 1); // Define the maximum number of edges of the // graph Since the most dense graph can have // N*(N-1)/2 edges where N = number of vertices // in the graph int NUMEDGE = 1 + random.Next(0, MAX_EDGES - 1); while (NUMEDGE > NUM * (NUM - 1) / 2) { NUMEDGE = 1 + random.Next(0, MAX_EDGES - 1); } // First print the number of vertices and edges Console.WriteLine($ "{NUM} {NUMEDGE}"); // Then print the edges of the form (a b) // where 'a' is connected to 'b' HashSet<Tuple<int, int> > container = new HashSet<Tuple<int, int> >(); for (int j = 1; j <= NUMEDGE; j++) { int a = 1 + random.Next(0, NUM - 1); int b = 1 + random.Next(0, NUM - 1); Tuple<int, int> p = new Tuple<int, int>(a, b); // Search for a random "new" edge everytime // Note - In a tree the edge (a, b) is same // as the edge (b, a) while (container.Contains(p)) { a = 1 + random.Next(0, NUM - 1); b = 1 + random.Next(0, NUM - 1); p = new Tuple<int, int>(a, b); } container.Add(p); } foreach(Tuple<int, int> p in container) { Console.WriteLine($ "{p.Item1} {p.Item2}"); } container.Clear(); Console.WriteLine(); } }} |
Javascript
// Javascript code addition // Define the number of runs for the test data generatedconst RUN = 5;// Define the maximum number of vertices of the graphconst MAX_VERTICES = 20;// Define the maximum number of edgesconst MAX_EDGES = 200;for (let i = 1; i <= RUN; i++) { const NUM = 1 + Math.floor(Math.random() * (MAX_VERTICES - 1)); // Define the maximum number of edges of the graph // Since the most dense graph can have N*(N-1)/2 edges // where N = number of vertices in the graph let NUMEDGE = 1 + Math.floor(Math.random() * (MAX_EDGES - 1)); while (NUMEDGE > (NUM * (NUM - 1)) / 2) { NUMEDGE = 1 + Math.floor(Math.random() * (MAX_EDGES - 1)); } // First print the number of vertices and edges console.log(`${NUM} ${NUMEDGE}`); // Then print the edges of the form (a b) // where 'a' is connected to 'b' const container = new Set(); for (let j = 1; j <= NUMEDGE; j++) { let a = 1 + Math.floor(Math.random() * NUM); let b = 1 + Math.floor(Math.random() * NUM); let p = `${a},${b}`; // Search for a random "new" edge everytime // Note - In a tree the edge (a, b) is same // as the edge (b, a) while (container.has(p)) { a = 1 + Math.floor(Math.random() * NUM); b = 1 + Math.floor(Math.random() * NUM); p = `${a},${b}`; } container.add(p); } for (let edge of container) { const [a, b] = edge.split(','); console.log(`${a} ${b}`); } container.clear(); console.log();}// The code is contributed by Arushi Goel. |
Generating Random Directed Weighted Graphs
- Since this is a graph, the test data generation plan doesn’t guarantee that a cycle gets formed or not.
- The number of edges – NUMEDGE is greater than zero and less than NUM*(NUM-1)/2, where NUM = Number of Vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUMEDGE lines are of the form (a b wt) where a is connected to b and the edge is directed from a to b (a->b) and the edge has a weight of wt
- Each of the NUMEDGE lines will have distinct edges, for e.g – if (1, 2) is there in one of the NUMEDGE lines then it is guaranteed, that (1, 2) will not be there in the remaining NUMEDGE-1 lines as this is a directed graph.
Example:
CPP
// A C++ Program to generate test cases for// a weighted directed graph#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 vertices of the graph#define MAX_VERTICES 20// Define the maximum number of edges#define MAX_EDGES 200// Define the maximum weight of edges#define MAXWEIGHT 200int 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_Directed_Weighted_Graph.in", // "w", stdout); // For random values every time srand(time(NULL)); int NUM; // Number of Vertices int NUMEDGE; // Number of Edges for (int i = 1; i <= RUN; i++) { NUM = 1 + rand() % MAX_VERTICES; // Define the maximum number of edges of the graph // Since the most dense graph can have N*(N-1)/2 // edges where N = n number of vertices in the graph NUMEDGE = 1 + rand() % MAX_EDGES; while (NUMEDGE > NUM * (NUM - 1) / 2) NUMEDGE = 1 + rand() % MAX_EDGES; // First print the number of vertices and edges printf("%d %d\n", NUM, NUMEDGE); // Then print the edges of the form (a b) // where 'a' is connected to 'b' for (int j = 1; j <= NUMEDGE; j++) { int a = 1 + rand() % NUM; int b = 1 + rand() % NUM; pair<int, int> p = make_pair(a, b); // Search for a random "new" edge every time // Note - In a tree the edge (a, b) is same // as the edge (b, a) while (container.find(p) != container.end()) { a = 1 + rand() % NUM; b = 1 + rand() % NUM; p = make_pair(a, b); } container.insert(p); } for (it = container.begin(); it != container.end(); ++it) { int wt = 1 + rand() % MAXWEIGHT; printf("%d %d %d\n", it->first, it->second, wt); } container.clear(); printf("\n"); } // Uncomment the below line to store // the test data in a file // fclose(stdout); return (0);} |
Java
// A Java Program to generate test cases for// a weighted directed graphimport java.util.*;public class TestCasesGenerator { // Define the number of runs for // the test data generated static final int RUN = 5; // Define the maximum number of // vertices of the graph static final int MAX_VERTICES = 20; // Define the maximum number of edges static final int MAX_EDGES = 200; // Define the maximum weight of edges static final int MAX_WEIGHT = 200; public static void main(String[] args) { Set<Pair<Integer, Integer> > container; container = new HashSet<>(); // Uncomment the below line to store // the test data in a file // System.setOut(new PrintStream(new // FileOutputStream("Test_Cases_Directed_Weighted_Graph.in"))); Random rand = new Random(); int NUM; // Number of Vertices int NUMEDGE; // Number of Edges for (int i = 1; i <= RUN; i++) { NUM = 1 + rand.nextInt(MAX_VERTICES); // Define the maximum number of edges of the // graph Since the most dense graph can have // N*(N-1)/2 edges where N = n number of // vertices in the graph NUMEDGE = 1 + rand.nextInt(MAX_EDGES); while (NUMEDGE > NUM * (NUM - 1) / 2) NUMEDGE = 1 + rand.nextInt(MAX_EDGES); // First print the number of vertices and edges System.out.println(NUM + " " + NUMEDGE); // Then print the edges of the form (a b) // where 'a' is connected to 'b' for (int j = 1; j <= NUMEDGE; j++) { int a = 1 + rand.nextInt(NUM); int b = 1 + rand.nextInt(NUM); Pair<Integer, Integer> p = new Pair<>(a, b); // Search for a random "new" edge every time // Note - In a tree the edge (a, b) is same // as the edge (b, a) while (container.contains(p)) { a = 1 + rand.nextInt(NUM); b = 1 + rand.nextInt(NUM); p = new Pair<>(a, b); } container.add(p); } for (Pair<Integer, Integer> p : container) { int wt = 1 + rand.nextInt(MAX_WEIGHT); System.out.println(p.getFirst() + " " + p.getSecond() + " " + wt); } container.clear(); System.out.println(); } // Uncomment the below line to store // the test data in a file // System.out.close(); } // Pair class to store a pair of integers static class Pair<T, U> { private T first; private U second; public Pair(T first, U second) { this.first = first; this.second = second; } public T getFirst() { return first; } public U getSecond() { return second; } }}// The code is contributed by Nidhi goel. |
Output
...63 17 14 92 18 1 62 18 3 161 18 13 182 18 18 83 19 1 20 19 15 96 19 17 196 3 1 3 1 88 17 104 1 1 109 1 5 104 1 7 72 1 10 116 2 1 184 2 4 115 2 5 180 2 7 94 2 8 139 2 9 113 2 11 130 2 14 119 2 15 121 2 16 24 3 3 88 3 5 55 3 6 137 3 12 158 3 13 16 3 15 66 4 5 196 4 11 165 4 12 197 4 14 186 4 15 97 5 1 59 5 3 107 5 7 46 5 9 104 5 15 115 5 17 109 6 1 164 6 4 171 6 6 180 6 8 31 6 11 154 6 14 46 6 15 162 6 17 199 7 9 185 7 11 75 7 15 80 7 17 103 8 1 147 8 2 56 8 7 142 8 9 2 8 14 192 8 15 100 8 16 169 8 17 10 9 2 95 9 7 133 9 8 6 9 12 33 9 17 29 10 3 65 10 6 91 10 7 26 10 8 120 10 9 5 10 14 135 10 17 35 11 8 175 11 9 66 11 12 18 11 15 80 12 2 112 12 3 179 12 4 30 12 5 96 12 9 5 12 11 110 12 16 150 13 1 152 13 5 165 13 9 92 13 14 153 13 15 108 13 16 191 14 1 73 14 2 117 14 5 37 14 6 5 14 7 123 14 11 69 14 13 185 14 17 139 15 1 111 15 3 10 15 6 10 15 7 116 15 9 144 15 10 196 15 14 42 15 16 162 16 4 13 16 5 74 16 6 73 16 7 144 16 10 103 16 17 120 17 12 148 17 13 12 9 3 2 2 74 5 5 111 9 2 15
Generating Random Undirected Unweighted Graphs
- Since this is a graph, the test data generation plan doesn’t guarantee that a cycle gets formed or not.
- The number of edges – NUMEDGE is greater than zero and less than NUM*(NUM-1)/2, where NUM = Number of Vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUMEDGE lines are of the form (a b) where a is connected to b
- Each of the NUMEDGE lines will have distinct edges, for e.g – if (1, 2) is there in one of the NUMEDGE lines then it is guaranteed, that (1, 2) and (2, 1) both will not be there in the remaining NUMEDGE-1 lines as this is an undirected graph.
CPP
// A C++ Program to generate test cases for// an unweighted undirected graph#include& lt; bits / stdc++.h & gt;using namespace std;// Define the number of runs for the test data// generated#define RUN 5// Define the maximum number of vertices of the graph#define MAX_VERTICES 20// Define the maximum number of edges#define MAX_EDGES 200int main(){ set& lt; pair& lt; int, int& gt; > container; set& lt; pair& lt; int, int& gt; > ::iterator it; // Uncomment the below line to store // the test data in a file // freopen("Test_Cases_Undirected_Unweighted_Graph.in", // "w", stdout); // For random values every time srand(time(NULL)); int NUM; // Number of Vertices int NUMEDGE; // Number of Edges for (int i = 1; i& lt; = RUN; i++) { NUM = 1 + rand() % MAX_VERTICES; // Define the maximum number of edges of the graph // Since the most dense graph can have N*(N-1)/2 // edges where N = number of vertices in the graph NUMEDGE = 1 + rand() % MAX_EDGES; while (NUMEDGE & gt; NUM * (NUM - 1) / 2) NUMEDGE = 1 + rand() % MAX_EDGES; // First print the number of vertices and edges printf(" % d % d\n & quot;, NUM, NUMEDGE); // Then print the edges of the form (a b) // where 'a' is connected to 'b' for (int j = 1; j& lt; = NUMEDGE; j++) { int a = rand() % NUM; int b = rand() % NUM; pair& lt; int, int& gt; p = make_pair(a, b); pair& lt; int, int& gt; reverse_p = make_pair(b, a); // Search for a random "new" edge // everytime Note - In a tree the edge (a, b) is // same as the edge (b, a) while (container.find(p) != container.end() || container.find(reverse_p) != container.end()) { a = rand() % NUM; b = rand() % NUM; p = make_pair(a, b); reverse_p = make_pair(b, a); } container.insert(p); } for (it = container.begin(); it != container.end(); ++it) printf(" % d % d\n & quot;, it - > first, it - > second); container.clear(); printf("\n & quot;); } // Uncomment the below line to store // the test data in a file // fclose(stdout); return (0);} |
Generating Random Undirected Weighted Graphs
- Since this is a graph, the test data generation plan doesn’t guarantee that a cycle gets formed or not.
- The number of edges – NUMEDGE is greater than zero and less than NUM*(NUM-1)/2, where NUM = Number of Vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUMEDGE lines are of the form (a b wt) where a is connected to b and the edge has a weight of wt
- Each of the NUMEDGE lines will have distinct edges, for e.g – if (1, 2) is there in one of the NUMEDGE lines then it is guaranteed, that (1, 2) and (2, 1) both will not be there in the remaining NUMEDGE-1 lines as this is an undirected graph.
CPP
// A C++ Program to generate test cases for// an weighted undirected graph#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 vertices of the graph#define MAX_VERTICES 20// Define the maximum number of edges#define MAX_EDGES 200// Define the maximum weight of edges#define MAXWEIGHT 200int 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_Undirected_Weighted_Graph.in", // "w", stdout); //For random values every time srand(time(NULL)); int NUM; // Number of Vertices int NUMEDGE; // Number of Edges for (int i=1; i<=RUN; i++) { NUM = 1 + rand() % MAX_VERTICES; // Define the maximum number of edges of the graph // Since the most dense graph can have N*(N-1)/2 edges // where N = number of vertices in the graph NUMEDGE = 1 + rand() % MAX_EDGES; while (NUMEDGE > NUM*(NUM-1)/2) NUMEDGE = 1 + rand() % MAX_EDGES; // First print the number of vertices and edges printf("%d %d\n", NUM, NUMEDGE); // Then print the edges of the form (a b) // where 'a' is connected to 'b' for (int j=1; j<=NUMEDGE; j++) { int a = rand() % NUM; int b = rand() % NUM; pair<int, int> p = make_pair(a, b); pair<int, int> reverse_p = make_pair(b, a); // Search for a random "new" edge everytime // Note - In a tree the edge (a, b) is same // as the edge (b, a) while (container.find(p) != container.end() || container.find(reverse_p) != container.end()) { a = rand() % NUM; b = rand() % NUM; p = make_pair(a, b); reverse_p = make_pair(b, a); } container.insert(p); } for (it=container.begin(); it!=container.end(); ++it) { int wt = 1 + rand() % MAXWEIGHT; printf("%d %d %d\n", it->first, it->second, wt); } container.clear(); printf("\n"); } // Uncomment the below line to store // the test data in a file // fclose(stdout); return(0);} |
Time Complexity : O(RUN*(MAX_EDGES+MAX_VERTICES*log(MAX_VERTICES))), where RUN is the number of test cases generated, MAX_EDGES is the maximum number of edges, and MAX_VERTICES is the maximum number of vertices. This is because the outer loop runs for ‘RUN’ times, and the inner loop runs for ‘MAX_EDGES’ times. The set container used in the code has a time complexity of O(log(MAX_VERTICES)) for insert, find, and clear operations.
Space complexity : O(MAX_VERTICES*RUN), as the container set is used to store the edges and its size grows as the number of vertices in the graph increases, and this is multiplied by the number of test cases generated.
This article is contributed by Rachit Belwariar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. 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!
