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
2) 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:
1
2
3
4
5
6
7
8
9
10
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:
1
2
3
4
5
6
7
8
9
10
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
}
}
|
|
|
|
