Friday, November 25, 2011

Implemenations of BFS & DFS traversal for Graph using adjancency Matrix (Java)


import java.io.BufferedInputStream;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

/**
 *
 * @author santosh
 */
public class AdjMatGraph {

    class Queue {

        LinkedList queueHead = new LinkedList();
        int size;

        public void enqueue(GNode gn) {
            size++;
            queueHead.add(gn);
        }

        public GNode dequeue() {
            if (size > 0) {
                size--;
                return queueHead.removeLast();
            }

            return null;
        }

        public GNode peek() {
            return queueHead.getFirst();
        }

        public GNode tail() {
            return queueHead.getLast();
        }

        public int qSize() {
            return size;
        }

        public boolean isEmpty() {
            if (size <= 0) {
                return true;
            } else {
                return false;
            }
        }
    }

    private class GNode {

        int vLabel;
        boolean isVisited;
    }
    private int adjMat[][];
    private int noOfEdges;
    private int noOfVertex;
    private GNode vertex[];
    private Stack stack;
    private Queue queue;

    public AdjMatGraph() {

        adjMat = new int[100][100];

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                adjMat[i][j] = 0;
            }
        }

        noOfEdges = 0;
        noOfVertex = 0;
        vertex = new GNode[100];

        for (int k = 0; k < 100; k++) {
            vertex[k] = new GNode();
            vertex[k].isVisited = false;
            vertex[k].vLabel = -1;
        }

        stack = new Stack();
        queue = new Queue();
    }

    public void setNoEdges(int val) {
        noOfEdges = val;
    }

    public void setNoVertex(int val) {
        noOfVertex = val;
        for (int i = 1; i <= val; i++) {
            vertex[i - 1].vLabel = i;
        }
    }

    public int findVertex(int v) {

        for (int i = 0; i < noOfVertex; i++) {
            if (vertex[i].vLabel == v) {
                return i;
            }
        }

        return -1;
    }

    public void addEdge(int v1, int v2) {

        int index1 = findVertex(v1);
        int index2 = findVertex(v2);

        if (index1 != -1 && index2 != -2) {
            adjMat[index1][index2] = 1;
            adjMat[index2][index1] = 1;
        }
    }

    public void printMatrix() {

        for (int i = 0; i < noOfVertex; i++) {
            System.out.println();
            for (int j = 0; j < noOfVertex; j++) {
                System.out.print("\t" + adjMat[i][j]);
            }
        }
    }

    public GNode getAdjNode(GNode node) {

        int index = findVertex(node.vLabel);

        if (index != -1) {
            for (int i = 0; i < noOfVertex; i++) {
                if (adjMat[index][i] == 1 && !vertex[i].isVisited) {
                    // System.out.println("GetAdj: " + vertex[i].vLabel);
                    return vertex[i];
                }
            }
        }

        return null;
    }

    public void DFS() {
        System.out.print("DFS: ");
        for (int i = 0; i < noOfVertex; i++) {
            if (!vertex[i].isVisited) {
                stack.add(vertex[i]);
                while (!stack.isEmpty()) {
                    GNode tmp = stack.pop();
                    if (!tmp.isVisited) {
                        tmp.isVisited = true;
                        System.out.print("\t" + tmp.vLabel);

                        // get adjacent node
                        GNode t2 = getAdjNode(tmp);
                        if (t2 != null) {
                            stack.add(t2);
                        }
                    }
                }
            }
        }

        for (int i = 0; i < noOfVertex; i++) {
            vertex[i].isVisited = false;
        }
    }

    public void BFS() {
        System.out.print("\nBFS: ");
        for (int i = 0; i < noOfVertex; i++) {
            if (!vertex[i].isVisited) {
                vertex[i].isVisited = true;
                System.out.print("\t" + vertex[i].vLabel);
                queue.enqueue(vertex[i]);
                while (!queue.isEmpty()) {
                    GNode tmp = queue.dequeue();
                    GNode v = null;
                    tmp.isVisited = true;
                    while ((v = getAdjNode(tmp)) != null) {
                        v.isVisited = true;
                        System.out.print("\t" + v.vLabel);
                        queue.enqueue(v);
                    }
                }
            }
        }
        System.out.println();
        for (int i = 0; i < noOfVertex; i++) {
            vertex[i].isVisited = false;
        }
    }

    /**
     * This section contains function to help implement Directed Graph
     * and topological sorting.
     */
    public void addDirectEdge(int v1, int v2) {

        int index1 = findVertex(v1);
        int index2 = findVertex(v2);

        if (index1 != -1 && index2 != -1) {
            adjMat[index1][index2] = 1;
        }
    }

    public int noSuccessor() {

        for (int i = 0; i < noOfVertex; i++) {
            boolean isVisited = false;
            for (int j = i; j < noOfVertex; j++) {
                if (adjMat[i][j] > 0) {
                    isVisited = true;
                    break;
                }
            }
            if (!isVisited) {
                return i;
            }
        }

        return -1;
    }

    public void deleteVertex(int index) {

        //int index = findVertex(v);
       
        if (index != noOfVertex - 1) {

           // System.out.println("No of Vertex: " + noOfVertex + "\tindex: " + index);
           
            for (int i = index; i < noOfVertex-1; i++) {
                vertex[i].vLabel = vertex[i + 1].vLabel;
           
                moveRowUp(i, noOfVertex); // shift all rows next to given vertex to 1 row up.
               
                moveColLeft(i, noOfVertex-1); // shift all column to 1 left from given vertex.

            }
        }

        noOfVertex--;

    }

    public void topologicalSorting(){
        int orig_nVerts = noOfVertex;
       
        while(noOfVertex > 0){
            int currVertex = noSuccessor();
           
            if(currVertex == -1){
                System.out.println("There is Cycle !!");
                return;
            }
           
            //System.out.println("Total Vertex: " + noOfVertex + "\tCurrent Vertex: " + vertex[currVertex].vLabel + "\tIndex: " + currVertex);
           
            // insert vertex label in sorted array (start at end)
            sortedArray[noOfVertex-1] = vertex[currVertex].vLabel;
           
            // delete vertex
            deleteVertex(currVertex);
           
            /*
            System.out.println();
            printMatrix();
            System.out.println();
             *
             */
        }
       
        System.out.print("Topological Sorted: ");
       
        for(int i=0; i            System.out.print("\t" + sortedArray[i]);
        }
       
        System.out.println();
    }
    // ------------------
    private void moveRowUp(int row, int length) {
        for (int col = 0; col < length; col++) {
            adjMat[row][col] = adjMat[row + 1][col];
        }
    }
// ------------------

    private void moveColLeft(int col, int length) {
        for (int row = 0; row < length; row++) {
            adjMat[row][col] = adjMat[row][col + 1];
        }
    }
// ------------------------------------------------------------


    public static void main(String args[]) {

        AdjMatGraph graph = new AdjMatGraph();
        Scanner stdin = new Scanner(new BufferedInputStream(System.in));

        System.out.println("Please enter the #vertex #Edges !!");
        graph.setNoVertex(stdin.nextInt());
        graph.setNoEdges(stdin.nextInt());

        System.out.println("Please enter the Edges And enter non-numeric character to end !!");

        while (true) {
            if (stdin.hasNextInt()) {
                //System.out.println(stdin.nextInt());
                graph.addEdge(stdin.nextInt(), stdin.nextInt());

                /* use this function to add edge in case graph is directed graph */

                // graph.addDirectEdge(stdin.nextInt(), stdin.nextInt());
            } else {
                break;
            }
        }

        graph.printMatrix();
        System.out.println("\n");
        graph.DFS();
        System.out.println();
        graph.BFS();


         
        // graph.topologicalSorting();
    }
}

Tuesday, November 22, 2011

Binary Tree Implementation (Java Code)

Node.java
/**
 *
 * @author santosh
 */

public class Node {
   
     Node left;
     Node right;
     Node parent;
     int     val;
     int     height;
     int     balanceFactor;
     int     NaV = -99999999; // not a value.
   
    public Node(){
        left = right = parent = null;
        val = height = balanceFactor = NaV;
    }
   
    public Node(int val){
        left = right = parent = null;
        this.val = val;
        height = balanceFactor = NaV;
    }
   
    public Node(int val, int key){
        left = right = parent = null;
        this.val = val;
        this.balanceFactor = key;
        height = NaV;
    }
}

BST.java

/**
 *
 * @author santosh
 */
public class BST {

    private Node root;
   
    public BST(){
        root = null;
    }
   
    /**
     * Insert a node in given tree.
     * @param val
     */
    public void insert(int val){
       
        Node t = new Node(val);
        if(root == null){
            root = t;
            return;
        }else{
            Node temp = root, prev = null;
            while(temp != null){
                prev = temp;
                if(val > temp.val){
                    temp = temp.right;
                }else{
                    temp = temp.left;
                }
            }
           
            t.parent = prev; // assign the parent to new node;
           
            if(val > prev.val)
                prev.right = t;
            else
                prev.left = t;
        }
        return;
    }
   
    /**
     * Find the node whose data is given.
     * @param t
     * @param val
     * @return
     */
    public Node findNode(Node t, int val){
       
        Node temp = null;
       
        if(t != null && t.val == val)
            return t;
       
        if(t.left != null)
            temp = findNode(t.left, val);
        if(temp == null & t.right != null)
            temp = findNode(t.right, val);
       
        return temp;
    }
   
    /**
     * Returns the min value in a non-empty binary search tree.
     * @param t
     * @return
     */
    public Node findMin(Node t){
       
        if(t != null && t.left == null)
            return t;
        else
            return findMin(t.left);
    }
   
    /**
     * Returns the min value in a non-empty binary search tree.
     * @param t
     * @return
     */
    public Node findMax(Node t){
       
        if(t != null && t.right == null)
            return t;
        else
            return findMax(t.right);
    }
   
    /**
     * Print path of each leaf node in recursive order.
     * @param sum
     * @param t
     * @return
     */
    public int printPath(int sum, Node t){
       
        while(t != null){
            System.out.print("\t" + t.val);
            sum += t.val;
            t = t.parent;
        }
        return sum;
    }
   
    /**
     * Print leaf nodes
     * @param t
     */
    public void printLeafNodes(Node t){
       
        if(t != null && t.left == null && t.right == null){
            System.out.print("\t" + t.val);
        }
       
        if(t != null){
            printLeafNodes(t.left);
            printLeafNodes(t.right);
        }
       
        return;
    }
   
    /**
     * find path for each leaf node
     * @param t
     */
    public void findPath(Node t){
        if(t != null && t.left == null && t.right == null) {
            System.out.print("Path: ");
            int sum = printPath(0, t);
            System.out.println("\tSum: " + sum);
        }
        if(t != null){
            findPath(t.left);
            findPath(t.right);
        }
        return;
    }
   
    /**
     * Check if any path has given sum.
     * @param t
     * @param sum
     * @return
     */
    public boolean hasPathSum(Node t, int sum){
        if(t == null)
            return (sum == 0);
        else{
            sum -= t.val;
            return hasPathSum(t.left, sum) || hasPathSum(t.right, sum);
        }
    }
   
    /**
     * Make mirror image of given tree.
     * @param t
     */
    public void mirrorTree(Node t){
       
        if(t == null)
            return;
       
        Node temp = null;
        mirrorTree(t.left);
        mirrorTree(t.right);
       
        temp = t.left;
        t.left = t.right;
        t.right = temp;
       
        return;
    }
   
    /**
     * For each node in a binary search tree, create a new duplicate node, and insert
     * the duplicate as the left child of the original node.
     * The resulting tree should still be a binary search tree. So the tree...
     *          2
     *         / \
     *        1   3
     * Is changed to...
     *          2
     *         / \
     *        2   3
     *      /    /
     *     1    3
     *    /
     *   1
     *
     **/
    public void doubleTree(Node t){
       
        if(t == null)
            return;
       
        Node oldLeft = null;
        doubleTree(t.left);
        doubleTree(t.right);
       
        oldLeft = t.left;
        t.left = new Node(t.val);
        t.left.parent = t; // assign parent to new node
        t.left.left = oldLeft;
        if(t.left.left != null)
            t.left.left.parent = t.left; // update the parent for old node
       
    }
   
    /**
     * Given two trees, return true if they are structurally identical.
     * @param t1
     * @param t2
     * @return
     */
    public boolean checkMatchingTree(Node t1, Node t2){
     
        // both empty
        if(t1 == null && t2 == null)
            return true;
       
        else if(t1 != null && t2 != null)
            return (t1.val == t2.val &&
                    checkMatchingTree(t1.left, t2.left) &&
                    checkMatchingTree(t1.right, t2.right));
        else // one of them empty
            return false;
    }
   
    /**
     * Count number of nodes in a given tree.
     * @param t
     * @return
     */
    public int countTNode(Node t){
       
        if(t == null)
            return 0;
        else
            return (countTNode(t.left) + 1 + countTNode(t.right));
           
    }
   
    /**
     * For the key values 1...numKeys, how many structurally unique binary
     * search trees are possible that store those keys?
     * Strategy: consider that each value could be the root.
     * Recursively find the size of the left and right subtrees.
     * @param key
     * @return
     */
    public int countTrees(int key){
       
        if(key <= 1)
            return 1;
        else{
            // there will be one value at the root, with whatever remains
            // on the left and right each forming their own subtrees.
            // Iterate through all the values that could be the root...
            int sum = 0;
            int lht, rht, rt = 0;
           
            for(rt=1; rt<=key; rt++ ){
                lht = countTrees(rt-1);
                rht = countTrees(key-rt);
               
                // number of possible trees with this root == left*right
                sum += lht * rht;
            }
           
            return sum;
        }
    }
   
    /**
     * Find the maximum depth of a given tree.
     * @param t
     * @return
     */
    public int maxDept(Node t){
       
        if(t == null)
            return 0;
       
        int lDepth = maxDept(t.left);
        int rDepth = maxDept(t.right);
       
        return (lDepth>rDepth)?(lDepth+1):(rDepth+1);
       
    }
   
    /**
     * Print the tree in In-Order.
     * @param t
     */
    public void printInOrder(Node t){
        if(t == null)
            return;
       
        printInOrder(t.left);
        System.out.print("\t"+t.val);
        printInOrder(t.right);
    }
   
    /**
     * print the tree in Post-Order.
     * @param t
     */
    public void printPostOrder(Node t){
        if(t == null)
            return;
       
        printPostOrder(t.left);
        printPostOrder(t.right);
        System.out.print("\t"+t.val);
       
    }
   
    /**
     * Print the tree in Pre-order.
     * @param t
     */
    public void printPreOrder(Node t){
        if(t == null)
            return;
       
        System.out.print("\t"+t.val);
        printPreOrder(t.left);
        printPreOrder(t.right);
    }
   
    /**
     * Get root of the node.
     * @return
     */
    public Node getRoot(){
        return root;
    }
}