creategraphic.java

Create the Northern Ireland graphic

    {
    	int j=0;
       	EdgeInfo current  = VertexList[v].firstEdge;//the EdgeInfo node used to move
       	while(current !=null)
       	{
       		if(current.distance == s)
       		{
       			j = current.ToCity;
       		}
       		
       		current = current.nextEdge;
       	}
       	return j;
        
    }
    
 /********************************************************************************
 *Input: A vertex No, and a distance
 *Output: The destination vertex No 
 *Function: Find the destination vertex No of the unvisited Edge
 *********************************************************************************/  
    
    public EdgeInfo getEdgeInfo (int v,double s)
    {
    	EdgeInfo p =  VertexList[v].firstEdge;
       	EdgeInfo current  = VertexList[v].firstEdge;//the EdgeInfo node used to move
       	while(current !=null)
       	{
       		if(current.distance == s)
       		{
       			p = current;
       		}
       		
       		current = current.nextEdge;
       	}
       	return p;
        
    }
    
/***************************************************************************
  Input: A vertex No
  Output: Shortest distance 
  Function: Find the shortest distance of the unvisited edge from the input vertex
  **************************************************************************/    
      
    public double getShortestUnvisitedDistance(int v)
      {
      	int j=0;//the shortest unvisited vertex No
      	double shortest =1000.0;
      	int linkedNum = VertexList[v].linkedEdgenum;//the linked route number of the node
      	EdgeInfo current  = VertexList[v].firstEdge;//the EdgeInfo node used to move
      	EdgeInfo p  = VertexList[v].firstEdge;
      	int n=0;//unvisited subroute
      	
      	unvisitedEdge = new EdgeInfo[linkedNum]; 
      	
      	//if all of the linked node have been visited return 0.0
      	
      	while(VertexList[current.ToCity].isVisited == true)
      	{
      		System.out.println("Visited City" + current.ToCity);
      		current = current.nextEdge;
      		if(current==null)
      		{
      			return 0.0;
      		}
      	}
      
      	
        current  = VertexList[v].firstEdge;//reset the current Edge
      	
      	//store all of the unvisited edge in unvisitedEdge array
      	while(current!=null )
      	{
      		System.out.println(current.distance);
      	   
      		if(VertexList[current.ToCity].isVisited == false)
      		{
      		   unvisitedEdge[n] = current;
      		   n++;//the number of unvisited vertex
      	    }	
      	    current = current.nextEdge;//move to next EdgeInfo
      	    
      	}
      //	System.out.println("n="+n);
      
      //find the shortest EdgeInfo in the unvisitedEdge array
      	for(int i=0;i<n;i++)
      	{
      		if(unvisitedEdge[i].distance < shortest)
      		shortest = unvisitedEdge[i].distance;
      	}
      	
      	
      	System.out.println("the shortest distance is" + shortest);
        return shortest;
    	
    	
      } 
      
  /***************************************************************************
  Input: A vertex No
  Output: Longest distance 
  Function: Find the longest distance of the unvisited edge from the input vertex
  **************************************************************************/    
      
    public double getLongestUnvisitedDistance(int v)
      {
      	int j=0;//the shortest unvisited vertex No
      	double longest =0.1;
      	int linkedNum = VertexList[v].linkedEdgenum;//the linked route number of the node
      	EdgeInfo current  = VertexList[v].firstEdge;//the EdgeInfo node used to move
      	EdgeInfo p  = VertexList[v].firstEdge;
      	int n=0;//unvisited subroute
      	
      	unvisitedEdge = new EdgeInfo[linkedNum]; 
      	
      	//if all of the linked node have been visited return 0.0
      	
      	while(VertexList[current.ToCity].isVisited == true)
      	{
      		System.out.println("Visited City" + current.ToCity);
      		current = current.nextEdge;
      		if(current==null)
      		{
      			return 0.0;
      		}
      	}
      
      	
        current  = VertexList[v].firstEdge;//reset the current Edge
      	
      	//store all of the unvisited edge in unvisitedEdge array
      	while(current!=null )
      	{
      		System.out.println(current.distance);
      	   
      		if(VertexList[current.ToCity].isVisited == false)
      		{
      		   unvisitedEdge[n] = current;
      		   n++;//the number of unvisited vertex
      	    }	
      	    current = current.nextEdge;//move to next EdgeInfo
      	    
      	}
      //	System.out.println("n="+n);
      
      //find the longest EdgeInfo in the unvisitedEdge array
      	for(int i=0;i<n;i++)
      	{
      		if(unvisitedEdge[i].distance > longest)
      		longest = unvisitedEdge[i].distance;
      	}
      	
      	
      	System.out.println("the longest distance is" + longest);
        return longest;
    	
    	
      } 
      
      
     public EdgeInfo[] LongDFS( int start, int end )
	{
		int subRouteNum =0;
		int n = 0;//the vertex No of the peek Vertex of the stack
		int k = 0;//the Vertex No with the shortest distance
		int i;
		double s = 0.0;//the longest distance
		myStack theStack = new myStack();
		Vertex v = new Vertex();
		EdgeInfo[] edge;
		VertexList[start].isVisited = true;
		theStack.push(VertexList[start]);
	
		//find a possible current longest route
		while(theStack.peek()!=VertexList[end])
		{
		
			n = theStack.peek().verNo;
			s = getLongestUnvisitedDistance(n);//find the current longest distance
			if (s == 0.0)//if all of the linked routes have been visited
			{
				theStack.pop();
			}
			else
			{
				k = getVertex(n,s);
				VertexList[k].isVisited = true;
				theStack.push(VertexList[k]);//push the longest linked vertex into the stack
			}
		}//end while
		
		subRouteNum = theStack.gettop();//get the sub route number of the route
		//System.out.println(subRouteNum);
	    i = subRouteNum-1;
		edge = new EdgeInfo[subRouteNum];
	
	//Convert the Vertex seqence into EdgeInfo sequence and store the current longest route into a EdgeInfo array
		while(theStack.gettop()!= 0)
		{
			
			EdgeInfo current = new EdgeInfo();
			int o = 0;//origin
			int d = 0;//destination
			o = theStack.peek().verNo;
			theStack.pop();
			d = theStack.peek().verNo;
			current = VertexList[o].firstEdge;
			while(current!=null)
			{
				if(current.ToCity == d)
				{
					edge[i] = current;	
					//System.out.println("The edge is" + edge[i].routeNo);
					break;
				}
				
				else
				{
					current = current.nextEdge;
				}
			}
			
			i--;		
		
		}
		
		// reset flags
	    for(int j=1; j<	NumOfVer; j++)          
         VertexList[j].isVisited = false;
		
		 return edge;	
			
		}
      
     
    public static void main(String[] args)
      {
      	CreateGraphic c = new CreateGraphic();
      	 EdgeInfo shortRoute[];
      	 EdgeInfo longRoute[];
      	
        c.Create();
      for(int i=1;i<23;i++)
      {
      	  System.out.print(c.VertexList[i].name);
          c.VertexList[i].displayList(i);   
      }  
     
        shortRoute = c.ShortDFS(6,22);   
        longRoute = c.LongDFS(6,22);   
        System.out.println("The shortest route is:");     
        for(int i=0; i<shortRoute.length;i++)
        {
        	System.out.print(shortRoute[i].routeNo+" ");
        }   
        System.out.println("\nThe longest route is:");   
        for(int i=0; i<longRoute.length;i++)
        {
        	System.out.print(longRoute[i].routeNo+" ");
        }   

      }  // end 
	
 
}