Implementing Generic Graph in Java

0 0 3 minutes read

We can also use them to code for Graph in Java. The Graph class is implemented using HashMap in Java. As we know HashMap contains a key and a value, we represent nodes as keys and their adjacency list in values in the graph.

Illustration: An undirected and unweighted graph with 5 vertices.

Adjacency Matrix is as follows:

Adjacency List is as follows:

Approach:

Just unlikely in C++, we use <> to specify parameter types in generic class creation.

Syntax: To create objects of a generic class

BaseType <Type> obj = new BaseType <Type>()

Note: In Parameter type, we cannot use primitives like ‘int’, ‘char’, or ‘double’.

Example

Java

// Java program to implement Graph
// with the help of Generics
 
import java.util.*;
 
class Graph<T> {
 
    // We use Hashmap to store the edges in the graph
    private Map<T, List<T> > map = new HashMap<>();
 
    // This function adds a new vertex to the graph
    public void addVertex(T s)
    {
        map.put(s, new LinkedList<T>());
    }
 
    // This function adds the edge
    // between source to destination
    public void addEdge(T source,
                        T destination,
                        boolean bidirectional)
    {
 
        if (!map.containsKey(source))
            addVertex(source);
 
        if (!map.containsKey(destination))
            addVertex(destination);
 
        map.get(source).add(destination);
        if (bidirectional == true) {
            map.get(destination).add(source);
        }
    }
 
    // This function gives the count of vertices
    public void getVertexCount()
    {
        System.out.println("The graph has "
                           + map.keySet().size()
                           + " vertex");
    }
 
    // This function gives the count of edges
    public void getEdgesCount(boolean bidirection)
    {
        int count = 0;
        for (T v : map.keySet()) {
            count += map.get(v).size();
        }
        if (bidirection == true) {
            count = count / 2;
        }
        System.out.println("The graph has "
                           + count
                           + " edges.");
    }
 
    // This function gives whether
    // a vertex is present or not.
    public void hasVertex(T s)
    {
        if (map.containsKey(s)) {
            System.out.println("The graph contains "
                               + s + " as a vertex.");
        }
        else {
            System.out.println("The graph does not contain "
                               + s + " as a vertex.");
        }
    }
 
    // This function gives whether an edge is present or not.
    public void hasEdge(T s, T d)
    {
        if (map.get(s).contains(d)) {
            System.out.println("The graph has an edge between "
                               + s + " and " + d + ".");
        }
        else {
            System.out.println("The graph has no edge between "
                               + s + " and " + d + ".");
        }
    }
 
    // Prints the adjancency list of each vertex.
    @Override
    public String toString()
    {
        StringBuilder builder = new StringBuilder();
 
        for (T v : map.keySet()) {
            builder.append(v.toString() + ": ");
            for (T w : map.get(v)) {
                builder.append(w.toString() + " ");
            }
            builder.append("\n");
        }
 
        return (builder.toString());
    }
}
 
// Driver Code
public class Main {
 
    public static void main(String args[])
    {
 
        // Object of graph is created.
        Graph<Integer> g = new Graph<Integer>();
 
        // edges are added.
        // Since the graph is bidirectional,
        // so boolean bidirectional is passed as true.
        g.addEdge(0, 1, true);
        g.addEdge(0, 4, true);
        g.addEdge(1, 2, true);
        g.addEdge(1, 3, true);
        g.addEdge(1, 4, true);
        g.addEdge(2, 3, true);
        g.addEdge(3, 4, true);
 
        // Printing the graph
        System.out.println("Graph:\n"
                           + g.toString());
 
        // Gives the no of vertices in the graph.
        g.getVertexCount();
 
        // Gives the no of edges in the graph.
        g.getEdgesCount(true);
 
        // Tells whether the edge is present or not.
        g.hasEdge(3, 4);
 
        // Tells whether vertex is present or not
        g.hasVertex(5);
    }
}

Output:

Graph:
0: 1 4 
1: 0 2 3 4 
2: 1 3 
3: 1 2 4 
4: 0 1 3 

The graph has 5 vertex
The graph has 7 edges.
The graph has an edge between 3 and 4.
The graph does not contain 5 as a vertex.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!