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

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.

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.

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.