Demo entry 6655734

mst

   

Submitted by anonymous on Oct 27, 2017 at 15:47
Language: Java. Code size: 7.0 kB.

package Assi02Q1_4;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class mst {
	static int n=200;
	static double sum=0;
	static double mst=0;
	static double aver=0;
	static double partial=0;
	static long averTime=0;
	static long startTime=0;
	static long endTime=0;
	static long totalTime=0;
	static int t=1;
	static int p=20;
	
	public static ArrayList<Vertex> allVertex=new ArrayList<Vertex>();
	public static Comparator<Vertex> Comparator = new Comparator<Vertex>(){

		@Override
		public int compare(Vertex v0, Vertex v1) {
			// TODO Auto-generated method stub
			return Double.compare(v0.weight, v1.weight);
		}
    };
	
    public static Queue<Vertex> Q=new PriorityQueue<Vertex>(n, Comparator);
    public static Queue<Vertex> selectedQ=new PriorityQueue<Vertex>(n, Comparator);
    
	public static void main(String arg[]) {
		System.out.println("Part 1");
		System.out.println("Case 01: n = 200");
		for(int i=0;i<p;i++) {
			prim();
			
			allVertex.clear();
			Q.clear();
			
			mst+=sum;
			sum=0;
			averTime+=totalTime;
			totalTime=0;
			startTime=0;
			endTime=0;
		}
		
		aver=mst/p;
		System.out.println("running time="+String.valueOf(averTime/20.0000)+"ms");
		System.out.println("Average MST weight="+String.valueOf(aver));
		
		n=400;
		aver=0;
		averTime=0;
		mst=0;
		System.out.println("Case 02: n = 400");
		for(int i=0;i<p;i++) {
			prim();
			
			allVertex.clear();
			Q.clear();
			
			mst+=sum;
			sum=0;
			averTime+=totalTime;
			totalTime=0;
			startTime=0;
			endTime=0;
		}
		aver=mst/p;
		System.out.println("Runnning time="+String.valueOf(averTime/20.0000)+"ms");
		System.out.println("Average MST weight="+String.valueOf(aver));
		
		n=800;
		aver=0;
		averTime=0;
		mst=0;
		System.out.println("Case 03: n = 800");
		for(int i=0;i<p;i++) {
			prim();
			
			allVertex.clear();
			Q.clear();
			
			mst+=sum;
			sum=0;
			averTime+=totalTime;
			totalTime=0;
			startTime=0;
			endTime=0;
		}
		aver=mst/p;
		System.out.println("Running time="+String.valueOf(averTime/20.0000)+"ms");
		System.out.println("Average MST weight="+String.valueOf(aver));
		
		n=1600;
		aver=0;
		averTime=0;
		mst=0;
		System.out.println("Case 04: n = 1600");
		for(int i=0;i<p;i++) {
			prim();
			
			allVertex.clear();
			Q.clear();
			
			mst+=sum;
			sum=0;
			averTime+=totalTime;
			totalTime=0;
			startTime=0;
			endTime=0;
		}
		aver=mst/p;
		System.out.println("Running time="+String.valueOf(averTime/20.0000)+"ms");
		System.out.println("Average MST weight="+String.valueOf(aver)+"\n");
		
		System.out.println("Part 2");
		n=200;
		System.out.println("Case 01: n="+n);
		double[][] edge=new double[n][n];
		select(edge);
		sum=0;
		
		n=400;
		System.out.println("Case 02: n="+n);
		double[][] edge1=new double[n][n];
		select(edge1);
		sum=0;
		
		n=800;
		System.out.println("Case 03: n="+n);
		double[][] edge2=new double[n][n];
		select(edge2);
		sum=0;
		
		n=1600;
		System.out.println("Case 04: n="+n);
		double[][] edge3=new double[n][n];
		select(edge3);
	}
	
	public static void buildGraph() {
		int order=0;
		for(int j=0;j<n;j++) {
			for(int i=0;i<n;i++)
				allVertex.add(new Vertex(Math.random()*10, Math.random()*10, order++));
		}
	}
	
	public static void addEdge(double[][] edge) {
		buildGraph();
		for(int i=0;i<n;i++) {						//initialise edge
			for(int j=0;j<n;j++)
				edge[i][j]=Math.sqrt(Math.pow(allVertex.get(i).x-allVertex.get(j).x, 2)+Math.pow(allVertex.get(i).y-allVertex.get(j).y,2));
		}
		
	}
	
	public static void prim() {						//this is the prim we use in part1
		double[][] edge=new double[n][n];
		addEdge(edge);
		
		startTime = System.currentTimeMillis();
		
		for(int i=0;i<n;i++) 						//add into the queue except the 1-st vertex
			Q.offer(allVertex.get(i));
		
		allVertex.get(0).weight=0;
		allVertex.get(0).p=allVertex.get(0);
		
		while(!Q.isEmpty()) {
			int k=Q.peek().num;
			Vertex tp=Q.poll();						//get the top out
			for(int i=0;i<n;i++) {
				if(edge[k][i]<allVertex.get(i).weight && Q.contains(allVertex.get(i))) {
					Q.remove(allVertex.get(i));
					allVertex.get(i).weight=edge[k][i];
					Q.add(allVertex.get(i));
					allVertex.get(i).p=tp;
				}
			}
			sum+=allVertex.get(k).weight;
		}
		
		endTime = System.currentTimeMillis();
		totalTime = endTime-startTime;
	}
	
	public static void prim(double[][] edge) {		//another prim-applied on part2
		addEdge(edge);
		
		for(int i=0;i<n;i++) 						//add into the queue except the 1-st vertex
			Q.offer(allVertex.get(i));
		
		allVertex.get(0).weight=0;
		allVertex.get(0).p=allVertex.get(0);
		
		while(!Q.isEmpty()) {
			int k=Q.peek().num;
			Vertex tp=Q.poll();						//get the top out
			for(int i=0;i<n;i++) {
				if(edge[k][i]<allVertex.get(i).weight && Q.contains(allVertex.get(i))) {
					Q.remove(allVertex.get(i));
					allVertex.get(i).weight=edge[k][i];
					Q.add(allVertex.get(i));
					allVertex.get(i).p=tp;
				}
			}
			sum+=allVertex.get(k).weight;
		}
		
		System.out.println("MST weight="+String.valueOf(sum));
	}
	
	public static void select(double[][] edge) {	//used for selecting vertexes and calculating ratios
		prim(edge);
		
		int t=1;
		double part=0.75;
		while(t<=3) {
			if(t==1)
				part=0.75;
			else if(t==2)
				part=0.5;
			else
				part=0.25;
			
			
			selectedQ.clear();
		
			for(int m=0;m<n;m++) {
				allVertex.get(m).weight=9999;
				allVertex.get(m).p=null;
			}
		
			Random r=new Random();
			int sel=0,p=0,pn=(int) (part*n-1);
			sel=r.nextInt(n);
			selectedQ.add(allVertex.get(sel));
			allVertex.get(sel).weight=0;
			allVertex.get(sel).p=allVertex.get(sel);
		
			while(p<pn) {
				if(selectedQ.contains(allVertex.get(sel=r.nextInt(n)))!=true) {
					selectedQ.add(allVertex.get(sel));
					p++;
				}
			}		
		
			partial=0;
			while(!selectedQ.isEmpty()) {
				int k=selectedQ.peek().num;
				Vertex tp=selectedQ.poll();	
				for(int i=0;i<n;i++) {
					if(selectedQ.contains(allVertex.get(i)) && edge[k][i]<allVertex.get(i).weight) {
						selectedQ.remove(allVertex.get(i));
						allVertex.get(i).weight=edge[k][i];
						selectedQ.add(allVertex.get(i));
						allVertex.get(i).p=tp;
					}
				}
			partial+=allVertex.get(k).weight;
			}
			double ratio=partial/sum;
			System.out.println("U"+t+"="+part+"V:"+"The ratio is "+String.valueOf(ratio));
			t++;
		}
	}
	
}

class Vertex implements Comparable<Vertex> {
	public double x;
	public double y;
	public Vertex p;
	public double weight;
	public int num;
	public Vertex(double d, double e, int n){
		this.x=d;
		this.y=e;
		this.num=n;
		this.p=null;
		this.weight=9999;
	}
	public int compareTo(Vertex o) {
		// TODO Auto-generated method stub
		return Double.compare(this.weight, o.weight);
	}
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).