Program Explanation Program: Edge.java: Refer book from chapter 28 – Listing 28.1. Graph.java: Refer book from chapter 28 – Listing 28.3. UnweightedGraph.java: Refer book from chapter 28 – Listing 28.4. WeightedGraph.java: Refer book from chapter 29 – Listing 29.2. WeightedEdge.java: Refer book from chapter 29 – Listing 29.1. NineTailModel.java : Refer book from chapter 28 – Listing 28.13. //import statement import java.util.*; //definition of "Test" class public class Test { //main method public static void main(String[] args) { //allocation of memory new Test(); } //definition of "Test" public Test() { //declare and set the values for the variable String[] vertices = { "Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston" }; //declare and set the values for the variable int[][] edges = { { 0, 1 },{ 0, 3 },{ 0, 5 }, { 1, 0 },{ 1, 2 },{ 1, 3 }, { 2, 1 },{ 2, 3 },{ 2, 4 },{ 2, 10 }, { 3, 0 },{ 3, 2 },{ 3, 4 },{ 3, 5 }, { 4, 2 },{ 4, 3 },{ 4, 5 },{ 4, 7 },{ 4, 8 },{ 4, 10 }, { 5, 0 },{ 5, 3 },{ 5, 4 },{ 5, 6 },{ 5, 7 }, { 6, 5 },{ 6, 7 }, { 7, 4 },{ 7, 5 },{ 7, 6 },{ 7, 8 }, { 8, 4 },{ 8, 7 },{ 8, 9 },{ 8, 10 },{ 8, 11 }, { 9, 8 },{ 9, 11 }, { 10, 2 },{ 10, 4 },{ 10, 8 },{ 10, 11 }, { 11, 8 },{ 11, 9 },{ 11, 10 } }; //create an object Graph<String> graph1 = new UnweightedGraph<>(vertices, edges); //display the edges System.out.println("The edges for graph1:"); graph1.printEdges(); //memory allocation for the "edge" variable edges = new int[][]{ { 0, 2 },{ 1, 2 },{ 2, 4 },{ 3, 4 } }; //create an object Graph<Integer> graph2 = new UnweightedGraph<>(edges, 5); //display the edges System.out.println("The edges for graph2:"); graph2.printEdges(); //display the output System.out.println("A Hamiltonian path is " + graph1.getHamiltonianPath(0)); System.out.println("A Hamiltonian cycle is " + graph1.getHamiltonianCycle()); System.out.println("A Hamiltonian cycle from New York is " + graph1.getHamiltonianCycle(graph1.getIndex("New York"))); System.out.println("A Hamiltonian path is " + graph1.getHamiltonianPath()); } //graph interface gets defined public interface Graph<V> { //return the number of vertices public int getSize(); //vertice in the graph are returned public java.util.List<V> getVertices(); //index of the vertex gets returned public V getVertex(int index); //return index of the specific vertex public int getIndex(V v); //return the neighbor of the specific index public java.util.List<Integer> getNeighbors(int index); //degree of the specified index gets returned public int getDegree(int v); //edge gets printed public void printEdges(); //graph gets clear public void clear(); //new vertex are added public boolean addVertex(V vertex); //add edge public boolean addEdge(int u, int v); //edge of the graph is added public boolean addEdge(Edge e); //vertex of the graph is removed public default boolean remove(V v) { return true; } //edge gets removed from the graph public default boolean remove(int u, int v) { return true; } //perform depth first search public UnweightedGraph<V>.SearchTree dfs(int v); //perform breadth first search public UnweightedGraph<V>.SearchTree bfs(int v); //perform hamiltonian path operation public List<Integer> getHamiltonianPath(V vertex); //perform hamiltonian path operation public List<Integer> getHamiltonianPath(int v); //perform hamiltonian path operation public List<Integer> getHamiltonianPath(); //perform hamiltonian cycle operation public List<Integer> getHamiltonianCycle(); //perform hamiltonian cycle operation public List<Integer> getHamiltonianCycle(int v); } //define the class public class UnweightedGraph<V> implements Graph<V> { //vertices are stored protected List<V> vertices = new ArrayList<>(); //define the adjacency lists protected List<List<Edge>> neighbors = new ArrayList<>(); //empty constructor protected UnweightedGraph() { } //graph gets created protected UnweightedGraph(V[] vertices, int[][] edges) { //loop that iterates for the vertices for (int i = 0; i < vertices.length; i++) //add the vertices addVertex(vertices[i]); //new adjacencylist gets created createAdjacencyLists(edges, vertices.length); } //graph gets created protected UnweightedGraph(List<V> vertices, List<Edge> edges) { //loop that iterates for the vertices for (int i = 0; i < vertices.size(); i++) //add the vertices addVertex(vertices.get(i)); //new adjacency list gets created createAdjacencyLists(edges, vertices.size()); } //graph gets constructed protected UnweightedGraph(List<Edge> edges, int numberOfVertices) { /*loop that iterates for the total number of vertices*/ for (int i = 0; i < numberOfVertices; i++) //add the vertex addVertex((V)(new Integer(i))); //new adjacency list gets created createAdjacencyLists(edges, numberOfVertices); } //graph gets constructed protected UnweightedGraph(int[][] edges, int numberOfVertices) { /*loop that iterates to count the number of vertices*/ for (int i = 0; i < numberOfVertices; i++) //vertices gets added addVertex((V)(new Integer(i))); //create an adjacency list createAdjacencyLists(edges, numberOfVertices); } //adjacency list gets created private void createAdjacencyLists( int[][] edges, int numberOfVertices) { /*loop that iterates for the edge length of the vertices*/ for (int i = 0; i < edges.length; i++) { //add the edges addEdge(edges[i][0], edges[i][1]); } } //adjacency list for each vertex gets created private void createAdjacencyLists( //new edge gets created List<Edge> edges, int numberOfVertices) { //loop that iterates for the edges for (Edge edge : edges) { //edge gets added addEdge(edge.u, edge.v); } } @Override //number of vertices gets returned public int getSize() { //return return vertices.size(); } @Override //number of vertices gets returned public List<V> getVertices() { return vertices; } @Override //object of the specific vertex gets returned public V getVertex(int index) { //return return vertices.get(index); } @Override //object of the specific vertes gets returned public int getIndex(V v) { //return return vertices.indexOf(v); } @Override //neighbor of the specific index gets returned public List<Integer> getNeighbors(int index) { //list gets defined List<Integer> result = new ArrayList<>(); //loop that iterates that neighbor value for (Edge e : neighbors.get(index)) //add the result result.add(e.v); return result; } @Override //return the degree public int getDegree(int v) { //return return neighbors.get(v).size(); } @Override //edge gets printed public void printEdges() { /*loop that iterates for the neighbors node*/ for (int u = 0; u < neighbors.size(); u++) { //display the verted System.out.print(getVertex(u) + " (" + u + "): "); /*loop that iterates for the neighbor nodes*/ for (Edge e : neighbors.get(u)) { //display the vertex System.out.print("(" + getVertex(e.u) + ", " + getVertex(e.v) + ") "); } //new line System.out.println(); } } @Override //graph gets cleared public void clear() { //clear the vertices vertices.clear(); //clear the neighbor neighbors.clear(); } @Override //new vertex is added public boolean addVertex(V vertex) { //condition to validate the vertex if (!vertices.contains(vertex)) { //add the vertices vertices.add(vertex); //add the neighbor vertices neighbors.add(new ArrayList<Edge>()); //return true return true; } else { //return false return false; } } @Override //new edge gets added public boolean addEdge(Edge e) { //condition to validate the edges if (e.u < 0 || e.u > getSize() - 1) //exception handler throw new IllegalArgumentException("No such index: " + e.u); //condition to validate the edges if (e.v < 0 || e.v > getSize() - 1) //exception handler throw new IllegalArgumentException("No such index: " + e.v); //condition to validate the edges if (!neighbors.get(e.u).contains(e)) { neighbors.get(e.u).add(e); //return true return true; } else { //return false return false; } } @Override //edge gets added to the graph public boolean addEdge(int u, int v) { //add the edge return addEdge(new Edge(u, v)); } @Override //perform depth first search public SearchTree dfs(int v) { //new array list gets created List<Integer> searchOrder = new ArrayList<>(); //new parent node gets created int[] parent = new int[vertices.size()]; /*loop that iterates for the entire length*/ for (int i = 0; i < parent.length; i++) //return the parent parent[i] = -1; //visited vertices gets martked boolean[] isVisited = new boolean[vertices.size()]; // perform recursive search dfs(v, parent, searchOrder, isVisited); //search tree gets returned return new SearchTree(v, parent, searchOrder); } //perform dfs recursively private void dfs(int u, int[] parent, List<Integer> searchOrder, boolean[] isVisited) { // visted vertices are stored searchOrder...

MyLab Programming with Pearson eText -- Access Card -- for Introduction to Java Programming and Data Structures, Comprehensive Version

11th Edition

ISBN: 9780134672816

Author: Liang

Publisher: PEARSON

See similar textbooks

Concept explainers

Strongly Connected Components

A directed graph in which a path exists between all its pairs of vertices is called a strongly connected graph. A portion of the strongly connected directed graph that contains a path to reach from each vertex to other vertices is called a strongly conne…

Question

Chapter 28, Problem 28.17PE

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 28, Problem 28.16PE

Chapter 28, Problem 28.19PE

Students have asked these similar questions

No AI solutions please

Chapter 28 Solutions

MyLab Programming with Pearson eText -- Access Card -- for Introduction to Java Programming and Data Structures, Comprehensive Version

Chapter 28.2, Problem 28.2.1CP Chapter 28.2, Problem 28.2.2CP Chapter 28.2, Problem 28.2.3CP Chapter 28.2, Problem 28.2.4CP Chapter 28.3, Problem 28.3.1CP Chapter 28.3, Problem 28.3.2CP Chapter 28.4, Problem 28.4.1CP Chapter 28.4, Problem 28.4.2CP Chapter 28.4, Problem 28.4.3CP Chapter 28.4, Problem 28.4.4CP

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Chapter 28, Problem 28.17PE

Solution Summary: The author adds a java class named “Edge” to the package which is used to get the edges from the graph.

Concept explainers

Want to see the full answer?

Chapter 28 Solutions