import java.util.Random;

public class RandomGraph {
	private AdjGraph G;
	
	public RandomGraph(int n, double density){
		G=new AdjGraph(n);
		Random generator=new Random();
		int I,J,cost;
		for(int k=0;k<=n*(n-1)*density-1;k++)
		{//randomly generate an edge and add it to the graph
			I=generator.nextInt(n);
			J=generator.nextInt(n);
			cost=generator.nextInt(1000)+1;
			G.addNode(I, J, cost);
		}
	}
	
	public boolean ConnectTest (AdjGraph G){
		// test the connectivity of the graph G
		int n = G.getVertexNb();
		int[][] length=new int[n][n];
        for (int i=0;i<n;i++)
        	for (int j=0;j<n;j++){
        		length[i][j]=G.getWeight(i,j);
        	}
       int[] dist= new int[n];
       for(int j=0;j<=n-1;j++){
    	   dist[j]=5000;
       }
       
       boolean connect=true;
       int s=G.getSource();
       // using the simple schema to test the conectivity
       SimpleSSP tester = new SimpleSSP(G,n);
       dist=tester.ShortestPath(s);
  
	   for(int j=0;j<=n-1;j++){
		   if(dist[j]==5000){
			   // the dist[j] equal to MAX, means the node [j] cannot be reached
				connect=false;
		   }
	   }
	   return connect;
	}
	
	public AdjGraph GraphGenerator(int n, double density){
		//randomly generate graph
		RandomGraph randomG= new RandomGraph( n, density);
		if (!ConnectTest (randomG.G)){
			//re-generate it if not connected
			randomG=new RandomGraph(n,density);
		}
		return randomG.G;
	}
}