Create an Adjacency matrix Graph and perform Add and Remove operation

import java.util.ArrayList;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Implementation of a directed unweighted Graph using Adjacency Matrix
 * 
 * Complexity: addEdge, removeEdge, hasEdge O(1) / outEdges, inEdges O(n) /
 * Space O(n^2)
 */
public class AdjMatrixGraph {
 int size;
 private boolean[][] matrix;
 public static final byte WHITE = 1;
 public static final byte GREY = 2;

 public AdjMatrixGraph(int size) {
  this.size = size;
  this.matrix = new boolean[size][size];
 }

 public void addEdge(int nodeA, int nodeB) {
  matrix[nodeA][nodeB] = true;
 }

 public void removeEdge(int nodeA, int nodeB) {
  matrix[nodeA][nodeB] = false;
 }

 public boolean hasEdge(int nodeA, int nodeB) {
  return matrix[nodeA][nodeB];
 }

 public List<Integer> outEdges(int i) {
  List<Integer> edges = new ArrayList<Integer>();
  for (int j = 0; j < size; j++) {
   if (matrix[i][j]) {
    edges.add(j);
   }
  }
  return edges;
 }

 public List<Integer> inEdges(int i) {
  List<Integer> edges = new ArrayList<Integer>();
  for (int j = 0; j < size; j++) {
   if (matrix[j][i]) {
    edges.add(j);
   }
  }
  return edges;
 }

 public int nVertices() {
  return size;
 }

 public void breadthFirstSearch(int root) {
  boolean[] seen = new boolean[nVertices()];
  Queue<Integer> q = new LinkedList<Integer>();
  q.add(root);
  seen[root] = true;
  while (!q.isEmpty()) {
   int i = q.remove();
   for (Integer j : outEdges(i)) {
    if (!seen[j]) {
     q.add(j);
     seen[j] = true;
    }
   }
  }
 }

 public void depthFirstSearch(int r) {
  byte[] c = new byte[nVertices()];
  Stack<Integer> s = new Stack<Integer>();
  s.push(r);
  while (!s.isEmpty()) {
   int i = s.pop();
   if (c[i] == WHITE) {
    c[i] = GREY;
    for (int j : outEdges(i))
     s.push(j);
   }
  }
 }

 public static void main(String[] args) {
  AdjMatrixGraph graph = new AdjMatrixGraph(10);

  graph.addEdge(1, 3);
  graph.addEdge(2, 4);
  graph.addEdge(6, 8);
  graph.addEdge(3, 2);

  System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8));
  System.out.println("Edge from 2 to 4 is : " + graph.hasEdge(2, 4));
  System.out.println("Edge from 3 to 2 is : " + graph.hasEdge(3, 2));
  System.out.println("Edge from 1 to 3 is : " + graph.hasEdge(1, 3));

  graph.removeEdge(6, 8);
  System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8));

 }
}

Output of this Program:

Edge from 6 to 8 is : true
Edge from 2 to 4 is : true
Edge from 3 to 2 is : true
Edge from 1 to 3 is : true
Edge from 6 to 8 is : false

Try this by Yourself : http://ideone.com/ZZm7rW

[ Read More ]

Implementation of a basic generic tree, with labels of type T - Data Structure

// This implements a basic generic tree, with labels of type T,
// pointer to the parent node, and a singly linked list of children nodes.

class Tree<T>  {
    private T label;
    private Tree<T> parent;
    private Tree<T> nextSibling; // next node on the list of parents's 
                                 //  children
    private Tree<T> firstChild;  // first in the linked list of children

                                 
//  Getters and setters
    public T getLabel() { return label; }  
    public void setLabel(T v) { label = v; }
    public Tree<T> getParent() { return parent;}
    public Tree<T> getNextSibling() { return nextSibling;}
    public Tree<T> getFirstChild() { return firstChild;}

// Add C to the front of the children of this
    public void addChild(Tree<T> c) {
         c.parent = this;
         if (firstChild == null) 
           firstChild = c;
         else {
             c.nextSibling = firstChild;
             firstChild = c;
            }
    }

// Check if the node is a leaf
    public boolean Leaf() { return firstChild==null; }

// `Convert the tree into a string. The structure is indicated by
// square brackets. Uses a preorder listing.
    public String toString() {
       String S = "[ " + label.toString();
       Tree<T> N = firstChild;
       while (N != null) {
          S = S + " " + N.toString();
          N = N.nextSibling;
        }
       return S+" ]";
     }

     public void displayPreorder() {
         displayPreorder1(0); }

     public void displayPreorder1(int Indent) {
         for (int I = 0; I < Indent; I++) System.out.print(" ");
         System.out.println(label.toString());
         Tree<T> N = firstChild;
         while (N != null) { 
            N.displayPreorder1(Indent+3);
            N = N.nextSibling;
           }
         }

     public void displayPostorder() {
         displayPostorder1(0); }

     public void displayPostorder1(int Indent) {
         Tree<T> N = firstChild;
         while (N != null) { 
            N.displayPostorder1(Indent+3);
            N = N.nextSibling;
           }
         for (int I = 0; I < Indent; I++) System.out.print(" ");
         System.out.println(label.toString());
         }
}

[ Read More ]

Stack implemented as array - Data Structure

// Stack implemented as array
public class ArrayStack<T> {
     private T[] stack;
     private int numElements = 0; // points to slot after top element

     public ArrayStack(T[] s) { stack = s; }  

     public boolean emptyStack() { 
         return numElements == 0; }
   
     public T  top() {
         return stack[numElements-1];
       }

     public void push(T x) {
         stack[numElements] = x;
         numElements++;
       }
  
     public T pop() {
         numElements--;
         return stack[numElements];
      }

    public static void main(String[] args) {
       ArrayStack<Integer> s = new ArrayStack<Integer>(new Integer[100]);
       s.push(2);
       s.push(3);
       s.push(5);
       System.out.println(s.top());
       System.out.println(s.pop());
       System.out.println(s.pop());
       s.push(15);
       s.push(22);
       System.out.println(s.pop());
   }
}

[ Read More ]

Singly linked list with header - Data Structure

class OrderedList  {
   private int value;
   private OrderedList next;

// Note: No setValue() method or setNext() methods are provided, 
// since those could require reordering the list.
  
   public int getValue() {
       return value; }

   public OrderedList getNext() {
       return next; }

// If X is in the list, returns the previous node.
// If X is not in the list, returns the node for the greatest element less 
// than  X.

   public OrderedList searchBefore(int x) { // Locate node containing X
       OrderedList n = this;
       while (true) {
          if (n.next==null) return n;
          if (n.next.value >= x) return n;
          n = n.next;
         } 
      }

// Is element x in the list. Note the use of the left to right evaluation of 
// && (if the condition n.net != null is false, then the conjunction returns
// false without evaluating n.next.value=x.

   public boolean inList(int x) {
       OrderedList n = searchBefore(x);
       return n.next != null && n.next.value == x; }

// Adds x to the ordered list, if it is not already there.
   public void add(int x) {
       OrderedList n = searchBefore(x);
       if (n.next == null || n.next.value != x) {
           OrderedList newNode = new OrderedList();
           newNode.value = x;
           newNode.next = n.next;
           n.next = newNode;
         }
     }
       
// Deletes X from the ordered list, if it is there.

   public void delete(int x) {
       OrderedList n = searchBefore(x);
       if (n.next != null && n.next.value == x)
          n.next = n.next.next;
      }



   public String toString() {
          OrderedList a = next;
          String s = "[";
          while (a != null) {
             s = s + a.value + " ";
             a = a.next;
           }
         return s+ "]";
         }

   public static void main(String[] args) {
      OrderedList l = new OrderedList();
      l.add(31);
      l.add(41);
      l.add(59);
      l.add(26);
      l.add(53);
      l.add(58);
      l.add(37);
      l.delete(53);
      System.out.println(l.toString());
}
}

[ Read More ]

Ordered array of ints with no repetition - Data Structure

public class OrderedArray {

   private int numElements = 0;
   private int[] elements;

// Constructor..Note: the caller has to provide the array of elements.
// This is because Java generics do not allow a call "elements = new T[100]".
//
   public OrderedArray(int[] elts) {
        elements = elts; }

   public int getNumElements() { return numElements; } 

   public int nth(int n) { // return the Nth element
       if (n < numElements) return elements[n]; else return -1; }
  
   public int first() { return nth(0); } 
   public int  last() { return nth(numElements-1); } 

//  search(X) returns the index where X is, if X is in the list.
//  Otherwise, it returns the index of the smallest number greater than X
   public int search(int x) {
       if (numElements==0) return 0;
       if (x <= first()) return 0;
       if (x > last()) return numElements;
       if (x == last()) return numElements-1;
       return search1(x,0,numElements-1); 
     }

// X is strictly between L and U.
   public int search1(int x,int l,int u) {
        if (u==l+1) return u;
        else {
           int m = (l+u)/2;
           if (x==elements[m]) return m;
           else if (x < elements[m]) return  search1(x,l,m);
           else return search1(x,m,u);
        }
     }

   public boolean inList(int x) {
       return (elements[search(x)]==x); }

   public void add(int x) {
      int i = search(x);
      if (elements[i] != x)  {
        for (int j = numElements; j>i; j--)
           elements[j]=elements[j-1];
        elements[i]=x;
        numElements++;
       }
     }

   public void delete(int x) {
      int i = search(x);
      if (elements[i] == x) {
        for (int j=i+1; j < numElements; j++)
          elements[j-1] = elements[j];
        numElements--;
      }
    }


   public String toString() {
      String s = "[";
      for (int i=0; i < numElements; i++)
         s = s + " " + elements[i];
      return s+"]";
   }

   public static void main(String[] args) {
      OrderedArray l = new OrderedArray(new int[100]);
      l.add(31);
      l.add(41);
      l.add(59);
      l.add(26);
      l.add(53);
      l.add(58);
      l.add(37);
      l.delete(53);
      System.out.println(l.toString());
      System.out.println(l.search(2));
      System.out.println(l.search(26));
      System.out.println(l.search(53));
      System.out.println(l.search(54));
      System.out.println(l.search(195));
}
}

[ Read More ]