We know that Graph is a data structure that consists of a finite set of vertices and edges(that connect the vertices with each other). A graph can be directed(edges having a direction) or undirected(edges with no directions). However, a Random graph is a graph data structure that is generated randomly. Random Graph models are widely used in studying complex networks, social networks, communication engineering and even in biology(in studying intracellular regulatory networks, activating and inhibiting connections in biological networks etc.).
In this article, we are going to discuss some algorithms to generate various types of random graphs.
Algorithm 1:
This algorithm is based on randomly choosing the number of vertices and edges and then randomly selecting two vertices to add an edge between them.
- Randomly choose the number of vertices and edges. Say, V be the number of vertices and E be the number of edges
- Check if the chosen number of edges E is compatible with the number of vertices. As for a chosen number of vertices V, there can be at-most (V*(V-1)/2) edges (Why V*(V – 1)/2 ? it is discussed later) in an undirected graph(if it does not contain self-loops).
- Run a for loop that runs for i = 0 to i < number of edges E, and during each iteration, randomly choose two vertices and create an edge between them.
- Print the created graph.
Below is the implementation of the above approach:
Java
// Create a Random Graph Using// Random Edge Generation in Javaimport java.util.*;import java.io.*; public class GFGRandomGraph { public int vertices; public int edges; // Set a maximum limit to the vertices final int MAX_LIMIT = 20; // A Random instance to generate random values Random random = new Random(); // An adjacency list to represent a graph public List<List<Integer> > adjacencyList; // Creating the constructor public GFGRandomGraph() { // Set a maximum limit for // the number of vertices say 20 this.vertices = random.nextInt(MAX_LIMIT) + 1; // compute the maximum possible number of edges // and randomly choose the number of edges less than // or equal to the maximum number of possible edges this.edges = random.nextInt(computeMaxEdges(vertices)) + 1; // Creating an adjacency list // representation for the random graph adjacencyList = new ArrayList<>(vertices); for (int i = 0; i < vertices; i++) adjacencyList.add(new ArrayList<>()); // A for loop to randomly generate edges for (int i = 0; i < edges; i++) { // randomly select two vertices to // create an edge between them int v = random.nextInt(vertices); int w = random.nextInt(vertices); // add an edge between them addEdge(v, w); } } // Method to compute the maximum number of possible // edges for a given number of vertices int computeMaxEdges(int numOfVertices) { // As it is an undirected graph // So, for a given number of vertices // there can be at-most v*(v-1)/2 number of edges return numOfVertices * ((numOfVertices - 1) / 2); } // Method to add edges between given vertices void addEdge(int v, int w) { // Note: it is an Undirected graph // Add w to v's adjacency list adjacencyList.get(v).add(w); // Add v to w's adjacency list adjacencyList.get(w).add(v); } public static void main(String[] args) { // Create a GFGRandomGraph object GFGRandomGraph randomGraph = new GFGRandomGraph(); // Print the graph System.out.println("The generated random graph :"); for (int i = 0; i < randomGraph.adjacencyList.size(); i++) { System.out.print(i + " -> { "); List<Integer> list = randomGraph.adjacencyList.get(i); if (list.isEmpty()) System.out.print(" No adjacent vertices "); else { int size = list.size(); for (int j = 0; j < size; j++) { System.out.print(list.get(j)); if (j < size - 1) System.out.print(" , "); } } System.out.println("}"); } }} |
Output
The generated random graph :
0 -> { 7 , 10 , 7 , 2 , 8 , 7 , 1}
1 -> { 5 , 8 , 8 , 3 , 4 , 12 , 8 , 7 , 9 , 0 , 7}
2 -> { 2 , 2 , 7 , 0 , 2 , 2 , 11 , 12 , 3 , 9 , 4 , 2 , 2 , 12 , 5}
3 -> { 6 , 10 , 1 , 12 , 11 , 2 , 10 , 10 , 3 , 3 , 5}
4 -> { 1 , 8 , 6 , 8 , 8 , 2 , 5 , 11}
5 -> { 1 , 5 , 5 , 8 , 4 , 2 , 11 , 3}
6 -> { 3 , 9 , 12 , 4 , 10 , 8 , 9}
7 -> { 0 , 2 , 0 , 12 , 1 , 7 , 7 , 12 , 0 , 8 , 1}
8 -> { 5 , 1 , 1 , 0 , 1 , 4 , 4 , 4 , 6 , 11 , 7}
9 -> { 6 , 12 , 1 , 2 , 9 , 9 , 6 , 9 , 9}
10 -> { 3 , 0 , 3 , 3 , 10 , 10 , 6}
11 -> { 3 , 2 , 12 , 8 , 4 , 5}
12 -> { 7 , 3 , 9 , 1 , 6 , 11 , 2 , 7 , 2}
Each time you run the above program you will get a different undirected graph.
2. Remove the repetitions of the edges
Check if the edge already exists or not at run time. Using this approach complexity of the algorithm 1 will get increase but the optimization in the memory increases.
Below is the implementation of the above approach:
Java
// Create a Random Graph Using// Random Edge Generation in Javaimport java.util.*;import java.io.*; public class GFGRandomGraph { public int vertices; public int edges; // Set a maximum limit to the vertices final int MAX_LIMIT = 20; // A Random instance to generate random values Random random = new Random(); // An adjacency list to represent a graph public List<List<Integer> > adjacencyList; // Creating the constructor public GFGRandomGraph() { // Set a maximum limit for the number // of vertices say 20 this.vertices = random.nextInt(MAX_LIMIT) + 1; // compute the maximum possible number of edges // and randomly choose the number of edges less than // or equal to the maximum number of possible edges this.edges = random.nextInt(computeMaxEdges(vertices)) + 1; // Creating an adjacency list representation // for the random graph adjacencyList = new ArrayList<>(vertices); for (int i = 0; i < vertices; i++) adjacencyList.add(new ArrayList<>()); // A for loop to randomly generate edges for (int i = 0; i < edges; i++) { // randomly select two vertices to // create an edge between them int v = random.nextInt(vertices); int w = random.nextInt(vertices); // Check if there is already // an edge between v and w if (adjacencyList.get(v).contains(w)) { // Reduce the value of i // so that again v and w can be chosen // for the same edge count i = i - 1; continue; } // Add an edge between them if // not previously created addEdge(v, w); } } // Method to compute the maximum number of possible // edges for a given number of vertices int computeMaxEdges(int numOfVertices) { // As it is an undirected graph // So, for a given number of vertices V // there can be at-most V*(V-1)/2 number of edges return numOfVertices * ((numOfVertices - 1) / 2); } // Method to add edges between given vertices void addEdge(int v, int w) { // Note: it is an Undirected graph // Add w to v's adjacency list adjacencyList.get(v).add(w); // Add v to w's adjacency list // if v is not equal to w if (v != w) adjacencyList.get(w).add(v); // The above condition is important // If you don't apply the condition then // two self-loops will be created if // v and w are equal } public static void main(String[] args) { // Create a GFGRandomGraph object GFGRandomGraph randomGraph = new GFGRandomGraph(); // Print the graph System.out.println("The generated random graph :"); for (int i = 0; i < randomGraph.adjacencyList.size(); i++) { System.out.print(i + " -> { "); List<Integer> list = randomGraph.adjacencyList.get(i); if (list.isEmpty()) System.out.print(" No adjacent vertices "); else { int size = list.size(); for (int j = 0; j < size; j++) { System.out.print(list.get(j)); if (j < size - 1) System.out.print(" , "); } } System.out.println("}"); } }} |
Output
The generated random graph :
0 -> { 7 , 0 , 9 , 16 , 8 , 3 , 14 , 17 , 10 , 1 , 6 , 11 , 5 , 4 , 12}
1 -> { 17 , 8 , 6 , 12 , 9 , 11 , 13 , 5 , 15 , 0 , 2 , 7 , 16 , 3}
2 -> { 11 , 16 , 9 , 8 , 6 , 13 , 17 , 4 , 2 , 14 , 1 , 7 , 10}
3 -> { 4 , 8 , 13 , 10 , 12 , 17 , 0 , 15 , 16 , 3 , 7 , 6 , 5 , 1}
4 -> { 3 , 17 , 5 , 15 , 16 , 8 , 2 , 7 , 13 , 6 , 9 , 4 , 11 , 14 , 12 , 0}
5 -> { 10 , 17 , 6 , 16 , 4 , 9 , 14 , 13 , 8 , 1 , 3 , 5 , 0 , 15 , 7}
6 -> { 5 , 2 , 8 , 1 , 15 , 16 , 12 , 14 , 4 , 6 , 3 , 0 , 17 , 10 , 7}
7 -> { 9 , 11 , 0 , 15 , 7 , 4 , 10 , 13 , 17 , 16 , 3 , 8 , 1 , 6 , 2 , 5 , 12}
8 -> { 16 , 3 , 2 , 1 , 17 , 6 , 13 , 0 , 15 , 4 , 14 , 5 , 7 , 12 , 9 , 11}
9 -> { 7 , 10 , 2 , 9 , 0 , 1 , 5 , 17 , 16 , 4 , 12 , 11 , 13 , 8}
10 -> { 11 , 5 , 9 , 3 , 12 , 7 , 13 , 10 , 16 , 14 , 17 , 0 , 15 , 6 , 2}
11 -> { 2 , 10 , 17 , 12 , 7 , 15 , 16 , 11 , 1 , 13 , 14 , 4 , 9 , 0 , 8}
12 -> { 12 , 11 , 3 , 1 , 6 , 10 , 16 , 15 , 8 , 9 , 4 , 13 , 0 , 7}
13 -> { 14 , 3 , 17 , 15 , 2 , 8 , 7 , 10 , 5 , 1 , 4 , 11 , 9 , 13 , 12}
14 -> { 13 , 5 , 2 , 8 , 6 , 0 , 10 , 11 , 4 , 17 , 15}
15 -> { 13 , 11 , 17 , 4 , 7 , 6 , 8 , 3 , 1 , 12 , 10 , 16 , 14 , 5}
16 -> { 2 , 8 , 5 , 0 , 4 , 6 , 11 , 12 , 9 , 3 , 10 , 7 , 17 , 15 , 1}
17 -> { 1 , 11 , 5 , 4 , 13 , 8 , 15 , 3 , 2 , 9 , 7 , 0 , 16 , 10 , 14 , 6}
Now the output undirected graph does not contain any multiple edges between the same vertices. Though the graph may contain self-loops(but now only one for each vertex). However, if you want to generate undirected graphs without self-loops, then you can add another condition to the above code
//Check if there is already an edge between v and w or v and w are equal
if((v == w ) || adjacencyList.get(v).contains(w)) {
//Reduce the value of i
//so that again v and w can be chosen
//for the same edge count
i = i - 1;
continue;
}
Now, no self-loops and multiple edges are allowed in the generated undirected graph.
Why for a given number of vertices V in an undirected graph, there can be at-most V*((V-1)/2) number of edges?
Suppose, there are V number of vertices in a directed graph. Now, if the graph doesn’t contain any self-loops and multiple edges, then each vertex can have (V-1) edges with other (V-1) vertices. So, V vertices can have at-most V*(V – 1) vertices. If the graph contains self-loops then the maximum possible number of edges is V2 (with no multiple edges). Because, each vertex can have an edge with itself also. So, for Undirected graphs, the maximum possible number of edges is V*(V – 1)/2 as the edges don’t have any directions.
Till now, we have created random undirected graphs, however, if you want to create random directed graphs, then we have to make some changes to the above implemented code —
- For a randomly chosen number of vertices V, the maximum number of possible edges is now V*(V – 1)(with no multiple edges and self-loops).
- For directed graphs with no self-loops, we need to check if the two vertices chosen randomly, are equal. If they are not, then only create an edge between them.
- For directed graphs with no multiple edges, we need to check if there is already an edge between the randomly chosen vertices. If no such edge exists, then only create an edge between them.
- When creating an edge between two vertices, we only need to add w to the adjacency list of v and not v to the adjacency list of w as this is a directed graph.
Here is the code that creates random directed graphs with no multiple edges and self-loops —
Java
// Create a Random Graph Using// Random Edge Generation in Javaimport java.util.*;import java.io.*; public class GFGRandomGraph { public int vertices; public int edges; // Set a maximum limit to the vertices final int MAX_LIMIT = 20; // A Random instance to generate random values Random random = new Random(); // An adjacency list to represent a graph public List<List<Integer> > adjacencyList; // Creating the constructor public GFGRandomGraph() { // Set a maximum limit for the // number of vertices say 20 this.vertices = random.nextInt(MAX_LIMIT) + 1; // compute the maximum possible number of edges // and randomly choose the number of edges less than // or equal to the maximum number of possible edges this.edges = random.nextInt(computeMaxEdges(vertices)) + 1; // Creating an adjacency list // representation for the random graph adjacencyList = new ArrayList<>(vertices); for (int i = 0; i < vertices; i++) adjacencyList.add(new ArrayList<>()); // A for loop to randomly generate edges for (int i = 0; i < edges; i++) { // Randomly select two vertices to // create an edge between them int v = random.nextInt(vertices); int w = random.nextInt(vertices); // Check if there is already an edge between v // and w if ((v == w) || adjacencyList.get(v).contains(w)) { // Reduce the value of i // so that again v and w can be chosen // for the same edge count i = i - 1; continue; } // Add an edge between them if // not previously created addEdge(v, w); } } // Method to compute the maximum number of // possible edges for a given number of vertices int computeMaxEdges(int numOfVertices) { // As it is a directed graph // So, for a given number of vertices // there can be at-most v*(v-1) number of edges return numOfVertices * (numOfVertices - 1); } // Method to add edges between given vertices void addEdge(int v, int w) { // Note: it is a directed graph // Add w to v's adjacency list adjacencyList.get(v).add(w); } public static void main(String[] args) { // Create a GFGRandomGraph object GFGRandomGraph randomGraph = new GFGRandomGraph(); // Print the graph System.out.println("The generated random graph :"); for (int i = 0; i < randomGraph.adjacencyList.size(); i++) { System.out.print(i + " -> { "); List<Integer> list = randomGraph.adjacencyList.get(i); if (list.isEmpty()) System.out.print(" No adjacent vertices "); else { int size = list.size(); for (int j = 0; j < size; j++) { System.out.print(list.get(j)); if (j < size - 1) System.out.print(" , "); } } System.out.println("}"); } }} |
Output
The generated random graph :
0 -> { 4 , 3 , 5 , 15 , 13}
1 -> { 2 , 6 , 9 , 7 , 12 , 4}
2 -> { 4 , 7 , 13 , 12 , 11 , 9}
3 -> { 5 , 2 , 15 , 10}
4 -> { 2 , 16 , 8 , 7}
5 -> { 7 , 16 , 10 , 0 , 9}
6 -> { 12 , 11 , 14 , 2 , 5 , 16}
7 -> { 8 , 11 , 12 , 3 , 16 , 10 , 13}
8 -> { 6 , 7 , 15 , 12 , 0 , 5 , 9 , 16}
9 -> { 3 , 4 , 16}
10 -> { 9 , 12 , 16 , 6}
11 -> { 10 , 8 , 15 , 9 , 12 , 13}
12 -> { 5 , 7 , 10 , 1}
13 -> { 16 , 2 , 10 , 3 , 1}
14 -> { 3 , 15 , 8 , 12 , 7 , 1}
15 -> { 9 , 2 , 1 , 14 , 8 , 4}
16 -> { 1 , 2 , 9 , 3 , 10 , 7}
The above output graph is a random directed graph with no self-loops and multiple edges.
The algorithm 1 is based on randomly choosing a number of vertices v and edges e and creating a graph containing v vertices and e edges. The second algorithm we are going to discuss is based on Erdos-Renyi G(v,p) Random Graph model.
Algorithm 2 (The Erdos-Renyi G(v,p) model) :
The Erdos-Renyi G(v,p) model (named after Paul Erdos and Alfred Renyi) which is considered one of the first to attempt to describe the random networks, is one of the most popular models to generate random graphs. This model generates a random graph containing v vertices and edges between any two vertices with probability p. p is the probability that there is an edge between any two vertices.
- Randomly choose a number of vertices and the probability p. The value of p is between 0.0 to 1.0.
- Iterate over each pair of vertices and generate a random number between 0.0 and 1.0. If the randomly chosen number is less than the probability p, then add an edge between the two vertices of the pair. The number of edges in the graph totally depends on the probability p.
- Print the graph.
Below is the implementation of the above approach:
Java
// Create a Random Graph Using// Random Edge Generation in Javaimport java.util.*;import java.io.*; public class GFGRandomGraph { // Number of vertices public int vertices; // p represents the probability public float p; // Set a maximum limit to the vertices final int MAX_LIMIT = 20; // A Random instance to generate random values Random random = new Random(); // An adjacency list to represent a graph public List<List<Integer> > adjacencyList; // Creating the constructor public GFGRandomGraph() { // Set a maximum limit for the // number of vertices say 20 this.vertices = random.nextInt(MAX_LIMIT) + 1; // p is the probability that there // is an edge between any two vertices // say, 0.4 is the probability that there // is an edge between any two vertices this.p = random.nextFloat(); // Print the probability p System.out.println( "The probability that there is an edge" + " between any two vertices is : " + p); // Creating an adjacency list // representation for the random graph adjacencyList = new ArrayList<>(vertices); for (int i = 0; i < vertices; i++) adjacencyList.add(new ArrayList<>()); // A for loop to randomly generate edges for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { // edgeProbability is a random number // between 0.0 and 1.0 // If the randomly chosen number // edgeProbability is less than // the probability of an edge p, // say, edgeProbability = 0.2 which is less // than p = 0.4, then add an edge between the // vertex i and the vertex j float edgeProbability = random.nextFloat(); if (edgeProbability < p) addEdge(i, j); } } } // Method to add edges between given vertices void addEdge(int v, int w) { // Note: it is a directed graph // Add w to v's adjacency list adjacencyList.get(v).add(w); } public static void main(String[] args) { // Create a GFGRandomGraph object GFGRandomGraph randomGraph = new GFGRandomGraph(); // Print the graph System.out.println("The generated random graph :"); for (int i = 0; i < randomGraph.adjacencyList.size(); i++) { System.out.print(i + " -> { "); List<Integer> list = randomGraph.adjacencyList.get(i); if (list.isEmpty()) System.out.print(" No adjacent vertices "); else { int size = list.size(); for (int j = 0; j < size; j++) { System.out.print(list.get(j)); if (j < size - 1) System.out.print(" , "); } } System.out.println("}"); } }} |
Output
The probability that there is an edge between any two vertices is : 0.8065328
The generated random graph :
0 -> { 0 , 1 , 2 , 3 , 5 , 6 , 7 , 8 , 11 , 13 , 14 , 15 , 16 , 17}
1 -> { 0 , 2 , 3 , 5 , 6 , 7 , 8 , 9 , 10 , 12 , 14 , 15 , 16 , 17}
2 -> { 0 , 1 , 2 , 3 , 4 , 5 , 7 , 8 , 9 , 10 , 11 , 13 , 15 , 16 , 17}
3 -> { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17}
4 -> { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17}
5 -> { 0 , 1 , 3 , 7 , 9 , 13 , 14 , 15 , 16 , 17}
6 -> { 1 , 2 , 3 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17}
7 -> { 0 , 1 , 2 , 3 , 4 , 5 , 7 , 8 , 9 , 10 , 12 , 13 , 15 , 16 , 17}
8 -> { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17}
9 -> { 0 , 1 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17}
10 -> { 0 , 1 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 17}
11 -> { 0 , 1 , 2 , 3 , 4 , 6 , 7 , 8 , 9 , 10 , 12 , 14 , 15 , 16 , 17}
12 -> { 0 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 11 , 12 , 13 , 14 , 15 , 16 , 17}
13 -> { 0 , 1 , 2 , 3 , 4 , 5 , 7 , 9 , 10 , 12 , 13 , 14 , 15 , 16 , 17}
14 -> { 1 , 2 , 3 , 4 , 6 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 17}
15 -> { 0 , 1 , 3 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 13 , 14 , 15 , 16}
16 -> { 0 , 1 , 2 , 3 , 5 , 6 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16}
17 -> { 0 , 1 , 2 , 3 , 4 , 5 , 7 , 9 , 10 , 13 , 14 , 15 , 16}
The above program generates random directed graphs with self-loops.
