In Lecture 4 one of the standard data structures for representing Undirected Graphs was presented.
One weakness of the technique used, is that a 2-dimensional array is not an efficient way to hold details about graphs which do not have `many' edges, (so-called sparse graphs),
In order to overcome some of the problems with the adjacency matrix representation (as the technique used in Lecture 4 is known), an alternative approach (called incidence list representation) can be used.
For the graph,
The adjacency matrix (2-D array) form would be:
1 | 2 | 3 | 4 | 5 | |
1 | 0 | 0 | 1 | 1 | |
2 | 1 | 1 | 1 | ||
3 | 1 | 1 | |||
4 | 0 |
whereas the incidence list form would be:
So if G(V,E) is an n-vertex undirected graph with vertex set
The incidence list representation of G(V,E) uses:
An array of n-1 Linked Lists.
(One linked list for each of the vertices v such that 1< = v < n.)
The linked list for vertex k has one list cell for each vertex, w for which:
(if there are no such edges the corresponding linked list is empty).
Design, implement and test a Java Class, SparseGraph, whose Class Diagram is
Class Fields
Incidence is an array of EdgeList that will hold the Graph. The class EdgeList is the Linked List Class described in Lecture 6, but changed so that a List cell has two fields (as before):
int Node
ListCell Link
i.e. The data held in an EdgeList is always of type int rather than an arbitrary Object class.
You do not have to implement the class EdgeList.
An implementation of this can found obtained here.
Records the number of vertices in this SparseGraph instance. Hence Incidence[] when instantiated will be an array of Order-1 EdgeLists.
Records the number of edges in this SparseGraph instance.
Constructors
The parameter n defines the number of vertices in this instance. The fields should be instantiated so that Order is set to n; Size to 0; and Incidence as an array of n-1 new instances of EdgeList.
n is the number of vertices in this instance (so Order=n)
Mat is assumed to be 2-dimensional array with n rows and n columns; the field Incidence is instantiated to represent the undirected n-vertex graph that Mat describes as follows:
(N.B. Mat[][] is just an adjacency matrix representation of some Graph)
The SparseGraph instance formed by this constructor should correspond to the incidence list representation of the graph whose adjacency matrix is Mat.
Returns the value of the field Order for this instance.
Returns the value of the field Size for this instance.
Returns true if there is an edge between the vertices v and w in this SparseGraph instance.
Add an edge connecting vertices v and w.
Remove any edge connecting vertices v and w.
Return a String representing this instance. The String should consist of the contents each EdgeList (using the toString() instance method of that class) each list being separated by newline (i.e. "\n" characters).
You should hand in to your Group Tutor:
that will read a sequence of digits (stopping at a `whitespace' character) and return the integer value that has been read.
0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0
Your completed work should be handed in to your group tutor at your practical class on Thursday 24th February