Finds the number of vertices on either side of an edge in a tree graph.

MSTEdgeVertexCount.java

/**
Usage: 

       EdgeWeightedGraph MST;

Find a leaf in mst to start traversing. 
        int source=0;
        Edge sourceEdge = null;
          
        for(int i=1; i<=v ;i++){
            if(MST.getAdjEdges(i).size()==1){
                source = i;
                sourceEdge = MST.getAdjEdges(i).get(0);
                break;
            }
        } 
        
        MSTEdgeVertexCount dfs = new MSTEdgeVertexCount(G,source,sourceEdge);
        int[][] childCount = dfs.getChildCount();
        
 u-->v edge has childCount[u][v] vertices on one side and N-childCount[u][v] vertices on the other.

**/

static class MSTEdgeVertexCount{        
        int[][] child;

        public MSTEdgeVertexCount(EdgeWeightedGraph G, int source,Edge e){            
            child = new int[G.noOfVertices][G.noOfVertices];
            for(int i=1; i<child.length;i++){
                // since there is a minimum of 1 vertex on either side of each edge
                for(Edge edge: G.getAdjEdges(i)){
                    int u = edge.eitherVertex();
                    int w = edge.otherVertex(u);
                    child[u][w] = 1;
                    child[w][u] = 1;
                }
            }
            // send a dummy edge as grand parent
            dfs(G,e.otherVertex(source),e,new Edge(0,source,-1));
        }

        // w-->u-->v , v's parent edge is u-->v and grand parent edge is w-->u
        public void dfs(EdgeWeightedGraph G, int v, Edge parent, Edge grand){
            int u = parent.otherVertex(v);
            int w = grand.otherVertex(u);
            if(G.getAdjEdges(v).size() == 1){                
                child[w][u] = child[w][u] + 1;  
                child[u][w] = child[w][u];                
                return;
            }
            for(Edge e : G.getAdjEdges(v)){
                if(e == parent){ continue;}
                int x = e.otherVertex(v);
                dfs(G,x,e,parent);
            }
            child[w][u] = child[w][u] +  child[u][v];
            child[u][w] = child[w][u];
        }
       
       public int[][] getChildCount(){
            return child;
        }
}