Core Java

# Java Graph Example

In this example, we will demonstrate a Java Graph Example. We will start by explaining the theory and concepts behind graphs, its types, graph traversal, as well as the benefits and drawbacks of using a graph. We will walk through Java code that implements a Graph and models its properties and behavior. Finally, we will talk about some external libraries that can be used to implement a graph.

## 1. Introduction

Graph theory is a popular area of study in the field of mathematics. It has found its use in various physical sciences such as chemistry, biology, as well as computer science. The study of algorithms and data structures would be incomplete without a mention of graphs. In this article, we will define a graph through the eyes of Object Oriented Programming and with the help of data structures within the Java Collections framework such as a `List`, `Map` and `Set`.

## 2. What is a graph?

From the perspective of object-oriented programming, a graph is a data type that consists of a set of vertices(or nodes) and edges. A graph has a finite set of vertices and edges. In the figure below that represents a server architecture, vertices are represented by the blue circles, and the relationship between the vertices are represented by the edges.

In the above graph of a sample server architecture, there are 12 nodes and 12 edges. Each node represents an object type, which in this case is the server configuration. When a request to fetch an HTML file comes to the web server, we can see how the edges help us to follow the path from the topmost vertex to the vertices at the bottom.

## 3. Types of graphs

Graphs are classified based on the properties of their edges, and how they link to the vertices. We will cover the most common classifications of graphs.

### 3.1 Directed graphs

The edges that connect the vertices of the graph may be directed or undirected. Fig. 1 shows a directed graph, where edges capture the start and end node. This is in contrast with an undirected graph, where the information about the direction of edges is not stored. In Fig 2 below, we see an example of an undirected graph of a home network.

### 3.2 Weighted graph

Each edge of a graph can be associated with a value that represents the weight of the edge. This property can be especially useful to determine the optimal path while traversing a graph. For example, in a graph that represents network connections, a weight can be associated to determine the strength of the network cable connection.

### 3.3 Cyclic graph

An acyclic graph is a directed graph, where at least one vertex ends up having a connection or relation with itself.

## 4. Graph Representation

There are several ways to represent a graph data type. The differences arise in the data structures used to implement the set of vertices and edges. We will see 2 most common types of graph representations.

In this type of graph representation, a matrix is used to define the vertices and edges. The relationship between vertices is indicated by 1’s and 0’s. In Table 1 below, we see an adjacency matrix that represents the home network graph in Fig 2. Since the node labeled “Base station” is connected to the node “Home network”, there is a 1 in the cell corresponding to them.

An adjacency list is a different data structure used to represent the list of adjacent vertices in a graph. We can imagine this to be a `Map` with key/value pairs. The keys represent the vertices, and the values are a list of adjacent vertices. In Fig 3, we see the node representing “Home network” has a value that is a list of the vertices it is connected to.

## 5. Custom Graph class

In this section, we will see the implementation of a graph. We will use the directed graph in Fig 1 as an example and use the adjacency list implementation for this graph.

### 5.1 Tools used

The coding examples in this article were built and run with the following tools:

1. Java 11
2. Maven 3.6.0
3. Junit 4.13
4. Intellij Idea Edu 2020.1

### 5.2 Maven Project

In this section, we will create a Maven project to implement a custom Graph class. As a first step, we will review the `pom.xml` that contains `Junit`.pom.xml

```<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>jcg.ssowmya.demo</groupId>
<artifactId>graphExample</artifactId>
<version>1.0-SNAPSHOT</version>
<build>
<sourceDirectory>src</sourceDirectory>
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<version>3.8.0</version>
<configuration>
<release>11</release>
</configuration>
</plugin>
</plugins>
</build>
<dependencies>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.13</version>
</dependency>
</dependencies>

</project>
```

### 5.3 ServerConfig class

In this section, we will see the implementation of the ServerConfig class. This class will provide a way for each vertex of the graph in Fig 1 to hold more information than just the label.ServerConfig.java

```package jcg.ssowmya.demo.graphExample;

public class ServerConfig {
private String name;
private String serverType;

public ServerConfig(String name, String ipAddress, String serverType) {
this.name = name;
this.serverType = serverType;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

}

}

public String getServerType() {
return serverType;
}

public void setServerType(String serverType) {
this.serverType = serverType;
}

@Override
public String toString() {
return "ServerConfig{" +
"name='" + name + '\'' +
", serverType='" + serverType + '\'' +
'}';
}
}
```

### 5.4 ServerVertex class

In this section, we will implement a class to represent each vertex of the graph in Fig 1. As we can see in this implementation, the constructor takes in 2 parameters, one is the `label` and the other is an object of the `ServerConfig` class.ServerVertex.java

```package jcg.ssowmya.demo.graphExample;

import java.util.Objects;

public class ServerVertex {
private String label;
private ServerConfig serverConfig;

public ServerVertex(String label,ServerConfig serverConfig) {
this.label = label;
this.serverConfig = serverConfig;
}
public String getLabel() {
return label;
}

public void setLabel(String label) {
this.label = label;
}

public ServerConfig getServerConfig() {
return serverConfig;
}

public void setServerConfig(ServerConfig serverConfig) {
this.serverConfig = serverConfig;
}

@Override
public String toString() {
return "Vertex{" +
"label='" + label + '\'' +
", serverConfig=" + serverConfig +
'}';
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ServerVertex serverVertex = (ServerVertex) o;
return getServerConfig().equals(serverVertex.getServerConfig());
}

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

### 5.5 ServerEdge class

This class will be used to represent the edges of a graph. Since Fig 1 represents a directed graph, this class will have a start vertex, end vertex, an optional weight property.ServerEdge.java

```package jcg.ssowmya.demo.graphExample;

public class ServerEdge {

private ServerVertex start;
private ServerVertex end;
private float weight;

public ServerEdge(ServerVertex start, ServerVertex end) {
this.start = start;
this.end = end;
}

public ServerEdge(ServerVertex start, ServerVertex end, float weight) {
this.start = start;
this.end = end;
this.weight = weight;
}

public ServerVertex getStart() {
return start;
}

public void setStart(ServerVertex start) {
this.start = start;
}

public ServerVertex getEnd() {
return end;
}

public void setEnd(ServerVertex end) {
this.end = end;
}

public float getWeight() {
return weight;
}

public void setWeight(float weight) {
this.weight = weight;
}

@Override
public String toString() {
return "ServerEdge{" +
"start=" + start +
", end=" + end +
", weight=" + weight +
'}';
}
}
```

### 5.6 ServerGraph class

This class will combine objects of the above classes to implement a custom graph. This class will contain methods to add vertices and edges, as well as to remove them. Finally, the class has methods to perform 2 types of graph traversal, which we will be looking at in detail in the upcoming section.ServerGraph.java

```package jcg.ssowmya.demo.graphExample;

import java.util.*;

public class ServerGraph {
public ServerGraph() {
}
}

}
}
}
return;
if(!serverVertexOptional.isPresent())
return;
ServerVertex serverVertexToBeRemoved = serverVertexOptional.get();
serverVertexList.remove(serverVertexToBeRemoved);
});
}
}

public void removeEdge(ServerEdge edge) {
}

public List depthFirstTraversal(ServerVertex root) {
List visitedNodes = new ArrayList();
Stack serverVertexStack = new Stack();
serverVertexStack.push(root);
while(!serverVertexStack.isEmpty()) {
ServerVertex visitedElement = serverVertexStack.pop();
if(!visitedNodes.contains(visitedElement)) {
serverVertexStack.push(sv);
}
}
return visitedNodes;

}
List visitedNodes = new ArrayList();
while(!serverVertexQueue.isEmpty()) {
ServerVertex visitedElement = serverVertexQueue.poll();
if(!visitedNodes.contains(sv)) {
}
}
return visitedNodes;

}

@Override
public String toString() {
return "ServerGraph{" +
'}';
}
}
```

### 5.7 ServerGraphTest class

In this section, we will see a Junit test class to verify and validate our custom class `ServerGraph`.ServerGraphTest.java

```package jcg.ssowmya.demo.graphExample;

import org.junit.Test;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;

public class ServerGraphTest {

@Test
public void testGraphServerVertices() {
ServerGraph serverGraph = new ServerGraph();
serverGraph.addServerVertex(new ServerVertex("WS1:Web Server", new ServerConfig("JCG Web Server 1","1.2.3.4","Web")));
}

@Test
public void testGraphServerEdges() {
ServerGraph serverGraph = new ServerGraph();
ServerVertex wsVertex= new ServerVertex("WS1:Web Server",new ServerConfig("JCG Web Server 1","1.2.3.4","Web"));
serverGraph.removeEdge(new ServerEdge(wsVertex,lb1Vertex));
}
}
```

## 6. Graph Traversal

There are 2 ways in which a graph can be traversed: Breadth-first and Depth-first. We will understand with the help of code how they both differ.

### 6.1 ServerGraphTraversalTest class

In this section, we will implement a class that tests the 2 types of graph traversal methods.ServerGraphTest.java

```package jcg.ssowmya.demo.graphExample;

import org.junit.Before;
import org.junit.Test;

import java.util.List;

import static org.junit.Assert.assertNotNull;

public class ServerGraphTraversalTest {

private ServerGraph serverGraph;
private ServerVertex root;
@Before
public void initializeGraph() {
serverGraph = new ServerGraph();
ServerVertex wsVertex= new ServerVertex("WS1:Web Server",new ServerConfig("JCG Web Server 1","1.2.3.4","Web"));
ServerVertex ps1Vertex = new ServerVertex("PS1:Proxy Server Instance 1", new ServerConfig("Proxy Server Instance 1","1.2.3.7","Proxy Server"));
ServerVertex ps2Vertex = new ServerVertex("PS2:Proxy Server Instance 2", new ServerConfig("Proxy Server Instance 2","1.2.3.8","Proxy Server"));
ServerVertex ps3Vertex = new ServerVertex("PS3:Proxy Server Instance 3", new ServerConfig("Proxy Server Instance 3","1.2.3.9","Proxy Server"));
root = wsVertex;
}
@Test
assertNotNull(visitedList);
System.out.println("Breadth first traversal search path : ");
visitedList.stream().forEach(sv->System.out.println(sv.getLabel()));
}
@Test
public void testDepthFirstTraversal() {
List visitedList = serverGraph.depthFirstTraversal(root);
assertNotNull(visitedList);
System.out.println("Depth first traversal search path : ");
visitedList.stream().forEach(sv->System.out.println(sv.getLabel()));
}
}
```

Breadth-first traversal, as the name implies, means that all the nodes at a particular level on the graph are first visited, before proceeding down to the next level. So it involves visiting all nodes across the breadth of the graph before proceeding to go down.

When we run the method `testBreadthFirstTraversal()` by running the command ` mvn -Dtest=ServerGraphTraversalTest#testBreadthFirstTraversal test`from the project source folder, we see the following output:Output of ServerGraphTraversalTest#testBreadthFirstTraversal() method

```~/IdeaProjects/graphExample\$ mvn -Dtest=ServerGraphTraversalTest#testBreadthFirstTraversal test
WARNING: An illegal reflective access operation has occurred
WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations
WARNING: All illegal access operations will be denied in a future release
[INFO] Scanning for projects...
[INFO]
[INFO] ---------------------------------------
[INFO] Building graphExample 1.0-SNAPSHOT
[INFO] --------------------------------[ jar ]---------------------------------
[INFO]
[INFO] --- maven-resources-plugin:2.6:resources (default-resources) @ graphExample ---
[WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent!
[INFO] Copying 0 resource
[INFO]
[INFO] --- maven-compiler-plugin:3.8.0:compile (default-compile) @ graphExample ---
[INFO] Changes detected - recompiling the module!
[WARNING] File encoding has not been set, using platform encoding UTF-8, i.e. build is platform dependent!
[INFO] Compiling 6 source files to /home/vsowmya/IdeaProjects/graphExample/target/classes
[INFO]
[INFO] --- maven-resources-plugin:2.6:testResources (default-testResources) @ graphExample ---
[WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent!
[INFO] skip non existing resourceDirectory /home/vsowmya/IdeaProjects/graphExample/src/test/resources
[INFO]
[INFO] --- maven-compiler-plugin:3.8.0:testCompile (default-testCompile) @ graphExample ---
[INFO] Changes detected - recompiling the module!
[WARNING] File encoding has not been set, using platform encoding UTF-8, i.e. build is platform dependent!
[INFO] Compiling 2 source files to /home/vsowmya/IdeaProjects/graphExample/target/test-classes
[INFO]
[INFO] --- maven-surefire-plugin:2.12.4:test (default-test) @ graphExample ---
[INFO] Surefire report directory: /home/vsowmya/IdeaProjects/graphExample/target/surefire-reports

-------------------------------------------------------
T E S T S
-------------------------------------------------------
Running jcg.ssowmya.demo.graphExample.ServerGraphTraversalTest
Breadth first traversal search path :
WS1:Web Server
PS1:Proxy Server Instance 1
PS2:Proxy Server Instance 2
PS3:Proxy Server Instance 3
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.089 sec

Results :

Tests run: 1, Failures: 0, Errors: 0, Skipped: 0

[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  3.470 s
[INFO] Finished at: 2020-05-29T18:15:09-04:00
[INFO] ------------------------------------------------------------------------
```

Assuming that we are starting with the root as the node with label “WS1: Web Server” as level 0. From the output, we see that all the nodes at level 1, with the labels “LB1: Load Balancer 1” and “LB2: Load Balancer 2” are visited first. Similarly with level 2. By observing the `breadthFirstTraversal` method in the `ServerGraph` class, we see that we are making use of a `Queue` and a `LinkedList` implementation to track the visited nodes.

### 6.3 Depth First Traversal

In-depth first traversal, the search starts with a root node and proceeds all the way down to the lowest level, and then comes back up to visit the other nodes at a level. In other words, the traversal gives priority to the depth than the breadth of a node. To understand this better, let’s look at how the order of visited nodes looks like in the `testDepthFirstTraversal()` method of the `ServerGraphTraversalTest` class. To run this test method, we will need to execute `mvn -Dtest=ServerGraphTraversalTest#testDepthFirstTraversal test` from the project’s source folder in command line.Output of ServerGraphTraversalTest#testDepthFirstTraversal() method

```~/IdeaProjects/graphExample\$ mvn -Dtest=ServerGraphTraversalTest#testDepthFirstTraversal test
WARNING: An illegal reflective access operation has occurred
WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations
WARNING: All illegal access operations will be denied in a future release
[INFO] Scanning for projects...
[INFO]
[INFO] ---------------------------------------
[INFO] Building graphExample 1.0-SNAPSHOT
[INFO] --------------------------------[ jar ]---------------------------------
[INFO]
[INFO] --- maven-resources-plugin:2.6:resources (default-resources) @ graphExample ---
[WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent!
[INFO] Copying 0 resource
[INFO]
[INFO] --- maven-compiler-plugin:3.8.0:compile (default-compile) @ graphExample ---
[INFO] Changes detected - recompiling the module!
[WARNING] File encoding has not been set, using platform encoding UTF-8, i.e. build is platform dependent!
[INFO] Compiling 6 source files to /home/vsowmya/IdeaProjects/graphExample/target/classes
[INFO]
[INFO] --- maven-resources-plugin:2.6:testResources (default-testResources) @ graphExample ---
[WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent!
[INFO] skip non existing resourceDirectory /home/vsowmya/IdeaProjects/graphExample/src/test/resources
[INFO]
[INFO] --- maven-compiler-plugin:3.8.0:testCompile (default-testCompile) @ graphExample ---
[INFO] Nothing to compile - all classes are up to date
[INFO]
[INFO] --- maven-surefire-plugin:2.12.4:test (default-test) @ graphExample ---
[INFO] Surefire report directory: /home/vsowmya/IdeaProjects/graphExample/target/surefire-reports

-------------------------------------------------------
T E S T S
-------------------------------------------------------
Running jcg.ssowmya.demo.graphExample.ServerGraphTraversalTest
Depth first traversal search path :
WS1:Web Server
PS3:Proxy Server Instance 3
PS2:Proxy Server Instance 2
PS1:Proxy Server Instance 1
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.081 sec

Results :

Tests run: 1, Failures: 0, Errors: 0, Skipped: 0

[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  3.404 s
[INFO] Finished at: 2020-05-29T23:25:53-04:00
[INFO] ------------------------------------------------------------------------
```

From the above output, we can see how the traversal goes all the way down to the node labeled “PS3: Proxy Server Instance 3”, and then covers the other nodes at level 1. From looking at the implementation of the `depthFirstTraversal()` method in the `ServerGraph`class, we see that we are using a `Stack` to push and pop visited nodes.

## 7. Graph Benefits and Drawbacks

We find many real-life applications of graphs. Maps, Social network sites, Traffic, and transportation software are some applications that rely heavily on graphs. Let us look at the advantages and disadvantages of graphs as data structures.

### 7.1 Benefits

• The graph data structure makes it easy to represent parent/child and sibling relationships. Through this, we can visualize how to make the data in our applications hierarchical.
• Graphs are easy data structures that allow us to break down complex problems into smaller, simpler parts. It is no wonder that graphs are the foundation blocks for maps/GPS navigation software, where traversal algorithms can be optimized to find the shortest path between 2 nodes.
• In Operating Systems, resource allocation graphs are used to study processes and resources allocated to them, as well as the interaction between different processes and these resources. Graphs help to identify and prevent the state of deadlock.
• Social networking sites use the concepts of graph theory to represent people and the relationships between them.

### 7.2 Drawbacks

• Graphs face limitations when it comes to the way they are implemented. The theory and concepts behind graphs cannot be translated as-is with the perspective of memory. Hence the way we visualize a graph is different from how it’s actually stored in memory.
• Most programming languages, including Java, do not provide a Graph class. Hence there is no standard way of implementing this data structure.

## 8. Libraries that implement Graphs

In this section, we will look at some open source libraries that implement graphs in Java.

• JGraphT offers a flexible, powerful, and efficient API for implementing graphs. It covers all types of graphs, as well as traversal algorithms, with the ability to also integrate with other graph libraries
• Google’s Guava is a set of graph libraries offered and used by Google.
• Apache Commons Graph is a set of Graph API offered by Apache Commons
• JUNG – Java Universal Network Graph library is another open-source API for graph visualization.

## 9. Summary

To summarize, graphs are a very simple and interesting data structure to explore and use to solve many problems. Through this article, we have covered the basic concepts of a graph and implemented a custom Java Graph.

This was an example of Java Graph.