// Edge.java
// Mainly get/set methods for a weighted edge.

public class Edge {
    private int v1,v2;

    private int integer_weight;
    private double real_weight;
    private boolean weight_is_int;

    public Edge(int vertex1, int vertex2, boolean integer_weights) { 
	v1 = vertex1;
	v2 = vertex2;
	weight_is_int = integer_weights;
    }

    public int getIntegerWeight() {
	if(weight_is_int)
	    return integer_weight;
	
	throw new RuntimeException("Edge weight is a real number!");
    }

    public void setIntegerWeight(int weight) {
	weight_is_int = true;
	integer_weight = weight;
    }

    public double getRealWeight() {
	if(!weight_is_int)
	    return real_weight;

	throw new RuntimeException("Edge weight is an integer!");
    }
	
    public void setRealWeight(double weight) {
	weight_is_int = false;
	real_weight = weight;
    }

    public int getVertex1() {
	return v1;
    }

    public void setVertex1(int vertex1) {
	v1 = vertex1;
    }

    public int getVertex2() {
	return v2;
    }

    public void setVertex2(int vertex2) {
	v2 = vertex2;
    }

}
import java.util.*;

// RandomWeightedGraphs.java
// Generates a random connected graph whose edge weights vary randomly.

public class RandomWeightedGraphs{

    private HashSet usedEdges;
    private Edge [] edges;

    private boolean uniqueWeights;
    private boolean integerWeights;

    private int maxIntegerWeight;
    private double maxRealWeight;

    private HashSet usedEdgeWeights;

    // The MetaVertex class is used for constructing the graph
    // (Each MetaVertex is a spanning tree in a forest which will
    // eventually be connected.)

    private class MetaVertex{
	
	public ArrayList vertices;
	
	// each MetaVertex keeps track of vertices and edges
	// in the connected component it represents
	
	public MetaVertex(int i, int nV) { 
	    vertices = new ArrayList();
	    vertices.add(new Integer(i));
	}
	
    }
    
    // Creates a random connected graph with numVertices vertices and
    // numEdges edges, and edges with either int or double weights.
    // The maximum weight can be specified for either of these.  In
    // calling this method, set "uniqueWeights" to true if the graph's
    // edge weights should all be unique(this results in a unique
    // minimal spanning tree).  Set "integerWeights" to true if the
    // weights should be ints, false if they should be doubles.
    // returns the graph as a set of edges in an array [numEdges] of
    // Edge objects.  Each edge is between two vertices, vertices
    // numbered 0, ..., numVertices - 1.  First creates a random
    // spanning tree among the vertices and then adds new random edges
    // with random weights until has number of edges desired.
    
    public Edge [] generate(int numVertices, int numEdges, 
			    int maxIntegerWeight, double maxRealWeight,
			    boolean uniqueWeights, boolean integerWeights) {

	this.uniqueWeights = uniqueWeights;
	this.integerWeights = integerWeights;

	this.maxIntegerWeight = maxIntegerWeight;
	this.maxRealWeight = maxRealWeight;

	if(integerWeights && maxIntegerWeight < numEdges)
	    throw new RuntimeException("Max weight not appropriate.");

	if(!integerWeights && maxRealWeight <= 0)
	    throw new RuntimeException("Max weight not appropriate.");

	usedEdgeWeights = new HashSet();

	usedEdges = new HashSet();
	edges = new Edge [numEdges];
	if ((numEdges < (numVertices-1)) 
	    || (numEdges > ((numVertices * (numVertices -1)) / 2)))
	    throw new RuntimeException("Edge number not appropriate.");

	generateSpanningTree(numVertices);
	
	for(int j = 0; j1; j--) {
	    int firstMVert = (int) (Math.random()*j);
	    int secondMVert = firstMVert;
	    while (secondMVert == firstMVert)
		secondMVert = (int) (Math.random()*j);

	    mVs = combineMetaVertices(firstMVert, secondMVert, j, mVs, numVertices);
	}
    }
    
    ///
    ///
    
    private  MetaVertex [] combineMetaVertices(int v1, int v2, int nV, 
					       MetaVertex [] mVs, 
					       int numVertices) {
	MetaVertex mV1 = mVs[v1];
	MetaVertex mV2 = mVs[v2];

	int end1 = ((Integer) mV1.vertices.get((int) (Math.random()*mV1.vertices.size()))).intValue();
	int end2 = ((Integer) mV2.vertices.get((int) (Math.random()*mV2.vertices.size()))).intValue();

	if (end1 > end2) {
	    int temp = end1;
	    end1 = end2;
	    end2 = temp;
        }
    
	Edge e = new Edge(end1,end2,integerWeights);

	setEdgeWeight(e);
	
	edges[nV-2] = e;
	
	(mV1.vertices).addAll(mV2.vertices);
	usedEdges.add(new Integer(end1*numVertices + end2));
	mVs[v2] = mVs[nV-1];

	return mVs;
    }
    
    
    // Sets up a new edge.
    
    private void addNewEdge(int numEs, int numVs) {
	Edge e = edges[0];
	Edge newEdge = new Edge(e.getVertex1(),e.getVertex2(),integerWeights);
	
	while(isOld(newEdge, numVs)) {
	    newEdge.setVertex1((int) (Math.random() * numVs));
	    newEdge.setVertex2(newEdge.getVertex1());
	    while (newEdge.getVertex1() == newEdge.getVertex2())
		newEdge.setVertex2((int) (Math.random() * numVs));
	    
	    if(newEdge.getVertex1() > newEdge.getVertex2()) {
		int temp = newEdge.getVertex1();
		newEdge.setVertex1(newEdge.getVertex2());
		newEdge.setVertex2(temp);
	    }
	}

	setEdgeWeight(newEdge);

	edges[numEs] = newEdge;

	usedEdges.add(new Integer(newEdge.getVertex1()*numVs + newEdge.getVertex2()));

    }

    // Sets edge weight.  Nontrivial because we might want the weights
    // unique.

    private void setEdgeWeight(Edge e) {
	do {
	    if(integerWeights)
		e.setIntegerWeight(randomIntegerWeight());
	    else
		e.setRealWeight(randomRealWeight());
	} while(uniqueWeights && checkWeight(e));

	if(integerWeights)
	    usedEdgeWeights.add(new Integer(e.getIntegerWeight()));
	else
	    usedEdgeWeights.add(new Double(e.getRealWeight()));
    }
    
    // Are these two vertices already joined?
    
    private boolean isOld(Edge e, int numVs) {
	return usedEdges.contains(new Integer(e.getVertex1()*numVs + e.getVertex2()));
    }

    // It's important to watch your weight.  You might not want
    // someone else's.

    private boolean checkWeight(Edge e) {

	boolean result;
	
	if(integerWeights)
	    result = usedEdgeWeights.contains(new Integer(e.getIntegerWeight())) || e.getIntegerWeight() == 0;
	else
	    result = usedEdgeWeights.contains(new Double(e.getRealWeight())) || e.getRealWeight() == 0.0;
	
	return result;
    }

    // Create a random edge weight.

    private int randomIntegerWeight() {
        return (int) (Math.random()*maxIntegerWeight);
    }

    private double randomRealWeight() {
	return Math.random()*maxRealWeight;
    }
	
}

public class graphTest {
    public static void main(String [] args) {
	RandomWeightedGraphs g = new RandomWeightedGraphs();

	Edge [] edges = g.generate(10,30,100,0.0,true,true);

	for(int i = 0; i < 30; i++)
	    System.out.println("Edge " + i + ": (" + edges[i].getVertex1() +
			       "," + edges[i].getVertex2() + 
			       "), with weight " + 
			       edges[i].getIntegerWeight() + ".");

	edges = g.generate(10,30,100,0.0,false,true);

	for(int i = 0; i < 30; i++)
	    System.out.println("Edge " + i + ": (" + edges[i].getVertex1() +
			       "," + edges[i].getVertex2() + 
			       "), with weight " + 
			       edges[i].getIntegerWeight() + ".");

	edges = g.generate(10,30,0,100.0,false,false);

	for(int i = 0; i < 30; i++)
	    System.out.println("Edge " + i + ": (" + edges[i].getVertex1() +
			       "," + edges[i].getVertex2() + 
			       "), with weight " + 
			       edges[i].getRealWeight() + ".");

	edges = g.generate(10,30,0,100.0,true,false);

	for(int i = 0; i < 30; i++)
	    System.out.println("Edge " + i + ": (" + edges[i].getVertex1() +
			       "," + edges[i].getVertex2() + 
			       "), with weight " + 
			       edges[i].getRealWeight() + ".");

	edges = g.generate(10,30,10,0.0,true,true);

	for(int i = 0; i < 30; i++)
	    System.out.println("Edge " + i + ": (" + edges[i].getVertex1() +
			       "," + edges[i].getVertex2() + 
			       "), with weight " + 
			       edges[i].getIntegerWeight() + ".");

    }
}