heap

package heap;

part 1: complete the reHeapUp() and reHeapDown() methods

public class Heap> {

Comparable [] arr;

int next = -1;

public Heap(int size)

{

arr = new Comparable[size];

}

public Heap ()

{

this(10);

}

/*

* expandArray()

* - called when the current array is too small.

* 1. create a new array twice the size,

* 2. copy all elements to the new array

* 3. and then set the arr reference to the new array.

*/

private void expandArray()

{

Comparable [] temp = new Comparable[arr.length * 2];

for (int k=0; k

temp[k] = arr[k];

arr = temp;

}

// isEmpty - does the heap have any elements

public boolean isEmpty()

{

return next==-1;

}

// enqueue - add an element to the heap

public void enqueue( T val ) throws Exception

{

add(val);

}

/*

* add an element into the heap

* steps: verify the length of the array, expand if necessary.

* pre-increment next and copy into arr

* then call reHeapUp to verify/reorder the tree.

*/

public void add( T val ) throws Exception

{

//verify the array is not full

//add to the end of the array - pre increment next

if (next > arr.length-2) {

expandArray();

}

arr[++next] = val;

reHeapUp(next);

}

public int size()

{

return next+1;

}

/*

* reHeapUp - re-order the tree after a node has been inserted at next

* steps: 1. if the index == 0, base condition - return. We are at the root

* 2. determine the parent index

* 3. compare child (at index) with the parent

* if the child is less than the parent, return - order is correct

* if the child is greater than parent,

* swap and call reHeapUp with index of the parent

*

* Note: arr is a static array of Comparable objects, use compareTo()

*/

public void reHeapUp ( int index )

{

// TO DO:

//base condition

//1. determine parent node

//2. compare current node (index) with parent, if less than or equal => return

// 3. swap, then recursively call reHeapUp with parent index

}

public T dequeue()

{

return remove();

}

/*

* remove() - remove the root of the heap, then reorder the heap to maintain the order property.

* steps: 1. copy the element at the root

* 2. move the last element (lowest level, most right node) to the root

* 3. call reHeapDown to reorder the priority queue / heap.

*/

public T remove()

{

Comparable rVal = arr[0];

arr[0] = arr[next--];

reHeapDown(0);

return (T)rVal;

}

/*

* reHeapDown - maintain the order of the Heap's subtree of the given index

* - base condition: index is of a leaf node

*

*/

public void reHeapDown(int index)

{

// TO DO:

//verify this node at index has a least a valid left child

// if the rightChild index is valid, determine the max child

// is the max child greater than the parent (index)

// if so, swap elements and call reHeapDown with index of max child.

}

public static double lg( int x )

{

return Math.log10(x) / Math.log10(2);

}

protected String fillString(int length, char charToFill) {

char[] array = new char[length];

int pos = 0;

while (pos

array[pos] = charToFill;

pos++;

}

return new String(array);

}

public String toString()

{

int [] spaces = {45, 21, 9, 3, 0, 0, 0, 0};

if (next

return "heap empty";

String rStr = "";

int numLevels = (int)lg(next+1);

System.out.println("Heap: size=" + size() + ", next=" + next + ", depth = " + numLevels);

int cnt = 0;

for (int level = 0; level

{

int numNodes = (int)Math.pow(2, level);

String str = fillString(spaces[level], ' ');

rStr += str;

if (level > 0)

str = fillString(spaces[level-1], ' ');

for (int k = 0; k

{

rStr += String.format("%3d%s", arr[cnt++], str);

}

rStr += " ";

}

return rStr;

}

public static void main(String[] args) {

Heap myHeap = new Heap(10);

try{

myHeap.enqueue(10);

System.out.println(myHeap);

myHeap.enqueue(5);

myHeap.enqueue(7);

System.out.println(myHeap);

myHeap.enqueue(20);

System.out.println(myHeap);

myHeap.enqueue(11);

myHeap.enqueue(3);

myHeap.enqueue(54);

myHeap.enqueue(33);

myHeap.enqueue(6);

myHeap.enqueue(17);

System.out.println(myHeap);

myHeap.enqueue(8);

myHeap.enqueue(9);

myHeap.enqueue(16);

myHeap.enqueue(22);

myHeap.enqueue(24);

myHeap.enqueue(27);

System.out.println(myHeap);

Integer el2 = myHeap.dequeue();

System.out.println("dequeued: " + el2);

System.out.println(myHeap);

int numElements = myHeap.size();

for (int k=0; k

{

Integer el = myHeap.dequeue();

System.out.println("dequeued: " + el);

if (k%4 == 0 || myHeap.size()

System.out.println(myHeap);

}

}

catch(Exception e) {

System.out.println(e);

}

}

}

Queue

package queue;

public class QueueUnderflowException extends RuntimeException {

public QueueUnderflowException() {

super();

// TODO Auto-generated constructor stub

}

public QueueUnderflowException(String arg0) {

super(arg0);

// TODO Auto-generated constructor stub

}

}

package queue;

import java.util.ArrayList;

public class UnboundedQueue implements UnboundedQueueInterface {

ArrayList queue;

public UnboundedQueue()

{

queue = new ArrayList();

}

@Override

public T dequeue() throws QueueUnderflowException {

// TODO Auto-generated method stub

if (queue.size() == 0)

throw new QueueUnderflowException("queue empty");

return queue.remove(0);

}

@Override

public boolean isEmpty() {

// TODO Auto-generated method stub

return queue.size() == 0;

}

@Override

public void enqueue(T element) {

queue.add(element);

}

}

package queue;

public interface UnboundedQueueInterface {

T dequeue() throws QueueUnderflowException;

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

boolean isEmpty();

// Returns true if this queue is empty; otherwise, returns false.

void enqueue(T element);

// Adds element to the rear of this queue.

}

Flights

public class Flights implements Comparable

{

protected Object fromVertex;

protected Object toVertex;

protected int distance;

public Flights(Object fromVertex, Object toVertex, int distance)

{

this.fromVertex = fromVertex;

this.toVertex = toVertex;

this.distance = distance;

}

public Object getFromVertex()

{

return fromVertex;

}

public Object getToVertex()

{

return toVertex;

}

public int getDistance()

{

return distance;

}

public void setFromVertex(Object vertex)

{

fromVertex = vertex;

}

public void setToVertex(Object vertex)

{

toVertex = vertex;

}

public void setDistance(int distance)

{

this.distance = distance;

}

public int compareTo(Object otherFlights)

{

Flights other = (Flights)otherFlights;

return (other.distance - this.distance); // shorter is better

}

public String toString()

{

return (fromVertex + " " + toVertex + " " + distance);

}

}

UseGraph

//----------------------------------------------------------------------------

// UseGraph.java by Dale/Joyce/Weems Chapter 9

//

// Examples of uses of the Graph ADT.

//----------------------------------------------------------------------------

import java.util.Stack;

import heap.*;

import queue.UnboundedQueue;

import queue.UnboundedQueueInterface;

public class UseGraph

{

private static void shortestPaths(WeightedGraphInterface graph,

Object startVertex )

// Writes the shortest distance from startVertex to every

// other reachable vertex in graph.

{

Flights flight;

Flights saveFlight; // for saving on priority queue

int minDistance;

int newDistance;

Heap pq = new Heap(20); // Assume at most 20 vertices

Object vertex;

UnboundedQueueInterface vertexQueue = new UnboundedQueue();

graph.clearMarks();

saveFlight = new Flights(startVertex, startVertex, 0);

try {

pq.enqueue(saveFlight);

} catch (Exception e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

System.out.println("Last Vertex Destination Distance");

System.out.println("------------------------------------");

do

{

flight = (Flights)pq.dequeue();

if (!graph.isMarked(flight.getToVertex()))

{

graph.markVertex(flight.getToVertex());

System.out.println(flight);

flight.setFromVertex(flight.getToVertex());

minDistance = flight.getDistance();

vertexQueue = graph.getToVertices(flight.getFromVertex());

while (!vertexQueue.isEmpty())

{

vertex = vertexQueue.dequeue();

if (!graph.isMarked(vertex))

{

newDistance = minDistance

+ graph.weightIs(flight.getFromVertex(), vertex);

saveFlight = new Flights(flight.getFromVertex(), vertex, newDistance);

try {

pq.enqueue(saveFlight);

} catch (Exception e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

}

}

} while (!pq.isEmpty());

System.out.println();

System.out.println("The unreachable vertices are:");

vertex = graph.getUnmarked();

while (vertex != null)

{

System.out.println(vertex);

graph.markVertex(vertex);

vertex = graph.getUnmarked();

}

System.out.println();

}

private static boolean isPath(WeightedGraphInterface graph,

Object startVertex,

Object endVertex )

// Returns true if a path exists on graph, from startVertex to endVertex;

// otherwise returns false. Uses depth-first search algorithm.

{

Stack stack = new Stack();

UnboundedQueueInterface vertexQueue = new UnboundedQueue();

boolean found = false;

Object vertex;

Object item;

graph.clearMarks();

stack.push(startVertex);

do

{

vertex = stack.peek();

stack.pop();

if (vertex == endVertex)

found = true;

else

{

if (!graph.isMarked(vertex))

{

graph.markVertex(vertex);

vertexQueue = graph.getToVertices(vertex);

while (!vertexQueue.isEmpty())

{

item = vertexQueue.dequeue();

if (!graph.isMarked(item))

stack.push(item);

}

}

}

} while (!stack.isEmpty() && !found);

return found;

}

private static boolean isPath2(WeightedGraphInterface graph,

Object startVertex,

Object endVertex )

// Returns true if a path exists on graph, from startVertex to endVertex;

// otherwise returns false. Uses breadth-first search algorithm.

{

UnboundedQueueInterface queue = new UnboundedQueue();

UnboundedQueueInterface vertexQueue = new UnboundedQueue();

boolean found = false;

Object vertex;

Object item;

graph.clearMarks();

queue.enqueue(startVertex);

do

{

vertex = queue.dequeue();

if (vertex == endVertex)

found = true;

else

{

if (!graph.isMarked(vertex))

{

graph.markVertex(vertex);

vertexQueue = graph.getToVertices(vertex);

while (!vertexQueue.isEmpty())

{

item = vertexQueue.dequeue();

if (!graph.isMarked(item))

queue.enqueue(item);

}

}

}

} while (!queue.isEmpty() && !found);

return found;

}

public static void main(String[] args)

{

WeightedGraphInterface graph = new WeightedGraph();

String s0 = new String("Atlanta ");

String s1 = new String("Austin ");

String s2 = new String("Chicago ");

String s3 = new String("Dallas ");

String s4 = new String("Denver ");

String s5 = new String("Houston ");

String s6 = new String("Washington");

graph.addVertex(s0);

graph.addVertex(s1);

graph.addVertex(s2);

graph.addVertex(s3);

graph.addVertex(s4);

graph.addVertex(s5);

graph.addVertex(s6);

graph.addEdge(s0, s5, 800);

graph.addEdge(s0, s6, 600);

graph.addEdge(s1, s3, 200);

graph.addEdge(s1, s5, 160);

graph.addEdge(s2, s4, 1000);

graph.addEdge(s3, s1, 200);

graph.addEdge(s3, s2, 900);

graph.addEdge(s3, s4, 780);

graph.addEdge(s4, s0, 1400);

graph.addEdge(s4, s2, 1000);

graph.addEdge(s5, s0, 800);

graph.addEdge(s6, s0, 600);

graph.addEdge(s6, s3, 1300);

boolean result;

System.out.println("depth first ...");

result = isPath(graph, s1, s2);

System.out.println("s1 s2 " + result);

result = isPath(graph, s1, s6);

System.out.println("s1 s6 " + result);

result = isPath(graph, s6, s5);

System.out.println("s6 s5 " + result);

result = isPath(graph, s6, s3);

System.out.println("s6 s3 " + result);

result = isPath(graph, s6, s1);

System.out.println("s6 s1 " + result);

System.out.println();

System.out.println("breadth first ...");

result = isPath2(graph, s1, s2);

System.out.println("s1 s2 " + result);

result = isPath2(graph, s1, s6);

System.out.println("s1 s6 " + result);

result = isPath2(graph, s6, s5);

System.out.println("s6 s5 " + result);

result = isPath2(graph, s6, s3);

System.out.println("s6 s3 " + result);

result = isPath2(graph, s6, s1);

System.out.println("s6 s1 " + result);

System.out.println();

System.out.println("Shortest Path with Washington as starting node");

shortestPaths(graph, s6);

System.out.println();

System.out.println();

System.out.println("Shortest Path with Denver as starting node");

shortestPaths(graph, s4);

System.out.println();

System.out.println();

System.out.println("a new graph without Wash - Dallas leg");

System.out.println();

graph = new WeightedGraph();

s0 = new String("Atlanta ");

s1 = new String("Austin ");

s2 = new String("Chicago ");

s3 = new String("Dallas ");

s4 = new String("Denver ");

s5 = new String("Houston ");

s6 = new String("Washington");

graph.addVertex(s0);

graph.addVertex(s1);

graph.addVertex(s2);

graph.addVertex(s3);

graph.addVertex(s4);

graph.addVertex(s5);

graph.addVertex(s6);

graph.addEdge(s0, s5, 800);

graph.addEdge(s0, s6, 600);

graph.addEdge(s1, s3, 200);

graph.addEdge(s1, s5, 160);

graph.addEdge(s2, s4, 1000);

graph.addEdge(s3, s1, 200);

graph.addEdge(s3, s2, 900);

graph.addEdge(s3, s4, 780);

graph.addEdge(s4, s0, 1400);

graph.addEdge(s4, s2, 1000);

graph.addEdge(s5, s0, 800);

graph.addEdge(s6, s0, 600);

// graph.addEdge(s6, s3, 1300);

System.out.println("depth first ...");

result = isPath(graph, s1, s2);

System.out.println("s1 s2 " + result);

result = isPath(graph, s1, s6);

System.out.println("s1 s6 " + result);

result = isPath(graph, s6, s5);

System.out.println("s6 s5 " + result);

result = isPath(graph, s6, s3);

System.out.println("s6 s3 " + result);

result = isPath(graph, s6, s1);

System.out.println("s6 s1 " + result);

System.out.println();

System.out.println("breadth first ...");

result = isPath2(graph, s1, s2);

System.out.println("s1 s2 " + result);

result = isPath2(graph, s1, s6);

System.out.println("s1 s6 " + result);

result = isPath2(graph, s6, s5);

System.out.println("s6 s5 " + result);

result = isPath2(graph, s6, s3);

System.out.println("s6 s3 " + result);

result = isPath2(graph, s6, s1);

System.out.println("s6 s1 " + result);

System.out.println();

System.out.println("Shortest Path with Washington as starting node");

shortestPaths(graph, s6);

System.out.println();

System.out.println();

System.out.println("Shortest Path with Denver as starting node");

shortestPaths(graph, s4);

}

}

WeightedGraph

import queue.UnboundedQueue;

import queue.UnboundedQueueInterface;

//----------------------------------------------------------------------------

// WeightedGraph.java by Dale/Joyce/Weems Chapter 9

//

// Implements a directed graph with weighted edges.

// Vertices are objects and can be marked as having been visited.

// Edge weights are integers.

//

// General precondition: Except for the addVertex and hasVertex methods,

// any vertex passed as an argument to a method is in this graph.

//----------------------------------------------------------------------------

public class WeightedGraph implements WeightedGraphInterface

{

public static final int NULL_EDGE = 0;

private static final int DEFCAP = 50; // default capacity

private int numVertices; /umber of vertices added to the graph

private int maxVertices;

private Object[] vertices;

private int[][] edges;

private boolean[] marks; // marks[i] is mark for vertices[i]

public WeightedGraph()

// Instantiates a graph with capacity DEFCAP vertices.

{

this(DEFCAP);

}

public WeightedGraph(int maxV)

// Instantiates a graph with capacity maxV.

{

numVertices = 0; /umber of Vertices in the Graph, also index for vertices[]

maxVertices = maxV;

vertices = new Object[maxV];

marks = new boolean[maxV];

edges = new int[maxV][maxV];

}

public boolean isEmpty()

// Returns true if this graph is empty; otherwise, returns false.

{

//todo

return false;

}

public boolean isFull()

// Returns true if this graph is full; otherwise, returns false.

{

//todo

return false;

}

public void addVertex(Object vertex)

// Preconditions: This graph is not full.

// Vertex is not already in this graph.

// Vertex is not null.

//

// Adds vertex to this graph.

// - add vertex to the vertices array

// - clear out any edges for this vertex.

// - increment numVertices

{

}

public boolean hasVertex(Object vertex)

// Returns true if this graph contains vertex; otherwise, returns false.

{

return false;

}

public void addEdge(Object fromVertex, Object toVertex, int weight)

// Adds an edge with the specified weight from fromVertex to toVertex.

// modify edges. note: add private method to get the index of a vertex.

{

}

public int weightIs(Object fromVertex, Object toVertex)

// If edge from fromVertex to toVertex exists, returns the weight of edge;

// otherwise, returns NULL_EDGE

{

return 0;

}

public UnboundedQueueInterface getToVertices(Object vertex)

// Returns a queue of the vertices that are adjacent from vertex.

{

return null;

}

public void clearMarks()

// Sets marks for all vertices to false.

// modify the marks array.

{

}

public void markVertex(Object vertex)

// Sets mark for vertex to true.

// modify the marks array.

{

}

public boolean isMarked(Object vertex)

// Returns true if vertex is marked; otherwise, returns false.

{

return false;

}

public Object getUnmarked()

// Returns an unmarked vertex if any exist; otherwise, returns null.

{

return null;

}

}

WeightedGraphInterface.

import queue.UnboundedQueueInterface;

//---------------------------------------------------------------------------- // WeightedGraphInterface.java by Dale/Joyce/Weems Chapter 9 // // Interface for a class that implements a directed graph with weighted edges. // Vertices are objects and can be marked as having been visited. // Edge weights are integers. // // General precondition: Except for the addVertex and hasVertex methods, // any vertex passed as an argument to a method is in this graph. //----------------------------------------------------------------------------

public interface WeightedGraphInterface { boolean isEmpty(); // Returns true if this graph is empty; otherwise, returns false.

boolean isFull(); // Returns true if this graph is full; otherwise, returns false. void addVertex(Object vertex); // Preconditions: This graph is not full. // Vertex is not already in this graph. // Vertex is not null. // // Adds vertex to this graph.

boolean hasVertex(Object vertex); // Returns true if this graph contains vertex; otherwise, returns false.

void addEdge(Object fromVertex, Object toVertex, int weight); // Adds an edge with the specified weight from fromVertex to toVertex.

int weightIs(Object fromVertex, Object toVertex); // If edge from fromVertex to toVertex exists, returns the weight of edge; // otherwise, returns a special null-edge value.

UnboundedQueueInterface getToVertices(Object vertex); // Returns a queue of the vertices that are adjacent from vertex.

void clearMarks(); // Sets marks for all vertices to false.

void markVertex(Object vertex); // Sets mark for vertex to true.

boolean isMarked(Object vertex); // Returns true if vertex is marked; otherwise, returns false. Object getUnmarked(); // Returns an unmarked vertex if any exist; otherwise, returns null. }

Expected Output

Expected output:

depth first ...

s1 s2 true

s1 s6 true

s6 s5 true

s6 s3 true

s6 s1 true

breadth first ...

s1 s2 true

s1 s6 true

s6 s5 true

s6 s3 true

s6 s1 true

Last Vertex Destination Distance

------------------------------------

Washington Washington 0

Washington Atlanta 600

Washington Dallas 1300

Atlanta Houston 1400

Dallas Austin 1500

Dallas Denver 2080

Dallas Chicago 2200

The unreachable vertices are:

Last Vertex Destination Distance

------------------------------------

Denver Denver 0

Denver Chicago 1000

Denver Atlanta 1400

Atlanta Washington 2000

Atlanta Houston 2200

Washington Dallas 3300

Dallas Austin 3500

The unreachable vertices are:

a new graph without Wash - Dallas leg

depth first ...

s1 s2 true

s1 s6 true

s6 s5 true

s6 s3 false

s6 s1 false

breadth first ...

s1 s2 true

s1 s6 true

s6 s5 true

s6 s3 false

s6 s1 false

Last Vertex Destination Distance

------------------------------------

Washington Washington 0

Washington Atlanta 600

Atlanta Houston 1400

The unreachable vertices are:

Austin

Chicago

Dallas

Denver

Last Vertex Destination Distance

------------------------------------

Denver Denver 0

Denver Chicago 1000

Denver Atlanta 1400

Atlanta Washington 2000

Atlanta Houston 2200

The unreachable vertices are:

Austin

Dallas

The Heap and Directed Graphs - Shortest Path algorithm first, we will implement the enqueue and dequeue method of the heap. Then, we will use the heap in our Shortest Path algorithm and implement some Graph support functionality. The goal of this lab is to: Understand how the heap works, Get familiar with Graphs, - and then walk through the shortest path algorithm Download the src.zip file and import it into a new project. You will have 2 packages; heap and queue, as well as the default package where the graph code resides. After you import the code into your project, it should look like the following: JRE System Library [JavaSE-1.8 src ?(default package) Flights.java UseGraph java WeightedGraph.java WeightedGraphinterface java - heap Heap.java ? queue QueueUnderflowException.java UnboundedQueue.java UnboundedQueuelnterface.java Part 1 First, go to the heap package and implement the reHeapUp() method so that you can add elements to the heap. This should be a recursive method. The main() method has test code which will add several nodes. The toString() method implements a crude tree like display (for a limited number of levels). After you have the reHeapUp() method working, then implement the reHeapDown) methood Again, this should also be a recursive methood The Heap and Directed Graphs - Shortest Path algorithm first, we will implement the enqueue and dequeue method of the heap. Then, we will use the heap in our Shortest Path algorithm and implement some Graph support functionality. The goal of this lab is to: Understand how the heap works, Get familiar with Graphs, - and then walk through the shortest path algorithm Download the src.zip file and import it into a new project. You will have 2 packages; heap and queue, as well as the default package where the graph code resides. After you import the code into your project, it should look like the following: JRE System Library [JavaSE-1.8 src ?(default package) Flights.java UseGraph java WeightedGraph.java WeightedGraphinterface java - heap Heap.java ? queue QueueUnderflowException.java UnboundedQueue.java UnboundedQueuelnterface.java Part 1 First, go to the heap package and implement the reHeapUp() method so that you can add elements to the heap. This should be a recursive method. The main() method has test code which will add several nodes. The toString() method implements a crude tree like display (for a limited number of levels). After you have the reHeapUp() method working, then implement the reHeapDown) methood Again, this should also be a recursive methood