Chapter 28, Problem 28.16PE

Program Plan Intro

Induced subgraph

Program Plan:

• 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 “E16” to the package.
    • Import the required packages.
    • Declare the main class.
      • Give the “main ()” method.
        • Declare the string array that contains the names of the city.
        • Declare an integer array that contains the weight.
        • Create an object for unweighted graph.
        • Print the size of the graph, vertex of the graph, index of the vertex “Miami”, and the edges of the graph.
        • Call the function “maxInducedSubgraph ()”.
        • Print the size of the graph, vertex of the graph, index of the vertex “Miami”, and the edges of the graph.
      • Give function definition for “maxInducedSubgraph ()”.
        • Declare required variables
        • Do until the condition “(!Isdone && g.getSize() > 0)” fails.
          • Assign “true” to the variable.
          • Loop from 0 through size.
            • Check the condition “(g.getDegree(i) < k)”.
              • Call the function “remove_Vertex ()”.
              • Assign false to the variable.
              • Break the loop.
        • Return the graph.
      • Function definition for “UnweightedGraphInducedSubgraph ()”.
        • Construct the empty graph.
        • Construct a graph from vertices and edges stored in arrays.
          • Get the vertices and edges.
        • Construct a graph from vertices and edges stored in List.
          • Get the vertices and edges.
        • Construct a graph for integer vertices 0, 1, 2 and edge list.
          • Get the vertices and edges.
        • Construct a graph from integer vertices 0, 1, and edge array.
          • Get the vertices and edges.
        • Give function definition for “remove_Vertex ()”.
          • Check the condition “(vertices.contains(v))”.
            • Get the index.
            • Call the functions “vertices.remove ()”, and “neighbors.remove ()”.
            • Loop to remove the edges.
              • Loop from 0 through size.
                • Check the condition “(list.get(i).v == index)”. If it is true then remove the edge.
                • Else, increment the variable
            • Loop to reassign the labels.
              • Loop from 0 through size.
                • Check the condition “(list.get(i).u >= index)”. If the condition is true then get the edge
                • Check the condtion “(list.get(i).v >= index)”. If the condition is true then get the edge
            • Return “true”.
          • Else,
            • Return “false”.