ssp.java

This code implements the shortest path algorithm via the simple scheme and fibonacci heap data struc

import java.io.*;
import java.util.StringTokenizer;

public class ssp {
	// main function
	public static void main(String[] args) {	
		if (args[0].compareTo("-r")==0)  
		{   // Random Mode
			System.out.println("Number of nodes   "+"	 "+"Density"+"   "+"Simple scheme"+"   "+"F-heap scheme"); 
			for (int n=100; n<=500; n=n+100)
			{   // from 100 to 500 nodes
				for(int i=10;i<100;i=i+10)
				{ //density from 10 to 100
					StringBuffer temp=new StringBuffer();
					temp.append("         "+n+"                ");
					temp.append(i);
					temp.append("           ");

					RandomGraph randG = new RandomGraph(n, i/100);			
					AdjGraph G=new AdjGraph();
					G=randG.GraphGenerator(n,i/100);
							
					SimpleSSP tester = new SimpleSSP(G,n);
					FibonacciSSP tester2 = new FibonacciSSP(G,n);
					
					long []startSiSSP=new long[5];
					long []stopSiSSP=new long[5];
					long []timeSiSSP=new long[5];
					long []startFiSSP=new long[5];
					long []stopFiSSP=new long[5];
					long []timeFiSSP=new long[5];
					
					int j=0;
					do{
						//simple schema
						startSiSSP[j] = System.currentTimeMillis();
						for (int v=0; v<100; v++)
						{
							tester.ShortestPath(G.getSource());
						}
						//tester.ShortestPath(G.getSource());
						stopSiSSP[j] = System.currentTimeMillis();
						timeSiSSP[j] = stopSiSSP[j] - startSiSSP[j]; 
				
			            //fibonacci heap schema
						startFiSSP[j] = System.currentTimeMillis();
						for (int v=0; v<100; v++)
						{
							tester2.FShortestPath(G.getSource());
						}
						//tester2.FShortestPath(G.getSource());
						stopFiSSP[j]  = System.currentTimeMillis();
						timeFiSSP[j] = stopFiSSP[j] - startFiSSP[j];
						j++;
					}while(j<5);
					// run five times and get the average
					
					long sum1=0,sum2=0;
					for(j=0;j<5;j++)
					{
						sum1=sum1+timeSiSSP[j];
						sum2=sum2+timeFiSSP[j];
					}
					long time1,time2;
					time1=sum1/5;
					time2=sum2/5;
					//compute the average
				
					temp.append(time1+"               ");
			        temp.append(time2+"               ");
			 	    System.out.println(temp.toString());		    
					}
				}
			}	
		if(args.length==1)
		{
			if(args[0].compareTo("-is")==0)
			{// userinput simple schema
				AdjGraph graph= new AdjGraph(1000);
				System.out.println("Input: Starnode Endnode Weight");
				int linecounter=-1;
				//read from user's input
				
				try{
				InputStreamReader input = new InputStreamReader(System.in);
				BufferedReader in = new BufferedReader(input);
                String line = in.readLine();
                int readin[]=new int[3];
                
				while(line.compareTo("*")!=0){
					 linecounter++;
					 int i=0;
					 StringTokenizer T = new StringTokenizer(line);
				     while (T.hasMoreTokens()){
				    	 readin[i]=Integer.valueOf(T.nextToken()).intValue();
				         i++;
				     }
				     if (i<2) graph.setSource(readin[0]);
				     else graph.addNode(readin[0], readin[1], readin[2]);
				     line = in.readLine();
				}
				}
				catch(FileNotFoundException e)
				{
					System.out.println("Data file was not found");
					System.out.println("or could not be opened.");
				}
				catch(IOException e)
				{
					System.out.println("Error reading from file.");
				}
				
				//compute the shortest path
				AdjGraph G=graph;
				int n= linecounter;
				int s = G.getSource();
				int[] distance=new int[n];
				SimpleSSP tester = new SimpleSSP(G,n);
				distance=tester.ShortestPath(s);
				System.out.println("Node"+" Dist");
				for(int i=0;i<n;i++)
					if(distance[i]!=5000)
					System.out.println(i+"     "+distance[i]);
			}
				
			if(args[0].compareTo("-if")==0)
			{//user input fibonacci schema
				AdjGraph graph= new AdjGraph(1000);
				System.out.println("Input: Starnode Endnode Weight");
				int linecounter=-1;
				
				//read from usr input
				try{
				InputStreamReader input = new InputStreamReader(System.in);
				BufferedReader in = new BufferedReader(input);
                String line = in.readLine();
                int readin[]=new int[3];
                
				while(line.compareTo("*")!=0){
					 linecounter++;
					 int i=0;
					 StringTokenizer T = new StringTokenizer(line);
				     while (T.hasMoreTokens()){
				    	 readin[i]=Integer.valueOf(T.nextToken()).intValue();
				         i++;
				     }
				     if (i<2) graph.setSource(readin[0]);
				     else graph.addNode(readin[0], readin[1], readin[2]);
				     line = in.readLine();
				}
				}
				catch(FileNotFoundException e)
				{
					System.out.println("Data file was not found");
					System.out.println("or could not be opened.");
				}
				catch(IOException e)
				{
					System.out.println("Error reading from file.");
				}
				
				//compute the shortest path
				AdjGraph G=graph;
				int n= linecounter;
				int s = G.getSource();
				int[] distance=new int[n];
				FibonacciSSP tester = new FibonacciSSP(G,n);
				distance=tester.FShortestPath(s);
				System.out.println("Node"+" Dist");
				for(int i=0;i<n;i++)
					if(distance[i]!=5000)
					System.out.println(i+"     "+distance[i]);
			}
				
		}
		else
		{// if args.length ==2
			if(args[0].compareTo("-is")==0)
			{ // user file input simple schema
				
				//read from file
				ReadFile reader= new ReadFile(args[1]);			
				AdjGraph G=reader.getGraph();	
				int n= 6;
				int s = G.getSource();
				int[] distance=new int[n];
				
				//simple schema
				SimpleSSP tester = new SimpleSSP(G,n);
				distance=tester.ShortestPath(s);
				System.out.println("Node"+" Dist");
				for(int i=0;i<n;i++)
					if(distance[i]!=5000)
					System.out.println(i+"     "+distance[i]);
			}
				
			if(args[0].compareTo("-if")==0)
			{//user file input fibonacci schema
				
				//read from file
				ReadFile reader = new ReadFile(args[1]);					
				AdjGraph G=reader.getGraph();	
				int n= reader.linect;
				int s = G.getSource();
				int[] distance=new int[n];
				
				//comput shortest path
				FibonacciSSP tester2 = new FibonacciSSP(G,n);
				distance=tester2.FShortestPath(s);
				System.out.println("Node"+" Dist");
				for(int i=0;i<n;i++)
					if(distance[i]!=5000)
					System.out.println(i+"     "+distance[i]);
			}
				
		}
	}
}