Homework 4: Backtracking Algorithms

For this homework you will create 3 programs in the same Netbeans project. A shell is provided to get you started.

Problem 1: Graph Utilities

Open the project shell and find the GraphUtilities file. Complete the methods

    public 
    static List>  getAdjListFromFile() throws FileNotFoundException
    {
       JFileChooser fChooser = new JFileChooser(); 
       int response = fChooser.showOpenDialog(null);
       if (response != JFileChooser.APPROVE_OPTION)
       {
           System.out.println("No file selected");
           System.exit(1);           
       }
       File file = fChooser.getSelectedFile();
       Scanner sc = new Scanner(file);
       int numberVertices = sc.nextInt();   // number of vertices
       List<List<Integer>> adjList =  new ArrayList<>();
       
       // Add code to build the adjacency list
      
       return adjList;  
    }
    
    public static
    boolean [][] getMatrix(List<List<Integer>> adjList)
    {
        int numberVertices = adjList.size();
        boolean [] [] matrix = new boolean[numberVertices][numberVertices];
        
        // Add code to build the adjacency matrix from the adjacency list
        return matrix;
    }
    

The first method opens a file using a file chooser dialog, and then builds and returns an adjacency list from data that is stored in the file. The data in the file follows the following syntax: The file starts with the number of vertices of the graph, say N. The file follows this with N lines of data, one line for each vertex of the graph. Each line of data begins with a number V in the range 0,.., N-1 that represents a vertex of a graph. The vertex number V is followed by its outdegree D, the number of edges that come out of that vertex. The outdegree is followed by D integers that represent the terminal vertices of the edges that come out of V.

Here is an example:

5
2 4 0 1 3 4
0 2 1 2
3 2 2 4
4 2 2 3
1 2 0 2
    

This data represents a graph of 5 vertices with vertices 0, 1, 2, 3, and 4. Vertex 0 has two edges coming out it, going to vertex 1 and vertex 2. Vertex 2 has 4 edges coming out of it, going to vertices 0, 1, 3, and 4.

Here is another example:

12
0 3 1 10 6
1 3 2 10 0
2 3 1 3 9
3  3 2 4 8
4 3 3 8 5
5 3  4 7 6
6 3 5 0 7
7 3 5 6 11
8 3 3 4  11
9 3 2 11 10
10 3 9 1 0
11 3 8 9 7

    

The second method takes and adjacency list as parameter and returns an equivalent adjacency matrix.

Problem 2: Finding All Cliques of Maximum Size

In the project shell, you will find a file Homework4Clique. This file has a main method that reads the adjacency list of a graph from a file, and builds the equivalent adjacency matrix by calling the methods you wrote for Problem 1.

        List> adjList = getAdjListFromFile();
        System.out.println("Adjacency list is ");
        for (List x : adjList)
        {
            System.out.println(x);
        }
        boolean [][] m = getMatrix(adjList);
        System.out.println("Adjacency matrix is ");
        for (boolean [] x : m)
        {
            System.out.println(Arrays.toString(x));
        } 
        
        List> cliqueSet = new LinkedList<>();
        cliqueSet.add(new LinkedList<>());
        extendClique(cliqueSet, new LinkedList<>(), 0, m);
        
        System.out.printf("The set of largest cliques is %s\n", cliqueSet);    
    

Note that this method calls an extendCliqueSet() method to compute and return the set all cliques of the graph that are as large as possible. A clique in a graph is a subset K of the set of vertices such that for any two vertices v and w in K, the edge (v, w) is in the graph. That is, a clique is a set of vertices in which any two vertices are adjacent. For example, a single vertex is a clique of size 1, any edge is a clique of size 2, and three vertices that form a triangle constitute a clique of size 3.

Your job is this problem is to write the method that finds all cliques of graph that have maximum size. Do this by completing the following method:

    /**
     * 
     * @param best: A list containing the largest clicks  found so far.
     * @param partial: the partial solution we are trying to extend to
     *                 a clique of maxumum size.
     * @param k: the stage in the extension of the solution. At this stage, 
     *           vertices 0,.., k-1 have already been considered for inclusion
     *           or exclusion.
     * @param adjMatrix : adjacency matrix for graph
     */
    public static void extendClique(List<List<Integer>> best, 
                                    LinkedList<Integer> partial,  int k, 
                                    boolean [][] adjMatrix)
    {
           
    }
    

You need to keep the name and parameter list given in your solution.

Problem 3: Minimum Vertex Covers

This problem is similar to the last one: except you need to find the list of all minimum vertex covers in a graph. A vertex cover is a subset K of the set of vertices which is such that every edge of the graph has at least one of its endpoints in K. A trivial example of a vertex cover is the set of all vertices in the graph. But what we want is a list of all vertex covers that have as few elements as possible.

In the project shell, you will find a file Homework4Cover that prints the list of all minimum-size vertex covers by calling the method

     /**
     * 
     * @param best: a non-empty list of the smallest covers found so far.
     *              Original call sets this to the entire set of vertices.
     * @param partial : a list of vertices we are trying to extend to a cover.
     *                  At the time of call this is not yet a cover.
     * @param k : the current stage,0..k-1 have already been considered
     * @param adjMatrix: adjacency matrix for the graph 
     */
    public static void extendCover(List> best, 
                                   LinkedList partial,  int k, 
                                   boolean [][] adjMatrix)
    {        
             
    }
    

Again, you need to retain the name and parameter list of this meethod.

Due Date:

Friday at end of Week 8. Start working on this right away because you will get more homework the end of the week.