Can someone finish the main for me as I put in as comment and come up with a test text file? Thank you.

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

public class Driver { public static Scanner userScanner = new Scanner(System.in);

// opens a text file for input, returns a Scanner: public static Scanner openInputFile() { String filename; Scanner scanner=null; System.out.print("Enter the input filename: "); filename = userScanner.nextLine(); File file= new File(filename);

try{ scanner = new Scanner(file); }// end try catch(FileNotFoundException fe){ System.out.println("Can't open input file "); return null; // array of 0 elements } // end catch return scanner; } public static void displayMenu(){ //Display Menu

System.out.println(" ====================================================="); System.out.println("***************Euler Path Program********************"); System.out.println(" "); System.out.println("What would you like to do now? "); System.out.println("Options: "); System.out.println(" 1. Read a graph from a text file "); System.out.println(" 2. Add an edge to the graph "); System.out.println(" 3. Remove an edge from the graph "); System.out.println(" 4. Undo previous removal "); System.out.println(" 5. Display the graph(Depth-First traversal) "); System.out.println(" 6. Display the graph(Breadth-First traversal)"); System.out.println(" 7. Display the graph as an adjacency list "); System.out.println(" 8. Solve the problem for the graph "); System.out.println(" 9. Write the graph to a text file "); System.out.println(" 10. Exit program "); System.out.println("====================================================="); } public static void main(String[] args){ Scanner input = new Scanner(System.in); int choice = 0; displayMenu(); System.out.print("Select option(1-10): "); choice = input.nextInt(); while(choice < 1 || choice > 10){ System.out.print("Please enter an option in the range 1-10: "); choice = input.nextInt(); } while(choice != 10){ //I think for most cases, or maybe just from (2-9), it //Should check if a graph was previously read from an input file. //Otherwise if nothing has been read and the user chooses options 2-9 it //will probably cause an error switch(choice){ case 1 : Scanner fileScanner = openInputFile(); // check if file doesn't open and display error message if(fileScanner == null){ System.out.println("Ending program"); return; } //Read information(graph) from the input file fileScanner.close(); break; case 2 : //Adds an edge to the graph break; case 3 : //Removes an edge from the graph break; case 4 : //Reverts the previous removal(s) break; case 5 : //Display the graph using the Depth-First traversal break; case 6 : //Display the graph using the Breadth-First traversal break; case 7 : //Display the graph as an adjacency list break; case 8 : //Solves the graph problem break; case 9 : //Writes the graph to a text file break; } displayMenu(); System.out.print("Select option(1-10): "); choice = input.nextInt(); while(choice < 1 || choice > 10){ System.out.print("Please enter an option in the range 1-10: "); choice = input.nextInt(); } } System.out.println(" Thanks for using the program."); } }

__________________________________________________________________

import java.util.ArrayList; import java.util.Iterator; import java.util.Map; import java.util.Random;

public class EulerPath extends Graph {

/* * According to Euler: If a graph has more than 2 vertices of odd degree, * there cannot be an Euler Path Conditions for Euler path: Number of odd * vertices must be two * * * Need something to keep track number of edges First check if graph has an * Euler path, within a method: a) Have local counter variable initially set * to 0, keeps track of number of odd vertices b) Iterate through the vertex * set in Graph.java checking the number of edges for each vertex c) If, at * the end of the method, there exists exactly 2 odd vertices, than an Euler * path exists, continue with the program d) Otherwise let the user know * that an Euler path doesn't exist, quit program * * * Need: 1) ArrayList to keep track of traversals, prevent going back * to same edge 2) Stack to keep track of vertices 3) Queue * end result of algorithm, shows where an Euler path exists * * * Algorithm for finding Euler path: a) Declare an empty stack and queue b) * If there are any odd vertices, start at those vertices c) If no odd * vertices, start at any vertex d) From current vertex, pick any neighbor * to go to. Remove the edge connecting the neighbor to the current vertex - * If all edges have been traversed, add current vertex to queue, pop from * stack and set as current vertex - Else add current vertex to stack, go to * any neighbor, remove edge between current vertex and selected neighbor e) * Repeat d until stack is empty f) Return the queue of vertices, the queue * shows Euler path g) Since this algorithm deleted edges, need to rebuild * graph at the end in case user wants to find another Euler path */

private LinkedStack> traversalStack; private LinkedStack> eulerPathStack; private ArrayList> startingVertices; private Random rand;

public EulerPath() { traversalStack = new LinkedStack<>(); startingVertices = new ArrayList<>(); eulerPathStack = new LinkedStack<>(); rand = new Random(); }

public void checkForEulerPath() { // Check to see if an Euler Path exists if (!hasEulerPath()) { System.out.println("An Euler Path does not exist for the current graph"); return; } else { // If an Euler path exists, find a path then display it findEulerPath(); showEulerPath(); } }

// Check to see if an Euler path exists // Needs two Iterators, one to iterate through the graphs vertexSet, another // to iterate // through each vertex's adjList protected boolean hasEulerPath() { int numOddVertices = 0; Iterator> vertexSetItr = vertexSet.values().iterator(); // Iterates // through // vertexSet Iterator, Double>>> vertexAdjItr; // Iterates // through // each // vertex's // adjList

while (vertexSetItr.hasNext()) { int numEdges = 0; // To count the number of edges for each vertex Vertex currentVertex = vertexSetItr.next(); // Get next vertex in // vertexSet vertexAdjItr = currentVertex.iterator(); // Get iterator for // currentvertex's // adjList while (vertexAdjItr.hasNext()) { numEdges++; // increase for every entry in currentVertex's // adjList vertexAdjItr.next(); } if (numEdges % 2 != 0) { // increase if number of edges for current // vertex is odd numOddVertices++; startingVertices.add(currentVertex); // Add to startingVertices // list if currentVertex // has an odd number of // edges } } // Euler path for a graph exists if number of odd vertices for given // graph is exactly 2 if (numOddVertices == 2) return true; else return false; }

protected void findEulerPath() { // From the list of startingVertices, pick one randomly to begin int startIndex = getRandIndex(startingVertices); Vertex currentVertex = startingVertices.get(startIndex); Vertex neighbor; boolean done = false; // Exit flag

do { neighbor = getANeighbor(currentVertex); // Get a neighbor vertex // from currentVertex if (neighbor == null) { eulerPathStack.push(currentVertex); currentVertex = traversalStack.pop(); // A complete Euler path has been found when the traversalStack // is empty and if currentVertex // does not have any more neighbors, this is the exit condition // for the loop if (traversalStack.isEmpty() && currentVertex.adjList.size() == 0) { eulerPathStack.push(currentVertex); done = true; } } else { traversalStack.push(currentVertex); currentVertex = neighbor; } } while (!done); }

protected Vertex getANeighbor(Vertex currentVertex) { ArrayList> neighborsList = new ArrayList<>(); // Stores // currentVertex's // neighbors Iterator, Double>> currentVertexAdj_Itr = currentVertex.adjList.values().iterator(); Vertex neighborVertex = null; int index;

// Iterate through currentVertex's hashMap and populate listOfNeighbors while (currentVertexAdj_Itr.hasNext()) { neighborsList.add(currentVertexAdj_Itr.next().first); }

// If currentVertex has no neighbors if (neighborsList.isEmpty()) return null;

// Get a random index from neighborsList index = getRandIndex(neighborsList); neighborVertex = neighborsList.get(index);

// Sever the connection between currentVertex and neighborVerte to // prevent traversing // the same edge twice currentVertex.adjList.remove(neighborVertex.data); neighborVertex.adjList.remove(currentVertex.data);

return neighborVertex; }

public void showEulerPath() { Vertex currentVertex; System.out.print("Euler Path Vertices: "); while (!eulerPathStack.isEmpty()) { currentVertex = eulerPathStack.pop(); System.out.print(currentVertex.getData() + " "); } System.out.println(); }

// A helper method, returns a random index from an ArrayList passed into // this method // Enables different Euler paths to be found for a given graph private int getRandIndex(ArrayList> verticesList) { return rand.nextInt(verticesList.size()); }

}

_______________________________________________________________________

import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry;

public class Graph { // the graph data is all here -------------------------- protected HashMap> vertexSet;

// public graph methods -------------------------------- public Graph() { vertexSet = new HashMap>(); }

public void addEdge(E source, E dest, double cost) { Vertex src, dst;

// put both source and dest into vertex list(s) if not already there src = addToVertexSet(source); dst = addToVertexSet(dest);

// add dest to source's adjacency list src.addToAdjList(dst, cost); dst.addToAdjList(src, cost); // ADD THIS IF UNDIRECTED GRAPH }

public void addEdge(E source, E dest, int cost) { addEdge(source, dest, (double) cost); }

// adds vertex with x in it, and always returns ref to it public Vertex addToVertexSet(E x) { Vertex retVal = null; Vertex foundVertex;

// find if Vertex already in the list: foundVertex = vertexSet.get(x);

if (foundVertex != null) // found it, so return it { return foundVertex; }

// the vertex not there, so create one retVal = new Vertex(x); vertexSet.put(x, retVal);

return retVal; // should never happen }

public boolean remove(E start, E end) { Vertex startVertex = vertexSet.get(start); Vertex endVertex = vertexSet.get(end); boolean removedOK = false;

if (startVertex != null) { Pair, Double> endPair = startVertex.adjList.remove(end); removedOK = endPair != null; }

// Add if UNDIRECTED GRAPH: Vertex endVertex = vertexSet.get(end); if (endVertex != null) { Pair, Double> startPair = endVertex.adjList.remove(start); removedOK = startPair != null; }

return removedOK; }

public void showAdjTable() { Iterator>> iter;

System.out.println("------------------------ "); iter = vertexSet.entrySet().iterator(); while (iter.hasNext()) { (iter.next().getValue()).showAdjList(); } System.out.println(); }

public void clear() { vertexSet.clear(); }

// reset all vertices to unvisited public void unvisitVertices() { Iterator>> iter;

iter = vertexSet.entrySet().iterator(); while (iter.hasNext()) { iter.next().getValue().unvisit(); } }

/** Breadth-first traversal from the parameter startElement */ public void breadthFirstTraversal(E startElement, Visitor visitor) { unvisitVertices();

Vertex startVertex = vertexSet.get(startElement); breadthFirstTraversalHelper(startVertex, visitor); }

/** Depth-first traversal from the parameter startElement */ public void depthFirstTraversal(E startElement, Visitor visitor) { unvisitVertices();

Vertex startVertex = vertexSet.get(startElement); depthFirstTraversalHelper(startVertex, visitor); }

protected void breadthFirstTraversalHelper(Vertex startVertex, Visitor visitor) { LinkedQueue> vertexQueue = new LinkedQueue<>(); E startData = startVertex.getData();

startVertex.visit(); visitor.visit(startData); vertexQueue.enqueue(startVertex); while (!vertexQueue.isEmpty()) { Vertex nextVertex = vertexQueue.dequeue(); Iterator, Double>>> iter = nextVertex.iterator(); // iterate // adjacency // list

while (iter.hasNext()) { Entry, Double>> nextEntry = iter.next(); Vertex neighborVertex = nextEntry.getValue().first; if (!neighborVertex.isVisited()) { vertexQueue.enqueue(neighborVertex); neighborVertex.visit(); visitor.visit(neighborVertex.getData()); } } } } // end breadthFirstTraversalHelper

public void depthFirstTraversalHelper(Vertex startVertex, Visitor visitor) { // YOU COMPLETE THIS (USE THE RECURSIVE ALGORITHM GIVEN FOR LESSON 11 // EXERCISE) }

// WRITE THE INSTANCE METHOD HERE TO // WRITE THE GRAPH's vertices and its // adjacency list TO A TEXT FILE (SUGGEST TO PASS AN // ALREADY OPEN PrintWriter TO THIS) !

}

__________________________________________________________

//--- a simple pair data structure, (first, second), that uses first as a key public class Pair { public E first; public F second;

public Pair(E x, F y) { first = x; second = y; }

public boolean equals(Object rhs) { Pair other; other = (Pair) rhs; return first.equals(other.first); }

public int hashCode() { return first.hashCode(); }

}

____________________________________________________________

import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry;

class Vertex { public static final double INFINITY = Double.MAX_VALUE; public HashMap, Double>> adjList = new HashMap, Double>>(); public E data; public boolean visited;

public Vertex(E x) { data = x; }

public Vertex() { this(null); }

public E getData() { return data; }

public boolean isVisited() { return visited; }

public void visit() { visited = true; }

public void unvisit() { visited = false; }

public Iterator, Double>>> iterator() { return adjList.entrySet().iterator(); }

public void addToAdjList(Vertex neighbor, double cost) { if (adjList.get(neighbor.data) == null) adjList.put(neighbor.data, new Pair, Double>(neighbor, cost)); // Note: if you want to change the cost, you'll need to remove it and // then add it back }

public void addToAdjList(Vertex neighbor, int cost) { addToAdjList(neighbor, (double) cost); }

public boolean equals(Object rhs) { if (!(rhs instanceof Vertex)) return false; Vertex other = (Vertex) rhs;

return (data.equals(other.data));

}

public int hashCode() { return (data.hashCode()); }

public void showAdjList() { Iterator, Double>>> iter; Entry, Double>> entry; Pair, Double> pair;

System.out.print("Adj List for " + data + ": "); iter = adjList.entrySet().iterator(); while (iter.hasNext()) { entry = iter.next(); pair = entry.getValue(); System.out.print(pair.first.data + "(" + String.format("%3.1f", pair.second) + ") "); } System.out.println(); }

}

________________________________________________________________________________ public interface Visitor { public void visit(E obj); }

_________________________________________________________________________________

/** * Homework Assignment #2 Jae Kim 5/23/17 Windows/Ecplise A class that * implements the ADT queue by using a chain of nodes that has both head and * tail references. * * @author Frank M. Carrano * @author Timothy M. Henry * @version 4.0 UPDATED by C. Lee-Klawender NOTE: the LinkedQueue class includes * the Node class as an inner class */ public class LinkedQueue implements QueueInterface

{ private Node frontNode; // References node at front of queue private Node backNode; // References node at back of queue private int count = 0;

public LinkedQueue() { frontNode = null; backNode = null; } // end default constructor

public boolean enqueue(T newEntry) { Node newNode = new Node(newEntry); if (isEmpty()) { frontNode = newNode; backNode = frontNode; } else { backNode.next = newNode; backNode = newNode; } // ADD CODE TO add data to linked list HERE! // In addition to updating the backNode, also // make sure you check if the list was empty before adding this // and update the correct variable if so

++count; return true; } // end enqueue

public T peekFront() { if (isEmpty()) return null; else return frontNode.getData(); } // end getFront

public T dequeue() { T front = peekFront(); if (count > 0) { frontNode.data = null; frontNode = frontNode.next; } // ADD CODE TO remove data from linked list HERE! // In addition to updating the frontNode, also // make sure to check if the list becomes empty and // update the correct variable if so

--count;

return front; } // end dequeue

public boolean isEmpty() { if (frontNode == null) return true; else return false; } // end isEmpty

public int size() { return count;

}

public String toString() { String myStrr = ""; Node myCurrNode = frontNode; while (myCurrNode != null) { myStrr += "Event:" + myCurrNode.getData().toString() + " -> "; myCurrNode = myCurrNode.getNextNode(); } return myStrr; }

public void clear() { frontNode = null; }

private class Node { private T data; // Entry in queue private Node next; // Link to next node

private Node(T dataPortion) { data = dataPortion; next = null; } // end constructor

private Node(T dataPortion, Node linkPortion) { data = dataPortion; next = linkPortion; } // end constructor

private T getData() { return data; } // end getData

private void setData(T newData) { data = newData; } // end setData

private Node getNextNode() { return next; } // end getNextNode

private void setNextNode(Node nextNode) { next = nextNode; } // end setNextNode } // end Node

/* * (non-Javadoc) clones the content of the LinkedQueue if it is an event and * constructs it to the copy queue. * * @see DeepCloneable#deepClone() */ } // end Linkedqueue

_____________________________________________________________________________________________________________

/** An interface for the ADT queue. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 UPDATED by C. Lee-Klawender */ public interface QueueInterface { /** Adds a new entry to the back of this queue. @param newEntry An object to be added. @return True if succesfully added the newEntry, false otherwise*/ public boolean enqueue(T newEntry);

/** Removes and returns the entry at the front of this queue. @return The object at the front of the queue or null if the queue is empty before the operation. */ public T dequeue();

/** Retrieves the entry at the front of this queue. @return The object at the front of the queue or null if the queue is empty. */ public T peekFront();

/** Detects whether this queue is empty. @return True if the queue is empty, or false otherwise. */ public boolean isEmpty();

/** Returns number of items in this queue @return: Number of items */ public int size(); } // end QueueInterface