Graphs in Java

The prerequisite of this article is an Introduction To Graph. Please go through that article first before proceeding with this one.

Let's do a quick recap about graphs,

A graph is a data structure for storing connected data, such as a network of people. Data is stored in the form of vertices, which are connected by edges. Edges show relationships between two vertices.

In this article, we will dive into the representations of graphs in Java. We will see some very popular types of graphs, like directed, undirected, and weighted graphs, and their representations in Java.

Graph Representations

A graph can be represented using adjacency metrics or adjacency lists. In terms of setup, both forms of representation have advantages and disadvantages.?

Let's understand this representation more in detail,

Adjacency Metrics

An adjacency metric M is a square metric to represent a graph G=(V, E) with dimension (VxV) of vertices. M[Vi][Vj] is 1 if there is an adjacency (edge) between vertices Vi and Vj otherwise 0.

Let's represent the above graph into adjacency metrics,

The above is the representation of the undirected graph. A few interesting things to note in metric are if the graph does not have any self-loop then the diagonal of metric has zeros only. A metric of an undirected graph is always symmetric. A metric is symmetric when its transpose is equal to itself. Transpose of a metric A means when we convert all rows to columns and columns to rows.

In java implementation of adjacency metric will be straight forward like mentioned above a 2d array of 1's and 0's.

private static final int [][] graph = 
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 0, 0, 1},
        {0, 0, 1, 1, 0}
};        

This implementation is easy to implement and fairly simple and fast to query, but less efficient in terms of space occupied.

Adjacency List

An adjacency list is nothing but an array or map of lists. Where the size of the array or map is equal to the number of vertices. Index of an array or in the case of a map, the key represents the vertex and the value represents the list of all of the vertices to which the key is connected.

Let's see what the adjacency list for our above-mentioned graph looks like,

Adjacency lists are comparatively difficult to create and less efficient to query, although we can improve query by using proper data structures, but it is more efficient in space.

Here is a basic implementation of a graph using an adjacency list in Java.

private static final Map<Vertex, List<Vertex>> graph = new HashMap<>();        

Graphs in Java

Java does not have a default implementation of graphs; however, we can create graphs using Java classes and the collection framework. Let's use an adjacency list to create a custom graph in Java.

Let's create a Vertex class that will be generic and used to store data.

class Vertex<T> {

    private T data;

    public Vertex(T data) {
        this.data = data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Vertex<?> vertex = (Vertex<?>) o;
        return Objects.equals(data, vertex.data);
    }

    @Override
    public int hashCode() {
        return Objects.hash(data);
    }

    @Override
    public String toString() {
        return ""+data;
    }
}        

The above is a representation of vertices. It's a generic class that can be used to store any sort of data in it. With vertex, we can store names, numbers, or any other type of data. We also override hashCode and equals methods in our class to work with HashMaps?in the Java collection framework.

As we discussed earlier in the adjacency list, we represent vertices with a list or map of lists of vertices against a vertex. That list represents the vertices connected to a particular vertex.

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph<T> {
    private Map<Vertex<T>, List<Vertex<T>>> graph = new HashMap<>();
}        

To represent an adjacency list, we use a map from the Java Collection Framework, where the key of the map represents a vertex and the value of that key shows all edges to other vertices. A graph can have several read and mutation operations, like reading, updating, searching, and deleting.

We'll go over some of the most common graphing operations.?

Graph Mutation Operations

Mutation means to add, remove, or update operations. To start with we will define some mutation methods for graphs.

Let's define a method to add and remove vertices in our graph,

public void addVertex(T t) {
    graph.putIfAbsent(new Vertex<>(t), new ArrayList<>());
}

public void removeVertex(T t) {
    Vertex<T> vertex = new Vertex<>(t);
    graph.remove(vertex);
    graph.values().forEach(values -> values.remove(vertex));
}        

The above method will be used to add and remove vertices. If a generic value does not already exist in our graph map, the user can add it using the addVertex method. RemoveVertex requires us to remove vertices in two places: the graph itself and wherever that vertex is linked.?It means we must first remove the vertex key from the map to remove all of the edges of that vertex, and then we must go through all other edges and remove that vertex if it is linked somewhere else.

Let's define another method to add edges to our graph.

public void addEdge(T t1, T t2) {
    Vertex<T> vertex1 = new Vertex<>(t1);
    Vertex<T> vertex2 = new Vertex<>(t2);

    Optional.ofNullable(graph.get(vertex1))
            .orElseThrow()
            .add(vertex2);

    Optional.ofNullable(graph.get(vertex2))
            .orElseThrow()
            .add(vertex1);
}        

Using the addEdge method, we can add edges between two vertices. This method will ensure that a vertex exists in our graphs, otherwise, it will throw a NoSuchElementException.

We will implement another method for deleting edges, similar to addEdge.

public void removeEdge(T t1, T t2) { 
    Vertex<T> vertex1 = new Vertex<>(t1);
    Vertex<T> vertex2 = new Vertex<>(t2);

    Optional.ofNullable(graph.get(vertex1))
            .orElseThrow()
            .remove(vertex2);

    Optional.ofNullable(graph.get(vertex2))
            .orElseThrow()
            .remove(vertex1);
}        

lastly, we will create a method to get adjacent vertices against a particular vertex.

public List<Vertex<T>> getAdjVertices(T t) {
    return graph.get(new Vertex<>(t));
}        

Now let's add vertices from our defined diagram of the graph to our newly created data structure.

public static void main(String[] args) {
    Graph<String> graph = new Graph<>();
    graph.addVertex("Zoli");
    graph.addVertex("Alex");
    graph.addVertex("Steph");
    graph.addVertex("Bob");
    graph.addVertex("Mark");
    graph.addEdge("Zoli", "Steph");
    graph.addEdge("Zoli", "Alex");
    graph.addEdge("Alex", "Zoli");
    graph.addEdge("Alex", "Steph");
    graph.addEdge("Alex", "Mark");
    graph.addEdge("Steph", "Zoli");
    graph.addEdge("Steph", "Alex");
    graph.addEdge("Steph", "Bob");
    graph.addEdge("Mark", "Alex");
    graph.addEdge("Mark", "Bob");
    graph.addEdge("Bob", "Mark");
    graph.addEdge("Bob", "Steph");
}        

Let's print some of the vertices and edges associated with it.

System.out.println(graph.getAdjVertices("Zoli"));

// Result

[Steph, Alex]        

Traversing a Graph

After defining the graph above, we now need to comprehend how to traverse it. To achieve this, we may use either the depth-first search method or the breath-first search method.

Depth-First Traversal

A?depth-first?traversal?begins?with?the?supplied?root?and?probes?as?many deeper?vertices?as?it?can?before?reading?vertices?on?the?same?level.

Let's have a look at how we can define depth-first traversal in Java.

public Set<T> depthFirstTraversal(T root) {
    if(!this.graph.containsKey(new Vertex<>(root))) {
        throw new NoSuchElementException("Root vertex not found for {"+ root+ "}");
    }

    Set<T> visited = new LinkedHashSet<>();
    Stack<T> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        T vertex = stack.pop();
        if(!visited.contains(vertex)) {
            visited.add(vertex);
            for(Vertex<T> v : getAdjVertices(vertex)) {
                stack.push(v.getData());
            }
        }
    }

    return visited;
}        

The output for the above graph will be [Zoli, Alex, Mark, Bob, Steph] for root Zoli. We used the stack to record vertices and set it to track is a particular vertex is visited. The purpose of using stack is to have last-in and first-out behaviour. The adjacent vertex which will be pushed in last will be taken out first and we will go further down to its adjacent vertices.

Breadth-First Traversal

Breath-first, as contrast to depth-first, begins with a particular root and travels over all of its neighbouring vertices on the same level before descending.

Let's create a method to perform breadth-first traversal,

public Set<T> breadthFirstTraversal(T root) { 
    if(!this.graph.containsKey(new Vertex<>(root))) {
        throw new NoSuchElementException("Root vertex not found for {"+ root+ "}");
    }

    Set<T> visited = new LinkedHashSet<>();
    Queue<T> queue = new LinkedList<>();
    queue.add(root);
    visited.add(root);
    while(!queue.isEmpty()) {
        T node = queue.poll();
        for(Vertex<T> v : getAdjVertices(node)) {
            if(!visited.contains(v.getData())) {
                visited.add(v.getData());
                queue.add(v.getData());
            }
        }
    }
    return visited;
}        

The output for the above graph will be [Zoli, Steph, Alex, Bob, Mark] for root Zoli. Instead of travelling all the way down to neighbouring vertices, we utilised a queue to record vertices, so we recorded all of the vertices on the same level first. Each vertex will be added to a queue, retrieved first on first serve, and level order traversal repeated.

Conclusion

We explored the graph as a data structure and its representations in this article. Using Java Collections, we created a very basic graph and specified common traversals for it. We also go over adjacency arrays and lists for representing graphs, as well as their advantages and disadvantages.?I hope you understand those concepts and have a good reading day!!.