Test Case Generation | Set 4 (Random directed / undirected weighted and unweighted Graphs)
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
// 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 200
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_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 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.
import random
# Define the number of runs for the test data generated
RUN = 5
# Define the maximum number of vertices of the graph
MAX_VERTICES = 20
# Define the maximum number of edges
MAX_EDGES = 200
for 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()
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 code addition
// Define the number of runs for the test data generated
const RUN = 5;
// Define the maximum number of vertices of the graph
const MAX_VERTICES = 20;
// Define the maximum number of edges
const 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:
// 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 200
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_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);
}
// A Java Program to generate test cases for
// a weighted directed graph
import 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.
# Importing required libraries
import random
# Define the number of runs for the test data generated
RUN = 5
# Define the maximum number of vertices of the graph
MAX_VERTICES = 20
# Define the maximum number of edges
MAX_EDGES = 200
# Define the maximum weight of edges
MAXWEIGHT = 200
# Main function
def main():
# Container to store the edges
container = set()
# For random values every time
random.seed()
for _ in range(RUN):
# Number of Vertices
NUM = 1 + random.randint(0, 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 + random.randint(0, MAX_EDGES)
while NUMEDGE > NUM * (NUM - 1) / 2:
NUMEDGE = 1 + random.randint(0, MAX_EDGES)
# First print the number of vertices and edges
print(NUM, NUMEDGE)
# Then print the edges of the form (a b)
# where 'a' is connected to 'b'
for _ in range(NUMEDGE):
a = 1 + random.randint(0, NUM)
b = 1 + random.randint(0, NUM)
p = (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 p in container:
a = 1 + random.randint(0, NUM)
b = 1 + random.randint(0, NUM)
p = (a, b)
container.add(p)
for it in container:
wt = 1 + random.randint(0, MAXWEIGHT)
print(it[0], it[1], wt)
container.clear()
print()
# Call the main function
if __name__ == "__main__":
main()
using System;
using System.Collections.Generic;
public class GenerateTestCases
{
// Define the number of runs for the test data generated
const int RUN = 5;
// Define the maximum number of vertices of the graph
const int MAX_VERTICES = 20;
// Define the maximum number of edges
const int MAX_EDGES = 200;
// Define the maximum weight of edges
const int MAX_WEIGHT = 200;
public static void Main(string[] args)
{
var random = new Random();
var container = new HashSet<Tuple<int, int>>();
for (int i = 0; i < RUN; i++)
{
// Number of Vertices
int NUM = 1 + random.Next(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
int NUM_EDGE = 1 + random.Next(MAX_EDGES);
while (NUM_EDGE > NUM * (NUM - 1) / 2)
NUM_EDGE = 1 + random.Next(MAX_EDGES);
// First print the number of vertices and edges
Console.WriteLine($"{NUM} {NUM_EDGE}");
// Then print the edges of the form (a b)
// where 'a' is connected to 'b'
for (int j = 0; j < NUM_EDGE; j++)
{
int a = 1 + random.Next(NUM);
int b = 1 + random.Next(NUM);
var tuple = Tuple.Create(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(tuple))
{
a = 1 + random.Next(NUM);
b = 1 + random.Next(NUM);
tuple = Tuple.Create(a, b);
}
container.Add(tuple);
}
foreach (var edge in container)
{
int wt = 1 + random.Next(MAX_WEIGHT);
Console.WriteLine($"{edge.Item1} {edge.Item2} {wt}");
}
container.Clear();
Console.WriteLine();
}
}
}
// JavaScript Program to generate test cases for
// a weighted directed graph
// Define the number of runs for
// the test data generated
const RUN = 5;
// Define the maximum number of
// vertices of the graph
const MAX_VERTICES = 20;
// Define the maximum number of edges
const MAX_EDGES = 200;
// Define the maximum weight of edges
const MAX_WEIGHT = 200;
// Function to generate test cases
function generateTestCases() {
let container = new Set();
for (let i = 1; i <= RUN; i++) {
let NUM = 1 + Math.floor(Math.random() * 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
let NUMEDGE = 1 + Math.floor(Math.random() * MAX_EDGES);
while (NUMEDGE > NUM * (NUM - 1) / 2)
NUMEDGE = 1 + Math.floor(Math.random() * MAX_EDGES);
// 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'
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 = 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.has(p.toString())) {
a = 1 + Math.floor(Math.random() * NUM);
b = 1 + Math.floor(Math.random() * NUM);
p = new Pair(a, b);
}
container.add(p.toString());
}
for (let p of container) {
let wt = 1 + Math.floor(Math.random() * MAX_WEIGHT);
console.log(p + " " + wt);
}
container.clear();
console.log();
}
}
// Pair class to store a pair of integers
class Pair {
constructor(first, second) {
this.first = first;
this.second = second;
}
toString() {
return this.first + " " + this.second;
}
}
// Call the function to generate test cases
generateTestCases();
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.
#include <bits/stdc++.h>
using namespace std;
#define RUN 5
#define MAX_VERTICES 20
#define MAX_EDGES 200
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_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 <= 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
// every time 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", it->first, it->second);
container.clear();
printf("\n");
}
// Uncomment the below line to store
// the test data in a file
// fclose(stdout);
return (0);
}
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class Main {
static final int RUN = 5;
static final int MAX_VERTICES = 20;
static final int MAX_EDGES = 200;
public static void main(String[] args)
{
Set<String> container = new HashSet<>();
// For random values every time
Random random = new Random();
int NUM; // Number of Vertices
int NUMEDGE; // Number of Edges
for (int i = 1; i <= RUN; i++) {
NUM = 1 + random.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 + random.nextInt(MAX_EDGES);
while (NUMEDGE > NUM * (NUM - 1) / 2)
NUMEDGE = 1 + random.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 = random.nextInt(NUM);
int b = random.nextInt(NUM);
String edge = a + " " + b;
String reverseEdge = b + " " + a;
// 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(edge)
|| container.contains(reverseEdge)) {
a = random.nextInt(NUM);
b = random.nextInt(NUM);
edge = a + " " + b;
reverseEdge = b + " " + a;
}
container.add(edge);
}
for (String edge : container)
System.out.println(edge);
container.clear();
System.out.println();
}
}
}
import random
RUN = 5
MAX_VERTICES = 20
MAX_EDGES = 200
for _ in range(RUN):
container = set()
# Number of Vertices
NUM = random.randint(1, MAX_VERTICES)
# Number of Edges
NUMEDGE = random.randint(1, max(1, min(MAX_EDGES, NUM * (NUM - 1) // 2)))
# Print the number of vertices and edges
print(NUM, NUMEDGE)
# Generate and print edges
for _ in range(NUMEDGE):
a = random.randint(0, NUM - 1)
b = random.randint(0, NUM - 1)
edge = (a, b) if a <= b else (b, a)
# Search for a new edge
while edge in container:
a = random.randint(0, NUM - 1)
b = random.randint(0, NUM - 1)
edge = (a, b) if a <= b else (b, a)
container.add(edge)
for edge in container:
print(edge[0], edge[1])
print()
# This code is contributed by shivamgupta0987654321
// Number of test runs
const RUN = 5;
// Maximum number of vertices and edges
const MAX_VERTICES = 20;
const MAX_EDGES = 200;
// Main function
function main() {
let container = new Set();
for (let i = 1; i <= RUN; i++) {
let NUM = 1 + Math.floor(Math.random() * MAX_VERTICES);
let NUMEDGE = 1 + Math.floor(Math.random() * MAX_EDGES);
while (NUMEDGE > NUM * (NUM - 1) / 2)
NUMEDGE = 1 + Math.floor(Math.random() * MAX_EDGES);
// Print the number of vertices and edges
console.log(NUM + " " + NUMEDGE);
for (let j = 1; j <= NUMEDGE; j++) {
let a = Math.floor(Math.random() * NUM);
let b = Math.floor(Math.random() * NUM);
let p = [a, b].sort().join(" ");
while (container.has(p)) {
a = Math.floor(Math.random() * NUM);
b = Math.floor(Math.random() * NUM);
p = [a, b].sort().join(" ");
}
container.add(p);
}
container.forEach(edge => console.log(edge));
container.clear();
console.log();
}
}
// Execute the main function
main();
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.
#include <bits/stdc++.h>
using namespace std;
#define RUN 5
#define MAX_VERTICES 20
#define MAX_EDGES 200
#define MAXWEIGHT 200
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_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;
NUMEDGE = 1 + rand() % MAX_EDGES;
while (NUMEDGE > NUM * (NUM - 1) / 2)
NUMEDGE = 1 + rand() % MAX_EDGES;
printf("%d %d\n", NUM, NUMEDGE);
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);
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;
}
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
public class Main {
// 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 MAXWEIGHT = 200;
public static void main(String[] args) {
for (int i = 0; i < RUN; i++) {
// Number of Vertices
int NUM = 1 + ThreadLocalRandom.current().nextInt(0, 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
int NUMEDGE = 1 + ThreadLocalRandom.current().nextInt(0, MAX_EDGES);
while (NUMEDGE > NUM * (NUM - 1) / 2) {
NUMEDGE = 1 + ThreadLocalRandom.current().nextInt(0, MAX_EDGES);
}
// First print the number of vertices and edges
System.out.println(NUM + " " + NUMEDGE);
Set<String> edges = new HashSet<>();
// Then print the edges of the form (a b)
// where 'a' is connected to 'b'
for (int j = 0; j < NUMEDGE; j++) {
int a = ThreadLocalRandom.current().nextInt(0, NUM);
int b = ThreadLocalRandom.current().nextInt(0, NUM);
// Search for a random "new" edge every time
// Note - In a tree the edge (a, b) is same
// as the edge (b, a)
while (edges.contains(a + " " + b) || edges.contains(b + " " + a)) {
a = ThreadLocalRandom.current().nextInt(0, NUM);
b = ThreadLocalRandom.current().nextInt(0, NUM);
}
edges.add(a + " " + b);
int wt = 1 + ThreadLocalRandom.current().nextInt(0, MAXWEIGHT);
System.out.println(a + " " + b + " " + wt);
}
System.out.println();
}
}
}
# Python Program to generate test cases for
# a weighted undirected graph
import random
# Define the number of runs for the test data
# generated
RUN = 5
# Define the maximum number of vertices of the graph
MAX_VERTICES = 20
# Define the maximum number of edges
MAX_EDGES = 200
# Define the maximum weight of edges
MAXWEIGHT = 200
for _ in range(RUN):
# Number of Vertices
NUM = 1 + random.randint(0, 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 + random.randint(0, MAX_EDGES)
while NUMEDGE > NUM*(NUM-1)//2:
NUMEDGE = 1 + random.randint(0, MAX_EDGES)
# First print the number of vertices and edges
print(NUM, NUMEDGE)
edges = set()
# Then print the edges of the form (a b)
# where 'a' is connected to 'b'
for _ in range(NUMEDGE):
a = random.randint(0, NUM-1)
b = random.randint(0, NUM-1)
# Search for a random "new" edge every time
# Note - In a tree the edge (a, b) is same
# as the edge (b, a)
while (a, b) in edges or (b, a) in edges:
a = random.randint(0, NUM-1)
b = random.randint(0, NUM-1)
edges.add((a, b))
for edge in edges:
wt = 1 + random.randint(0, MAXWEIGHT)
print(edge[0], edge[1], wt)
print()
// Define the number of runs for the test data generated
const RUN = 5;
// Define the maximum number of vertices of the graph
const MAX_VERTICES = 20;
// Define the maximum number of edges
const MAX_EDGES = 200;
// Define the maximum weight of edges
const MAXWEIGHT = 200;
for (let r = 0; r < RUN; r++) {
// Number of Vertices
const NUM = 1 + Math.floor(Math.random() * 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
let NUMEDGE = 1 + Math.floor(Math.random() * MAX_EDGES);
while (NUMEDGE > (NUM * (NUM - 1)) / 2) {
NUMEDGE = 1 + Math.floor(Math.random() * MAX_EDGES);
}
// First print the number of vertices and edges
console.log(NUM, NUMEDGE);
const edges = new Set();
// Then print the edges of the form (a b)
// where 'a' is connected to 'b'
for (let i = 0; i < NUMEDGE; i++) {
let a = Math.floor(Math.random() * NUM);
let b = Math.floor(Math.random() * NUM);
// Search for a random "new" edge every time
// Note - In a tree the edge (a, b) is same
// as the edge (b, a)
while (edges.has(`${a}-${b}`) || edges.has(`${b}-${a}`)) {
a = Math.floor(Math.random() * NUM);
b = Math.floor(Math.random() * NUM);
}
edges.add(`${a}-${b}`);
}
edges.forEach(edge => {
const [a, b] = edge.split('-');
const wt = 1 + Math.floor(Math.random() * MAXWEIGHT);
console.log(`${a} ${b} ${wt}`);
});
console.log();
}
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.
Contact Us