Sunday, 4 September 2011

Unit-V Data Structures

Selection Sort In Java

Introduction
In this example we are going to sort the values of an array using selection sort.
In selection sorting algorithm, find the minimum value in the array then swap it first position. In next step leave the first value and find the minimum value within remaining values. Then swap it with the value of minimum index position. Sort the remaining values by using same steps. Selection sort is probably the most intuitive sorting algorithm to invent.

The complexity of selection sort algorithm is in worst-case, average-case, and best-case run-time of Θ(n2), assuming that comparisons can be done in constant time.

Code description:
In selection sort algorithm to find the minimum value in the array. First assign minimum index in key (index_of_min=x). Then find the minimum value and assign the index of minimum value in key (index_of_min=y). Then swap the minimum value with the value of minimum index.
At next iteration leave the value of minimum index position and sort the remaining values by following same steps.

Working of the selection sort :
Say we have an array unsorted A[0],A[1],A[2]................ A[n-1] and A[n] as input. Then the following steps are followed by selection sort algorithm to sort the values of an array . (Say we have a key index_of_min that indicate the position of minimum value)
1.Initaily varaible index_of_min=0;
2.Find the minimum value in the unsorted array.
3.Assign the index of the minimum value into index_of_min variable.
4.Swap minimum value to first position.
5.Sort the remaining values of array (excluding the first value).
The code of the program :

public class selectionSort{
  public static void main(String a[]){
  int i;
  int array[] = {12,9,4,99,120,1,3,10};
  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Selection Sort\n\n");
  System.out.println("Values Before the sort:\n");
  for(i = 0; i < array.length; i++)
  System.out.print( array[i]+"  ");
  System.out.println();
  selection_srt(array, array.length);
  System.out.print("Values after the sort:\n");
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println();
  System.out.println("PAUSE");
  }

  public static void selection_srt(int array[], int n){
  for(int x=0; x<n; x++){
  int index_of_min = x;
  for(int y=x; y<n; y++){
  if(array[index_of_min]<array[y]){
  index_of_min = y;
  }
  }
  int temp = array[x];
  array[x] = array[index_of_min];
  array[index_of_min] = temp;
  }
  }
}

Output of the example:

C:\array\sorting>javac selectionSort.java

C:\array\sorting>java selectionSort

       RoseIndia

       Selection Sort

Values Before the sort:

12  9  4  99  120  1  3  10

Values after the sort:

120  99  12  10  9  4  3  1

PAUSE

C:\array\sorting>_

Download this example.

Insertion Sort In Java

Introduction
In this example we are going to sort integer values of an array using insertion sort.

Insertion sorting algorithm is similar to bubble sort. But insertion sort is more efficient than bubble sort because in insertion sort the elements comparisons are less as compare to bubble sort. In insertion sorting algorithm compare the value until all the prior elements are lesser than compared value is not found. This mean that the all previous values are lesser than compared value. This algorithm is more efficient than the bubble sort .Insertion sort is a good choice for small values and for nearly-sorted values. There are more efficient algorithms such as quick sort, heap sort, or merge sort for large values .
Positive feature of insertion sorting:
1.It is simple to implement
2.It is efficient on (quite) small data values
3.It is efficient on data sets which are already nearly sorted.

The complexity of insertion sorting is O(n) at best case of an already sorted array and O(n²) at worst case .

Code description:
In insertion sorting take the element form left assign value into a variable. Then compare the value with previous values. Put value so that values must be lesser than the previous values. Then assign next value to a variable and follow the same steps relatively until the comparison not reached to end of array.
Working of insertion sorting:

The code of the program :

public class InsertionSort{
  public static void main(String a[]){
  int i;
  int array[] = {12,9,4,99,120,1,3,10};
  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Selection Sort\n\n");
  System.out.println("Values Before the sort:\n");
  for(i = 0; i < array.length; i++)
  System.out.print( array[i]+"  ");
  System.out.println();
  insertion_srt(array, array.length);
  System.out.print("Values after the sort:\n");
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println();
  System.out.println("PAUSE");
  }

  public static void insertion_srt(int array[], int n){
  for (int i = 1; i < n; i++){
  int j = i;
  int B = array[i];
  while ((j > 0) && (array[j-1] > B)){
  array[j] = array[j-1];
  j--;
  }
  array[j] = B;
  }
  }
}

Output of the example:

C:\array\sorting>javac InsertionSort.java

C:\array\sorting>java InsertionSort

       RoseIndia

       Selection Sort

Values Before the sort:

12  9  4  99  120  1  3  10

Values after the sort:

1  3  4  9  10  12  99  120

PAUSE

C:\array\sorting>_

Download this example.

Quick Sort in Java

Introduction
In this example we are going to sort integer values of an array using quick sort.

Quick sort algorithm is developed by C. A. R. Hoare. Quick sort is a comparison sort. The working of quick sort algorithm is depending on a divide-and-conquer strategy. A divide and conquer strategy is dividing an array into two sub-arrays. Quick sort is one of the fastest and simplest sorting algorithm. The complexity of quick sort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).
Code description:
In quick sort algorithm pick an element from array of elements. This element is called the pivot. Then compare the the values from left to right until a greater element is find then swap the values. Again start comparison from right with pivot. When lesser element is find then swap the values. Follow the same steps until all elements which are less than the pivot come before the pivot and all elements greater than the pivot come after it. After this partitioning, the pivot is in its last position. This is called the partition operation. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

Working of quick sort algorithm:
Input:12 9 4 99 120 1 3 10 13

Output:1 3 4 10 12 13 99 120
The code of the program :

public class QuickSort{
  public static void main(String a[]){
  int i;
  int array[] = {12,9,4,99,120,1,3,10,13};

  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Quick Sort\n\n");
  System.out.println("Values Before the sort:\n");
  for(i = 0; i < array.length; i++)
  System.out.print( array[i]+"  ");
  System.out.println();
  quick_srt(array,0,array.length-1);
  System.out.print("Values after the sort:\n");
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println();
  System.out.println("PAUSE");
  }

  public static void quick_srt(int array[],int low, int n){
  int lo = low;
  int hi = n;
  if (lo >= n) {
  return;
  }
  int mid = array[(lo + hi) / 2];
  while (lo < hi) {
  while (lo<hi && array[lo] < mid) {
  lo++;
  }
  while (lo<hi && array[hi] > mid) {
  hi--;
  }
  if (lo < hi) {
  int T = array[lo];
  array[lo] = array[hi];
  array[hi] = T;
  }
  }
  if (hi < lo) {
  int T = hi;
  hi = lo;
  lo = T;
  }
  quick_srt(array, low, lo);
  quick_srt(array, lo == low ? lo+1 : lo, n);
  }
}

Output of the example:

C:\array\sorting>javac QuickSort.java

C:\array\sorting>java QuickSort

       RoseIndia

       Quick Sort

Values Before the sort:

12  9  4  99  120  1  3  10  13

Values after the sort:

1  3  4  9  10  12  13  99  120

PAUSE

C:\array\sorting>_

Download this example.

Merge Sort in Java

Introduction
In this example we are going to sort integer values of an array using merge sort.

In merge sorting algorithm unsorted values are divided into two equal parts iteratively. Then merge both parts and sort it. Then again merge the next part and sort it. Do it iteratively until the values are not in sorted order. In merge sorting the number of elements must be even. The merge sorting is invented by John von Neumann in 1945 .
The complexity of the merge sorting is in worst-case O(n log n) and in average case O(n log n).

Code description:
In merge sort split the array values in halves recursively until each half has only single element. Merge the two 1/2 values together and sort the values. Do same steps iteratively until the values are not sorted.

Working of merge sort algorithm:
Say we have an array unsorted A[0],A[1],A[2]................ A[n-1] and A[n] as input. Then the following steps are followed by merge sort algorithm to sort the values of an array.

Step1:Spliting the values of array
Divide the values into two equal 1/2
A[0],A[1],A[2].........A[n/2-1] & A[n/2]....... .................A[n-1], A[n]

Again divide two equal 1/2
A[0] a[1]A[2]..............A[(n/2-1)/2-1] & A[(n/2-1)/2]............A[n/2-1],
A[n/2].............A[(2n-1)/2-1] & a[(2n-1)/2].............A[n-1],A[n]
..........................................................................................................................
..........................................................................................................................
........................................................................................................................
A[0] & A[1] & A[2]& A[3],..............................................................A[n-1]& A[n]

Step2:Merge two values and sort the values

A[0],A[1] & A[2],A[3]&..................................................................&A[n-1],A[n]
If A[1]<A[0],A[]<A[3]........................................................................A[n-1]>A[n]
then
A[1]A[0],A[2]A[3],...............................................................................A[n]A[n-1]
Step3:Merge four values and sort the values
A[2] A[1] A[0] A[3],...................................................................................A[n-1]
..................................................................................................................
..................................................................................................................
.................................................................................................................
Step3:Merge n values and sort the values
A[2]A[6]......................................................................................................A[n-5]

Where n must be even number.

Steps of Merge Sort:

Say unsorted an array values are:
12,9,4,99,120,1,3,10

The code of the program :

public class mergeSort{
  public static void main(String a[]){
  int i;
  int array[] = {12,9,4,99,120,1,3,10};
  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Selection Sort\n\n");
  System.out.println("Values Before the sort:\n");
  for(i = 0; i < array.length; i++)
  System.out.print( array[i]+"  ");
  System.out.println();
  mergeSort_srt(array,0, array.length-1);
  System.out.print("Values after the sort:\n");
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println();
  System.out.println("PAUSE");
  }

  public static void mergeSort_srt(int array[],int lo, int n){
  int low = lo;
  int high = n;
  if (low >= high) {
  return;
  }

  int middle = (low + high) / 2;
  mergeSort_srt(array, low, middle);
  mergeSort_srt(array, middle + 1, high);
  int end_low = middle;
  int start_high = middle + 1;
  while ((lo <= end_low) && (start_high <= high)) {
  if (array[low] < array[start_high]) {
  low++;
  } else {
  int Temp = array[start_high];
  for (int k = start_high- 1; k >= low; k--) {
  array[k+1] = array[k];
  }
  array[low] = Temp;
  low++;
  end_low++;
  start_high++;
  }
  }
  }
}

Output of the example:

C:\array\sorting>javac mergeSort.java

C:\array\sorting>java mergeSort

       RoseIndia

       Selection Sort

Values Before the sort:

12  9  4  99  120  1  3  10

Values after the sort:

1  3  4  9  10  12  99  120

PAUSE

C:\array\sorting>_

Download this example.

Linear Search in Java

In this section, we are going to find an element from an array using Linear Searching. Linear searching is a good way to find an element from the array. The array can be of any order, it checks whether a certain element (number , string , etc. ) is in a specified array or not. Basically it is used for small arrays. In the given code, we have allowed the user to enter the numbers to be stored into the arrays. If the element is found we can return the index where the element is located in the array. If the element is not found we can return -1.

Here is the code:

import java.util.*;

public class LinearSearch {
public int find(final int[] data, final int key) {
for (int i = 0; i < data.length; ++i) {
if (data[i] > key)
return -1;
else if (data[i] == key)
return i;
}
return -1;

}

public static void main(String[] args) {
final int arr[] = new int[10];
System.out.println("Enter 10 numbers");
Scanner input = new Scanner(System.in);
for (int i = 0; i < arr.length; i++) {
arr[i] = input.nextInt();
}
LinearSearch search = new LinearSearch();
System.out.print("Enter the element to search: ");
int num=input.nextInt();
int n = search.find(arr, num);
if ((n >= 0) && (n < arr.length)) {
System.out.println("Found at index: " + n);
} else {
System.out.println("Not Found");
}
}

}

Output:

Enter 10 numbers:

Enter the element to search:5

Found at index: 4

Binary Search in Java

In this section, we are going to search an element from an array using Binary Search. The advantage of a binary search over a linear search is astounding for large numbers. It can be done either recursively or iteratively. In the given code, we have allowed the user to enter the numbers to be stored into the array.Then we start the search from the middle element of the array. If the middle element is equal to the searched value, the algorithm stops otherwise we have two cases:

1)If searched value is less than the middle element. In this case, again get the middle element of the first half of the specified array.
2)If searched value is greater, than the middle element. In this case, again get the middle element of the second half of the specified array.
This will continue until we get the searched element.

Here is the code:

import java.util.*;

public class BinarySearch {
public static void main(String[] args) {
int[] intArray = new int[10];
int searchValue = 0, index;
System.out.println("Enter 10 numbers");
Scanner input = new Scanner(System.in);
for (int i = 0; i < intArray.length; i++) {
intArray[i] = input.nextInt();
}
System.out.print("Enter a number to search for: ");
searchValue = input.nextInt();
index = binarySearch(intArray, searchValue);
if (index != -1) {
System.out.println("Found at index: " + index);
} else {
System.out.println("Not Found");
}
}

static int binarySearch(int[] search, int find) {
int start, end, midPt;
start = 0;
end = search.length - 1;
while (start <= end) {
midPt = (start + end) / 2;
if (search[midPt] == find) {
return midPt;
} else if (search[midPt] < find) {
start = midPt + 1;
} else {
end = midPt - 1;
}
}
return -1;
}
}

Output

Enter 10 numbers:

Enter a number to search for:5

Found at index: 4

Implementing a Stack in Java

In this section, you will learn how to implement a stack in Java. A Stack is like a bucket in which you can put elements one-by-one in sequence and retrieve elements from the bucket according to the sequence of the last entered element. Stack is a collection of data and follows the LIFO (Last in, first out) rule that mean you can insert the elements one-by-one in sequence and the last inserted element can be retrieved at once from the bucket. Elements are inserted and retrieved to/from the stack through the push() and pop() method.
This program implements a stack and follows the LIFO rule. It asks you for the number of elements which have to be entered in the stack and then it takes elements for insertion in the stack. All the elements present in the stack are shown from the last inserted element to the first inserted element.
Stack<Integer>():
Above constructor of the Stack class creates a empty stack which holds the integer type value which is mention with the creation of stack. The Stack class extends the Vector class and both classes are implemented from the java.util.*; package.
Stack.push(Object obj):
Above method is used to insert or push the data or element in the stack. It takes an object like: data or elements and push its onto the top of the stack.
Stack.pop():
This is the method to removes the objects like: data or elements at the top positions of stack.
Here is the code of program:

import java.io.*;
import java.util.*;

public class StackImplement{
  Stack<Integer> stack;
  String str;
  int num, n;
  public static void main(String[] args){
  StackImplement q = new StackImplement();
  }
  public StackImplement(){
  try{
  stack = new Stack<Integer>();
  InputStreamReader ir = new InputStreamReader(System.in);
  BufferedReader bf = new BufferedReader(ir);
  System.out.print("Enter number of elements : ");
  str = bf.readLine();
  num = Integer.parseInt(str);
  for(int i = 1; i <= num; i++){
  System.out.print("Enter elements : ");
  str = bf.readLine();
  n = Integer.parseInt(str);
  stack.push(n);
  }
  }
  catch(IOException e){}
  System.out.print("Retrieved elements from the stack : ");
  while (!stack.empty()){
  System.out.print(stack.pop() + "  ");
  }
  }
}

Download this example

Implement the Queue in Java

In this section, you will learn how to implement the queue. A queue holds a collection of data or elements and follows the FIFO ( First In First Out) rule. The FIFO that means which data added first in the list, only that element can be removed or retrieved first from the list. In other sense, You can remove or perform operation on that data which had been added first in the Collection (list). Whenever you need to remove the last added element then you must remove all these elements which are entered before the certain element.
The given program implements a queue. It takes all elements as input by user. These values are added to the list and shows first, last and the rest elements present in the list separately. Some methods and APIs are explained below which have been used in the program for the certain purposes:
LinkedList<Integer>():
This is the constructor of the LinkedList class. This class is used by importing the java.util.*; package. This constructor is used for constructing an empty list. It can contain integer types data in the given program because in the declaration of the LinkedList class type checking has been used. This is an implementation of the List interface of the Collections Framework. The LinkeedList class provides inserting and deleting the data to/from the list.
removeFirst():
Above method removes and returns the first element of the list.
removeLast():
Above method removes and returns the last element of the list.
list.isEmpty():
This method checks whether the list is empty or not.
remove():
This method used to remove the elements in the list in a specified sequence.
Here is the code of program:

import java.io.*;
import java.util.*;

public class QueueImplement{
  LinkedList<Integer> list;
  String str;
  int num;
  public static void main(String[] args){
  QueueImplement q = new QueueImplement();
  }
  public QueueImplement(){
  try{
  list = new LinkedList<Integer>();
  InputStreamReader ir = new InputStreamReader(System.in);
  BufferedReader bf = new BufferedReader(ir);
  System.out.println("Enter number of elements : ");
  str = bf.readLine();
  if((num = Integer.parseInt(str)) == 0){
  System.out.println("You have entered either zero/null.");
  System.exit(0);
  }
  else{
  System.out.println("Enter elements : ");
  for(int i = 0; i < num; i++){
  str = bf.readLine();
  int n = Integer.parseInt(str);
  list.add(n);
  }
  }
  System.out.println("First element :" + list.removeFirst());
  System.out.println("Last element :" + list.removeLast());
  System.out.println("Rest elements in the list :");
  while(!list.isEmpty()){
  System.out.print(list.remove() + "\t");
  }
  }
  catch(IOException e){
  System.out.println(e.getMessage() + " is not a legal entry.");
  System.exit(0);
  }
  }
}

Download
this example

Circular Queue:
import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public final class CircularQueue extends AbstractCollection {

  // This is the largest capacity allowed by this implementation
  private static final int MAX_CAPACITY = 1 << 30;
  private static final int DEFAULT_CAPACITY = 1 << 8;

  private int size          = 0;
  private int producerIndex = 0;
  private int consumerIndex = 0;

  // capacity must be a power of 2 at all times
  private int capacity;
  private int maxCapacity;

  // we mask with capacity -1.  This variable caches that values
  private int bitmask;

  private Object[] q;

  public CircularQueue() {
    this(DEFAULT_CAPACITY);
  }

  // Construct a queue which has at least the specified capacity.  If
  // the value specified is a power of two then the queue will be
  // exactly the specified size.  Otherwise the queue will be the
  // first power of two which is greater than the specified value.
  public CircularQueue(int c) {
    this(c, MAX_CAPACITY);
  }

  public CircularQueue(int c, int mc) {
    if (c > mc) {
      throw new IllegalArgumentException("Capacity greater than maximum");
    }

    if (mc > MAX_CAPACITY) {
      throw new IllegalArgumentException("Maximum capacity greater than " +
        "allowed");
    }

    for (capacity = 1; capacity < c; capacity <<= 1) ;
    for (maxCapacity = 1; maxCapacity < mc; maxCapacity <<= 1) ;

    bitmask = capacity - 1;
    q = new Object[capacity];
  }

  // Constructor used by clone()
  private CircularQueue(CircularQueue oldQueue) {
    size = oldQueue.size;
    producerIndex = oldQueue.producerIndex;
    consumerIndex = oldQueue.consumerIndex;
    capacity = oldQueue.capacity;
    maxCapacity = oldQueue.maxCapacity;
    bitmask = oldQueue.bitmask;
    q = new Object[oldQueue.q.length];
    System.arraycopy(oldQueue.q, 0, q, 0, q.length);
  }

  private boolean expandQueue() {
    // double the size of the queue
    // This design assumes that this is a rare case

    if (capacity == maxCapacity) {
      return false;
    }

    int old_capacity = capacity;
    Object[] old_q    = q;

    capacity += capacity;
    bitmask   = capacity - 1;
    q         = new Object[capacity];

    System.arraycopy(old_q, consumerIndex, q, 0, old_capacity - consumerIndex);

    if (consumerIndex != 0) {
      System.arraycopy(old_q, 0, q, old_capacity - consumerIndex,
        consumerIndex);
    }

    consumerIndex = 0;
    producerIndex = size;

    return true;
  }

  public boolean add(Object obj) {
    if (size == capacity) {
      // no room
      if (!expandQueue()) return false;
    }

    size++;
    q[producerIndex] = obj;

    producerIndex = (producerIndex + 1) & bitmask;

    return true;
  }

  public Object remove() {
    Object obj;

    if (size == 0) return null;

    size--;
    obj = q[consumerIndex];
    q[consumerIndex] = null; // allow gc to collect

    consumerIndex = (consumerIndex + 1) & bitmask;

    return obj;
  }

  public boolean isEmpty() { return size == 0; }

  public int size() { return size; }

  public int capacity() { return capacity; }

  public Object peek() {
    if (size == 0) return null;
    return q[consumerIndex];
  }

  public void clear() {
    Arrays.fill(q, null);
    size = 0;
    producerIndex = 0;
    consumerIndex = 0;
  }

  public Object clone() {
    return new CircularQueue(this);
  }

  public String toString() {
    StringBuffer s = new StringBuffer(super.toString() + " - capacity: '" +
      capacity() + "' size: '" + size() + "'");

    if (size > 0) {
      s.append(" elements:");
      for (int i = 0; i < size; ++i) {
        s.append('\n');
        s.append('\t');
        s.append(q[consumerIndex + i & bitmask].toString());
      }
    }

    return s.toString();
  }

  public Iterator iterator() {
    return new Iterator() {
      private final int ci = consumerIndex;
      private final int pi = producerIndex;
      private int s = size;
      private int i = ci;

      public boolean hasNext() {
        checkForModification();
        return s > 0;
      }

      public Object next() {
        checkForModification();
        if (s == 0) throw new NoSuchElementException();

        s--;
        Object r = q[i];
        i = (i + 1) & bitmask;

        return r;
      }

      public void remove() {
        throw new UnsupportedOperationException();
      }

      private void checkForModification() {
        if (ci != consumerIndex) throw new ConcurrentModificationException();
        if (pi != producerIndex) throw new ConcurrentModificationException();
      }
    };
  }
}
Dequeue:

import java.lang.reflect.Array;

class Deque<Item>

        private int maxSize=100;

        private final Item[] array;

        private int front,rear;

        private int numberOfItems;

        public Deque()

               array=(Item[])(new Object[maxSize]);

               front=0;

               rear=-1;

               numberOfItems=0;

        public boolean isEmpty()

               return (numberOfItems==0);

        public void addFirst(Item item)

               if(front==0)

                       front=maxSize;

               array[--front]=item;

               numberOfItems++;

        public void addLast(Item item)

               if(rear==maxSize-1)

                       rear=-1;

               array[++rear]=item;

               numberOfItems++;

        public Item removeFirst()

               Item temp=array[front++];

               if(front==maxSize)

                       front=0;

               numberOfItems--;

               return temp;

        public Item removeLast()

               Item temp=array[rear--];

               if(rear==-1)

                       rear=maxSize-1;

               numberOfItems--;

               return temp;

        public int getFirst()

               return front;

        public int getLast()

               return rear;

        public static void main(String[] args)

               Deque<String> element1=new Deque<String>();

               Deque<String> element2=new Deque<String>();

               for(int i=0;i<args.length;i++)

               element1.addFirst(args[i]);

               try {

               for(;element1.numberOfItems+1>0;)

                       String temp=element1.removeFirst();

                       System.out.println(temp);

               catch(Exception ex)

                       System.out.println("End Of Execution due to remove from empty queue");

               System.out.println();

               for(int i=0;i<args.length;i++)

               element2.addLast(args[i]);

               try {

               for(;element2.numberOfItems+1>0;)

                       String temp=element2.removeLast();

                       System.out.println(temp);

               catch(Exception ex)

                       System.out.println("End Of Execution due to remove from empty queue");

Priority Queue:

/**

 * This class implements a priority queue that fits into

 * the Java 1.2 Collection hierarchy. This is a min-based

 * priority queue though a max-based queue can be easily obtained

 * by supplying an alternative <code>Comparator</code> object when

 * the priority queue is constructed.

 * <P>

 * This implementation

 * supports O(log n) operations for all fundamental priority

 * queue operations: add and peek/remove;

 * the implementation uses a standard min-heap. There is no

 * restriction on inserting unique elements, so it is ok to insert

 * an element that is equal to an element already in the priority

 * queue. No guarantees are provided about which of two equal elements

 * is returned first by a peek/remove.

 * <P>

 * The elements in a priority queue must implement the

 * <code>Comparable</code> interface or else a

 * <code>Comparator</code> must be provided when the priority queue is

 * constructed.

 * <P>

 * For version 2.0: the methods have been renamed to be consistent

 * with the Queue interface and PriorityQueue implementation from

 * Java 5. This class should be drop-in/compatible with the Java

 * 5 priority queue except this class doesn't support generics. In

 * addition, this class does not implement methods <code>poll</code>

 * or <code>offer</code> from the Java 5 Queue interface. Instead,

 * it provides <code>add</code> and <code>remove</code>.

 * <P>

 * @author Owen Astrachan

 * @version 1.0, July 2000

 * @version 2.0, October 2004

*/

import java.util.*;

public class PriorityQueue extends AbstractCollection

    private static class DefaultComparator implements Comparator

        public int compare (Object o1, Object o2)

            return ((Comparable) o1).compareTo(o2);

    private Comparator myComp = new DefaultComparator();

    private int        mySize;

    private ArrayList  myList;

/**

     * This is a trivial iterator class that returns

     * elements in the PriorityQueue ArrayList field

     * one-at-a-time

*/

    private class PQItr implements Iterator

        public Object next()

            return myList.get(myCursor);

        public boolean hasNext()

            return myCursor <= mySize;

        public void remove()

            throw new UnsupportedOperationException("remove not implemented");

        private int myCursor = 1;

/**

     * constructs an empty priority queue, when new elements

     * are added their natural order will be used to determine

     * which is minimal. This means elements that are added must

     * implement the <code>Comparable</code> interface and must

     * be <em>mutually comparable</em>, i.e.,

     * <code>e1.compareTo(e2)</code> must not throw a

     * <code>CastCastException</code> for any two elements <code>e1</code>

     * and <code>e2</code> in the priority queue.

*/

    public PriorityQueue()

        myList = new ArrayList(32);

        myList.add(null);             // first slot has index 1

        mySize = 0;

/**

     * constructs an empty priority queue, when new elements

     * are added the <code>Comparator comp</code> determines which is

     * smaller.

     * @param comp is the <code>Comparator</code> used in determining order

*/

    public PriorityQueue(Comparator comp)

        this();

        myComp = comp;

/**

     * all elements in coll are added to the priority queue. The

     * complexity is O(n) where <code>coll.size() == n</code>

     * @param coll is a collection of mutually comparable elements

*/

    public PriorityQueue(Collection coll)

        this();

        myList.addAll(coll);

        mySize = coll.size();

        for(int k=coll.size()/2; k >= 1; k--)

            heapify(k);

/**

     * A new element <code>o</code> is added to the priority queue

     * in O(log n) time where n is the size of the priority queue.

     * <P>

     * The return value should be ignored, a boolean value must be

     * returned because of the requirements of the

     * <code>Collection</code> interface.

     * @param o is the (Comparable) object added to the priority queue

     * @return true

*/

    public boolean add(Object o)

        myList.add(o);        // stored, but not correct location

        mySize++;             // added element, update count

        int k = mySize;       // location of new element

        while (k > 1 && myComp.compare(myList.get(k/2), o) > 0)

            myList.set(k, myList.get(k/2));

            k /= 2;

        myList.set(k,o);

        return true;

/**

     * @return the number of elements in the priority queue

*/

    public int size()

        return mySize;

/**

     * @return true if and only if the priority queue is empty

*/

    public boolean isEmpty()

        return mySize == 0;

/**

     * The smallest/minimal element is removed and returned

     * in O(log n) time where n is the size of the priority queue.

     * @return the smallest element (and removes it)

*/

    public Object remove()

        if (! isEmpty())

            Object hold = myList.get(1);

            myList.set(1, myList.get(mySize));  // move last to top

            myList.remove(mySize);              // pop last off

            mySize--;

            if (mySize > 1)

                heapify(1);

            return hold;

        return null;

/**

     * Executes in O(1) time, returns smallest element

     * @return the minimal element in the priority queue

*/

    public Object peek()

        return myList.get(1);

/**

     * The order of the elements returned by the iterator is not specified

     * @return an iterator of all elements in priority queue

*/

    public Iterator iterator()

        return new PQItr();

/**

     * works in O(log(size()-vroot)) time

     * @param vroot is the index at which re-heaping occurs

     * @precondition: subheaps of index vroot are heaps

     * @postcondition: heap rooted at index vroot is a heap

*/

    private void heapify(int vroot)

        Object last = myList.get(vroot);

        int child, k = vroot;

        while (2*k <= mySize)

            child = 2*k;

            if (child < mySize &&

                        myComp.compare(myList.get(child),

                                       myList.get(child+1)) > 0)

                child++;

            if (myComp.compare(last, myList.get(child)) <= 0)

                break;

            else

                myList.set(k, myList.get(child));

                k = child;

        myList.set(k, last);

/**

     * simple test harnass that inserts all arguments into a

     * priority queue and then removes them one at a time and prints

     * them one per line as they are removed

     * thus effectively sorting in O(n log n) time

*/

    public static void main(String args[])

        PriorityQueue pq = new PriorityQueue(Arrays.asList(args));

        while (pq.size() > 0)

            System.out.println(pq.peek());

            pq.remove();

Converts infix arithmetic expressions to postfix :

import java.io.IOException;

public class InToPost {
  private Stack theStack;

  private String input;

  private String output = "";

  public InToPost(String in) {
    input = in;
    int stackSize = input.length();
    theStack = new Stack(stackSize);
  }

  public String doTrans() {
    for (int j = 0; j < input.length(); j++) {
      char ch = input.charAt(j);
      switch (ch) {
      case '+':
      case '-':
        gotOper(ch, 1);
        break; //   (precedence 1)
      case '*': // it's * or /
      case '/':
        gotOper(ch, 2); // go pop operators
        break; //   (precedence 2)
      case '(': // it's a left paren
        theStack.push(ch); // push it
        break;
      case ')': // it's a right paren
        gotParen(ch); // go pop operators
        break;
      default: // must be an operand
        output = output + ch; // write it to output
        break;
      }
    }
    while (!theStack.isEmpty()) {
      output = output + theStack.pop();

    }
    System.out.println(output);
    return output; // return postfix
  }

  public void gotOper(char opThis, int prec1) {
    while (!theStack.isEmpty()) {
      char opTop = theStack.pop();
      if (opTop == '(') {
        theStack.push(opTop);
        break;
      }// it's an operator
      else {// precedence of new op
        int prec2;
        if (opTop == '+' || opTop == '-')
          prec2 = 1;
        else
          prec2 = 2;
        if (prec2 < prec1) // if prec of new op less
        { //    than prec of old
          theStack.push(opTop); // save newly-popped op
          break;
        } else
          // prec of new not less
          output = output + opTop; // than prec of old
      }
    }
    theStack.push(opThis);
  }

  public void gotParen(char ch){
    while (!theStack.isEmpty()) {
      char chx = theStack.pop();
      if (chx == '(')
        break;
      else
        output = output + chx;
    }
  }

  public static void main(String[] args) throws IOException {
    String input = "1+2*4/5-7+3/6";
    String output;
    InToPost theTrans = new InToPost(input);
    output = theTrans.doTrans();
    System.out.println("Postfix is " + output + '\n');

  }
  class Stack {
    private int maxSize;

    private char[] stackArray;

    private int top;

    public Stack(int max) {
      maxSize = max;
      stackArray = new char[maxSize];
      top = -1;
    }

    public void push(char j) {
      stackArray[++top] = j;
    }

    public char pop() {
      return stackArray[top--];
    }

    public char peek() {
      return stackArray[top];
    }

    public boolean isEmpty() {
      return (top == -1);
    }
  }

}

Parse postfix arithmetic expressions :

import java.io.IOException;

public class ParsePost {
  private Stack theStack;

  private String input;

  public ParsePost(String s) {
    input = s;
  }

  public int doParse() {
    theStack = new Stack(20);
    char ch;
    int j;
    int num1, num2, interAns;

    for (j = 0; j < input.length(); j++) {
      ch = input.charAt(j);
      theStack.displayStack("" + ch + " ");
      if (ch >= '0' && ch <= '9') // if a number push it
        theStack.push((int) (ch - '0'));
      else // it's an operator
      {
        num2 = theStack.pop();
        num1 = theStack.pop();
        switch (ch) {
        case '+':
          interAns = num1 + num2;
          break;
        case '-':
          interAns = num1 - num2;
          break;
        case '*':
          interAns = num1 * num2;
          break;
        case '/':
          interAns = num1 / num2;
          break;
        default:
          interAns = 0;
        }
        theStack.push(interAns);
      }
    }
    interAns = theStack.pop();
    return interAns;
  }

  public static void main(String[] args) throws IOException {
    String input = "1-2+3*4+5/6-7+8*9";
    int output;
    ParsePost aParser = new ParsePost(input);
    output = aParser.doParse();
    System.out.println("Evaluates to " + output);
  }
  class Stack {
    private int maxSize;

    private int[] stackArray;

    private int top;

    public Stack(int size) {
      maxSize = size;
      stackArray = new int[maxSize];
      top = -1;
    }

    public void push(int j) {
      stackArray[++top] = j;
    }

    public int pop() {
      return stackArray[top--];
    }

    public int peek() {
      return stackArray[top];
    }

    public boolean isEmpty() {
      return (top == -1);
    }

    public boolean isFull() {
      return (top == maxSize - 1);
    }

    public int size() {
      return top + 1;
    }

    public int peekN(int n) {
      return stackArray[n];
    }

    public void displayStack(String s) {
      System.out.print(s);
      System.out.print("Stack (bottom>top): ");
      for (int j = 0; j < size(); j++) {
        System.out.print(peekN(j));
        System.out.print(' ');
      }
      System.out.println("");
    }
  }
}

Linked List:

The LinkedList class extends AbstractSequentialList and implements the List interface. It provides a linked-list data structure. It has the two constructors, shown here:

LinkedList( )
LinkedList(Collection c)

The first constructor builds an empty linked list. The second constructor builds a linked list that is initialized with the elements of the collection c.

In addition to the methods that it inherits, the LinkedList class defines some useful methods of its own for manipulating and accessing lists. To add elements to the start of the list, use addFirst( ); to add elements to the end, use addLast( ). Their signatures are shown here:

void addFirst(Object obj)
void addLast(Object obj)

Here, obj is the item being added.

To obtain the first element, call getFirst( ). To retrieve the last element, call getLast( ). Their signatures are shown here:

Object getFirst( )
Object getLast( )

To remove the first element, use removeFirst( ); to remove the last element, call removeLast( ). They are shown here:

Object removeFirst( )
Object removeLast( )

The following program illustrates several of the methods supported by LinkedList:

// Demonstrate LinkedList.
import java.util.*;
class LinkedListDemo {
public static void main(String args[]) {
// create a linked list
LinkedList ll = new LinkedList();
// add elements to the linked list
ll.add("F");
ll.add("B");
ll.add("D");
ll.add("E");
ll.add("C");
ll.addLast("Z");
ll.addFirst("A");
ll.add(1, "A2");
System.out.println("Original contents of ll: " + ll);
// remove elements from the linked list
ll.remove("F");
ll.remove(2);
System.out.println("Contents of ll after deletion: " + ll);
// remove first and last elements
ll.removeFirst();
ll.removeLast();
System.out.println("ll after deleting first and last: " + ll);
// get and set a value
Object val = ll.get(2);
ll.set(2, (String) val + " Changed");
System.out.println("ll after change: " + ll);
}
}

The output from this program is shown here:

Original contents of ll: [A, A2, F, B, D, E, C, Z]
Contents of ll after deletion: [A, A2, D, E, C, Z]
ll after deleting first and last: [A2, D, E, C]
ll after change: [A2, D, E Changed, C]

Because LinkedList implements the List interface, calls to add(Object) append items to the end of the list, as does addLast( ). To insert items at a specific location, use the add(int, Object) form of add( ), as illustrated by the call to add(1, "A2") in the example. Notice how the third element in ll is changed by employing calls to get( ) and set( ). To obtain the current value of an element, pass get( ) the index at which the element is stored. To assign a new value to that index, pass set( ) the index and its new value.

Linked List 2:

  public class LinkedList {
  /**
   * This interface defines the methods required by any object that can be
   * linked into a linked list.
   */
  public interface Linkable {
    public Linkable getNext(); // Returns the next element in the list

    public void setNext(Linkable node); // Sets the next element in the list
  }

  // This class has a default constructor: public LinkedList() {}

  /** This is the only field of the class. It holds the head of the list */
  Linkable head;

  /** Return the first node in the list */
  public synchronized Linkable getHead() {
    return head;
  }

  /** Insert a node at the beginning of the list */
  public synchronized void insertAtHead(Linkable node) {
    node.setNext(head);
    head = node;
  }

  /** Insert a node at the end of the list */
  public synchronized void insertAtTail(Linkable node) {
    if (head == null)
      head = node;
    else {
      Linkable p, q;
      for (p = head; (q = p.getNext()) != null; p = q)
        /* no body */;
      p.setNext(node);
    }
  }

  /** Remove and return the node at the head of the list */
  public synchronized Linkable removeFromHead() {
    Linkable node = head;
    if (node != null) {
      head = node.getNext();
      node.setNext(null);
    }
    return node;
  }

  /** Remove and return the node at the end of the list */
  public synchronized Linkable removeFromTail() {
    if (head == null)
      return null;
    Linkable p = head, q = null, next = head.getNext();
    if (next == null) {
      head = null;
      return p;
    }
    while ((next = p.getNext()) != null) {
      q = p;
      p = next;
    }
    q.setNext(null);
    return p;
  }

  /**
   * Remove a node matching the specified node from the list. Use equals()
   * instead of == to test for a matched node.
   */
  public synchronized void remove(Linkable node) {
    if (head == null)
      return;
    if (node.equals(head)) {
      head = head.getNext();
      return;
    }
    Linkable p = head, q = null;
    while ((q = p.getNext()) != null) {
      if (node.equals(q)) {
        p.setNext(q.getNext());
        return;
      }
      p = q;
    }
  }

  /**
   * This is a test class that implements the Linkable interface
   */
  static class LinkableInteger implements Linkable {
    int i; // The data contained in the node

    Linkable next; // A reference to the next node in the list

    public LinkableInteger(int i) {
      this.i = i;
    } // Constructor

    public Linkable getNext() {
      return next;
    } // Part of Linkable

    public void setNext(Linkable node) {
      next = node;
    } // Linkable

    public String toString() {
      return i + "";
    } // For easy printing

    public boolean equals(Object o) { // For comparison
      if (this == o)
        return true;
      if (!(o instanceof LinkableInteger))
        return false;
      if (((LinkableInteger) o).i == this.i)
        return true;
      return false;
    }
  }

  /**
   * The test program. Insert some nodes, remove some nodes, then print
   * out all elements in the list. It should print out the numbers 4, 6,
   * 3, 1, and 5
   */
  public static void main(String[] args) {
    LinkedList ll = new LinkedList(); // Create a list
    ll.insertAtHead(new LinkableInteger(1)); // Insert some stuff
    ll.insertAtHead(new LinkableInteger(2));
    ll.insertAtHead(new LinkableInteger(3));
    ll.insertAtHead(new LinkableInteger(4));
    ll.insertAtTail(new LinkableInteger(5));
    ll.insertAtTail(new LinkableInteger(6));
    System.out.println(ll.removeFromHead()); // Remove and print a node
    System.out.println(ll.removeFromTail()); // Remove and print again
    ll.remove(new LinkableInteger(2)); // Remove another one

    // Now print out the contents of the list.
    for (Linkable l = ll.getHead(); l != null; l = l.getNext())
      System.out.println(l);
  }

}



   Doubly-linked list with data structure :

public class DoublyLinkedList {
  private Link first;

  private Link last;

  public DoublyLinkedList() {
    first = null;
    last = null;
  }

  public boolean isEmpty(){
    return first == null;
  }

  public void insertFirst(long dd){
    Link newLink = new Link(dd);

    if (isEmpty())
      last = newLink;
    else
      first.previous = newLink;
    newLink.next = first;
    first = newLink;
  }

  public void insertLast(long dd){
    Link newLink = new Link(dd);
    if (isEmpty())
      first = newLink;
    else {
      last.next = newLink;
      newLink.previous = last;
    }
    last = newLink;
  }

  public Link deleteFirst(){
    Link temp = first;
    if (first.next == null)
      last = null;
    else
      first.next.previous = null;
    first = first.next;
    return temp;
  }

  public Link deleteLast(){
    Link temp = last;
    if (first.next == null)
      first = null;
    else
      last.previous.next = null;
    last = last.previous;
    return temp;
  }

  public boolean insertAfter(long key, long dd) {
    Link current = first;
    while (current.dData != key){
      current = current.next;
      if (current == null)
        return false; // cannot find it
    }
    Link newLink = new Link(dd); // make new link

    if (current == last) // if last link,
    {
      newLink.next = null;
      last = newLink;
    } else // not last link,
    {
      newLink.next = current.next;

      current.next.previous = newLink;
    }
    newLink.previous = current;
    current.next = newLink;
    return true; // found it, insert
  }

  public Link deleteKey(long key){
    Link current = first;
    while (current.dData != key)
    {
      current = current.next;
      if (current == null)
        return null; // cannot find it
    }
    if (current == first) // found it; first item?
      first = current.next;
    else
      current.previous.next = current.next;

    if (current == last) // last item?
      last = current.previous;
    else
      // not last
      current.next.previous = current.previous;
    return current; // return value
  }

  public void displayForward() {
    System.out.print("List (first to last): ");
    Link current = first; // start at beginning
    while (current != null) // until end of list,
    {
      current.displayLink();
      current = current.next; // move to next link
    }
    System.out.println("");
  }

  public void displayBackward() {
    System.out.print("List : ");
    Link current = last;
    while (current != null){
      current.displayLink();
      current = current.previous;
    }
    System.out.println("");
  }

  public static void main(String[] args) {
    DoublyLinkedList theList = new DoublyLinkedList();

    theList.insertFirst(22);
    theList.insertFirst(44);
    theList.insertLast(33);
    theList.insertLast(55);

    theList.displayForward();
    theList.displayBackward();

    theList.deleteFirst();
    theList.deleteLast();
    theList.deleteKey(11);

    theList.displayForward();

    theList.insertAfter(22, 77); // insert 77 after 22
    theList.insertAfter(33, 88); // insert 88 after 33

    theList.displayForward();
  }

}

class Link {
  public long dData; // data item

  public Link next; // next link in list

  public Link previous; // previous link in list

  public Link(long d)
  {
    dData = d;
  }

  public void displayLink(){
    System.out.print(dData + " ");
  }

}

Java binary tree code

Binary Tree are the specialized tree that has two possible branches i.e left and right branch. These tree are useful when you build a parse of tree especially in mathematics and Boolean. The java binary tree find its application in games. Binary Tree is basic concept of data structure.

Understand with Example

In this Tutorial we want to describe you a code that helps you in understanding Java binary tree code. For this we have a class name BinayTreeExample.Inside the main method we instantiate Binary Tree Example class to a memory, that call run( ) method. Inside this class we have a static node class and have two static node variable Node left, Node right and int value to store the respective node value. The Node constructor create a node object that accept a node value as argument that can be object or reference. The run method ( ) create an instance of node class start with node value of 25.The System.out.println print the value of the node by calling -
rootnode.value - The rootnode.value return you the value of the node.
In the same way you insert the different value in the node using insert ( ) method.. The insert method accept a node and int as argument value. The conditional operator is used to evaluate the position of various node, if the value of the node is less than the root node then, the system.out.println print the value of node to the left of root node, Incase the value of node is greater than root node, the println print the node value to the right of it.

BinaryTreeExample.java

public class BinaryTreeExample {

public static void main(String[] args)

  new BinaryTreeExample().run();
  }

  static class Node
   {

  Node left;
  Node right;
  int value;

  public Node(int value) {
  this.value = value;
  }
  }

  public void run() {
  Node rootnode = new Node(25);
  System.out.println("Building tree with rootvalue
" + rootnode.value);
  System.out.println("=======================
==========");
  insert(rootnode, 11);
  insert(rootnode, 15);
  insert(rootnode, 16);
  insert(rootnode, 23);
  insert(rootnode, 79);
  System.out.println("Traversing tree in order");
  System.out.println("========================
=========");
  printInOrder(rootnode);

  }

  public void insert(Node node, int value) {
  if (value < node.value) {
  if (node.left != null) {
  insert(node.left, value);
  } else {
  System.out.println("  Inserted " + value +
    " to left of node " + node.value);
  node.left = new Node(value);
  }
  } else if (value > node.value) {
  if (node.right != null) {
  insert(node.right, value);
  } else {
  System.out.println("  Inserted " + value + "
to right of node " + node.value);
  node.right = new Node(value);
  }
  }
  }

  public void printInOrder(Node node) {
  if (node != null) {
  printInOrder(node.left);
  System.out.println("  Traversed " + node.value);
  printInOrder(node.right);
  }
  }
}

Output of the program

Building tree with root value 25
=================================
  Inserted 11 to left of node 25
  Inserted 15 to right of node 11
  Inserted 16 to right of node 15
  Inserted 23 to right of node 16
  Inserted 79 to right of node 25

Traversing tree in order
=================================
  Traversed 11
  Traversed 15
  Traversed 16
  Traversed 23
  Traversed 25
  Traversed 79

Download Source code

Binary Tree

       /*
DEVELOPING GAME IN JAVA

Caracteristiques

Editeur : NEW RIDERS
Auteur : BRACKEEN
Parution : 09 2003
Pages : 972
Isbn : 1-59273-005-1
Reliure : Paperback
Disponibilite : Disponible a la librairie
*/

public class BinaryTreeTest {

  public static void main(String[] args) {
    new BinaryTreeTest().run();
  }

  static class Node {
    Node left;

    Node right;

    int value;

    public Node(int value) {
      this.value = value;
    }
  }

  public void run() {
    // build the simple tree from chapter 11.
    Node root = new Node(5);
    System.out.println("Binary Tree Example");
    System.out.println("Building tree with root value " + root.value);
    insert(root, 1);
    insert(root, 8);
    insert(root, 6);
    insert(root, 3);
    insert(root, 9);
    System.out.println("Traversing tree in order");
    printInOrder(root);
    System.out.println("Traversing tree front-to-back from location 7");
    printFrontToBack(root, 7);
  }

  public void insert(Node node, int value) {
    if (value < node.value) {
      if (node.left != null) {
        insert(node.left, value);
      } else {
        System.out.println("  Inserted " + value + " to left of "
            + node.value);
        node.left = new Node(value);
      }
    } else if (value > node.value) {
      if (node.right != null) {
        insert(node.right, value);
      } else {
        System.out.println("  Inserted " + value + " to right of "
            + node.value);
        node.right = new Node(value);
      }
    }
  }

  public void printInOrder(Node node) {
    if (node != null) {
      printInOrder(node.left);
      System.out.println("  Traversed " + node.value);
      printInOrder(node.right);
    }
  }

  /**
   * uses in-order traversal when the origin is less than the node's value
   *
   * uses reverse-order traversal when the origin is greater than the node's
   * order
   */
  public void printFrontToBack(Node node, int camera) {
    if (node == null)
      return;
    if (node.value > camera) {
      // print in order
      printFrontToBack(node.left, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.right, camera);
    } else if (node.value < camera) {
      // print reverse order
      printFrontToBack(node.right, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.left, camera);
    } else {
      // order doesn't matter
      printFrontToBack(node.left, camera);
      printFrontToBack(node.right, camera);
    }
  }

}

Directed Graph Data Structure:

  import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
* A directed graph data structure.
*
* @author Scott.Stark@jboss.org
* @version $Revision$
* @param <T>
*/
@SuppressWarnings("unchecked")
public class Graph<T> {
  /** Color used to mark unvisited nodes */
  public static final int VISIT_COLOR_WHITE = 1;

  /** Color used to mark nodes as they are first visited in DFS order */
  public static final int VISIT_COLOR_GREY = 2;

  /** Color used to mark nodes after descendants are completely visited */
  public static final int VISIT_COLOR_BLACK = 3;

  /** Vector<Vertex> of graph verticies */
  private List<Vertex<T>> verticies;

  /** Vector<Edge> of edges in the graph */
  private List<Edge<T>> edges;

  /** The vertex identified as the root of the graph */
  private Vertex<T> rootVertex;

  /**
   * Construct a new graph without any vertices or edges
   */
  public Graph() {
    verticies = new ArrayList<Vertex<T>>();
    edges = new ArrayList<Edge<T>>();
  }

  /**
   * Are there any verticies in the graph
   *
   * @return true if there are no verticies in the graph
   */
  public boolean isEmpty() {
    return verticies.size() == 0;
  }

  /**
   * Add a vertex to the graph
   *
   * @param v
   *          the Vertex to add
   * @return true if the vertex was added, false if it was already in the graph.
   */
  public boolean addVertex(Vertex<T> v) {
    boolean added = false;
    if (verticies.contains(v) == false) {
      added = verticies.add(v);
    }
    return added;
  }

  /**
   * Get the vertex count.
   *
   * @return the number of verticies in the graph.
   */
  public int size() {
    return verticies.size();
  }

  /**
   * Get the root vertex
   *
   * @return the root vertex if one is set, null if no vertex has been set as
   *         the root.
   */
  public Vertex<T> getRootVertex() {
    return rootVertex;
  }

  /**
   * Set a root vertex. If root does no exist in the graph it is added.
   *
   * @param root -
   *          the vertex to set as the root and optionally add if it does not
   *          exist in the graph.
   */
  public void setRootVertex(Vertex<T> root) {
    this.rootVertex = root;
    if (verticies.contains(root) == false)
      this.addVertex(root);
  }

  /**
   * Get the given Vertex.
   *
   * @param n
   *          the index [0, size()-1] of the Vertex to access
   * @return the nth Vertex
   */
  public Vertex<T> getVertex(int n) {
    return verticies.get(n);
  }

  /**
   * Get the graph verticies
   *
   * @return the graph verticies
   */
  public List<Vertex<T>> getVerticies() {
    return this.verticies;
  }

  /**
   * Insert a directed, weighted Edge<T> into the graph.
   *
   * @param from -
   *          the Edge<T> starting vertex
   * @param to -
   *          the Edge<T> ending vertex
   * @param cost -
   *          the Edge<T> weight/cost
   * @return true if the Edge<T> was added, false if from already has this Edge<T>
   * @throws IllegalArgumentException
   *           if from/to are not verticies in the graph
   */
  public boolean addEdge(Vertex<T> from, Vertex<T> to, int cost) throws IllegalArgumentException {
    if (verticies.contains(from) == false)
      throw new IllegalArgumentException("from is not in graph");
    if (verticies.contains(to) == false)
      throw new IllegalArgumentException("to is not in graph");

    Edge<T> e = new Edge<T>(from, to, cost);
    if (from.findEdge(to) != null)
      return false;
    else {
      from.addEdge(e);
      to.addEdge(e);
      edges.add(e);
      return true;
    }
  }

  /**
   * Insert a bidirectional Edge<T> in the graph
   *
   * @param from -
   *          the Edge<T> starting vertex
   * @param to -
   *          the Edge<T> ending vertex
   * @param cost -
   *          the Edge<T> weight/cost
   * @return true if edges between both nodes were added, false otherwise
   * @throws IllegalArgumentException
   *           if from/to are not verticies in the graph
   */
  public boolean insertBiEdge(Vertex<T> from, Vertex<T> to, int cost)
      throws IllegalArgumentException {
    return addEdge(from, to, cost) && addEdge(to, from, cost);
  }

  /**
   * Get the graph edges
   *
   * @return the graph edges
   */
  public List<Edge<T>> getEdges() {
    return this.edges;
  }

  /**
   * Remove a vertex from the graph
   *
   * @param v
   *          the Vertex to remove
   * @return true if the Vertex was removed
   */
  public boolean removeVertex(Vertex<T> v) {
    if (!verticies.contains(v))
      return false;

    verticies.remove(v);
    if (v == rootVertex)
      rootVertex = null;

    // Remove the edges associated with v
    for (int n = 0; n < v.getOutgoingEdgeCount(); n++) {
      Edge<T> e = v.getOutgoingEdge(n);
      v.remove(e);
      Vertex<T> to = e.getTo();
      to.remove(e);
      edges.remove(e);
    }
    for (int n = 0; n < v.getIncomingEdgeCount(); n++) {
      Edge<T> e = v.getIncomingEdge(n);
      v.remove(e);
      Vertex<T> predecessor = e.getFrom();
      predecessor.remove(e);
    }
    return true;
  }

  /**
   * Remove an Edge<T> from the graph
   *
   * @param from -
   *          the Edge<T> starting vertex
   * @param to -
   *          the Edge<T> ending vertex
   * @return true if the Edge<T> exists, false otherwise
   */
  public boolean removeEdge(Vertex<T> from, Vertex<T> to) {
    Edge<T> e = from.findEdge(to);
    if (e == null)
      return false;
    else {
      from.remove(e);
      to.remove(e);
      edges.remove(e);
      return true;
    }
  }

  /**
   * Clear the mark state of all verticies in the graph by calling clearMark()
   * on all verticies.
   *
   * @see Vertex#clearMark()
   */
  public void clearMark() {
    for (Vertex<T> w : verticies)
      w.clearMark();
  }

  /**
   * Clear the mark state of all edges in the graph by calling clearMark() on
   * all edges.
   */
  public void clearEdges() {
    for (Edge<T> e : edges)
      e.clearMark();
  }

  /**
   * Perform a depth first serach using recursion.
   *
   * @param v -
   *          the Vertex to start the search from
   * @param visitor -
   *          the vistor to inform prior to
   * @see Visitor#visit(Graph, Vertex)
   */
  public void depthFirstSearch(Vertex<T> v, final Visitor<T> visitor) {
    VisitorEX<T, RuntimeException> wrapper = new VisitorEX<T, RuntimeException>() {
      public void visit(Graph<T> g, Vertex<T> v) throws RuntimeException {
        if (visitor != null)
          visitor.visit(g, v);
      }
    };
    this.depthFirstSearch(v, wrapper);
  }

  /**
   * Perform a depth first serach using recursion. The search may be cut short
   * if the visitor throws an exception.
   *
   * @param <E>
   *
   * @param v -
   *          the Vertex to start the search from
   * @param visitor -
   *          the vistor to inform prior to
   * @see Visitor#visit(Graph, Vertex)
   * @throws E
   *           if visitor.visit throws an exception
   */
  public <E extends Exception> void depthFirstSearch(Vertex<T> v, VisitorEX<T, E> visitor) throws E {
    if (visitor != null)
      visitor.visit(this, v);
    v.visit();
    for (int i = 0; i < v.getOutgoingEdgeCount(); i++) {
      Edge<T> e = v.getOutgoingEdge(i);
      if (!e.getTo().visited()) {
        depthFirstSearch(e.getTo(), visitor);
      }
    }
  }

  /**
   * Perform a breadth first search of this graph, starting at v.
   *
   * @param v -
   *          the search starting point
   * @param visitor -
   *          the vistor whose vist method is called prior to visting a vertex.
   */
  public void breadthFirstSearch(Vertex<T> v, final Visitor<T> visitor) {
    VisitorEX<T, RuntimeException> wrapper = new VisitorEX<T, RuntimeException>() {
      public void visit(Graph<T> g, Vertex<T> v) throws RuntimeException {
        if (visitor != null)
          visitor.visit(g, v);
      }
    };
    this.breadthFirstSearch(v, wrapper);
  }

  /**
   * Perform a breadth first search of this graph, starting at v. The vist may
   * be cut short if visitor throws an exception during a vist callback.
   *
   * @param <E>
   *
   * @param v -
   *          the search starting point
   * @param visitor -
   *          the vistor whose vist method is called prior to visting a vertex.
   * @throws E
   *           if vistor.visit throws an exception
   */
  public <E extends Exception> void breadthFirstSearch(Vertex<T> v, VisitorEX<T, E> visitor)
      throws E {
    LinkedList<Vertex<T>> q = new LinkedList<Vertex<T>>();

    q.add(v);
    if (visitor != null)
      visitor.visit(this, v);
    v.visit();
    while (q.isEmpty() == false) {
      v = q.removeFirst();
      for (int i = 0; i < v.getOutgoingEdgeCount(); i++) {
        Edge<T> e = v.getOutgoingEdge(i);
        Vertex<T> to = e.getTo();
        if (!to.visited()) {
          q.add(to);
          if (visitor != null)
            visitor.visit(this, to);
          to.visit();
        }
      }
    }
  }

  /**
   * Find the spanning tree using a DFS starting from v.
   *
   * @param v -
   *          the vertex to start the search from
   * @param visitor -
   *          visitor invoked after each vertex is visited and an edge is added
   *          to the tree.
   */
  public void dfsSpanningTree(Vertex<T> v, DFSVisitor<T> visitor) {
    v.visit();
    if (visitor != null)
      visitor.visit(this, v);

    for (int i = 0; i < v.getOutgoingEdgeCount(); i++) {
      Edge<T> e = v.getOutgoingEdge(i);
      if (!e.getTo().visited()) {
        if (visitor != null)
          visitor.visit(this, v, e);
        e.mark();
        dfsSpanningTree(e.getTo(), visitor);
      }
    }
  }

  /**
   * Search the verticies for one with name.
   *
   * @param name -
   *          the vertex name
   * @return the first vertex with a matching name, null if no matches are found
   */
  public Vertex<T> findVertexByName(String name) {
    Vertex<T> match = null;
    for (Vertex<T> v : verticies) {
      if (name.equals(v.getName())) {
        match = v;
        break;
      }
    }
    return match;
  }

  /**
   * Search the verticies for one with data.
   *
   * @param data -
   *          the vertex data to match
   * @param compare -
   *          the comparator to perform the match
   * @return the first vertex with a matching data, null if no matches are found
   */
  public Vertex<T> findVertexByData(T data, Comparator<T> compare) {
    Vertex<T> match = null;
    for (Vertex<T> v : verticies) {
      if (compare.compare(data, v.getData()) == 0) {
        match = v;
        break;
      }
    }
    return match;
  }

  /**
   * Search the graph for cycles. In order to detect cycles, we use a modified
   * depth first search called a colored DFS. All nodes are initially marked
   * white. When a node is encountered, it is marked grey, and when its
   * descendants are completely visited, it is marked black. If a grey node is
   * ever encountered, then there is a cycle.
   *
   * @return the edges that form cycles in the graph. The array will be empty if
   *         there are no cycles.
   */
  public Edge<T>[] findCycles() {
    ArrayList<Edge<T>> cycleEdges = new ArrayList<Edge<T>>();
    // Mark all verticies as white
    for (int n = 0; n < verticies.size(); n++) {
      Vertex<T> v = getVertex(n);
      v.setMarkState(VISIT_COLOR_WHITE);
    }
    for (int n = 0; n < verticies.size(); n++) {
      Vertex<T> v = getVertex(n);
      visit(v, cycleEdges);
    }

    Edge<T>[] cycles = new Edge[cycleEdges.size()];
    cycleEdges.toArray(cycles);
    return cycles;
  }

  private void visit(Vertex<T> v, ArrayList<Edge<T>> cycleEdges) {
    v.setMarkState(VISIT_COLOR_GREY);
    int count = v.getOutgoingEdgeCount();
    for (int n = 0; n < count; n++) {
      Edge<T> e = v.getOutgoingEdge(n);
      Vertex<T> u = e.getTo();
      if (u.getMarkState() == VISIT_COLOR_GREY) {
        // A cycle Edge<T>
        cycleEdges.add(e);
      } else if (u.getMarkState() == VISIT_COLOR_WHITE) {
        visit(u, cycleEdges);
      }
    }
    v.setMarkState(VISIT_COLOR_BLACK);
  }

  public String toString() {
    StringBuffer tmp = new StringBuffer("Graph[");
    for (Vertex<T> v : verticies)
      tmp.append(v);
    tmp.append(']');
    return tmp.toString();
  }

}

* A directed, weighted edge in a graph
*
* @author Scott.Stark@jboss.org
* @version $Revision$
* @param <T>
*/
class Edge<T> {
  private Vertex<T> from;

  private Vertex<T> to;

  private int cost;

  private boolean mark;

  /**
   * Create a zero cost edge between from and to
   *
   * @param from
   *          the starting vertex
   * @param to
   *          the ending vertex
   */
  public Edge(Vertex<T> from, Vertex<T> to) {
    this(from, to, 0);
  }

  /**
   * Create an edge between from and to with the given cost.
   *
   * @param from
   *          the starting vertex
   * @param to
   *          the ending vertex
   * @param cost
   *          the cost of the edge
   */
  public Edge(Vertex<T> from, Vertex<T> to, int cost) {
    this.from = from;
    this.to = to;
    this.cost = cost;
    mark = false;
  }

  /**
   * Get the ending vertex
   *
   * @return ending vertex
   */
  public Vertex<T> getTo() {
    return to;
  }

  /**
   * Get the starting vertex
   *
   * @return starting vertex
   */
  public Vertex<T> getFrom() {
    return from;
  }

  /**
   * Get the cost of the edge
   *
   * @return cost of the edge
   */
  public int getCost() {
    return cost;
  }

  /**
   * Set the mark flag of the edge
   *
   */
  public void mark() {
    mark = true;
  }

  /**
   * Clear the edge mark flag
   *
   */
  public void clearMark() {
    mark = false;
  }

  /**
   * Get the edge mark flag
   *
   * @return edge mark flag
   */
  public boolean isMarked() {
    return mark;
  }

  /**
   * String rep of edge
   *
   * @return string rep with from/to vertex names and cost
   */
  public String toString() {
    StringBuffer tmp = new StringBuffer("Edge[from: ");
    tmp.append(from.getName());
    tmp.append(",to: ");
    tmp.append(to.getName());
    tmp.append(", cost: ");
    tmp.append(cost);
    tmp.append("]");
    return tmp.toString();
  }
}

/**
* A named graph vertex with optional data.
*
* @author Scott.Stark@jboss.org
* @version $Revision$
* @param <T>
*/
@SuppressWarnings("unchecked")
class Vertex<T> {
  private List<Edge<T>> incomingEdges;

  private List<Edge<T>> outgoingEdges;

  private String name;

  private boolean mark;

  private int markState;

  private T data;

  /**
   * Calls this(null, null).
   */
  public Vertex() {
    this(null, null);
  }

  /**
   * Create a vertex with the given name and no data
   *
   * @param n
   */
  public Vertex(String n) {
    this(n, null);
  }

  /**
   * Create a Vertex with name n and given data
   *
   * @param n -
   *          name of vertex
   * @param data -
   *          data associated with vertex
   */
  public Vertex(String n, T data) {
    incomingEdges = new ArrayList<Edge<T>>();
    outgoingEdges = new ArrayList<Edge<T>>();
    name = n;
    mark = false;
    this.data = data;
  }

  /**
   * @return the possibly null name of the vertex
   */
  public String getName() {
    return name;
  }

  /**
   * @return the possibly null data of the vertex
   */
  public T getData() {
    return this.data;
  }

  /**
   * @param data
   *          The data to set.
   */
  public void setData(T data) {
    this.data = data;
  }

  /**
   * Add an edge to the vertex. If edge.from is this vertex, its an outgoing
   * edge. If edge.to is this vertex, its an incoming edge. If neither from or
   * to is this vertex, the edge is not added.
   *
   * @param e -
   *          the edge to add
   * @return true if the edge was added, false otherwise
   */
  public boolean addEdge(Edge<T> e) {
    if (e.getFrom() == this)
      outgoingEdges.add(e);
    else if (e.getTo() == this)
      incomingEdges.add(e);
    else
      return false;
    return true;
  }

  /**
   * Add an outgoing edge ending at to.
   *
   * @param to -
   *          the destination vertex
   * @param cost
   *          the edge cost
   */
  public void addOutgoingEdge(Vertex<T> to, int cost) {
    Edge<T> out = new Edge<T>(this, to, cost);
    outgoingEdges.add(out);
  }

  /**
   * Add an incoming edge starting at from
   *
   * @param from -
   *          the starting vertex
   * @param cost
   *          the edge cost
   */
  public void addIncomingEdge(Vertex<T> from, int cost) {
    Edge<T> out = new Edge<T>(this, from, cost);
    incomingEdges.add(out);
  }

  /**
   * Check the vertex for either an incoming or outgoing edge mathcing e.
   *
   * @param e
   *          the edge to check
   * @return true it has an edge
   */
  public boolean hasEdge(Edge<T> e) {
    if (e.getFrom() == this)
      return incomingEdges.contains(e);
    else if (e.getTo() == this)
      return outgoingEdges.contains(e);
    else
      return false;
  }

  /**
   * Remove an edge from this vertex
   *
   * @param e -
   *          the edge to remove
   * @return true if the edge was removed, false if the edge was not connected
   *         to this vertex
   */
  public boolean remove(Edge<T> e) {
    if (e.getFrom() == this)
      incomingEdges.remove(e);
    else if (e.getTo() == this)
      outgoingEdges.remove(e);
    else
      return false;
    return true;
  }

  /**
   *
   * @return the count of incoming edges
   */
  public int getIncomingEdgeCount() {
    return incomingEdges.size();
  }

  /**
   * Get the ith incoming edge
   *
   * @param i
   *          the index into incoming edges
   * @return ith incoming edge
   */
  public Edge<T> getIncomingEdge(int i) {
    return incomingEdges.get(i);
  }

  /**
   * Get the incoming edges
   *
   * @return incoming edge list
   */
  public List getIncomingEdges() {
    return this.incomingEdges;
  }

  /**
   *
   * @return the count of incoming edges
   */
  public int getOutgoingEdgeCount() {
    return outgoingEdges.size();
  }

  /**
   * Get the ith outgoing edge
   *
   * @param i
   *          the index into outgoing edges
   * @return ith outgoing edge
   */
  public Edge<T> getOutgoingEdge(int i) {
    return outgoingEdges.get(i);
  }

  /**
   * Get the outgoing edges
   *
   * @return outgoing edge list
   */
  public List getOutgoingEdges() {
    return this.outgoingEdges;
  }

  /**
   * Search the outgoing edges looking for an edge whose's edge.to == dest.
   *
   * @param dest
   *          the destination
   * @return the outgoing edge going to dest if one exists, null otherwise.
   */
  public Edge<T> findEdge(Vertex<T> dest) {
    for (Edge<T> e : outgoingEdges) {
      if (e.getTo() == dest)
        return e;
    }
    return null;
  }

  /**
   * Search the outgoing edges for a match to e.
   *
   * @param e -
   *          the edge to check
   * @return e if its a member of the outgoing edges, null otherwise.
   */
  public Edge<T> findEdge(Edge<T> e) {
    if (outgoingEdges.contains(e))
      return e;
    else
      return null;
  }

  /**
   * What is the cost from this vertext to the dest vertex.
   *
   * @param dest -
   *          the destination vertex.
   * @return Return Integer.MAX_VALUE if we have no edge to dest, 0 if dest is
   *         this vertex, the cost of the outgoing edge otherwise.
   */
  public int cost(Vertex<T> dest) {
    if (dest == this)
      return 0;

    Edge<T> e = findEdge(dest);
    int cost = Integer.MAX_VALUE;
    if (e != null)
      cost = e.getCost();
    return cost;
  }

  /**
   * Is there an outgoing edge ending at dest.
   *
   * @param dest -
   *          the vertex to check
   * @return true if there is an outgoing edge ending at vertex, false
   *         otherwise.
   */
  public boolean hasEdge(Vertex<T> dest) {
    return (findEdge(dest) != null);
  }

  /**
   * Has this vertex been marked during a visit
   *
   * @return true is visit has been called
   */
  public boolean visited() {
    return mark;
  }

  /**
   * Set the vertex mark flag.
   *
   */
  public void mark() {
    mark = true;
  }

  /**
   * Set the mark state to state.
   *
   * @param state
   *          the state
   */
  public void setMarkState(int state) {
    markState = state;
  }

  /**
   * Get the mark state value.
   *
   * @return the mark state
   */
  public int getMarkState() {
    return markState;
  }

  /**
   * Visit the vertex and set the mark flag to true.
   *
   */
  public void visit() {
    mark();
  }

  /**
   * Clear the visited mark flag.
   *
   */
  public void clearMark() {
    mark = false;
  }

  /**
   * @return a string form of the vertex with in and out edges.
   */
  public String toString() {
    StringBuffer tmp = new StringBuffer("Vertex(");
    tmp.append(name);
    tmp.append(", data=");
    tmp.append(data);
    tmp.append("), in:[");
    for (int i = 0; i < incomingEdges.size(); i++) {
      Edge<T> e = incomingEdges.get(i);
      if (i > 0)
        tmp.append(',');
      tmp.append('{');
      tmp.append(e.getFrom().name);
      tmp.append(',');
      tmp.append(e.getCost());
      tmp.append('}');
    }
    tmp.append("], out:[");
    for (int i = 0; i < outgoingEdges.size(); i++) {
      Edge<T> e = outgoingEdges.get(i);
      if (i > 0)
        tmp.append(',');
      tmp.append('{');
      tmp.append(e.getTo().name);
      tmp.append(',');
      tmp.append(e.getCost());
      tmp.append('}');
    }
    tmp.append(']');
    return tmp.toString();
  }
}

/**
* A graph visitor interface.
*
* @author Scott.Stark@jboss.org
* @version $Revision$
* @param <T>
*/
interface Visitor<T> {
  /**
   * Called by the graph traversal methods when a vertex is first visited.
   *
   * @param g -
   *          the graph
   * @param v -
   *          the vertex being visited.
   */
  public void visit(Graph<T> g, Vertex<T> v);
}

/**
* A graph visitor interface that can throw an exception during a visit
* callback.
*
* @author Scott.Stark@jboss.org
* @version $Revision$
* @param <T>
* @param <E>
*/
interface VisitorEX<T, E extends Exception> {
  /**
   * Called by the graph traversal methods when a vertex is first visited.
   *
   * @param g -
   *          the graph
   * @param v -
   *          the vertex being visited.
   * @throws E
   *           exception for any error
   */
  public void visit(Graph<T> g, Vertex<T> v) throws E;
}

/**
* A spanning tree visitor callback interface
*
* @see Graph#dfsSpanningTree(Vertex, DFSVisitor)
*
* @author Scott.Stark@jboss.org
* @version $Revision$
* @param <T>
*/
interface DFSVisitor<T> {
  /**
   * Called by the graph traversal methods when a vertex is first visited.
   *
   * @param g -
   *          the graph
   * @param v -
   *          the vertex being visited.
   */
  public void visit(Graph<T> g, Vertex<T> v);

  /**
   * Used dfsSpanningTree to notify the visitor of each outgoing edge to an
   * unvisited vertex.
   *
   * @param g -
   *          the graph
   * @param v -
   *          the vertex being visited
   * @param e -
   *          the outgoing edge from v
   */
  public void visit(Graph<T> g, Vertex<T> v, Edge<T> e);
}

   Topological sorting :

class Vertex {
  public char label;

  public Vertex(char lab) {
    label = lab;
  }
}

public class GraphTS {
  private final int MAX_VERTS = 20;

  private Vertex vertexList[]; // list of vertices

  private int matrix[][]; // adjacency matrix

  private int numVerts; // current number of vertices

  private char sortedArray[];

  public GraphTS() {
    vertexList = new Vertex[MAX_VERTS];
    matrix = new int[MAX_VERTS][MAX_VERTS];
    numVerts = 0;
    for (int i = 0; i < MAX_VERTS; i++)
      for (int k = 0; k < MAX_VERTS; k++)
        matrix[i][k] = 0;
    sortedArray = new char[MAX_VERTS]; // sorted vert labels
  }

  public void addVertex(char lab) {
    vertexList[numVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
    matrix[start][end] = 1;
  }

  public void displayVertex(int v) {
    System.out.print(vertexList[v].label);
  }

  public void topo() // toplogical sort
  {
    int orig_nVerts = numVerts;

    while (numVerts > 0) // while vertices remain,
    {
      // get a vertex with no successors, or -1
      int currentVertex = noSuccessors();
      if (currentVertex == -1) // must be a cycle
      {
        System.out.println("ERROR: Graph has cycles");
        return;
      }
      // insert vertex label in sorted array (start at end)
      sortedArray[numVerts - 1] = vertexList[currentVertex].label;

      deleteVertex(currentVertex); // delete vertex
    }

    // vertices all gone; display sortedArray
    System.out.print("Topologically sorted order: ");
    for (int j = 0; j < orig_nVerts; j++)
      System.out.print(sortedArray[j]);
    System.out.println("");
  }

  public int noSuccessors() // returns vert with no successors (or -1 if no such verts)
  {
    boolean isEdge; // edge from row to column in adjMat

    for (int row = 0; row < numVerts; row++) {
      isEdge = false; // check edges
      for (int col = 0; col < numVerts; col++) {
        if (matrix[row][col] > 0) // if edge to another,
        {
          isEdge = true;
          break; // this vertex has a successor try another
        }
      }
      if (!isEdge) // if no edges, has no successors
        return row;
    }
    return -1; // no
  }

  public void deleteVertex(int delVert) {
    if (delVert != numVerts - 1) // if not last vertex, delete from vertexList
    {
      for (int j = delVert; j < numVerts - 1; j++)
        vertexList[j] = vertexList[j + 1];

      for (int row = delVert; row < numVerts - 1; row++)
        moveRowUp(row, numVerts);

      for (int col = delVert; col < numVerts - 1; col++)
        moveColLeft(col, numVerts - 1);
    }
    numVerts--; // one less vertex
  }

  private void moveRowUp(int row, int length) {
    for (int col = 0; col < length; col++)
      matrix[row][col] = matrix[row + 1][col];
  }

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

  public static void main(String[] args) {
    GraphTS g = new GraphTS();
    g.addVertex('A'); // 0
    g.addVertex('B'); // 1
    g.addVertex('C'); // 2
    g.addVertex('D'); // 3
    g.addVertex('E'); // 4
    g.addVertex('F'); // 5
    g.addVertex('G'); // 6
    g.addVertex('H'); // 7

    g.addEdge(0, 3); // AD
    g.addEdge(0, 4); // AE
    g.addEdge(1, 4); // BE
    g.addEdge(2, 5); // CF
    g.addEdge(3, 6); // DG
    g.addEdge(4, 6); // EG
    g.addEdge(5, 7); // FH
    g.addEdge(6, 7); // GH

    g.topo(); // do the sort
  }
}

Java program codes

Sunday, 4 September 2011

Unit-V Data Structures

Selection Sort In Java

Insertion Sort In Java

Quick Sort in Java

Merge Sort in Java

Implementing a Stack in Java

Implement the Queue in Java

Understand with Example

No comments: