INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM
ICS 202: DATA STRUCTURES
LAB#10 : Implementation of Graphs
Download lab10.zip and
unzip it under the ics202 main folder.
After unzipping, the following files will be added to the ics202 package:
The following files will be placed in a package ics202.lab10:
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.
Complete the implementation of GraphAsArrayLists by implementing each of the following methods:
The purge( ) method that purges the invoking graph.
The addEdge(String from, String to, Comparable weight) method that adds an edge to the invoking graph.
The getEdges( ) method that returns an Iterator of all edges in the invoking graph.
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:
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
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?
(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: