Featured post

Why should I learn Go?

Image
What is unique about GO language? Here are some of the advantages of GO programming language:           Code runs fast           Garbage collection           Simpler objects           Efficient concurrency Code runs faster: Before understanding why GO runs faster, let us know the process of software translation. Basically, we have three broad categories of languages:             Machine level language ·        Machine level language is a low-level language where instructions are directly executed on the CPU. Machine level instructions are small steps which are straight forward and simple (Ex: ADD, SUBTRACT, MULTIPLY ) Assembly language ·        Assembly language is similar to machine level language but a bit more specific for humans to understand. For example, 1000...

GRAPHS - REPRESENTATION


GRAPHS:

A graph is a data structure that contains two components :
  • 1.      A finite set of vertices called nodes
  • 2.      A finite set of ordered pairs called edges.


An ordered pair (u,v) representing an edge between vertex u and vertex v. Graphs are generally used to represent many real time applications. Graphs are extremely useful in case of computer networks. A country connecting various cities can be represented using a graph. Consider an example of social networking website, facebook where each user is represented using a node and two users are said to be friends only if there exists an edge between them. A graph can be a directed or undirected graph.       A graph is said to be directed if there exists a specific direction from one vertex to another vertex.  A directed graph is unidirectional. A graph is said to be undirected graph if there exists a bidirectional path between two vertices. Example of directed and undirected graph is shown below:







REPRESENTATION OF GRAPHS:

Graphs can be represented using two methods:

  • Adjacency matrix
  • Adjacency list



Adjacency matrix:

In this method, the entire graph is represented using a 2-Dimensional matrix of size V x V .Here V represents the number of vertices of the graph G. The matrix entry adj[i][j] is 1 if there is an edge from I to j. Otherwise the entry adj[i][j] is 0.


Pros: 

Representation is easier to implement and follow.
 Removing an edge takes O(1) time.
 Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).

Cons: 

Consumes more space O(V^2).
 Even if the graph is sparse(contains less number of edges), it consumes the same space.
Adding a vertex is O(V^2) time.

Adjacency matrix representation in java :


package graph;

import java.util.Scanner;
public class Graph {
    public static void main(String[] args) {
       
        Scanner sc=new Scanner(System.in);
        System.out.println("enter the number of vertices");
        int n=sc.nextInt();
        int graph[][]=new int[n][n];
        while(true){
        System.out.println("enter your choice");
        System.out.println("1.create an edge");
        System.out.println("2. check if there is an edge");
        System.out.println("3. remove an edge");
        System.out.println("4.exit");
        System.out.println("****************");
        int ch=sc.nextInt();
        if(ch>4)
            System.out.println("wrong choice");
        else{
        switch(ch){
            case 1:
                System.out.println("PLEASE NOTE THAT THE VERTEX RANGE IS FROM 0 TO "+ (n-1));
                 System.out.println("*****************************************************");
                System.out.println("enter vertex 1");
            int e1=sc.nextInt();
                    System.out.println("enter vertex 2");
                    int e2=sc.nextInt();
                    if(e1<0||e2<0||e1>=n||e2>=n)
                        System.out.println("WRONG INPUT");
                    else{
                        graph[e1][e2]=1;
                        graph[e2][e1]=1;
                    }
                    System.out.println("CREATED EDGE SUCCESFULLY");
                    System.out.println("*****************************************************");
                       break;
                      
            case 2: System.out.println("PLEASE NOTE THAT THE VERTEX RANGE IS FROM 0 TO "+(n-1));
                 System.out.println("*****************************************************");

                System.out.println("enter vertex 1");
            int u=sc.nextInt();
                    System.out.println("enter vertex 2");
                    int v=sc.nextInt();
                    if(u<0||v<0||u>=n||v>=n)
                        System.out.println("WRONG INPUT");
                    else{
                   
                    if(graph[u][v]==1)
                        System.out.println("EDGE EXISTS");
                    else
                         System.out.println("NO EDGE BETWEEN "+u+" and "+v);
                 
                    }
                     System.out.println("*****************************************************");
                    break;
            case 3: System.out.println("PLEASE NOTE THAT THE VERTEX RANGE IS FROM 0 TO "+ (n-1));
                 System.out.println("*****************************************************");

                System.out.println("enter vertex 1");
            int t1=sc.nextInt();
                    System.out.println("1.create an edge");
                    int t2=sc.nextInt();
                    if(t1<0||t2<0||t1>=n||t2>=n)
                        System.out.println("WRONG INPUT");
                    else{
                        graph[t1][t2]=0;
                        System.out.println("EDGE REMOVED SUCCESSFULLY");
                      
                    }
                     System.out.println("*****************************************************");
                    break;
                   
            case 4: System.exit(1);
        }
        }
        }
    }
   
}



Adjacency List:

Here an array of linked lists is used. Size of the array is equal to number of vertices. Let the array be a[]. An entry a[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists.

 Following is adjacency list representation of the above graph in java.


class Graph {
    //Map of adjacency lists for each node
    Map<Integer, List<Integer>> adj;

    public Graph(int[] nodes) {
        //your node labels are consecutive integers starting with one. 
        //to make the indexing easier we will allocate an array of adjacency one element larger than necessary
        adj = new HashMap<Integer, LinkedList<Integer>>();
        for (int i = 0; i < nodes.length; ++i) {
            adj.put(i, new LinkedList<Integer>());
        }
    }

    public addNeighbor(int v1, int v2) {
        adj.get(v1).add(v2);
    }

    public List<Integer> getNeighbors(int v) {
        return adj.get(v);
    }

public static void main(String[] args) {
    try {
        BufferedReader br = new BufferedReader(new StreamReader(System.in));
        String line = br.readLine();


        if (line != null) {
            //read nodes
            String[] nodeNames = line.split(" ");
            int[] nodes = new int[nodeNames.length]
            for (int i = 0; i < nodes.length; ++i) {
               nodes[i] = Integer.parseInt(nodeNames[i]);
            }

            //create graph
            Graph g = new Graph(nodes);

            //read edges
            while((line = br.readLine()) != null) {
                String[] tokens = line.split(" ");
                int v1 = Integer.parseInt(tokens[0]);
                int v2 = Integer.parseInt(tokens[1]);


                //we add neighbor to each node in both directions.
                g.addNeighbor(v1, v2);
                g.addNeighbor(v2, v1);
            }

        }
        br.close();
    }
    catch(IOException e) {
        System.out.println(e);
    }

}



}


There are other representations also like, Incidence Matrix and Incidence List. The choice of the graph representation is situation specific. It totally depends on the type of operations to be performed and ease of use.









Comments

Popular posts from this blog

Introduction to Big Data and Hadoop

LocationManager vs GoogleApiClient

Why should I learn Go?