Graph API program | Undirected graph


import java.util.List;
import java.util.ArrayList;

class Graph {
    private final int V; // number of vertices
    private final List[] adj; // adjacency lists... 0 to V-1
    
    /** create an empty graph with V vertices */
    public Graph(int V) {
        this.V = V;
        this.adj = new ArrayList[V]; // create empty graph with V vertices
        for(int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    /** add an edge v-w */
    public void addEdge(int v, int w) {
        // add edge v-w (parallel edges and self-loops allowed)
        adj[v].add(w);
        adj[w].add(v);
    }
    
    /** vertices adjacent to v */
    public Iterable adj(int v) {
        return adj[v];
    }
    
    /** number of vertices */
    public int V() {
        return V;
    }
    
    /** number of edges */
    public int E() {
        int countEdges = 0;
        for(int v = 0; v < V; v++) {
            countEdges += adj[v].size();
        }
        return countEdges/2; // Each edge counted twice
    }
    
    /** string representation */
    public String toString() {
        return "TODO";
    }
    
	public static void main (String[] args) {
	    System.out.println("Test graph ");
		int[][] edges = new int[][] {
		    {0, 5},
		    {4, 3},
		    {0, 1},
		    {9, 12},
		    {6, 4},
		    {5, 4},
		    {0, 2},
		    {11, 12},
		    {9, 10},
		    {0, 6},
		    {7, 8},
		    {9, 11},
		    {5, 3}
		};
		
		Graph G = new Graph(edges.length);
		// add all edges 
		for(int i = 0; i < edges.length; i++) {
		    int v = edges[i][0];
		    int w = edges[i][1];
		    G.addEdge(v, w);
		}
		System.out.println("V: " + G.V());
		System.out.println("E: " + G.E());
		System.out.println("Max degree: " + Graph.GraphProcessing.maxDegree(G));
		System.out.println("Avg degree: " + Graph.GraphProcessing.averageDegree(G));
		System.out.println("No of self loops: " + Graph.GraphProcessing.numberOfSelfLoops(G));
	}
	
	public static class GraphProcessing {
        /** compute degree of v */
        public static int degree(Graph G, int v) {
            int degree = 0;
            for(int w : G.adj(v)) {
                degree++;
            }
            return degree; // (or) return G.adj(v).size()
        }
        
        /** Compute max degree of graph */
        public static int maxDegree(Graph G) {
            int maxDegree = 0;
            for(int v = 0; v < G.V(); v++) {
            int degreeOfV = degree(G, v);
                maxDegree = degreeOfV > maxDegree ? degreeOfV : maxDegree;
            }
            return maxDegree;
        }
        
        /** Compute average degree */
        public static double averageDegree(Graph G) {
            return 2.0 * G.E()/G.V();
        }
        
        /** Compute self loops */
        public static int numberOfSelfLoops(Graph G) {
            int numberOfLoops = 0;
            for(int v = 0; v < G.V(); v++) {
                for(int w : G.adj(v)) {
                    numberOfLoops = (v == w) ? ++numberOfLoops : numberOfLoops;
                }
            }
            return numberOfLoops/2; // each edge counted twice
        }
    }

    public static class Path {
        /* is there a path from s to v? */
        public boolean hasPathTo(Graph G, int s, int v)  {
            return G.adj(s).contains(v);
        }
        
        /* path from s to v; null if no such path */
        public Iterable pathTo(Graph G, int s, int v) {
            
        }
        
        /* Print all vertices connected to s */
        public void printAllConnected(Graph G, int s) {
            //for()
        }
    }
}

Output
Test graph 
V: 13
E: 13
Max degree: 4
Avg degree: 2.0
No of self loops: 0

Comments

Popular posts from this blog

gsutil Vs Storage Transfer Service Vs Transfer Appliance

SQL basic interview question