Chapter 28, Problem 28.17PE

Program Plan Intro

Program Plan:

• Include the required import statement.
• Create a package “main”.
  • Add a java class named “Edge” to the package which is used to get the edges from the graph.
  • Add a java class named “Graph” to the package which is used to add and remove vertices, edges.
  • Add a java class named “UnweightedGraph” to the package which is used to store vertices and neighbors.
  • Add a java class named “WeightedGraph” to the package which is used to get the weighted edges and print the edges.
  • Add a java class named “WeightedEdge” to the package which is used to compare edges.
  • Add a java class named “NineTailModel” to the package which is used to compare edges.
  • Define the main method using public static main.
    • Allocate memory to the class “Test”.
    • Define the “Test” class.
    • Declare and set the values for the variables.
    • Create an object1 for the “Graph” class.
    • Display the edge.
    • Allocate memory for the “edge” variable.
    • Create an object2 for the “Graph” class.
    • Display the edge.
    • Display the results.
  • Define the “Graph” class.
    • A graph interface gets created.
    • Method to return the size gets defined.
    • Method to return the vertices gets defined.
    • Method to return the index gets created.
    • Method to get the neighbor node gets created.
    • Method to get the degree gets created.
    • Method to print the edges.
    • Method to clear the node gets created.
    • Method to add the edges, add vertex gets created.
    • Method to remove the vertices gets defined.
    • Method for the depth first search gets defined.
    • Method for the breadth first search gets defined.
  • Create a class “UnweightedGraph”:
    • New list for the vertices gets created.
    • New list for the neighbor node gets created.
    • Create an empty constructor.
    • Method to create new graph gets created and adjacency list gets created.
    • Method to create an adjacency list gets created.
    • Method to return the size of the vertices.
    • Method to return the index of the vertices gets defined.
    • Method to gets the neighbor node gets defined.
    • Method to return the degree of the vertices gets created.
    • Method to print the Edges gets created.
    • New to clear the graph gets created.
    • Method to add vertex gets created.
    • Method to add edge gets created.
    • Method to perform the depth first search gets defined.
    • Method to perform breadth first search gets defined.
      • Search tree gets returned.
    • Create a class “SearchTree”
      • Define the method to return the root.
      • Method to return the parent of the vertices
      • Method to return the search order gets defined.
      • Method to return the number of vertices found gets defined.
      • Method to get the path of the vertices gets defined.
        • Loop to validate the path gets defined.
        • Path gets returned.
      • Method to print the path gets defined.
      • Method to print the tree gets defined.
        • Display the edge.
        • Display the root.
        • Condition to validate the parent node to display the vertices gets created.
      • Define the “getHamiltonianPath” method.
        • If the size of graph is equal to “i” value, return a Hamiltonian path from the specified vertex object.
        • Otherwise, return null if the graph does not have a Hamiltonian path.
      • Define the “getHamiltonianPath” method.
        • Return the value using array list.
      • Define the “getHamiltonianPath” method.
        • Declare the required variables.
        • If the length of the graph, indicate no subpath from “i” is found.
        • The vertices in the Hamiltonian path are stored in result.
        •  Reorder the adjacency list for each vertex.
        • Create a list for path
        • Add vertex to the result list.
        • Get the next vertex in the path.
        • Return null if no Hamiltonian path is found.
      • Define the “reorderNeigborsBasedOnDegree” method.
        • Check the condition.
          • Find the maximum in the list.
        • Check the condition and swap the list with another list.
      • Define the “allVisited” method.
        • Declare the variables.
        • Check if all the elements in array is visited and return true.
        • Otherwise return the result.
      • Define the “getHamiltonianPath” method.
        • Declare the variables
        • If all the vertices are found then include all the vertices.
        • Then search for a Hamiltonian path from “v”.
      • Define “getHamiltonianCycle” method.
        • Return a Hamiltonian cycle.
      • Define “getHamiltonianCycle” method.
        • Declare the variable.
        • If the length of the graph, indicate no subpath from “i” is found.
        • The vertices in the Hamiltonian path are stored in result.
        •  Reorder the adjacency list for each vertex.
        • Create a list for path
        • Add vertex to the result list.
        • Get the next vertex in the path.
        • Return null if no Hamiltonian path is found.
      • Define “getHamiltonianCycle” method.
        • Declare the variable.
        • If all the vertex is visited the return true.
        • Otherwise backtrack “v” is marked unvisited.
        • Return false.
      • Define “isCycle” method.
        • Return the value.