Basics of Graph in computer science using Java

Hello friends,

Lets try to have basic understanding of Graphs in computer science context.

• Graph is a way to represent the data : it is a Data structure.
• It consists of Nodes (or Vertices, we will use the term nodes) and Nodes are connected with edges.
• To identify a Node, each node has a unique name.
• An Edge is identified by the pair of nodes it connects.
• Each node has a value, often called as 'cost'. Nodes may or may not have same values. Note that this 'cost' is dependent upon the scenario and not for all graphs we require to associate 'cost' with its node.
• Each edge has a value, often called as 'weight'. These may be same or in some cases all the edges may have same value. Like 'cost' of a node, edge-weight is also dependent upon the scenario and not all graphs are required to have 'weight' associated with its edges.
• In case edges of the graph is directional then for each edge one of the pair of nodes connected by that edge is called the source and other node of the pair is called the destination. Such graph is called Directed Graph. It may happen that a single pair of nodes have two different edges and also may have two different weights.
• In case the direction does not matter then the edges do not have a direction and such graph is called Non directed graph. In-fact this is a special case of directed graph, where each pair of node is connected by two edges of same weight such that for source node of one edge is destination node for other edge and vice versa.
• In case of a directed graph if there is no cycle then it is called as ;DAG, directed a-cyclic graph.

Above are the basic definitions of the graphs. Below lets see few examples of Graph.







 Graphs can used to represent data of any social networking sites, where each user can be represented by the node. If the two users are connected with each other on the site then the nodes representing the two users can be connected by an edge. For the non connected users, their nodes are not connected by any edge.

Similarly cites connected via roads can also be represented by Graphs. Each city may be represented by the node and if two cities are connected then their corresponding nodes can be connected using an edge. We can have distance or the amount of time required to travel between two cities as the weight of the edge. Suppose each city has a market and there is a businessman who travels to different cities and to for each visit to a particular city he books a hotel. The cost of the hotel may be represented by the cost of the Node corresponding to that particular city.There are many such other scenarios where graph may be useful.

For representation of Graph we have two methods.

1. Adjacency List
2. Adjacency Matrix

Lets try to construct the above graph in figure I in below code using Adjacency List.

/**
 * 
 * @author krishna kumar
 * 
 * This is a basic implementation of Graph using  Adjacency list. 
 *
 */
public class Graph {

    private Node[] vertices; // stores the nodes of the graph
    private int size; // number of nodes in the graph
    
    public Graph(int size){
        this.size = size;
        vertices = new Node[size];
    }
    
    public class Node {
        int name;
        Neighbour neighbourList;
        int cost;
        Node (int name, int cost){
            this.name = name;
            this.cost = cost;
        }
    }

    public class Neighbour {
        int index;
        Neighbour next;
        int weight;
        public Neighbour(int index, int weight, Neighbour next) {
            this.index = index;
            this.weight = weight;
            this.next = next;
        }
    }
    
    public void addNode(int name, int cost){
        vertices[name-1] = new Node(name, cost);
    }
    
    public void addEdge(int sourceName, int destinationName, int weight){
        int sourceIndex = sourceName-1;
        int destinationIndex = destinationName-1;
        Node source = vertices[sourceIndex];
        source.neighbourList = new Neighbour(destinationIndex, weight, source.neighbourList);
    }
    
    
    public void printState(){
        for(int i = 0 ; i < size; i++){
            Node u = vertices[i];
            Neighbour temp = u.neighbourList;
            while(temp != null){
                Node v = vertices[temp.index];
                System.out.println("name:"+u.name+",cost:"+u.cost+" is connected with "+"name:"+v.name+",cost:"+v.cost +" with edge-weight as "+temp.weight);
                temp = temp.next;
            }
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addNode(1, 2);
        graph.addNode(2, 10);
        graph.addNode(3,19);
        graph.addNode(4, 3);
        
        graph.addEdge(1, 2, 4);
        graph.addEdge(1, 3, 5);
        graph.addEdge(3, 4, 100);
        graph.addEdge(4, 2, 90);
        graph.addEdge(4, 3, 2);
        graph.addEdge(4, 2, 2);
        
        graph.printState();
    }
}

Output :
name:1,cost:2 is connected with name:3,cost:19 with edge-weight as 5
name:1,cost:2 is connected with name:2,cost:10 with edge-weight as 4
name:3,cost:19 is connected with name:4,cost:3 with edge-weight as 100
name:4,cost:3 is connected with name:2,cost:10 with edge-weight as 2
name:4,cost:3 is connected with name:3,cost:19 with edge-weight as 2
name:4,cost:3 is connected with name:2,cost:10 with edge-weight as 90

In case we would have had non directional graph [ or bidirectional graph with both the edges between two nodes, n1 and n2 having same weight and this statement being true for all the pair of connected nodes]
Then only 'addEdge' method needs to be modified as below

public void addEdge(int n1Name, int n2Name, int weight){
        int n1Index = n1Name-1;
        int n2Index = n2Name-1;
        Node n1 = vertices[n1Index];
        Node n2 = vertices[n2Index];
        n1.neighbourList = new Neighbour(n2Index, weight, n1.neighbourList);
        n2.neighbourList = new Neighbour(n1Index, weight, n2.neighbourList);
    }

Now lets try to construct below graph shown in figure J using Adjacency Matrix

* note that as compared to figure I here we have a edge, with edge weight as 90 and connecting node named 4 to node name 2, missing in Figure J. This is because it is difficult to represent more than 1 edges with same direction between two nodes. Below is the code.

/**
 * 
 * @author krishna kumar
 * 
 *         This is a basic Implementation of Graph using Adjacency matrix.
 *
 */
public class Graph {
    private int[] costs;
    private int[][] adjacencyMatrix;
    private int size; // number of nodes in the graph

    public Graph(int size) {
        this.size = size;
        costs = new int[size]; //Initialized with all 0s
        adjacencyMatrix = new int[size][size];//Initialized with all 0s
    }

    public void addNode(int name, int cost) {
        costs[name - 1] = cost;
    }

    public void addEdge(int sourceName, int destinationName, int weight) {
        int sourceIndex = sourceName - 1;
        int destinationIndex = destinationName - 1;
        adjacencyMatrix[sourceIndex][destinationIndex] = weight;
        /*
         * In case we would have had non directional graph [ or bidirectional
         * graph with both the edges between two nodes, n1 and n2 having same
         * weight and this statement being true for all the pair of connected
         * nodes], we just need to add(uncomment) below statement
         */
        //adjacencyMatrix[destinationIndex][sourceIndex] = weight;
    }
    
    public void printState(){
        for(int i = 0 ; i < size; i++){
            for(int j = 0 ; j < size ; j++){
                if(adjacencyMatrix[i][j] != 0){
                    System.out.println("name:"+(i+1)+",cost:"+costs[i]+" is connected with "+"name:"+(j+1)+",cost:"+costs[j] +" with edge-weight as "+adjacencyMatrix[i][j]);
                }
            }
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addNode(1, 2);
        graph.addNode(2, 10);
        graph.addNode(3, 19);
        graph.addNode(4, 3);

        graph.addEdge(1, 2, 4);
        graph.addEdge(1, 3, 5);
        graph.addEdge(3, 4, 100);
        graph.addEdge(4, 2, 90);
        graph.addEdge(4, 3, 2);
        graph.addEdge(4, 2, 2);

        graph.printState();
    }

}

Output :
name:1,cost:2 is connected with name:2,cost:10 with edge-weight as 4
name:1,cost:2 is connected with name:3,cost:19 with edge-weight as 5
name:3,cost:19 is connected with name:4,cost:3 with edge-weight as 100
name:4,cost:3 is connected with name:2,cost:10 with edge-weight as 2
name:4,cost:3 is connected with name:3,cost:19 with edge-weight as 2