Código para gerar grafos aleatórios G(n,p)

eclipseSegue o código em Java para geração de grafos aleatórios G(n,p), onde n é o numero de vértices e p é a probabilidade para a inserção de cada aresta no grafo.

Para usar este código é preciso instalar o pacote JGraphT no Eclipse.

No método main, é criado um grafo de exemplo com n = 10 e p = 0,4. E imprime no prompt todas as arestas de cada vértice do grafo.

import java.util.Iterator;
import org.jgrapht.*;

//Gera um grafo aleatório G(n,p)
public class GeradorGrafoAlearorio {

    int n;
    double p;

    public GeradorGrafoAlearorio(int n, double p) {
        this.n = n;
        this.p = p;
    }

    public Graph<Object, DefaultEdge> gerarGrafoAleatorio() {
        Graph<Object, DefaultEdge> g = new SimpleGraph<>(DefaultEdge.class);
        for (int i = 0; i < n; i++) {
            g.addVertex(i);
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.random() < p) {
                    g.addEdge(i, j);
                }
            }
        }
        return g;
    }

    public static void main(String[] args) {
        Graph<Object, DefaultEdge> g;
        g = new SimpleGraph<>(DefaultEdge.class);

        // Cria o gerador de grafo aleatorio
        GeradorGrafoAlearorio gerador;
        gerador = new GeradorGrafoAlearorio(10, 0.4);

        // Usa o gerador para gerar um grafo
        g = gerador.gerarGrafoAleatorio();

        // Imprime o grafo, mostra as arestas de cada vertice
        Iterator<Object> iterador = new DepthFirstIterator<>(g);
        Object v;
        while (iterador.hasNext()) {
            v = iterador.next();
            System.out.println(v.toString() + " -> " + g.edgesOf(v).toString());
        }
    }
}

Saída:

0 -> [(0 : 3), (0 : 4), (0 : 5), (0 : 7), (0 : 8)]
 8 -> [(0 : 8), (1 : 8), (2 : 8), (3 : 8), (5 : 8), (6 : 8), (8 : 9)]
 9 -> [(1 : 9), (4 : 9), (7 : 9), (8 : 9)]
 7 -> [(0 : 7), (7 : 9)]
 4 -> [(0 : 4), (2 : 4), (4 : 5), (4 : 9)]
 5 -> [(0 : 5), (4 : 5), (5 : 6), (5 : 8)]
 6 -> [(1 : 6), (2 : 6), (3 : 6), (5 : 6), (6 : 8)]
 3 -> [(0 : 3), (3 : 6), (3 : 8)]
 2 -> [(1 : 2), (2 : 4), (2 : 6), (2 : 8)]
 1 -> [(1 : 2), (1 : 6), (1 : 8), (1 : 9)]

Comentar

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s