In java generate a random graph using the following process: Given a graph with

Question

In java generate a random graph using the following process: Given a graph with n nodes, and a number p chosen between 0 and 1, a link between two nodes is going to be generated if a uniform random draw between 0 and 1 is less than the number p.

choose you graph implementation allowing to build such graphs(you should be able to generate graphs up to 1000 nodes).

Implement a method on your graph using breadth first search to check if all nodes are reachable from each other. Then implement the following experiment for n being 100, 200, 300, 400, 500, and for each value of n, for p equal to .25, .5, .75:

Generate 1000 random graphs for n and p, and countre connected using the above.

This is what I have so far.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;


public class Graph2<T> {
  
   private static int numberOfNodes;
    private boolean[][] adjacencyMatrix;
    private static int connectedCount = 0;
    private static int connected;
    //constructor
    Graph2(int n0) {
        Graph2.numberOfNodes = n0;
        this.adjacencyMatrix = new boolean[numberOfNodes][numberOfNodes];
    }
  
    List<Integer> outEdges(int node1) {
        List<Integer> edges = new ArrayList<Integer>();
        for (int node2 = 0; node2 < numberOfNodes; node2++)
            if (adjacencyMatrix[node1][node2]){
               edges.add(node2);
            }
        return edges;
    }
    //method to generate random graphs
    public static Graph2<?> createRandomGraph(int nodeCount, float p, int graphIndex) {
       Graph2<?> graph = new Graph2<Object>(graphIndex+1);
      
       Random randomInt = new Random();
       int randomNode = randomInt.nextInt(graphIndex+1);
       int randomNode1 = randomInt.nextInt(graphIndex+1);
       Random random = new Random();  
       float randomDraw = random.nextFloat();//uniform random draw between 0 and 1
       //System.out.println("Random Draw " + randomDraw + " Index " + graphIndex);
       if(randomDraw < p){//if random draw is less than p, a link between two nodes is generated
           graph.adjacencyMatrix[randomNode1][randomNode] = true;
           graph.adjacencyMatrix[randomNode][randomNode1] = true;
           connected++;
           connectedCount++;
       }
       graph.adjacencyMatrix[graphIndex][graphIndex]=false;
      
       return graph ;
          
   }//end method generate graph
  


   public void breadthFirst(){
          
   }
   boolean breadthFirstSearch(Graph2<?> graph, int graphIndex) {//checks connectivity
        boolean[] visited = new boolean[graph.adjacencyMatrix.length];
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(graphIndex);//adds the current index to the queue
        visited[graphIndex] = true;//marks the current index as visited
        while (!queue.isEmpty()) {
            int removedFromQueue = queue.remove();//removes the current index from queue after visiting it
            for (Object j : graph.outEdges(removedFromQueue)) {//sends current index to outEdges method
                if (!visited[(int) j]) {//if j is not visited add it to queue
                   //System.out.println(j);
                    queue.add((Integer) j);
                    visited[(int) j] = true;//mark j as visited add to visited array
                    return true;
                   // System.out.println("visited" + visited);
                }
            }
        }
       return false;
    }
  

   public static void main(String[] args){
      
           //generate 1000 random graphs for n and p, and count how many are connected
           // using above method.
           //Experiment for n = 100, 200, 300, 400, 500, and for each
           //value of n, for p equal to .25, .5 and .75:
       Graph2<?> graph = new Graph2<Object>(numberOfNodes);
      
       for (int nodeCount = 100; nodeCount <= 500; nodeCount += 100) {

           for (float p = (float) .25; p <=.75; p += .25) {
               System.out.println(" FOR n = " + nodeCount + " AND p = "+ p);
               connected = 0;
               for (int graphIndex = 0; graphIndex < 1000; ++graphIndex) {
              
                   graph = createRandomGraph(nodeCount, p, graphIndex);
              
                   if (graph.breadthFirstSearch(graph, graphIndex)) { //..... }
                       System.out.println(connectedCount + " graphs are connected.");
                        }
                    }
               System.out.println(" NUMBER OF TOTAL CONNECTED THIS GRAPH IS: " + connected);
              
           }
       }
       System.out.println(" NUMBER OF TOTAL CONNECTED IS: " + connectedCount);
   }//end main
  
}//end class Graph

Explanation / Answer

package edu.uci.ics.jung.algorithms.generators.random;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
  
import org.apache.commons.collections15.Factory;

import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.UndirectedGraph;
  
/**
* Generates a random graph using the Erdos-Renyi binomial model
* (each pair of vertices is connected with probability p).
*
* @author William Giordano, Scott White, Joshua O'Madadhain
*/
public class ErdosRenyiGenerator<V,E> implements GraphGenerator<V,E> {
private int mNumVertices;
private double mEdgeConnectionProbability;
private Random mRandom;
Factory<UndirectedGraph<V,E>> graphFactory;
Factory<V> vertexFactory;
Factory<E> edgeFactory;
  
/**
*
* @param numVertices number of vertices graph should have
* @param p Connection's probability between 2 vertices
*/
public ErdosRenyiGenerator(Factory<UndirectedGraph<V,E>> graphFactory,
Factory<V> vertexFactory, Factory<E> edgeFactory,
int numVertices,double p)
{
if (numVertices <= 0) {
throw new IllegalArgumentException("A positive # of vertices must be specified.");
}
mNumVertices = numVertices;
if (p < 0 || p > 1) {
throw new IllegalArgumentException("p must be between 0 and 1.");
}
this.graphFactory = graphFactory;
this.vertexFactory = vertexFactory;
this.edgeFactory = edgeFactory;
mEdgeConnectionProbability = p;
mRandom = new Random();
}
  
/**
* Returns a graph in which each pair of vertices is connected by
* an undirected edge with the probability specified by the constructor.
*/
public Graph<V,E> create() {
UndirectedGraph<V,E> g = graphFactory.create();
for(int i=0; i<mNumVertices; i++) {
g.addVertex(vertexFactory.create());
}
List<V> list = new ArrayList<V>(g.getVertices());
  
for (int i = 0; i < mNumVertices-1; i++) {
V v_i = list.get(i);
for (int j = i+1; j < mNumVertices; j++) {
V v_j = list.get(j);
if (mRandom.nextDouble() < mEdgeConnectionProbability) {
g.addEdge(edgeFactory.create(), v_i, v_j);
}
}
}
return g;
}
  
/**
* Sets the seed of the internal random number generator to {@code seed}.
* Enables consistent behavior.
*/
public void setSeed(long seed) {
mRandom.setSeed(seed);
}
}

beradth first search in java:

public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;

int[] visited = new int[number_of_nodes + 1];
int i, element;

visited[source] = 1;
queue.add(source);

while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + " ");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.