CS 112 Lab 11 - BFS to compute Graph diameter

The diameter of a graph is the shortest path distance between the farthest pair of nodes in the graph.

We run BFS traversal starting from each node in the graph and compute the max distance value over all BFS traversals. We also keep track of the node pair that gives the max distance, this gives the diametrically opposite vertices in the graph.

TASKS:

1. Save lab-subgraph.txt file to your Z:\ drive ( i.e., as Z:\lab-subgraph.txt ).
   
   
2. Complete the tasks within Graph.java.
   
   
3. Complete the "homework tasks" within Graph.java and GraphClient.java

package lab11;
import java.io.*;
import java.util.*;
 
public class Graph {
    
    // adjacencyList is an array of NodeLists, the NodeList class is defined below. 
    NodeList [] adjacencyList;
    
    // numNodes is number of nodes in the graph
    int numNodes;
    int getNumNodes(){ return numNodes; }
    
    public Graph(String graphFileName) throws FileNotFoundException {
        
        Scanner fileScanner = new Scanner(new FileInputStream(graphFileName));
        int maxNodeId = -1;
 
        // TASK: Get the maximum NodeId in the input file.
        
        fileScanner.close();
        
        // Set numNodes: note that the nodeIds are in the range [1, maxNodeId].
        numNodes = maxNodeId + 1;  
        
        // TASKS:
        // (a) initialize adjacencyList to NodeList array of length numNodes.
        // (b) initialize each adjacencyList element to a new NodeList.
        
        // Reopen the file to construct the graph.
        fileScanner = new Scanner(new FileInputStream(graphFileName));
        while( fileScanner.hasNextInt() ){
            // TASKS: 
            // (a) Read a pair of nodeIds (node1, node2) from the input file.
            // (b) Add node2 to the NodeList corresponding to node1 in adjacencyList.  
        }
        fileScanner.close();
    }
    
    // This method returns the shortest path distance from startNode to all nodes 
    // in the graph using Breadth First Search.
    public int[] BFS_distance( int startNode ){
        
        // BFS_queue will be used for BFS traversal.
        // Use BFS_queue.add(...) and BFS_queue.remove() to enqueue and dequeue nodes.   
        LinkedList<Integer> BFS_queue = new LinkedList<Integer>();
        
        // Visited array keeps track of nodes that are visited: 
        //   visited nodes are nodes that have previously been added to the queue.
        boolean [] visited = new boolean[numNodes];
        
        // bfs_distances array stores the distance from startNode to all nodes in the graph. 
        int [] bfs_distances = new int[numNodes];
        // Initialize the distances to -1, this implies their distance is not yet known. 
        for( int i = 0; i < numNodes; i++ )    bfs_distances[i] = -1;
        
        // TASKS: perform BFS initialization here.
        // (a) Insert startNode into BFS_queue
        // (b) Set bfs_distances for startNode: what is its distance value?
        // (c) Set visited for startNode. 
        
        // Loop until the BFS_queue is empty.
        while( !BFS_queue.isEmpty() ) {
            
            // TASK: get currentNode from BFS_queue.
            
            // TASKS:
            //  For each 'unvisited' node V adjacent to currentNode do (a) - (c) below
            //  (you can use the NodeList iterator to get nodes adjacent to currentNode)
            //
            //     (a) add V to the BFS_queue
            //     (b) set the visited flag for V in visited array
            //     (c) set distance value for V in bfs_distances array  
            //           HINT: you will need to use currentNode's distance.
            //
        }
        
        return bfs_distances;
    }
    
    // This method computes "diameter" of the input graph.
    // The diameter of the graph is the shortest path distance between farthest 
    // pair of nodes.
    // We get the graph diameter by running BFS starting from all nodes in the 
    // graph and computing the max distance value over all BFS traversals.
    void getGraphDiameter(){

        int diameterNode1 = 0, diameterNode2 = 0;
        int graphDiameter = -1;
        for( int i = 0; i < numNodes; i++ ){
            if( adjacencyList[i].getSize() == 0 )
                continue;
            int [] cur_bfs_distance = BFS_distance( i );
            for( int j = 0; j < numNodes; j++ ){
                if( cur_bfs_distance[j] > graphDiameter ){
                    diameterNode1 = i;
                    diameterNode2 = j;
                    graphDiameter = cur_bfs_distance[j];
                }
            }
        }
        System.out.println("Graph diameter = " + graphDiameter);
        System.out.println("Diameter vertices: ( " + 
                    diameterNode1 + ", " + diameterNode2 + " )");
    }
    
    int getNodeDegree(int node){
        // HOMEWORK TASK:
        //   return the degree for input node.   
        return 0;
    }
    
    float getClusteringCoefficient( int node ) {
        // HOMEWORK TASK:
        //   return the clusteringCoefficient for input node.
        return 0;
    }
    
    float getClosenessCentrality( int node ) {
        // HOMEWORK TASK:
        //   return the closeness centrality (CLC) for input node.
        return 0;
    }
}
 
class Node{
    int nodeId;
    Node nextNode;
    public Node(int newNodeId, Node newNext){
        nodeId = newNodeId;
        nextNode = newNext; 
    }
    public int getNodeId(){ return nodeId; }
    public Node getNext() { return nextNode; }
}
 
class NodeListIterator implements Iterator<Integer>{
    Node currentNode;
    public NodeListIterator(Node headNode){
        currentNode = headNode;
    }
    public boolean hasNext(){
        return (currentNode != null);
    }
    public Integer next(){ 
        Integer currentNodeId = currentNode.getNodeId();
        currentNode = currentNode.getNext();
        return currentNodeId; 
    }
    public void remove(){}
}
 
class NodeList implements Iterable<Integer>{
    int size;
    Node headNode;
    public NodeList(){
        size = 0;
        headNode = null;
    }
    public int getSize(){ return size; }
    public void addToHead(int addNodeId){
        headNode = new Node(addNodeId, headNode);
        size++;
    }
    public NodeListIterator iterator(){
        return new NodeListIterator(headNode);
    }
}

package lab11;
import java.io.*;
 
class Pair { 
    int nodeId;
    float nodeRank;
    Pair(int inNodeId, float inRank){
        nodeId = inNodeId;
        nodeRank = inRank;
    }
    int getNodeId(){ return nodeId; }
    float getNodeRank(){ return nodeRank; }
}
 
public class GraphClient {
    public static void main(String[] args) throws Exception{
        
        Graph graph = new Graph("Z:/lab-subgraph.txt");
        // We will compute the graph diameter for the lab example.
        graph.getGraphDiameter();
        
        Pair [] nodeDegrees = new Pair[graph.getNumNodes()];
        // HOMEWORK TASK: 
        // (a) Complete getNodeDegree() in Graph class
        // (b) Assign node degrees for all nodes into the nodeDegrees array,
        //     create a new Pair instance (nodeId, nodeDegree) for each node.
        mergesort_descending(nodeDegrees);
        writePairArrayToFile(nodeDegrees, "Z:/degreeRanking.txt");
        
        Pair [] clusteringCoefficients = new Pair[100];
        // HOMEWORK TASK:
        // (a) Complete getClusteringCoefficient() in Graph class
        // (b) Assign node clusteringCoefficients for top 100 nodeDegree vertices
        //     into clusteringCoefficients array, 
        //     create a new Pair instance (nodeId, clusteringCoefficient) for 
        //     top 100 nodeDegree nodes.    
        mergesort_descending(clusteringCoefficients);
        writePairArrayToFile(clusteringCoefficients, "Z:/clusteringRanking.txt");
        
        Pair [] CLC = new Pair[100];
        // HOMEWORK TASK:
        // (a) Complete getClosenessCentrality() in Graph class
        // (b) Assign node closenessCentrality for top 100 nodeDegree vertices
        //     into CLC array, 
        //     create a new Pair instance (nodeId, closenessCentrality) for 
        //     top 100 nodeDegree nodes.
        mergesort_ascending(CLC);    
        writePairArrayToFile(CLC, "Z:/closenessRanking.txt");
    }
    
    static void writePairArrayToFile( Pair [] pairs, String outFile ) 
                throws FileNotFoundException{
        PrintStream out = new PrintStream(outFile);
        for( int i = 0; i < Math.min(pairs.length, 1000); i++ )
            out.printf("%7d %12.6f\n", pairs[i].getNodeId(), pairs[i].getNodeRank());
        out.close();
    }
    
    static void mergesort_ascending( Pair [] A ){
        mergesort_descending(A);
        for( int i = 0; i < A.length/2; i++ ){
            Pair temp = A[i];
            A[i] = A[A.length - 1 - i];
            A[A.length - 1 - i] = temp;
        }
    }
    
    public static void mergesort_descending( Pair [] A ){
        int chunk = 2;
        while(true) {
            for( int chunkStart = 0; chunkStart < A.length; chunkStart += chunk ){
                int start = chunkStart;
                int middle = chunkStart + chunk/2;
                int end = chunkStart + chunk - 1;
                if( middle >= A.length )
                    break;
                if( end >= A.length )
                    end = A.length - 1;
                merge(A, start, middle, end);
            }
            if( chunk > A.length )
                break;
            else
                chunk *= 2;
        }
    }
    
    static void merge (Pair [] A,  int leftPos, int rightPos, int rightEnd){
        int leftEnd = rightPos - 1;
        int numElements = rightEnd - leftPos + 1;
        Pair [] B = new Pair[numElements];
        int bPos = 0;
 
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (A[leftPos].nodeRank >= A[rightPos].nodeRank)
                B[bPos++] = A[leftPos++];
            else
            B[bPos++] = A[rightPos++];
        }
        while (leftPos <= leftEnd) 
            B[bPos++] = A[leftPos++];
            
        while (rightPos <= rightEnd) 
            B[bPos++] = A[rightPos++];
 
        leftPos = rightEnd - numElements + 1;
        for (bPos = 0; bPos < numElements; bPos ++)
            A[leftPos++] = B[bPos];
    }
}

Graph diameter = 23
Diameter vertices: ( 3141, 4646 )

// This method returns the shortest path distance from startNode to all nodes 
// in the graph using Breadth First Search.
public int[] BFS_distance( int startNode ){
    
    // BFS_queue will be used for BFS traversal.
    // Use BFS_queue.add(...) and BFS_queue.remove() to enqueue and dequeue nodes.   
    LinkedList<Integer> BFS_queue = new LinkedList<Integer>();
    
    // Visited array keeps track of nodes that are visited: 
    //   visited nodes are nodes that have previously been added to the queue.
    boolean [] visited = new boolean[numNodes];
    
    // bfs_distances array stores the distance from startNode to all nodes in the graph. 
    int [] bfs_distances = new int[numNodes];
    // Initialize the distances to -1, this implies their distance is not yet known. 
    for( int i = 0; i < numNodes; i++ )    bfs_distances[i] = -1;
    
    // TASKS: perform BFS initialization here.
    // (a) Insert startNode into BFS_queue
    // (b) Set bfs_distances for startNode: what is its distance value?
    // (c) Set visited for startNode. 
    BFS_queue.add(startNode);
    visited[startNode] = true;
    bfs_distances[startNode] = 0;
    
    // Loop until the BFS_queue is empty.
    while( !BFS_queue.isEmpty() ) {
        
        // TASK: get currentNode from BFS_queue.
        int currentNode = BFS_queue.remove();
        
        // TASKS:
        //  For each 'unvisited' node V adjacent to currentNode do (a) - (c) below
        //  (you can use the NodeList iterator to get nodes adjacent to currentNode)
        //
        //     (a) add V to the BFS_queue
        //     (b) set the visited flag for V in visited array
        //     (c) set distance value for V in bfs_distances array  
        //           HINT: you will need to use currentNode's distance.
        for( Integer adjacentNode : adjacencyList[currentNode] ){
            if( !visited[adjacentNode] ){
                BFS_queue.add(adjacentNode);
                visited[adjacentNode] = true;
                bfs_distances[adjacentNode] = bfs_distances[currentNode] + 1; 
            }
        }
    }
    
    return bfs_distances;
}

http://cs-people.bu.edu/tvashwin/cs112_spring09/lab11.html