Design Graph using OOP concepts in Java


Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

In this Blog, you are going to learn to design and implement the graph data structure using OOP (Object Oriented Programming) Concepts. We will implement in Java but the ideas are applicable in any language.

First You need to understand What is Graph Data Structure all about? Learn from here

The main components of graph are:

  1. Vertex/Nodes
  2. Edges

graph-1

So, how can we initialize these components using Object-Oriented Concepts ?

Let's talk about nodes(vertex),
We need to have multiple nodes in graph having same properties.
To have same properties among different nodes, They should be the Object of the same Class.

So, We need to initialize a Class of Node and need to initialize objects of Node with different attributes but with similar methods(behaviors).

What are the attributes does node have?

  1. Identifier: Each node should have its identifier(name). Assume cities as nodes of the graph of countries. Then the node have identifier as the city name.
  2. Neighboring Nodes: Each node stores the identifier of its neighboring nodes connected by Edges.

So, here is the Class(Structure) of Node:

    class Node{
        String identifier;
        ArrayList<> neighbors = new ArrayList<String>();
        
        // Constructor
        Node(String Name){
            this.identifier = Name;
        }
    }

Now, What are the methods(behaviors) does node have?

There could be many methods but Let's only talk about the two.

  1. updateIdentifier: As the name suggests, Using this method, We can update the identifier of the Node.
  2. addNeighbor: As the name suggests, Using this method, We can add neighbors to the Node's neighbor list.

Let's update the Node class:

    class Node{
        String identifier;
        ArrayList<> neighbors = new ArrayList<String>();
        
        // Constructor
        Node(String Name){
            this.identifier = Name;
        }
        
        public void updateIdentifier(String updatedName){
            this.identifier = updatedName;
        }
        
        public void addNeighbor(String neighbor){
            neighbors.add(neighbor);
        }
    }

Now every object of the Class Node have specific attributes and methods.

That's how Structure of Node looks like:
Node

Let's create an object of the Node.

    // object initialisation
    Node USA = new Node('USA');
    
    // update identifier
    USA.updateIdentifier('United States of America');
    
    // adding Neighbors
    USA.addNeighbor('Canada');
    USA.addNeighbor('Mexico');

USA

Now, Let's learn about the other component i.e. Edge.

Edges connect the two nodes in the graph.

What are the attributes does Edge have?

  1. Nodes Connected : This attribute stores the two nodes as source and destination.

  2. Weight of the Edge : Suppose in a graph of cities of the country. In this graph, this weight could represent the distance between the cities.

So, here is the Class(Structure) of Edge:

    class Edge{
        String source,destination;
        int weight;
        
        // Constructor
        Edge(String sourceNode, String destinationNode, int edgeWeight){
            this.source = sourceNode;
            this.destination = destinationNode;
            this.weight = edgeWeight;
        }
    }

Now, What are the methods(behaviors) does Edge have?

Let's take three methods for the Edge class:

  1. updateSource: To update the source of the edge.
  2. updateDestination: To update the destination of the edge.
  3. updateWeight: To update the weight of the edge.

Let's update the Edge class:

    class Edge{
        String source,destination;
        int weight;
        
        // Constructor
        Edge(String sourceNode, String destinationNode, int edgeWeight){
            this.source = sourceNode;
            this.destination = destinationNode;
            this.weight = edgeWeight;
        }
        
        // Methods
        public void updateSource(String sourceUpdate){
            this.source = sourceUpdate;
        }
        
        public void updateDestination(String destinationUpdate){
            this.destination = destinationUpdate;
        }
        
        public void updateWeight(int weightUpdate){
            this.weight = weightUpdate;
        }
    }

Structure of Edge:

Edge

Let's create an object of the Edge.

    // object initialisation
    Edge USA_Canada = new Edge('USA','Canada',2300);
    
    // update Source
    USA_Canada.updateSource('United States of America');
    
    // update Destination
    USA_Canada.updateDestination('Dominion of Canada');
    
    // update Weight
    USA_Canada.updateWeight(2262)

Usa_Canada_Edge

Now, Let's build a graph:

We are going to use two attributes(data structures) to build a graph.

  1. nodeMap: Using a key-value pair i.e. map to store the graph where key is the identifier of the node and value is the reference to that node.

  2. edgeList: Storing the objects of edges.

Methods Graph class should have:

  1. addNode: Creating a new node of the graph and storing that into the map.

  2. addEdge: Creating a new Edge of the graph and adding source into the neighbor list of destination and similarly destination into neighbor list of source.

So, here is the class of the graph:

        class Graph{
    
            Map<String,Node> nodeMap = new HashMap<String,Node>();
            List<Edge> edgeList = new ArrayList<Edge>();

            public addNode(String identifier){
                nodeMap.put(identifier,new Node(identifier));
            }

            public addEdge(String source,String destination,int weight){
                edgeList.add(new Edge(source,destination,weight));
                nodeMap.get(source).addNeighbor(destination);
                nodeMap.get(destination).addNeighbor(source);
            }
    
        }

Graph_class

Let's create an object of the graph:

    // object initialisation
    Graph graphObject = new Graph();
    
    // adding Node
    graphObject.addNode('USA');
    graphObject.addNode('Canada');
    
    // adding Edge
    graphObject.addEdge('USA','Canada',2262);

Graph_object

That's how we can build a graph.

Thanks for Reading.😀