INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS 202: DATA STRUCTURES

LAB#10 : Implementation of Graphs

Objectives:

1. To understand the implementation of GraphAsArrayLists (Adjacency Lists).
2. To implement purge, addEdge, getEdges methods of GraphAsArrayLists.
3.       To test  implementation by creating a graph instance and traversing it using both depth-first and breadth-first traversal methods.
4.       To implement the method isEmanatingEdgeMate(String label1, String label2) and hasDistinctEdgeWeights( ) of the GraphAsArrayLists class.

Classes and Interfaces needed for the Implementation

The following figure shows how the interfaces and classes needed for the implementation of graphs are related:

1.  Downloadables:

Download lab10.zip and unzip it under the ics202 main folder.

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

             Edge.java

             Vertex.java

             Graph.java 

             AbstractGraph.java

             GraphAsLists.java

             GraphAsArrayLists.java

              GraphAsMatrix.java

               CountingVisitor.java

     The following files will be placed in a package ics202.lab10:

             TestGraph.java

             GraphData.txt

2.      Task1

Study each of the files added to ics202 package as listed above (except CountingVisitor. This will be used in lab11) and make sure you understand what each of them is doing.  You will notice that the classes, GraphVertex and GraphEdge are implemented as inner classes inside the AbstractGraph class, since edges and vertices can only exist in the context of a graph.

Note that the vertices are numbered by array indexes, starting from 0.

3.      Task2

Complete the implementation of GraphAsArrayLists by implementing each of the following methods:

(i)       The purge( ) method that purges the invoking graph.

(ii)       The addEdge(String from, String to, Comparable weight) method that adds an edge to the invoking graph.

(iii)       The getEdges( ) method that returns an Iterator of all edges in the invoking graph.

4.      Task3

The text file GraphData.txt represents the information about the undirected graph shown below.  The first line shows the number of vertices in the graph, the next six lines are the vertex labels, and the rest of the lines represent the edges.  Open this file and study it together with the following graph to make sure you understand how the graph data is stored in the file. Note the vetex labels below are strings and not integers:

The program GraphTest.java reads the data in the GraphData.txt file and uses the data to create an undirected  instance of a GraphAsArrayLists.  The program then prints the graph and the result of depth-first traversals and breadth-first traversal of the graph.

Compile and run the program. You should get the following output:

How does the output compare with what you will get if you do the traversals manually?

5.      Task4

(i)       Write an instance method public boolean isEmanatingEdgeMate(String label1, String label2) of the GraphAsArrayLists class that returns true if the invoking object has a vertex with label1 that has an emanating edge with the vertex with label2 as a mate; otherwise it returns false. Represent the following graph in a text-file and use it to test your method:

(ii)      Write an instance method public boolean hasDistinctEdgeWeights( ) of the GraphAsArrayLists class that returns true if the invoking weighted, directed graph has edges that have distinct weights; otherwise it returns false. 

            Hint: Use a MySearchableContainer.

         Represent each of the following graphs in a text-file and then use each one to test your method: