import java.io.File;
import java.io.FileNotFoundException;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
import java.util.stream.Collectors;

/**
*
* @author
*/
public class project {

private static String sequence;
public static void main(String[] args) {

   // hashhmap all vertex in the graph
   // each vertex is the key of another map
   // which is contain the distacne between this vertex and other vertices
   HashMap<Vertex, HashMap<Vertex, Integer>> graph;
   graph = new HashMap<>();

   // read file
   readGraph(graph);
   readDistanceToZ(graph);

   Scanner scanner = new Scanner(System.in);
   boolean valid = false;
   do {
         System.out.print("Enter start node: ");
         String start = scanner.next();

         System.out.println("User enters node " + start + " as the start node");
         System.out.println("");
         System.out.println("Algorithm 1: ");
         System.out.println("");
         valid = Algorithm1(start, graph);

         System.out.println("");
         System.out.println("Algorithm 2: ");
         System.out.println("");
         valid = valid && Algorithm2(start, graph);

         // stop when the input is the name of a valid node
   } while (valid == false);

}

private static boolean Algorithm2(String name,
         HashMap<Vertex, HashMap<Vertex, Integer>> graph) {
   // reset all vertices
   for (Vertex vertex : graph.keySet()) {
         vertex.setVisited(false);
   }

   // find the key
   Vertex key = null;
   for (Vertex vertex : graph.keySet()) {
         if (vertex.getName().equals(name)) {
            key = vertex;
            break;
         }
   }

   // invalid name
   if (key == null) {
         return false;
   }

   key.setVisited(true);
   Stack<Vertex> stack = new Stack<>();
   stack.push(key);

   // call algorithm
   sequence = name;
   boolean result = Algorithm2(stack, graph);
   if (result == true) {
         System.out.println("\tSequence of all nodes: " + sequence);
         System.out.println("\tShortest path: " + generatePath(stack));
         System.out.println("\tShortest path length: "
               + generatePathLength(stack, graph));
   } else {
         System.out.println("There is no path");
   }
   return true;
}

private static boolean Algorithm2(Stack<Vertex> stack,
         HashMap<Vertex, HashMap<Vertex, Integer>> graph) {
   // current node
   Vertex current = stack.peek();
   // list adjacent nodes:
   HashMap<Vertex, Integer> adj = graph.get(current);

   /**
      * Algorithm 2: Among all nodes v that are adjacent to the node n,
      * choose the one for which w(n, v) + dd(v) is the smallest.
      */
   Comparator<? super Map.Entry<Vertex, Integer>> comparator
            = (Map.Entry<Vertex, Integer> o1, Map.Entry<Vertex, Integer> o2) -> {
               HashMap<Vertex, Integer> value = graph.get(current);
               int dd1 = value.get(o1.getKey()) + o1.getKey().getDistanceToZ();
               int dd2 = value.get(o2.getKey()) + o2.getKey().getDistanceToZ();
               return dd1 - dd2;
            };

   // sort the map by w(n, v) + dd(v)
   Map<Vertex, Integer> sortedAdj = adj.entrySet()
            .stream()
            .sorted(comparator)
            .collect(Collectors.toMap(
                     Map.Entry::getKey,
                     Map.Entry::getValue,
                     (oldValue, newValue) -> oldValue, LinkedHashMap::new));

   /**
      * work on each vertex
      */
   for (Vertex vertex : sortedAdj.keySet()) {
         sequence += " -> " + vertex.getName();
         if (vertex.isVisited() == false) {
            vertex.setVisited(true);
            stack.push(vertex);

            if (vertex.getName().equals("Z")) {
               return true;
            }
            boolean result = Algorithm2(stack, graph);
            if (result == true) {
               return true;
            }
            // backtrack
            stack.pop();
            vertex.setVisited(false);
         }
   }

   return false;
}

/**
* algorithm 1
*
* @param name name of the starting point
* @param graph the graph
* @return return false when key is invalid
*/
private static boolean Algorithm1(String name,
         HashMap<Vertex, HashMap<Vertex, Integer>> graph) {

   // reset all vertices
   for (Vertex vertex : graph.keySet()) {
         vertex.setVisited(false);
   }

   // find the key
   Vertex key = null;
   for (Vertex vertex : graph.keySet()) {
         if (vertex.getName().equals(name)) {
            key = vertex;
            break;

Data Structures Assignment 1 1 Motivation we often discuss the i...