Implementing Generic Graph in Java – GeeksforGeeks

Prerequisite: Generic Class 

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:

Tóm Tắt

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




 

import java.util.*;

 

class Graph<T> {

 

    

    private Map<T, List<T> > map = new HashMap<>();

 

    

    public void addVertex(T s)

    {

        map.put(s, new LinkedList<T>());

    }

 

    

    

    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);

        }

    }

 

    

    public void getVertexCount()

    {

        System.out.println("The graph has "

                           + map.keySet().size()

                           + " vertex");

    }

 

    

    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.");

    }

 

    

    

    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.");

        }

    }

 

    

    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 + ".");

        }

    }

 

    

    @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());

    }

}

 

public class Main {

 

    public static void main(String args[])

    {

 

        

        Graph<Integer> g = new Graph<Integer>();

 

        

        

        

        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);

 

        

        System.out.println("Graph:\n"

                           + g.toString());

 

        

        g.getVertexCount();

 

        

        g.getEdgesCount(true);

 

        

        g.hasEdge(3, 4);

 

        

        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.

 

My Personal Notes

arrow_drop_up