Using the code provided in lab5.java, which uses an adjacency matrix to store a directed graph, complete the following two methods.

the depth first traversal method DFS that prints each visited vertex, as discussed in class.

the method printIndegrees which prints the indegree of each vertex in the graph.

Note that in the code provided, the adjacency matrix is an 2-dimensional array of booleans where false means 0, and true means 1.

The output of your program should look like the following (in fact, this is the output for test file graph1.txt):

COMP 2140 Directed graph practice question,

Winter 2018 In-degrees of all vertices:

Vertex 0 has in-degree 2

Vertex 1 has in-degree 1

Vertex 2 has in-degree 1

Vertex 3 has in-degree 2

Vertex 4 has in-degree 2

Vertices visited starting from 0

0

1

2

4

3

Program completed normally.

Lab5.java

/************************************************

* Adjacency matrix representation of a graph *

* *

************************************************/

import java.io.*;

import java.util.*;

import javax.swing.*;

public class lab5 {

public static void main( String[] args )

{

GraphAM G; // Directed graph

int numVertices; // Number of vertices in G

JFileChooser pickFile = new JFileChooser(); // Dialog box to pick

// input file.

FileReader theFile; // The file to be read (character file).

BufferedReader in; // Read text from a character-input stream.

String inLine; // A line of input from BufferedReader in.

String token; // The next element from a line of input.

StringTokenizer tokens; // To get the elements from a line of input.

int from; // The vertex FROM which an edge goes out.

int to; // The vertex TO which an edge goes.

G = null;

System.out.println( "COMP 2140 Directed graph practice question, Winter 2018" );

System.out.println( );

// First, read in the directed graph.

try

{

// Retrieve the file to be read.

if (pickFile.showOpenDialog(null) == JFileChooser.APPROVE_OPTION)

{

theFile = new FileReader( pickFile.getSelectedFile() );

in = new BufferedReader( theFile );

// First line contains the number of vertices in the graph.

inLine = in.readLine();

tokens = new StringTokenizer( inLine );

numVertices = Integer.parseInt( tokens.nextToken() );

// Create a directed graph with numVertices vertices and no edges.

G = new GraphAM( numVertices );

// Each following line contains an edge from vertex "from" to

// vertex "to".

inLine = in.readLine();

while (inLine != null)

{

// Another edge.

tokens = new StringTokenizer( inLine );

from = Integer.parseInt( tokens.nextToken() );

to = Integer.parseInt( tokens.nextToken() );

G.addEdge( from, to );

// Read in next edge (if one exists).

inLine = in.readLine();

} // end while (inLine != null)

in.close();

} // end if pickFile.showOpenDialog()

} // end try

catch (IOException ex)

{

System.out.println( "I/O error: " + ex.getMessage() );

}

// Now, print the in-degree of every vertex.

G.printIndegrees( );

// Finally, print the vertices you visit on

// a depth-first search starting from vertex 0.

G.printInTraversal( 0 );

System.out.println();

System.out.println( "Program completed normally." );

System.exit(0);

} // end method main

}

//Representation of graph using adjacency matrix

class GraphAM

{

private boolean[][] adjacent; // Adjacency matrix

private int numVertices; // Number of vertices in the graph

// (number of rows and columns in the matrix).

private boolean[] visited; // For traversals.

/*******************************************************************

* GraphAM constructor *

* *

* Purpose: Construct a graph with nVert vertices and no edges. *

*******************************************************************/

public GraphAM( int nVert )

{

int i, j; // for-loop indices to loop through vertices.

numVertices = nVert;

// Create adjacency matrix "adjacent" and initiallize it

// to have no edges.

adjacent = new boolean[numVertices][numVertices];

for (i= 0; i < numVertices; i++)

{

for (j=0; j < numVertices; j++)

{

// No edge from vertex i to vertex j.

adjacent[i][j] = false;

}

}

visited = new boolean[ numVertices ];

// Every traversal will have to initiallize visited,

// so we won't do it here.

} // end GraphAM constructor

/*********************************************************************

* addEdge *

* *

* Purpose: Add an edge from vertex "from" to vertex "to". *

*********************************************************************/

public void addEdge( int from, int to )

{

if (0 <= from && from < numVertices)

{

if (0 <= to && to < numVertices)

adjacent[from][to] = true;

else

System.out.println( "Error: Can't add an edge to vertex " + to

+ " when graph only contains " + numVertices

+ " vertices." );

}

else

System.out.println( "Error: Can't add an edge from vertex " + from

+ " when graph only contains " + numVertices

+ " vertices." );

} // end method addEdge

/******************************************************************

* printIndegrees *

* *

* Purpose: Print the in-degree of every vertex in the graph. *

******************************************************************/

public void printIndegrees()

{

//put your code here

} // end method printIndegrees

/******************************************************************

* printInTraversal *

* *

* Purpose: Print the vertices visited in depth-first traversal *

* starting at vertex startVertex. *

* - print out a header for the vertices *

* - initiallize the visited array to all false *

* - call the recursive traversal method, which prints *

* out each vertex it visits on a separate line. *

******************************************************************/

public void printInTraversal( int startVertex )

{

int i;

System.out.println();

System.out.println( "Vertices visited starting from " + startVertex );

System.out.println();

for ( i = 0; i < numVertices; i++ )

visited[i] = false;

DFS( startVertex); //do depth first traversal.

} // end method PrintInTraversal

/******************************************************************

* DFS *

* *

* Purpose: Do a recursive depth-first traversal, printing each *

* vertex as you visit it, starting at vertex startVertex.*

* *

******************************************************************/

private void DFS( int currVertex )

{

//put your code here

} // end method recursiveTraversal

} // end class GraphAM

graph.txt

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