 # Project Assignment The goal of this assignment is to give students...

## Question

Show transcribed text

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Comparator;
import java.util.HashMap;
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<>();

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)
.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;...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

\$138.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.