DS Implementation

Section 7.6 Implementation

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.

import java.util.HashMap;
import java.util.Set;

class Vertex<T extends Comparable<T>>
    implements Comparable<Vertex<T>> {

    T key;
    HashMap<Vertex<T>, Integer> neighbors;

    Vertex(T key) {
        this.key = key;
        this.neighbors = new HashMap<Vertex<T>, Integer>();
    }

    /*
     * Get the weight of the edge from this vertex
     * to the other vertex. Returns null if there is no
     * connection to the other vertex.
     */
    Integer getNeighbor(Vertex<T> other) {
        return neighbors.get(other);
    }

    /*
     * Set a connection from this vertex to the other
     * vertex with a weight of zero
     */
    void setNeighbor(Vertex<T> other) {
        setNeighbor(other, 0);
    }

    /*
     * Set a connection from this vertex to the other
     * vertex with the given weight
     */
    void setNeighbor(Vertex<T> other, Integer weight) {
        neighbors.put(other, weight);
    }

    /*
     * Return a Set of the neighbor vertices.
     */
    Set<Vertex<T>> getNeighbors() {
        return neighbors.keySet();
    }

    /*
     * Return the key for this vertex.
     */
    T getKey() {
        return key;
    }

    public String toString() {
        String result = this.key.toString();
        if (neighbors.size() > 0) {
            result = result + " connected to: ";
            for (Vertex<T> vertex: this.getNeighbors()) {
                result = result + vertex.key + ", ";
            }
            result = result.substring(0, result.length() - 2);
        } else {
            result = result + " has no connections";
        }
        return result;
    }

    public int compareTo(Vertex<T> other) {
        return this.key.compareTo(other.key);
    }

}

Listing 7.6.1. The Vertex Class

Note 7.6.2. Java Notes.

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.

import java.util.HashMap;
import java.util.Set;

class Graph<T> {
    HashMap<T, Vertex<T>> vertices;

    public Graph() {
        this.vertices = new HashMap<T, Vertex<T>>();
    }

    public void setVertex(T key) {
        vertices.put(key, new Vertex<T>(key));
    }

    public Vertex<T> getVertex(T key) {
        return vertices.get(key);
    }

    public boolean containsVertex(T key) {
        return vertices.containsKey(key);
    }

    public void addEdge(T fromVertex, T toVertex) {
        addEdge(fromVertex, toVertex, 0);
    }

    public void addEdge(T fromVertex, T toVertex,
        Integer weight) {
        if (!vertices.containsKey(fromVertex)) {
            setVertex(fromVertex);
        }
        if (!vertices.containsKey(toVertex)) {
            setVertex(toVertex);
        }
        Vertex<T> from = vertices.get(fromVertex);
        Vertex<T> to = vertices.get(toVertex);
        from.setNeighbor(to, weight);
    }

    public HashMap<T, Vertex<T>> getVertices() {
        return this.vertices;
    }

    public Set<T> getVertexKeys() {
        return this.vertices.keySet();
    }
}

Listing 7.6.3.

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.

import java.util.Comparator;
import java.util.HashMap;
import java.util.Set;
import java.util.ArrayList;
import java.util.NoSuchElementException;

class Graph<T extends Comparable<T>> {
    
    HashMap<T, Vertex<T>> vertices;
    
    public Graph() {
        this.vertices = new HashMap<T, Vertex<T>>();
    }

public void setVertex(T key) {
        Vertex<T> v = new Vertex<T>(key);
        vertices.put(key, v);
    }
    
    public Vertex<T> getVertex(T key) {
        return vertices.get(key);
    }

public boolean containsVertex(T key) {
        return vertices.containsKey(key);
    }
    
    public void addEdge(T fromVertex, T toVertex) {
        addEdge(fromVertex, toVertex, 0);
    }
    
    public void addEdge(T fromVertex, T toVertex,
        Integer weight) {
        if (!vertices.containsKey(fromVertex)) {
            setVertex(fromVertex);
        }
        if (!vertices.containsKey(toVertex)) {
            setVertex(toVertex);
        }
        Vertex<T> from = vertices.get(fromVertex);
        Vertex<T> to = vertices.get(toVertex);
        from.setNeighbor(to, weight);
    }
    
    public HashMap<T, Vertex<T>> getVertices() {
        return this.vertices;
    }
    
    public ArrayList<Vertex<T>> getVertexList() {
        ArrayList<Vertex<T>> result = new ArrayList<>();
        for (T key: vertices.keySet()) {
            result.add(vertices.get(key));
        }
        return result;
    }
    
    public Set<T> getVertexKeys() {
        return this.vertices.keySet();
    }
    
    public void bfs(Vertex<T> start) {
        start.color = VertexColor.GRAY;
        start.distance = 0;
        start.previous = null;
        
        Queue<Vertex<T>> vertexQueue = new Queue<>();
        vertexQueue.enqueue(start);
        while (vertexQueue.size() > 0) {
            Vertex<T> current = vertexQueue.dequeue();
            for (Vertex<T> neighbor: current.getNeighbors()) {
                if (neighbor.color == VertexColor.WHITE) {
                    neighbor.color = VertexColor.GRAY;
                    neighbor.distance = current.distance + 1;
                    neighbor.previous = current;
                    vertexQueue.enqueue(neighbor);
                }
            }
                    
            current.color = VertexColor.BLACK;
        }
    }
}

class Vertex<T extends Comparable<T>>
    implements Comparable<Vertex<T>> {
    
    T key;
    HashMap<Vertex<T>, Integer> neighbors;
    
    int distance;
    Vertex<T> previous;
    VertexColor color;
    
    int discoveryTime;
    int closingTime;
    
    public Vertex(T key) {
        this.key = key;
        this.neighbors = new HashMap<Vertex<T>, Integer>();
        this.distance = 0;
        this.previous = null;
        this.color = VertexColor.WHITE;
        this.discoveryTime = 0;
        this.closingTime = 0;
    }

/*
     * Get the weight of the edge from this vertex
     * to the other vertex. Returns null if there is no
     * connection to the other vertex.
     */
    Integer getNeighbor(Vertex<T> other) {
        return neighbors.get(other);
    }
    
    /*
     * Set a connection from this vertex to the other
     * vertex with a weight of zero
     */
    void setNeighbor(Vertex<T> other) {
        setNeighbor(other, 0);
    }
    
    /*
     * Set a connection from this vertex to the other
     * vertex with the given weight
     */
    void setNeighbor(Vertex<T> other, Integer weight) {
        neighbors.put(other, weight);
    }
    
    /*
     * Return a Set of the neighbor vertices.
     */
    Set<Vertex<T>> getNeighbors() {
        return neighbors.keySet();
    }

/*
     * Return the key for this vertex.
     */
    T getKey() {
        return key;
    }
    
    public Vertex<T> getPrevious() {
        return this.previous;
    }
    
    public void setPrevious(Vertex<T> v) {
        this.previous = v;
    }
    
    
    public VertexColor getColor() {
        return this.color;
    }
    
    public void setColor(VertexColor color) {
        this.color = color;
    }
    
    public String toString() {
        String result = this.key.toString();
        if (neighbors.size() > 0) {
            result = result + " connected to: ";
            for (Vertex<T> vertex: this.getNeighbors()) {
                result = result + vertex.key + ", ";
            }
            result = result.substring(0, result.length() - 2);
        } else {
            result = result + " has no connections";
        }
        return result;
    }
    
    public int compareTo(Vertex<T> other) {
        return this.key.compareTo(other.key);
    }

static class ByDiscoveryTime implements Comparator<Vertex> {
        public int compare(Vertex a, Vertex b) {
            return a.discoveryTime - b.discoveryTime;
        }
    }

static class ByClosingTime implements Comparator<Vertex> {
        public int compare(Vertex a, Vertex b) {
            return a.closingTime - b.closingTime;
        }
    }
}

class Queue<T> {

ArrayList<T> items;

public Queue() {
        this.items = new ArrayList<T>();
    }

public boolean isEmpty() {
        return (this.items.isEmpty());
    }

public void enqueue(T item) {
        this.items.add(0, item);
    }

public T dequeue() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return this.items.remove(this.size() - 1);
    }

public T peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return this.items.get(this.size() - 1);
    }

public int size() {
        return this.items.size();
    }

public String toString() {

if (!this.items.isEmpty()) {
            String arrString = this.items.toString();
            return "tail ->" + arrString + "-> head";
        } else {
            return "<<empty queue>>";
        }
    }
}

enum VertexColor {
    WHITE, GRAY, BLACK
}

^^^^
public class TestGraph {
    public static void main(String[] args) {
        Graph<Integer> g = new Graph<>();
        for (int i = 0; i < 6; i++) {
            g.setVertex(i);
        }
        g.addEdge(0, 1, 5);
        g.addEdge(0, 5, 2);
        g.addEdge(1, 2, 4);
        g.addEdge(2, 3, 9);
        g.addEdge(3, 4, 7);
        g.addEdge(3, 5, 3);
        g.addEdge(4, 0, 1);
        g.addEdge(5, 4, 8);
        g.addEdge(5, 2, 1);

for (Integer key: g.getVertexKeys()) {
            System.out.println(g.getVertex(key));
        }
    }
}

Listing 7.6.4. Testing the Graph Class

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

You have attempted of activities on this page.

Prev Top Next