Thursday, November 26, 2015

Undirected Graph using Adjacency List

Code for representing Undirected graph using Adjacency List in Java : 

Operations :
    1. void addEdge(int v, int w)                      - Adding an edge between two vertices 
    2. Iterable<Integer> adj(int v)                    - Returns vertices adjacent to vertex v
    3. int V()                                                     - Returns the number of vertices
    4. int E()                                                      - Returns the number of edges
    5. static int degree(Graph G, int v)             - Returns the degree of vertex v
    6. static int maxDegree(Graph G)               - Returns the max vertex degree in the graph
    7. static double averageDegree(Graph G)   - Returns the average degree in the graph
    8. static int numberOfSelfLoops(Graph G) - Returns the number of self loops.

import java.util.ArrayList; 

public class Graph {
    
    private final int V;
    private int E;
    
    private ArrayList<ArrayList<Integer>> adj;
    
    Graph(int V){
        this.V = V;
        adj = new ArrayList<>();
        for(int v = 0;v<V;v++)
            adj.add(new ArrayList<>());
    }
    
    public void addEdge(int v, int w){
        adj.get(v).add(w);
        adj.get(w).add(v);
        E++;
    }
    
    public Iterable<Integer> adj(int v){
        return adj.get(v);
    }
    
//    Graph(InputStream in){
//       
//    } 
    
    int V(){return V;}
    
    int E(){return E;}
    
    public static int degree(Graph G, int v){
        int degree = 0;
        for(int w:G.adj(v)) degree++;
        return degree;
    }
    
    public static int maxDegree(Graph G){
        int max = 0;
        for(int v=0;v<G.V();v++)
            if(degree(G, v)>max)max = degree(G, v);
        return max;
    }
    
    public static double averageDegree(Graph G){
        return 2.0 * G.E() / G.V();
    }
    
    public static int numberOfSelfLoops(Graph G){
        int count=0;
        for(int v = 0;v<G.V();v++){
            for(int w:G.adj(v)){
                if(v==w)count++;
            }
        }
        return count/2;
    }
    
    public static void main(String[] args){
        //Use graph API
        Graph G = new Graph(5);
        
        System.out.println("Adding edges to graph...");
        G.addEdge(0, 1);
        G.addEdge(1, 2);
        G.addEdge(2, 3);
        G.addEdge(3, 4);
        G.addEdge(4, 2);
        G.addEdge(0, 2);
              
        System.out.println("\nPrinting adjacent vertices of all vertices...");
        for(int i=0;i<G.V();++i){
            System.out.print("Vertices adjacent to vertex "+i+" are: ");
            for(int j:G.adj(i))System.out.print(j+" ");
            System.out.println();
        }
        
        System.out.println("\nNumber of vertices : "+G.V()+" Number of edges : "+G.E());
        
        System.out.println("\nPrinting degrees of all vertices...");
        for(int i=0;i<G.V();++i){
            System.out.println("Degree of vertex "+i+" is: "+Graph.degree(G, i));
        }
        
        System.out.println("\nMax degree is "+Graph.maxDegree(G));
        
        System.out.println("\nAverage degree is "+Graph.averageDegree(G));
        System.out.println("\nNo of self loops : "+Graph.numberOfSelfLoops(G));
        
        System.out.println("\nAdding a selp loop on vertex 1");
        G.addEdge(1, 1);
        System.out.println("No of self loops : "+Graph.numberOfSelfLoops(G));
        
    }
}


Output:

Adding edges to graph...

Printing adjacent vertices of all vertices...
Vertices adjacent to vertex 0 are: 1 2 
Vertices adjacent to vertex 1 are: 0 2 
Vertices adjacent to vertex 2 are: 1 3 4 0 
Vertices adjacent to vertex 3 are: 2 4 
Vertices adjacent to vertex 4 are: 3 2 

Number of vertices : 5 Number of edges : 6

Printing degrees of all vertices...
Degree of vertex 0 is: 2
Degree of vertex 1 is: 2
Degree of vertex 2 is: 4
Degree of vertex 3 is: 2
Degree of vertex 4 is: 2

Max degree is 4

Average degree is 2.4

No of self loops : 0

Adding a selp loop on vertex 1
No of self loops : 1

No comments:

Post a Comment