Using HashMaps, it is easy to implement the adjacency list in Java. In our implementation of the graph abstract data type, we will create two classes: Vertex, which will represent each vertex in the graph (see Listing 7.6.1), and Graph, which holds the master list of vertices (see Listing 7.6.3).
Each Vertex uses a HashMap to keep track of the vertices to which it is connected and the weight of each edge. This map is called neighbors. The listing below shows the code for the Vertex class. The constructor initializes the key, which will typically be a string, and the neighbors HashMap. The setNeighbor method is used to add a connection from this vertex to another. The getNeighbors method returns all of the vertices in the adjacency list, as represented by the neighbors instance variable. The getNeighbor method returns the weight of the edge from this vertex to the vertex passed as a parameter.
We not only want to make sure that the data type of a key can be compared (line 4); we also want to make sure that we can compare vertices to each other (line 5) in some of the algorithms for this chapter. This requires us to implement a compareTo method (lines 68–70). It returns the result of comparing the keys; a negative number if this.key is less than other.key, zero if they are equal, and positive if this.key is greater than other.key.
In line 41, we return the neighbors as a Java Set. A set has the property that there are no duplicate elements. Sets are iterable, which means that we can use an extended for loop to examine all of a vertex’s neighbors. Using a Set also frees us from having to construct an Iterator class and implement the next and hasNext methods, as we had to do for the BinarySearchTree in Section 6.14.
The Graph class, shown in the following listing, contains a HashMap that maps vertex names to vertex objects. In Section 7.5 this HashMap is represented by the shaded gray box. Graph also provides methods for adding vertices to a graph and connecting one vertex to another. The getVertices method returns the names of all of the vertices in the graph. In addition, we have implemented the __iter__ method to make it easy to iterate over all the vertex objects in a particular graph. Together, the two methods allow you to iterate over the vertices in a graph by name, or by the objects themselves.
Using the Graph and Vertex classes just defined, the following program creates the graph in Section 7.2. First we create six vertices numbered 0 through 5. Then we display the vertex HashMap. Notice that for each key 0 through 5 we have created an instance of a Vertex. Next, we add the edges that connect the vertices together. Finally, loop verifies that each edge in the graph is properly stored. You should check the output of the edge list at the end of this session against the graph shown in Section 7.2.
Here is its output:
0 connected to: 5, 1
1 connected to: 2
2 connected to: 3
3 connected to: 4, 5
4 connected to: 0
5 connected to: 4, 2