Sabemos que Graph es una estructura de datos que consta de un conjunto finito de vértices y aristas (que conectan los vértices entre sí). A puede ser dirigido (bordes que tienen una dirección) o no dirigido (bordes sin direcciones). Sin embargo, un gráfico aleatorio es una estructura de datos de gráficos que se genera aleatoriamente. Los modelos de gráficos aleatorios se utilizan ampliamente en el estudio de redes complejas, redes sociales, ingeniería de comunicaciones e incluso en biología (en el estudio de redes reguladoras intracelulares, activando e inhibiendo conexiones en redes biológicas, etc.).
En este artículo, vamos a discutir algunos algoritmos para generar varios tipos de gráficos aleatorios.
Algoritmo 1:
Este algoritmo se basa en elegir aleatoriamente el número de vértices y aristas y luego seleccionar aleatoriamente dos vértices para agregar una arista entre ellos.
- Elige al azar el número de vértices y aristas. Digamos, V sea el número de vértices y E sea el número de aristas
- Compruebe si el número elegido de aristas E es compatible con el número de vértices. En cuanto a un número elegido de vértices V, puede haber como máximo (V*(V-1)/2) aristas (¿Por qué V*(V – 1)/2 ? se discute más adelante) en un grafo no dirigido (si no contiene bucles automáticos).
- Ejecute un bucle for que se ejecute para i = 0 a i < número de aristas E, y durante cada iteración, elija aleatoriamente dos vértices y cree una arista entre ellos.
- Imprime el gráfico creado.
A continuación se muestra la implementación del enfoque anterior:
Java
// Create a Random Graph Using
// Random Edge Generation in Java
import 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("}");
}
}
}
Producción
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}
Cada vez que ejecute el programa anterior, obtendrá un gráfico no dirigido diferente.
2. Elimina las repeticiones de los bordes
Compruebe si el borde ya existe o no en tiempo de ejecución. Usando este enfoque, la complejidad del algoritmo 1 aumentará, pero la optimización en la memoria aumenta.
A continuación se muestra la implementación del enfoque anterior:
Java
// Create a Random Graph Using
// Random Edge Generation in Java
import 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("}");
}
}
}
Producción
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}
Ahora, el gráfico no dirigido de salida no contiene aristas múltiples entre los mismos vértices. Aunque el gráfico puede contener bucles automáticos (pero ahora solo uno para cada vértice). Sin embargo, si desea generar gráficos no dirigidos sin bucles automáticos, puede agregar otra condición al código anterior.
//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;
}
Ahora, no se permiten bucles automáticos ni bordes múltiples en el gráfico no dirigido generado.
¿Por qué para un número dado de vértices V en un gráfico no dirigido, puede haber como máximo V*((V-1)/2) número de aristas?
Supongamos que hay V número de vértices en un gráfico dirigido. Ahora, si el gráfico no contiene bucles automáticos ni aristas múltiples, entonces cada vértice puede tener aristas (V-1) con otros vértices (V-1). Entonces, V vértices pueden tener como máximo V*(V – 1) vértices. Si el gráfico contiene bucles automáticos, el número máximo posible de aristas es V 2 (sin aristas múltiples). Porque cada vértice también puede tener una arista consigo mismo. Entonces, para gráficos no dirigidos, el número máximo posible de aristas es V*(V – 1)/2 ya que las aristas no tienen direcciones.
Hasta ahora, hemos creado gráficos aleatorios no dirigidos; sin embargo, si desea crear gráficos aleatorios dirigidos, debemos realizar algunos cambios en el código implementado anteriormente:
- Para un número de vértices V elegido al azar, el número máximo de aristas posibles ahora es V*(V – 1) (sin aristas múltiples ni bucles automáticos).
- Para gráficos dirigidos sin bucles automáticos, debemos verificar si los dos vértices elegidos al azar son iguales. Si no lo son, solo cree un borde entre ellos.
- Para gráficos dirigidos sin bordes múltiples, debemos verificar si ya hay un borde entre los vértices elegidos al azar. Si no existe tal borde, solo cree un borde entre ellos.
- Al crear un borde entre dos vértices, solo necesitamos agregar w a la lista de adyacencia de v y no v a la lista de adyacencia de w, ya que este es un gráfico dirigido.
Aquí está el código que crea gráficos aleatorios dirigidos sin bordes múltiples y bucles automáticos:
Java
// Create a Random Graph Using
// Random Edge Generation in Java
import 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("}");
}
}
}
Producción
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}
El gráfico de salida anterior es un gráfico dirigido aleatorio sin bucles automáticos y múltiples bordes.
El algoritmo 1 se basa en elegir aleatoriamente un número de vértices v y aristas e y crear un gráfico que contenga v vértices y e aristas. El segundo algoritmo que vamos a discutir se basa en el modelo de gráfico aleatorio Erdos-Renyi G(v,p) .
Algoritmo 2 (El modelo Erdos-Renyi G(v,p)):
El modelo Erdos-Renyi G(v,p) (llamado así por Paul Erdos y Alfred Renyi), que se considera uno de los primeros en intentar describir las redes aleatorias, es uno de los modelos más populares para generar gráficos aleatorios. Este modelo genera un gráfico aleatorio que contiene v vértices y aristas entre dos vértices con probabilidad p. p es la probabilidad de que haya una arista entre dos vértices cualesquiera.
- Elige aleatoriamente un número de vértices y la probabilidad p. El valor de p está entre 0,0 y 1,0.
- Iterar sobre cada par de vértices y generar un número aleatorio entre 0,0 y 1,0. Si el número elegido al azar es menor que la probabilidad p, agregue una arista entre los dos vértices del par. El número de aristas en el gráfico depende totalmente de la probabilidad p.
- Imprime el gráfico.
A continuación se muestra la implementación del enfoque anterior:
Java
// Create a Random Graph Using
// Random Edge Generation in Java
import 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("}");
}
}
}
Producción
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}
El programa anterior genera gráficos aleatorios dirigidos con bucles automáticos.