Home » Core Java » Java Graph Example

About Sowmya Shankar

Sowmya works as a Senior Web Applications Programmer in the higher educational sector, where she leads projects based on Java. She graduated from Anna University's Computer Sciences department, followed by a Masters degree in Computer and Information Sciences from the University of Delaware. Her project portfolio features diverse web applications using frameworks such as Struts2, Spring, Spring Boot, as well as her recent experiments in the world of Microservices and the React JS framework.

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.

Java Graph - Sample Server Architecture
Fig. 1. Graph of Sample Server Architecture

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.

Java Graph - home network
Fig 2. Undirected graph of 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.

4.1 Adjacency Matrix

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.

Base stationHome networkDesktop 1Laptop 1Laptop 2
Base station01000
Home network10111
Desktop 101000
Laptop 101000
Laptop 201000
Table 1. Adjacency Matrix representation of Fig 2

4.2 Adjacency List

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.

Java Graph - Adjacency List representation of Home network
Fig. 3. Adjacency List representation of Home network

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 ipAddress;
    private String serverType;

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

    public String getName() {
        return name;
    }

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

    public String getIpAddress() {
        return ipAddress;
    }

    public void setIpAddress(String ipAddress) {
        this.ipAddress = ipAddress;
    }

    public String getServerType() {
        return serverType;
    }

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

    @Override
    public String toString() {
        return "ServerConfig{" +
                "name='" + name + '\'' +
                ", ipAddress='" + ipAddress + '\'' +
                ", 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 {
    private Map<ServerVertex, List> adjServerVertices;
    public ServerGraph() {
        adjServerVertices = new LinkedHashMap();
    }
    public Map<ServerVertex, List> getAdjServerVertices() {
        return adjServerVertices;
    }

    public void setAdjServerVertices(Map<ServerVertex, List> adjServerVertices) {
        this.adjServerVertices = adjServerVertices;
    }
    public List getAdjVerticesForServerVertex(ServerVertex serverVertex) {
        return adjServerVertices.get(serverVertex);
    }
    public void addServerVertex(ServerVertex serverVertex) {
        adjServerVertices.putIfAbsent(serverVertex,new ArrayList());
    }
    public void removeServerVertexByIpAddress(String ipAddress) {
        if(adjServerVertices.isEmpty())
            return;
        Optional serverVertexOptional = adjServerVertices.keySet().stream().filter(serverVertex -> ipAddress.equals(serverVertex.getServerConfig().getIpAddress())).findAny();
        if(!serverVertexOptional.isPresent())
            return;
        ServerVertex serverVertexToBeRemoved = serverVertexOptional.get();
        adjServerVertices.values().stream().forEach(serverVertexList-> {
            serverVertexList.remove(serverVertexToBeRemoved);
        });
        adjServerVertices.remove(serverVertexToBeRemoved);
    }
    public void addEdge(ServerEdge edge){
        adjServerVertices.get(edge.getStart()).add(edge.getEnd());
        adjServerVertices.get(edge.getEnd()).add(edge.getStart());
    }

    public void removeEdge(ServerEdge edge) {
        adjServerVertices.get(edge.getStart()).remove(edge.getEnd());
        adjServerVertices.get(edge.getEnd()).remove(edge.getStart());
    }

    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)) {
                visitedNodes.add(visitedElement);
                for(ServerVertex sv:getAdjVerticesForServerVertex(visitedElement))
                    serverVertexStack.push(sv);
            }
        }
        return visitedNodes;

    }
    public List breadthFirstTraversal(ServerVertex root) {
        List visitedNodes = new ArrayList();
        Queue serverVertexQueue = new LinkedList();
        serverVertexQueue.add(root);
        visitedNodes.add(root);
        while(!serverVertexQueue.isEmpty()) {
            ServerVertex visitedElement = serverVertexQueue.poll();
            for(ServerVertex sv:getAdjVerticesForServerVertex(visitedElement))
                if(!visitedNodes.contains(sv)) {
                    visitedNodes.add(sv);
                    serverVertexQueue.add(sv);
            }
        }
        return visitedNodes;

    }

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

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();
        assertNotNull(serverGraph.getAdjServerVertices());
        serverGraph.addServerVertex(new ServerVertex("WS1:Web Server", new ServerConfig("JCG Web Server 1","1.2.3.4","Web")));
        assertEquals(1,serverGraph.getAdjServerVertices().size());
        serverGraph.removeServerVertexByIpAddress("1.2.3.4");
        assertEquals(0,serverGraph.getAdjServerVertices().size());
    }

    @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"));
        ServerVertex lb1Vertex = new ServerVertex("LB1:Load Balancer 1", new ServerConfig("JCG Load Balance Server 1","1.2.3.5","Load Balancer"));
        serverGraph.addServerVertex(wsVertex);
        serverGraph.addServerVertex(lb1Vertex);
        assertEquals(2,serverGraph.getAdjServerVertices().size());
        serverGraph.addEdge(new ServerEdge(wsVertex,lb1Vertex));
        assertEquals(1,serverGraph.getAdjServerVertices().get(wsVertex).size());
        assertEquals(1,serverGraph.getAdjServerVertices().get(lb1Vertex).size());
        serverGraph.removeEdge(new ServerEdge(wsVertex,lb1Vertex));
        assertEquals(0,serverGraph.getAdjServerVertices().get(wsVertex).size());
        assertEquals(0,serverGraph.getAdjServerVertices().get(lb1Vertex).size());
    }
}

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 lb1Vertex = new ServerVertex("LB1:Load Balancer 1", new ServerConfig("JCG Load Balance Server 1","1.2.3.5","Load Balancer"));
        ServerVertex lb2Vertex = new ServerVertex("LB2:Load Balancer 2", new ServerConfig("JCG Load Balance Server 2","1.2.3.6","Load Balancer"));
        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"));
        serverGraph.addServerVertex(wsVertex);
        serverGraph.addServerVertex(lb1Vertex);
        serverGraph.addServerVertex(lb2Vertex);
        serverGraph.addServerVertex(ps1Vertex);
        serverGraph.addServerVertex(ps2Vertex);
        serverGraph.addServerVertex(ps3Vertex);
        serverGraph.addEdge(new ServerEdge(wsVertex,lb1Vertex));
        serverGraph.addEdge(new ServerEdge(wsVertex,lb2Vertex));
        serverGraph.addEdge(new ServerEdge(lb1Vertex,ps1Vertex));
        serverGraph.addEdge(new ServerEdge(lb1Vertex,ps2Vertex));
        serverGraph.addEdge(new ServerEdge(lb2Vertex,ps3Vertex));
        root = wsVertex;
    }
    @Test
    public void testBreadthFirstTraversal() {
        List visitedList = serverGraph.breadthFirstTraversal(root);
        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()));
    }
}

6.2 Breadth First Traversal

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 testfrom 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: Illegal reflective access by com.google.inject.internal.cglib.core.$ReflectUtils$1 (file:/usr/share/maven/lib/guice.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int,java.security.ProtectionDomain)
WARNING: Please consider reporting this to the maintainers of com.google.inject.internal.cglib.core.$ReflectUtils$1
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
LB1:Load Balancer 1
LB2:Load Balancer 2
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: Illegal reflective access by com.google.inject.internal.cglib.core.$ReflectUtils$1 (file:/usr/share/maven/lib/guice.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int,java.security.ProtectionDomain)
WARNING: Please consider reporting this to the maintainers of com.google.inject.internal.cglib.core.$ReflectUtils$1
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
LB2:Load Balancer 2
PS3:Proxy Server Instance 3
LB1:Load Balancer 1
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 ServerGraphclass, 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.

10. Download the Source Code

This was an example of Java Graph.

Download
You can download the full source code of this example here: Java Graph Example

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

 

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments