import java.util.*;

import java.io.*;

public class NetworkMain
{
	public static void main (String[ ] args)  
	{            
      		final String PROMPT1 = 
			"\nPlease enter the vertices whose shortest path you want: ";

      		final String SENTINEL = "***";

      		final String PROMPT2 = "\nPlease enter " +
                  	"two vertices and a weight (the sentinel is " + SENTINEL + "): ";

      		final String SHORTEST_PATH_MESSAGE1 = 
			"\n\n\nThe shortest path from ";

      		final String SHORTEST_PATH_MESSAGE2 = " and its total weight are ";
	
      		Network<String> network = new Network<String>();

      		BufferedReader reader = new BufferedReader
                            		(new InputStreamReader (System.in));

      		StringTokenizer tokens;

      		String start,
	               finish,
	               vertex1,
                       vertex2,
	               line;
                
      		double weight;

      		try 
      		{
          		// Get start and finish vertices.
          		System.out.print (PROMPT1);
          		line = reader.readLine();
          		tokens = new StringTokenizer (line);
          		start = tokens.nextToken();
          		finish = tokens.nextToken();

	    		// Get edges and weights.
          		while (true)
          		{
           			System.out.print (PROMPT2);
           			line = reader.readLine();
           			if (line.equals(SENTINEL))
           				break;
           			tokens = new StringTokenizer (line);
           			vertex1 = tokens.nextToken();
           			vertex2 = tokens.nextToken();
           			weight = Double.parseDouble (tokens.nextToken());
           			network.addEdge (vertex1, vertex2, weight);
       			} // while
	
       			System.out.println ("\nnetwork = " + network);
       			LinkedList pathList = network.getShortestPath (start, finish);
       			System.out.println (SHORTEST_PATH_MESSAGE1 + start + " to " + finish
                                     + SHORTEST_PATH_MESSAGE2 + pathList);
       			System.out.println ("neighbors of start = " + network.neighbors (start));

	 		boolean networkIsConnected = network.isConnected();
	 		System.out.println ("is connected is " + networkIsConnected);
       			if (networkIsConnected)
       				System.out.println ("spanning tree = " + network.getMinimumSpanningTree());
       
       			System.out.println ("empty is " + network.isEmpty());
       			System.out.println ("vertex count = " + network.size());
       			System.out.println ("edge count = " + network.getEdgeCount());
       			System.out.println ("contains f is " + network.containsVertex ("f"));
       			System.out.println ("contains edge a t is " + network.containsEdge ("a", "t"));
       			System.out.println("contains edge a d is " + network.containsEdge ("a", "d"));
       
       			System.out.println ("\n\nbreadth-first iterating from " + start + ": ");
       			Iterator<String> itr = network.breadthFirstIterator (start);
       			while (itr.hasNext())
              			System.out.print (itr.next() + " ");

       			System.out.println ("\n\ndepth-first iterating from " + start + ": ");
       			itr = network.depthFirstIterator (start);
       			while (itr.hasNext())
             			System.out.print (itr.next() + " ");

       			System.out.println ("\n\niterating over network:");
       			for (String s : network)      
             			System.out.print (s + " ");

       			network.removeEdge ("b", "c");
       			network.removeVertex ("d");
       			System.out.println ("\n\niterating over network after removing b-c and d:");
       			for (String s : network)      
               			System.out.print (s + " ");

       			System.out.println ("\n\nedge weight of a b is " + 
		      		network.getEdgeWeight ("a", "b"));

       			pathList = network.getShortestPath (start, finish);
       			System.out.println (SHORTEST_PATH_MESSAGE1 + start + " to " + finish
                                      + SHORTEST_PATH_MESSAGE2 + pathList);
     		} // try
     		catch (IOException e)
     		{
			System.out.println (e);
     		} // catch
	} // method main

} // class NetworkMain