Objectives:

1. To understand the implementation of:

· Topological sort algorithm

· Cycle detection algorithm and

· Connectedness and Strong connectedness algorithms.

To implement an algorithm that tests for weak connectedness.
To implement an algorithm that counts the number of connected components in a graph.
To understand the implementation of:

· Dijkstra’s shortest-path algorithm

· Prim’s Algorithm for finding minimum-cost spanning tree and

· Kruskal’s Algorithm for finding minimum-cost spanning tree.

1. Downloadables:

Download lab11.zip and unzip it under the ics202 package.

After unzipping, the following files will be added to the ics202 package:

Algorithms.java

You will also find the following files in the ics202.lab11 sub-package.

TestGraphAlgorithms.java.

graph1.txt

graph2.txt

graph3.txt

graph4.txt

2. Task1

Study the CountingVisitor class in the ics202 packege. You will notice that it is simply counting the number of objects it visits. This number can be accessed using the getCount( ) method.

Study the following AbstractGraph methods: topologicalOrderTraversal, isConnected, isStronglyConnected and isCyclic to make sure you understand what each of them is doing.

Also study and understand the test class, TestGraphAlgorithms.java in lab11

3. Task2

Find (manually) the topological order traversal of the following graph.

The text file, graph1.txt, contains information about the above graph. Run the TestGraphAlgorithms class using this file to verify what you get manually above.

4. Task3

(a) Write an instance method public Graph getUndirected() of the AbstractGraph class that returns the current graph if the invoking object is undirected; otherwise it returns the undirected graph obtained by ignoring the direction of the edges in the current graph. Hint: You need to create a new undirected instance of the invoking graph, add all the vertices of the current graph to it, add all the edges and their opposites to it and return it. (Note: The process of adding opposite edges is automatically done by the addEdge method if the graph is undirected).

(b) Complete the instance method public boolean isWeaklyConnected() of the AbstractGraph class such that it returns true if the

current Digraph is weakly connected and false otherwise. Hint: You only need to get the underlying undirected graph using

the getUndirected method and check for its connectedness.

Test the methods topologicalOrderTraversal, isConnected, isStronglyConnected, isCyclic and isWeaklyConnected by running

the TestGraphAlgorithms program on both graph1 above and graph2 below (represented in the text file, graph2.txt )

(c) Write an instance method public int countConnectedComponents( ) in the AbstractGraph class that counts the number of connected components of the invoking graph. Hint: The number of connected components of a graph is the number of traversals required to visit all the vertices in the underlying undirected graph.

Represent the graph below in a text-file and then use it to test your program:

5. Task4

Study each of the following algorithms in the Algorithms class:

·         Dijkstra’s shortest-path algorithm.

·         Prim’s Algorithm for finding minimum-cost spanning tree

·         Kruskal’s Algorithm for finding minimum-cost spanning tree

Use the following graph to trace the Dijkstra’s algorithm manually.

The graph above is represented in the text file, graph3.txt. Run the TestGraphAlgorithms class using this file to verify your manual tracing.

Use the following graph to trace the Prim’s algorithm and the Kruskal’s Dijkstra’s algorithm manually.

The graph above is represented in the text file, graph4.txt. Run the TestGraphAlgorithms class using this file to verify your manual tracing.