2,546 Xb3FinalProject/Data/tinyRoads.txt
View file

Large diffs are not rendered by default.

BIN +3.97 KB Xb3FinalProject/bin/DijkstraSP.class
View file
Binary file not shown.
BIN -220 Bytes (86%) Xb3FinalProject/bin/Edge.class
View file
Binary file not shown.
BIN +0 Bytes (100%) Xb3FinalProject/bin/EdgeWeightedGraph.class
View file
Binary file not shown.
BIN +1.47 KB Xb3FinalProject/bin/IndexMinPQ$HeapIterator.class
View file
Binary file not shown.
BIN +5.05 KB Xb3FinalProject/bin/IndexMinPQ.class
View file
Binary file not shown.
BIN +0 Bytes (100%) Xb3FinalProject/bin/JPanelTest$1.class
View file
Binary file not shown.
BIN +0 Bytes (100%) Xb3FinalProject/bin/JPanelTest.class
View file
Binary file not shown.
BIN +1.81 KB (170%) Xb3FinalProject/bin/Surface.class
View file
Binary file not shown.
147 Xb3FinalProject/src/DijkstraSP.java
View file
@@ -0,0 +1,147 @@
import java.util.Queue;
import java.util.Stack;


public class DijkstraSP {
private double[] distTo; // distTo[v] = distance of shortest s->v path
private Edge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
private IndexMinPQ<Double> pq; // priority queue of vertices

/**
* Computes a shortest paths tree from <tt>s</tt> to every other vertex in
* the edge-weighted digraph <tt>G</tt>.
* @param G the edge-weighted digraph
* @param s the source vertex
* @throws IllegalArgumentException if an edge weight is negative
* @throws IllegalArgumentException unless 0 &le; <tt>s</tt> &le; <tt>V</tt> - 1
*/
public DijkstraSP(EdgeWeightedGraph G, int s) {
for (Edge e : G.edges()) {
if (e.weight() < 0)
throw new IllegalArgumentException("edge " + e + " has negative weight");
}

distTo = new double[G.V()];
edgeTo = new Edge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;

// relax vertices in order of distance from s
pq = new IndexMinPQ<Double>(G.V());
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin();
for (Edge e : G.adj(v))
relax(e);
}

// check optimality conditions
assert check(G, s);
}

// relax edge e and update pq if changed
private void relax(Edge e) {
int v = e.either(), w = e.other(e.either());
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}

/**
* Returns the length of a shortest path from the source vertex <tt>s</tt> to vertex <tt>v</tt>.
* @param v the destination vertex
* @return the length of a shortest path from the source vertex <tt>s</tt> to vertex <tt>v</tt>;
* <tt>Double.POSITIVE_INFINITY</tt> if no such path
*/
public double distTo(int v) {
return distTo[v];
}

/**
* Is there a path from the source vertex <tt>s</tt> to vertex <tt>v</tt>?
* @param v the destination vertex
* @return <tt>true</tt> if there is a path from the source vertex
* <tt>s</tt> to vertex <tt>v</tt>, and <tt>false</tt> otherwise
*/
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}

/**
* Returns a shortest path from the source vertex <tt>s</tt> to vertex <tt>v</tt>.
* @param v the destination vertex
* @return a shortest path from the source vertex <tt>s</tt> to vertex <tt>v</tt>
* as an iterable of edges, and <tt>null</tt> if no such path
*/
public Iterable<Edge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Edge> path = new Stack<Edge>();
for (Edge e = edgeTo[v]; e != null;) {
path.push(e);
e = edgeTo[e.either()];
}
return path;
}


// check optimality conditions:
// (i) for all edges e: distTo[e.to()] <= distTo[e.from()] + e.weight()
// (ii) for all edge e on the SPT: distTo[e.to()] == distTo[e.from()] + e.weight()
private boolean check(EdgeWeightedGraph G, int s) {

// check that edge weights are nonnegative
for (Edge e : G.edges()) {
if (e.weight() < 0) {
System.err.println("negative edge weight detected");
return false;
}
}

// check that distTo[v] and edgeTo[v] are consistent
if (distTo[s] != 0.0 || edgeTo[s] != null) {
System.err.println("distTo[s] and edgeTo[s] inconsistent");
return false;
}
for (int v = 0; v < G.V(); v++) {
if (v == s) continue;
if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) {
System.err.println("distTo[] and edgeTo[] inconsistent");
return false;
}
}

// check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight()
for (int v = 0; v < G.V(); v++) {
for (Edge e : G.adj(v)) {
int w = e.either();
if (distTo[v] + e.weight() < distTo[w]) {
System.err.println("edge " + e + " not relaxed");
return false;
}
}
}

// check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight()
for (int w = 0; w < G.V(); w++) {
if (edgeTo[w] == null) continue;
Edge e = edgeTo[w];
int v = e.other(e.either());
if (w != e.either()) return false;
if (distTo[v] + e.weight() != distTo[w]) {
System.err.println("edge " + e + " on shortest path not tight");
return false;
}
}
return true;
}


/**
* Unit tests the <tt>DijkstraSP</tt> data type.
*/

}
2 Xb3FinalProject/src/Edge.java
View file
@@ -1,5 +1,5 @@

public class Edge<pulbic> {
public class Edge {
private final int v;
private final int w;
private final double weight;
1 Xb3FinalProject/src/EdgeWeightedGraph.java
View file
@@ -1,6 +1,5 @@
import java.util.Stack;


public class EdgeWeightedGraph {
private final int V;
private int E;
298 Xb3FinalProject/src/IndexMinPQ.java
View file
@@ -0,0 +1,298 @@
/*************************************************************************
* Compilation: javac IndexMinPQ.java
* Execution: java IndexMinPQ
*
* Minimum-oriented indexed PQ implementation using a binary heap.
*
*********************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
* The <tt>IndexMinPQ</tt> class represents an indexed priority queue of generic keys.
* It supports the usual <em>insert</em> and <em>delete-the-minimum</em>
* operations, along with <em>delete</em> and <em>change-the-key</em>
* methods. In order to let the client refer to keys on the priority queue,
* an integer between 0 and NMAX-1 is associated with each key&mdash;the client
* uses this integer to specify which key to delete or change.
* It also supports methods for peeking at the minimum key,
* testing if the priority queue is empty, and iterating through
* the keys.
* <p>
* This implementation uses a binary heap along with an array to associate
* keys with integers in the given range.
* The <em>insert</em>, <em>delete-the-minimum</em>, <em>delete</em>,
* <em>change-key</em>, <em>decrease-key</em>, and <em>increase-key</em>
* operations take logarithmic time.
* The <em>is-empty</em>, <em>size</em>, <em>min-index</em>, <em>min-key</em>, and <em>key-of</em>
* operations take constant time.
* Construction takes time proportional to the specified capacity.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
private int NMAX; // maximum number of elements on PQ
private int N; // number of elements on PQ
private int[] pq; // binary heap using 1-based indexing
private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
private Key[] keys; // keys[i] = priority of i

/**
* Initializes an empty indexed priority queue with indices between 0 and NMAX-1.
* @param NMAX the keys on the priority queue are index from 0 to NMAX-1
* @throws java.lang.IllegalArgumentException if NMAX < 0
*/
public IndexMinPQ(int NMAX) {
if (NMAX < 0) throw new IllegalArgumentException();
this.NMAX = NMAX;
keys = (Key[]) new Comparable[NMAX + 1]; // make this of length NMAX??
pq = new int[NMAX + 1];
qp = new int[NMAX + 1]; // make this of length NMAX??
for (int i = 0; i <= NMAX; i++) qp[i] = -1;
}

/**
* Is the priority queue empty?
* @return true if the priority queue is empty; false otherwise
*/
public boolean isEmpty() {
return N == 0;
}

/**
* Is i an index on the priority queue?
* @param i an index
* @throws java.lang.IndexOutOfBoundsException unless (0 &le; i < NMAX)
*/
public boolean contains(int i) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
return qp[i] != -1;
}

/**
* Returns the number of keys on the priority queue.
* @return the number of keys on the priority queue
*/
public int size() {
return N;
}

/**
* Associates key with index i.
* @param i an index
* @param key the key to associate with index i
* @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
* @throws java.util.IllegalArgumentException if there already is an item associated with index i
*/
public void insert(int i, Key key) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
N++;
qp[i] = N;
pq[N] = i;
keys[i] = key;
swim(N);
}

/**
* Returns an index associated with a minimum key.
* @return an index associated with a minimum key
* @throws java.util.NoSuchElementException if priority queue is empty
*/
public int minIndex() {
if (N == 0) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}

/**
* Returns a minimum key.
* @return a minimum key
* @throws java.util.NoSuchElementException if priority queue is empty
*/
public Key minKey() {
if (N == 0) throw new NoSuchElementException("Priority queue underflow");
return keys[pq[1]];
}

/**
* Removes a minimum key and returns its associated index.
* @return an index associated with a minimum key
* @throws java.util.NoSuchElementException if priority queue is empty
*/
public int delMin() {
if (N == 0) throw new NoSuchElementException("Priority queue underflow");
int min = pq[1];
exch(1, N--);
sink(1);
qp[min] = -1; // delete
keys[pq[N+1]] = null; // to help with garbage collection
pq[N+1] = -1; // not needed
return min;
}

/**
* Returns the key associated with index i.
* @param i the index of the key to return
* @return the key associated with index i
* @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
* @throws java.util.NoSuchElementException no key is associated with index i
*/
public Key keyOf(int i) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
else return keys[i];
}

/**
* Change the key associated with index i to the specified value.
* @param i the index of the key to change
* @param key change the key assocated with index i to this key
* @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
* @deprecated Replaced by changeKey()
*/
@Deprecated public void change(int i, Key key) {
changeKey(i, key);
}

/**
* Change the key associated with index i to the specified value.
* @param i the index of the key to change
* @param key change the key assocated with index i to this key
* @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
* @throws java.util.NoSuchElementException no key is associated with index i
*/
public void changeKey(int i, Key key) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
keys[i] = key;
swim(qp[i]);
sink(qp[i]);
}

/**
* Decrease the key associated with index i to the specified value.
* @param i the index of the key to decrease
* @param key decrease the key assocated with index i to this key
* @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
* @throws java.lang.IllegalArgumentException if key &ge; key associated with index i
* @throws java.util.NoSuchElementException no key is associated with index i
*/
public void decreaseKey(int i, Key key) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
if (keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
keys[i] = key;
swim(qp[i]);
}

/**
* Increase the key associated with index i to the specified value.
* @param i the index of the key to increase
* @param key increase the key assocated with index i to this key
* @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
* @throws java.lang.IllegalArgumentException if key &le; key associated with index i
* @throws java.util.NoSuchElementException no key is associated with index i
*/
public void increaseKey(int i, Key key) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
if (keys[i].compareTo(key) >= 0) throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
keys[i] = key;
sink(qp[i]);
}

/**
* Remove the key associated with index i.
* @param i the index of the key to remove
* @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
* @throws java.util.NoSuchElementException no key is associated with index i
*/
public void delete(int i) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
int index = qp[i];
exch(index, N--);
swim(index);
sink(index);
keys[i] = null;
qp[i] = -1;
}


/**************************************************************
* General helper functions
**************************************************************/
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}

private void exch(int i, int j) {
int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap;
qp[pq[i]] = i; qp[pq[j]] = j;
}


/**************************************************************
* Heap helper functions
**************************************************************/
private void swim(int k) {
while (k > 1 && greater(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}

private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && greater(j, j+1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}


/***********************************************************************
* Iterators
**********************************************************************/

/**
* Returns an iterator that iterates over the keys on the
* priority queue in ascending order.
* The iterator doesn't implement <tt>remove()</tt> since it's optional.
* @return an iterator that iterates over the keys in ascending order
*/
public Iterator<Integer> iterator() { return new HeapIterator(); }

private class HeapIterator implements Iterator<Integer> {
// create a new pq
private IndexMinPQ<Key> copy;

// add all elements to copy of heap
// takes linear time since already in heap order so no keys move
public HeapIterator() {
copy = new IndexMinPQ<Key>(pq.length - 1);
for (int i = 1; i <= N; i++)
copy.insert(pq[i], keys[pq[i]]);
}

public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }

public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}


/**
* Unit tests the <tt>IndexMinPQ</tt> data type.
*/
}
61 Xb3FinalProject/src/JPanelTest.java
View file
@@ -6,6 +6,8 @@
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

import javax.swing.JFrame;
@@ -23,15 +25,17 @@ private void doDrawing(Graphics g) throws IOException {

String singleLine = "";

BufferedReader in1 = new BufferedReader(new FileReader("Data/TG.txt"));//reads the input file
BufferedReader in1 = new BufferedReader(new FileReader("Data/OLCoordinates.txt"));//reads the input file

int count = 0;
while(in1.readLine()!=null){//counts number of lines in the file
count +=1;
}
in1.close();

BufferedReader in2 = new BufferedReader(new FileReader("Data/TG.txt"));
EdgeWeightedGraph graph = new EdgeWeightedGraph(count);

BufferedReader in2 = new BufferedReader(new FileReader("Data/OLCoordinates.txt"));

int count2 = 0;

@@ -60,20 +64,20 @@ private void doDrawing(Graphics g) throws IOException {

singleLine = "";

BufferedReader in3 = new BufferedReader(new FileReader("Data/TG2.txt"));//reads the input file
BufferedReader in3 = new BufferedReader(new FileReader("Data/OLRoads.txt"));//reads the input file

count = 0;
while(in3.readLine()!=null){//counts number of lines in the file
count +=1;
}
in3.close();

BufferedReader in4 = new BufferedReader(new FileReader("Data/TG2.txt"));

count2 = 0;
// EdgeWeightedGraph graph = new EdgeWeightedGraph(count);

EdgeWeightedGraph graph = new EdgeWeightedGraph(count);
BufferedReader in4 = new BufferedReader(new FileReader("Data/OLRoads.txt"));

count2 = 0;

while(count2!=count){
singleLine = in4.readLine();
String[] temp = singleLine.split(" ");
@@ -87,14 +91,53 @@ private void doDrawing(Graphics g) throws IOException {
double y2= data2[1];

Edge e = new Edge(Integer.parseInt(temp[1]), Integer.parseInt(temp[2]), Double.parseDouble(temp[3]));
Edge e2 = new Edge(Integer.parseInt(temp[2]), Integer.parseInt(temp[1]), Double.parseDouble(temp[3]));
graph.addEdge(e);
graph.addEdge(e2);
g2d.drawLine((int)x1+150, (int)y1+10, (int)x2+150, (int)y2+10);

count2++;
}
in4.close();
}


DijkstraSP sp = new DijkstraSP(graph, 0);

int counter = 0;
for (int t = 0; t < graph.V(); t++) {
if (sp.hasPathTo(t)) {
System.out.printf("%d to %d (%.2f) ", 0, t, sp.distTo(t));
if (sp.hasPathTo(t)) {
for (Edge e : sp.pathTo(t)) {
counter++;
System.out.print("");
}

Edge[] edgeArray = new Edge[counter];
int tempcount = 0;

for (Edge e : sp.pathTo(t)) {
edgeArray[tempcount] = e;
tempcount++;
}

Collections.reverse(Arrays.asList(edgeArray));
for (int i = 0; i < edgeArray.length; i++)
{
if (edgeArray[i] != null)
{
System.out.print(edgeArray[i] + " ");
}

}
}
System.out.println();
}
else {
System.out.printf("%d to %d no path\n", 0, t);
}
}
count =0;
}
@Override
public void paintComponent(Graphics g) {