Index: applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/AssignmentProblem.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/AssignmentProblem.java (revision 28116)
+++ applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/AssignmentProblem.java (revision 28116)
@@ -0,0 +1,192 @@
+// License: GPL v3 or later courtesy of author Kevin Wayne
+package edu.princeton.cs.algs4;
+
+/*************************************************************************
+ * Compilation: javac AssignmentProblem.java
+ * Execution: java AssignmentProblem N
+ * Dependencies: DijkstraSP.java DirectedEdge.java
+ *
+ * Solve an N-by-N assignment problem in N^3 log N time using the
+ * successive shortest path algorithm.
+ *
+ * Remark: could use dense version of Dijsktra's algorithm for
+ * improved theoretical efficiency of N^3, but it doesn't seem to
+ * help in practice.
+ *
+ * Assumes N-by-N cost matrix is nonnegative.
+ *
+ *
+ *********************************************************************/
+
+public class AssignmentProblem {
+ private static final int UNMATCHED = -1;
+
+ private int N; // number of rows and columns
+ private double[][] weight; // the N-by-N cost matrix
+ private double[] px; // px[i] = dual variable for row i
+ private double[] py; // py[j] = dual variable for col j
+ private int[] xy; // xy[i] = j means i-j is a match
+ private int[] yx; // yx[j] = i means i-j is a match
+
+
+ public AssignmentProblem(double[][] weight) {
+ N = weight.length;
+ this.weight = new double[N][N];
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ this.weight[i][j] = weight[i][j];
+
+ // dual variables
+ px = new double[N];
+ py = new double[N];
+
+ // initial matching is empty
+ xy = new int[N];
+ yx = new int[N];
+ for (int i = 0; i < N; i++) xy[i] = UNMATCHED;
+ for (int j = 0; j < N; j++) yx[j] = UNMATCHED;
+
+ // add N edges to matching
+ for (int k = 0; k < N; k++) {
+ assert isDualFeasible();
+ assert isComplementarySlack();
+ augment();
+ }
+ assert check();
+ }
+
+ // find shortest augmenting path and upate
+ private void augment() {
+
+ // build residual graph
+ EdgeWeightedDigraph G = new EdgeWeightedDigraph(2*N+2);
+ int s = 2*N, t = 2*N+1;
+ for (int i = 0; i < N; i++) {
+ if (xy[i] == UNMATCHED) G.addEdge(new DirectedEdge(s, i, 0.0));
+ }
+ for (int j = 0; j < N; j++) {
+ if (yx[j] == UNMATCHED) G.addEdge(new DirectedEdge(N+j, t, py[j]));
+ }
+ for (int i = 0; i < N; i++) {
+ for (int j = 0; j < N; j++) {
+ if (xy[i] == j) G.addEdge(new DirectedEdge(N+j, i, 0.0));
+ else G.addEdge(new DirectedEdge(i, N+j, reduced(i, j)));
+ }
+ }
+
+ // compute shortest path from s to every other vertex
+ DijkstraSP spt = new DijkstraSP(G, s);
+
+ // augment along alternating path
+ for (DirectedEdge e : spt.pathTo(t)) {
+ int i = e.from(), j = e.to() - N;
+ if (i < N) {
+ xy[i] = j;
+ yx[j] = i;
+ }
+ }
+
+ // update dual variables
+ for (int i = 0; i < N; i++) px[i] += spt.distTo(i);
+ for (int j = 0; j < N; j++) py[j] += spt.distTo(N+j);
+ }
+
+ // reduced cost of i-j
+ private double reduced(int i, int j) {
+ return weight[i][j] + px[i] - py[j];
+ }
+
+ // total weight of min weight perfect matching
+ public double weight() {
+ double total = 0.0;
+ for (int i = 0; i < N; i++) {
+ if (xy[i] != UNMATCHED)
+ total += weight[i][xy[i]];
+ }
+ return total;
+ }
+
+ public int sol(int i) {
+ return xy[i];
+ }
+
+ // check that dual variables are feasible
+ private boolean isDualFeasible() {
+ // check that all edges have >= 0 reduced cost
+ for (int i = 0; i < N; i++) {
+ for (int j = 0; j < N; j++) {
+ if (reduced(i, j) < 0) {
+// StdOut.println("Dual variables are not feasible");
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ // check that primal and dual variables are complementary slack
+ private boolean isComplementarySlack() {
+
+ // check that all matched edges have 0-reduced cost
+ for (int i = 0; i < N; i++) {
+ if ((xy[i] != UNMATCHED) && (reduced(i, xy[i]) != 0)) {
+// StdOut.println("Primal and dual variables are not complementary slack");
+ return false;
+ }
+ }
+ return true;
+ }
+
+ // check that primal variables are a perfect matching
+ private boolean isPerfectMatching() {
+
+ // check that xy[] is a perfect matching
+ boolean[] perm = new boolean[N];
+ for (int i = 0; i < N; i++) {
+ if (perm[xy[i]]) {
+// StdOut.println("Not a perfect matching");
+ return false;
+ }
+ perm[xy[i]] = true;
+ }
+
+ // check that xy[] and yx[] are inverses
+ for (int j = 0; j < N; j++) {
+ if (xy[yx[j]] != j) {
+// StdOut.println("xy[] and yx[] are not inverses");
+ return false;
+ }
+ }
+ for (int i = 0; i < N; i++) {
+ if (yx[xy[i]] != i) {
+// StdOut.println("xy[] and yx[] are not inverses");
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+
+ // check optimality conditions
+ private boolean check() {
+ return isPerfectMatching() && isDualFeasible() && isComplementarySlack();
+ }
+
+// public static void main(String[] args) {
+// In in = new In(args[0]);
+// int N = in.readInt();
+// double[][] weight = new double[N][N];
+// for (int i = 0; i < N; i++) {
+// for (int j = 0; j < N; j++) {
+// weight[i][j] = in.readDouble();
+// }
+// }
+//
+// AssignmentProblem assignment = new AssignmentProblem(weight);
+// StdOut.println("weight = " + assignment.weight());
+// for (int i = 0; i < N; i++)
+// StdOut.println(i + "-" + assignment.sol(i) + " " + weight[i][assignment.sol(i)]);
+// }
+
+}
Index: applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Bag.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Bag.java (revision 28116)
+++ applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Bag.java (revision 28116)
@@ -0,0 +1,117 @@
+// License: GPL v3 or later courtesy of author Kevin Wayne
+package edu.princeton.cs.algs4;
+
+/*************************************************************************
+ * Compilation: javac Bag.java
+ * Execution: java Bag < input.txt
+ *
+ * A generic bag or multiset, implemented using a linked list.
+ *
+ *************************************************************************/
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * The Bag class represents a bag (or multiset) of
+ * generic items. It supports insertion and iterating over the
+ * items in arbitrary order.
+ *
+ * The add, isEmpty, and size operation
+ * take constant time. Iteration takes time proportional to the number of items.
+ *
+ * For additional documentation, see Section 1.3 of
+ * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
+ */
+public class Bag- implements Iterable
- {
+ private int N; // number of elements in bag
+ private Node first; // beginning of bag
+
+ // helper linked list class
+ private class Node {
+ private Item item;
+ private Node next;
+ }
+
+ /**
+ * Create an empty stack.
+ */
+ public Bag() {
+ first = null;
+ N = 0;
+ assert check();
+ }
+
+ /**
+ * Is the BAG empty?
+ */
+ public boolean isEmpty() {
+ return first == null;
+ }
+
+ /**
+ * Return the number of items in the bag.
+ */
+ public int size() {
+ return N;
+ }
+
+ /**
+ * Add the item to the bag.
+ */
+ public void add(Item item) {
+ Node oldfirst = first;
+ first = new Node();
+ first.item = item;
+ first.next = oldfirst;
+ N++;
+ assert check();
+ }
+
+ // check internal invariants
+ private boolean check() {
+ if (N == 0) {
+ if (first != null) return false;
+ }
+ else if (N == 1) {
+ if (first == null) return false;
+ if (first.next != null) return false;
+ }
+ else {
+ if (first.next == null) return false;
+ }
+
+ // check internal consistency of instance variable N
+ int numberOfNodes = 0;
+ for (Node x = first; x != null; x = x.next) {
+ numberOfNodes++;
+ }
+ if (numberOfNodes != N) return false;
+
+ return true;
+ }
+
+
+ /**
+ * Return an iterator that iterates over the items in the bag.
+ */
+ public Iterator
- iterator() {
+ return new ListIterator();
+ }
+
+ // an iterator, doesn't implement remove() since it's optional
+ private class ListIterator implements Iterator
- {
+ private Node current = first;
+
+ public boolean hasNext() { return current != null; }
+ public void remove() { throw new UnsupportedOperationException(); }
+
+ public Item next() {
+ if (!hasNext()) throw new NoSuchElementException();
+ Item item = current.item;
+ current = current.next;
+ return item;
+ }
+ }
+
+}
Index: applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/DijkstraSP.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/DijkstraSP.java (revision 28116)
+++ applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/DijkstraSP.java (revision 28116)
@@ -0,0 +1,170 @@
+// License: GPL v3 or later courtesy of author Kevin Wayne
+package edu.princeton.cs.algs4;
+
+/*************************************************************************
+ * Compilation: javac DijkstraSP.java
+ * Execution: java DijkstraSP input.txt s
+ * Dependencies: EdgeWeightedDigraph.java IndexMinPQ.java Stack.java DirectedEdge.java
+ * Data files: http://algs4.cs.princeton.edu/44sp/tinyEWD.txt
+ * http://algs4.cs.princeton.edu/44sp/mediumEWD.txt
+ * http://algs4.cs.princeton.edu/44sp/largeEWD.txt
+ *
+ * Dijkstra's algorithm. Computes the shortest path tree.
+ * Assumes all weights are nonnegative.
+ *
+ * % java DijkstraSP tinyEWD.txt 0
+ * 0 to 0 (0.00)
+ * 0 to 1 (1.05) 0->4 0.38 4->5 0.35 5->1 0.32
+ * 0 to 2 (0.26) 0->2 0.26
+ * 0 to 3 (0.99) 0->2 0.26 2->7 0.34 7->3 0.39
+ * 0 to 4 (0.38) 0->4 0.38
+ * 0 to 5 (0.73) 0->4 0.38 4->5 0.35
+ * 0 to 6 (1.51) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52
+ * 0 to 7 (0.60) 0->2 0.26 2->7 0.34
+ *
+ * % java DijkstraSP mediumEWD.txt 0
+ * 0 to 0 (0.00)
+ * 0 to 1 (0.71) 0->44 0.06 44->93 0.07 ... 107->1 0.07
+ * 0 to 2 (0.65) 0->44 0.06 44->231 0.10 ... 42->2 0.11
+ * 0 to 3 (0.46) 0->97 0.08 97->248 0.09 ... 45->3 0.12
+ * 0 to 4 (0.42) 0->44 0.06 44->93 0.07 ... 77->4 0.11
+ * ...
+ *
+ *************************************************************************/
+
+public class DijkstraSP {
+ private double[] distTo; // distTo[v] = distance of shortest s->v path
+ private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
+ private IndexMinPQ pq; // priority queue of vertices
+
+ public DijkstraSP(EdgeWeightedDigraph G, int s) {
+ distTo = new double[G.V()];
+ edgeTo = new DirectedEdge[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(G.V());
+ pq.insert(s, distTo[s]);
+ while (!pq.isEmpty()) {
+ int v = pq.delMin();
+ for (DirectedEdge e : G.adj(v))
+ relax(e);
+ }
+
+ // check optimality conditions
+ assert check(G, s);
+ }
+
+ // relax edge e and update pq if changed
+ private void relax(DirectedEdge e) {
+ int v = e.from(), w = e.to();
+ if (distTo[w] > distTo[v] + e.weight()) {
+ distTo[w] = distTo[v] + e.weight();
+ edgeTo[w] = e;
+ if (pq.contains(w)) pq.change(w, distTo[w]);
+ else pq.insert(w, distTo[w]);
+ }
+ }
+
+ // length of shortest path from s to v
+ public double distTo(int v) {
+ return distTo[v];
+ }
+
+ // is there a path from s to v?
+ public boolean hasPathTo(int v) {
+ return distTo[v] < Double.POSITIVE_INFINITY;
+ }
+
+ // shortest path from s to v as an Iterable, null if no such path
+ public Iterable pathTo(int v) {
+ if (!hasPathTo(v)) return null;
+ Stack path = new Stack();
+ for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
+ path.push(e);
+ }
+ 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(EdgeWeightedDigraph G, int s) {
+
+ // check that edge weights are nonnegative
+ for (DirectedEdge 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 (DirectedEdge e : G.adj(v)) {
+ int w = e.to();
+ 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;
+ DirectedEdge e = edgeTo[w];
+ int v = e.from();
+ if (w != e.to()) return false;
+ if (distTo[v] + e.weight() != distTo[w]) {
+ System.err.println("edge " + e + " on shortest path not tight");
+ return false;
+ }
+ }
+ return true;
+ }
+
+
+// public static void main(String[] args) {
+// In in = new In(args[0]);
+// EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
+// int s = Integer.parseInt(args[1]);
+//
+// // compute shortest paths
+// DijkstraSP sp = new DijkstraSP(G, s);
+//
+//
+// // print shortest path
+// for (int t = 0; t < G.V(); t++) {
+// if (sp.hasPathTo(t)) {
+// StdOut.printf("%d to %d (%.2f) ", s, t, sp.distTo(t));
+// if (sp.hasPathTo(t)) {
+// for (DirectedEdge e : sp.pathTo(t)) {
+// StdOut.print(e + " ");
+// }
+// }
+// StdOut.println();
+// }
+// else {
+// StdOut.printf("%d to %d no path\n", s, t);
+// }
+// }
+// }
+
+}
Index: applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/DirectedEdge.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/DirectedEdge.java (revision 28116)
+++ applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/DirectedEdge.java (revision 28116)
@@ -0,0 +1,66 @@
+// License: GPL v3 or later courtesy of author Kevin Wayne
+package edu.princeton.cs.algs4;
+
+/*************************************************************************
+ * Compilation: javac DirectedEdge.java
+ * Execution: java DirectedEdge
+ *
+ * Immutable weighted directed edge.
+ *
+ *************************************************************************/
+
+/**
+ * The DirectedEdge class represents a weighted edge in an directed graph.
+ *
+ * For additional documentation, see Section 4.4 of
+ * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
+ */
+
+public class DirectedEdge {
+ private final int v;
+ private final int w;
+ private final double weight;
+
+ /**
+ * Create a directed edge from v to w with given weight.
+ */
+ public DirectedEdge(int v, int w, double weight) {
+ this.v = v;
+ this.w = w;
+ this.weight = weight;
+ }
+
+ /**
+ * Return the vertex where this edge begins.
+ */
+ public int from() {
+ return v;
+ }
+
+ /**
+ * Return the vertex where this edge ends.
+ */
+ public int to() {
+ return w;
+ }
+
+ /**
+ * Return the weight of this edge.
+ */
+ public double weight() { return weight; }
+
+ /**
+ * Return a string representation of this edge.
+ */
+ public String toString() {
+ return v + "->" + w + " " + String.format("%5.2f", weight);
+ }
+
+ /**
+ * Test client.
+ */
+// public static void main(String[] args) {
+// DirectedEdge e = new DirectedEdge(12, 23, 3.14);
+// StdOut.println(e);
+// }
+}
Index: applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/EdgeWeightedDigraph.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/EdgeWeightedDigraph.java (revision 28116)
+++ applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/EdgeWeightedDigraph.java (revision 28116)
@@ -0,0 +1,174 @@
+// License: GPL v3 or later courtesy of author Kevin Wayne
+package edu.princeton.cs.algs4;
+
+/*************************************************************************
+ * Compilation: javac EdgeWeightedDigraph.java
+ * Execution: java EdgeWeightedDigraph V E
+ * Dependencies: Bag.java DirectedEdge.java
+ *
+ * An edge-weighted digraph, implemented using adjacency lists.
+ *
+ *************************************************************************/
+
+/**
+ * The EdgeWeightedDigraph class represents an directed graph of vertices
+ * named 0 through V-1, where each edge has a real-valued weight.
+ * It supports the following operations: add an edge to the graph,
+ * iterate over all of edges leaving a vertex.
+ * Parallel edges and self-loops are permitted.
+ *
+ * For additional documentation, see Section 4.4 of
+ * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
+ */
+
+
+
+public class EdgeWeightedDigraph {
+ private final int V;
+ private int E;
+ private Bag[] adj;
+
+ /**
+ * Create an empty edge-weighted digraph with V vertices.
+ */
+ public EdgeWeightedDigraph(int V) {
+ if (V < 0) throw new RuntimeException("Number of vertices must be nonnegative");
+ this.V = V;
+ this.E = 0;
+ adj = (Bag[]) new Bag[V];
+ for (int v = 0; v < V; v++)
+ adj[v] = new Bag();
+ }
+
+ /**
+ * Create a edge-weighted digraph with V vertices and E edges.
+ */
+ public EdgeWeightedDigraph(int V, int E) {
+ this(V);
+ if (E < 0) throw new RuntimeException("Number of edges must be nonnegative");
+ for (int i = 0; i < E; i++) {
+ int v = (int) (Math.random() * V);
+ int w = (int) (Math.random() * V);
+ double weight = Math.round(100 * Math.random()) / 100.0;
+ DirectedEdge e = new DirectedEdge(v, w, weight);
+ addEdge(e);
+ }
+ }
+
+ /**
+ * Create an edge-weighted digraph from input stream.
+ */
+// public EdgeWeightedDigraph(In in) {
+// this(in.readInt());
+// int E = in.readInt();
+// for (int i = 0; i < E; i++) {
+// int v = in.readInt();
+// int w = in.readInt();
+// double weight = in.readDouble();
+// addEdge(new DirectedEdge(v, w, weight));
+// }
+// }
+
+ /**
+ * Copy constructor.
+ */
+ public EdgeWeightedDigraph(EdgeWeightedDigraph G) {
+ this(G.V());
+ this.E = G.E();
+ for (int v = 0; v < G.V(); v++) {
+ // reverse so that adjacency list is in same order as original
+ Stack reverse = new Stack();
+ for (DirectedEdge e : G.adj[v]) {
+ reverse.push(e);
+ }
+ for (DirectedEdge e : reverse) {
+ adj[v].add(e);
+ }
+ }
+ }
+
+ /**
+ * Return the number of vertices in this digraph.
+ */
+ public int V() {
+ return V;
+ }
+
+ /**
+ * Return the number of edges in this digraph.
+ */
+ public int E() {
+ return E;
+ }
+
+
+ /**
+ * Add the edge e to this digraph.
+ */
+ public void addEdge(DirectedEdge e) {
+ int v = e.from();
+ adj[v].add(e);
+ E++;
+ }
+
+
+ /**
+ * Return the edges leaving vertex v as an Iterable.
+ * To iterate over the edges leaving vertex v, use foreach notation:
+ * for (DirectedEdge e : graph.adj(v)).
+ */
+ public Iterable adj(int v) {
+ return adj[v];
+ }
+
+ /**
+ * Return all edges in this graph as an Iterable.
+ * To iterate over the edges, use foreach notation:
+ * for (DirectedEdge e : graph.edges()).
+ */
+ public Iterable edges() {
+ Bag list = new Bag();
+ for (int v = 0; v < V; v++) {
+ for (DirectedEdge e : adj(v)) {
+ list.add(e);
+ }
+ }
+ return list;
+ }
+
+ /**
+ * Return number of edges leaving v.
+ */
+ public int outdegree(int v) {
+ return adj[v].size();
+ }
+
+
+
+ /**
+ * Return a string representation of this graph.
+ */
+ public String toString() {
+ String NEWLINE = System.getProperty("line.separator");
+ StringBuilder s = new StringBuilder();
+ s.append(V + " " + E + NEWLINE);
+ for (int v = 0; v < V; v++) {
+ s.append(v + ": ");
+ for (DirectedEdge e : adj[v]) {
+ s.append(e + " ");
+ }
+ s.append(NEWLINE);
+ }
+ return s.toString();
+ }
+
+ /**
+ * Test client.
+ */
+// public static void main(String[] args) {
+// In in = new In(args[0]);
+// EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
+// StdOut.println(G);
+// }
+
+}
Index: applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/IndexMinPQ.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/IndexMinPQ.java (revision 28116)
+++ applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/IndexMinPQ.java (revision 28116)
@@ -0,0 +1,220 @@
+// License: GPL v3 or later courtesy of author Kevin Wayne
+package edu.princeton.cs.algs4;
+
+/*************************************************************************
+ * Compilation: javac IndexMinPQ.java
+ * Execution: java IndexMinPQ
+ *
+ * Indexed PQ implementation using a binary heap.
+ *
+ *********************************************************************/
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public class IndexMinPQ> implements Iterable {
+ 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
+
+ public IndexMinPQ(int 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?
+ public boolean isEmpty() { return N == 0; }
+
+ // is k an index on the priority queue?
+ public boolean contains(int k) {
+ return qp[k] != -1;
+ }
+
+ // number of keys in the priority queue
+ public int size() {
+ return N;
+ }
+
+ // associate key with index k
+ public void insert(int k, Key key) {
+ if (contains(k)) throw new NoSuchElementException("item is already in pq");
+ N++;
+ qp[k] = N;
+ pq[N] = k;
+ keys[k] = key;
+ swim(N);
+ }
+
+ // return the index associated with a minimal key
+ public int minIndex() {
+ if (N == 0) throw new NoSuchElementException("Priority queue underflow");
+ return pq[1];
+ }
+
+ // return a minimal key
+ public Key minKey() {
+ if (N == 0) throw new NoSuchElementException("Priority queue underflow");
+ return keys[pq[1]];
+ }
+
+ // delete a minimal key and returns its associated index
+ 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;
+ }
+
+ // return key associated with index k
+ public Key keyOf(int k) {
+ if (!contains(k)) throw new NoSuchElementException("item is not in pq");
+ else return keys[k];
+ }
+
+ // change the key associated with index k
+ public void change(int k, Key key) {
+ changeKey(k, key);
+ }
+
+ // change the key associated with index k
+ public void changeKey(int k, Key key) {
+ if (!contains(k)) throw new NoSuchElementException("item is not in pq");
+ keys[k] = key;
+ swim(qp[k]);
+ sink(qp[k]);
+ }
+
+ // decrease the key associated with index k
+ public void decreaseKey(int k, Key key) {
+ if (!contains(k)) throw new NoSuchElementException("item is not in pq");
+ if (keys[k].compareTo(key) <= 0) throw new RuntimeException("illegal decrease");
+ keys[k] = key;
+ swim(qp[k]);
+ }
+
+ // increase the key associated with index k
+ public void increaseKey(int k, Key key) {
+ if (!contains(k)) throw new NoSuchElementException("item is not in pq");
+ if (keys[k].compareTo(key) >= 0) throw new RuntimeException("illegal decrease");
+ keys[k] = key;
+ sink(qp[k]);
+ }
+
+ // delete the key associated with index k
+ public void delete(int k) {
+ if (!contains(k)) throw new NoSuchElementException("item is not in pq");
+ int index = qp[k];
+ exch(index, N--);
+ swim(index);
+ sink(index);
+ keys[k] = null;
+ qp[k] = -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
+ **********************************************************************/
+
+ /**
+ * Return an iterator that iterates over all of the elements on the
+ * priority queue in ascending order.
+ *
+ * The iterator doesn't implement remove() since it's optional.
+ */
+ public Iterator iterator() { return new HeapIterator(); }
+
+ private class HeapIterator implements Iterator {
+ // create a new pq
+ private IndexMinPQ 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(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();
+ }
+ }
+
+
+// public static void main(String[] args) {
+// // insert a bunch of strings
+// String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
+//
+// IndexMinPQ pq = new IndexMinPQ(strings.length);
+// for (int i = 0; i < strings.length; i++) {
+// pq.insert(i, strings[i]);
+// }
+//
+// // delete and print each key
+// while (!pq.isEmpty()) {
+// int i = pq.delMin();
+// StdOut.println(i + " " + strings[i]);
+// }
+// StdOut.println();
+//
+// // reinsert the same strings
+// for (int i = 0; i < strings.length; i++) {
+// pq.insert(i, strings[i]);
+// }
+//
+// // print each key using the iterator
+// for (int i : pq) {
+// StdOut.println(i + " " + strings[i]);
+// }
+// while (!pq.isEmpty()) {
+// pq.delMin();
+// }
+//
+// }
+}
Index: applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Stack.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Stack.java (revision 28116)
+++ applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Stack.java (revision 28116)
@@ -0,0 +1,170 @@
+// License: GPL v3 or later courtesy of author Kevin Wayne
+package edu.princeton.cs.algs4;
+
+/*************************************************************************
+ * Compilation: javac Stack.java
+ * Execution: java Stack < input.txt
+ *
+ * A generic stack, implemented using a linked list. Each stack
+ * element is of type Item.
+ *
+ * % more tobe.txt
+ * to be or not to - be - - that - - - is
+ *
+ * % java Stack < tobe.txt
+ * to be not that or be (2 left on stack)
+ *
+ *************************************************************************/
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+
+/**
+ * The Stack class represents a last-in-first-out (LIFO) stack of generic items.
+ * It supports the usual push and pop operations, along with methods
+ * for peeking at the top item, testing if the stack is empty, and iterating through
+ * the items in LIFO order.
+ *
+ * All stack operations except iteration are constant time.
+ *
+ * For additional documentation, see Section 1.3 of
+ * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
+ */
+public class Stack- implements Iterable
- {
+ private int N; // size of the stack
+ private Node first; // top of stack
+
+ // helper linked list class
+ private class Node {
+ private Item item;
+ private Node next;
+ }
+
+ /**
+ * Create an empty stack.
+ */
+ public Stack() {
+ first = null;
+ N = 0;
+ assert check();
+ }
+
+ /**
+ * Is the stack empty?
+ */
+ public boolean isEmpty() {
+ return first == null;
+ }
+
+ /**
+ * Return the number of items in the stack.
+ */
+ public int size() {
+ return N;
+ }
+
+ /**
+ * Add the item to the stack.
+ */
+ public void push(Item item) {
+ Node oldfirst = first;
+ first = new Node();
+ first.item = item;
+ first.next = oldfirst;
+ N++;
+ assert check();
+ }
+
+ /**
+ * Delete and return the item most recently added to the stack.
+ * Throw an exception if no such item exists because the stack is empty.
+ */
+ public Item pop() {
+ if (isEmpty()) throw new RuntimeException("Stack underflow");
+ Item item = first.item; // save item to return
+ first = first.next; // delete first node
+ N--;
+ assert check();
+ return item; // return the saved item
+ }
+
+
+ /**
+ * Return the item most recently added to the stack.
+ * Throw an exception if no such item exists because the stack is empty.
+ */
+ public Item peek() {
+ if (isEmpty()) throw new RuntimeException("Stack underflow");
+ return first.item;
+ }
+
+ /**
+ * Return string representation.
+ */
+ public String toString() {
+ StringBuilder s = new StringBuilder();
+ for (Item item : this)
+ s.append(item + " ");
+ return s.toString();
+ }
+
+
+ // check internal invariants
+ private boolean check() {
+ if (N == 0) {
+ if (first != null) return false;
+ }
+ else if (N == 1) {
+ if (first == null) return false;
+ if (first.next != null) return false;
+ }
+ else {
+ if (first.next == null) return false;
+ }
+
+ // check internal consistency of instance variable N
+ int numberOfNodes = 0;
+ for (Node x = first; x != null; x = x.next) {
+ numberOfNodes++;
+ }
+ if (numberOfNodes != N) return false;
+
+ return true;
+ }
+
+
+ /**
+ * Return an iterator to the stack that iterates through the items in LIFO order.
+ */
+ public Iterator
- iterator() { return new ListIterator(); }
+
+ // an iterator, doesn't implement remove() since it's optional
+ private class ListIterator implements Iterator
- {
+ private Node current = first;
+ public boolean hasNext() { return current != null; }
+ public void remove() { throw new UnsupportedOperationException(); }
+
+ public Item next() {
+ if (!hasNext()) throw new NoSuchElementException();
+ Item item = current.item;
+ current = current.next;
+ return item;
+ }
+ }
+
+
+ /**
+ * A test client.
+ */
+// public static void main(String[] args) {
+// Stack s = new Stack();
+// while (!StdIn.isEmpty()) {
+// String item = StdIn.readString();
+// if (!item.equals("-")) s.push(item);
+// else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
+// }
+// StdOut.println("(" + s.size() + " left on stack)");
+// }
+}
+
Index: applications/editors/josm/plugins/utilsplugin2/src/org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/HungarianAlgorithm.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/HungarianAlgorithm.java (revision 28045)
+++ (revision )
@@ -1,605 +1,0 @@
-/*
- * Created on Apr 25, 2005
- *
- * Munkres-Kuhn (Hungarian) Algorithm Clean Version: 0.11
- *
- * Konstantinos A. Nedas
- * Department of Spatial Information Science & Engineering
- * University of Maine, Orono, ME 04469-5711, USA
- * kostas@spatial.maine.edu
- * http://www.spatial.maine.edu/~kostas
- *
- * This Java class implements the Hungarian algorithm [a.k.a Munkres' algorithm,
- * a.k.a. Kuhn algorithm, a.k.a. Assignment problem, a.k.a. Marriage problem,
- * a.k.a. Maximum Weighted Maximum Cardinality Bipartite Matching].
- *
- * [It can be used as a method call from within any main (or other function).]
- * It takes 2 arguments:
- * a. A 2-D array (could be rectangular or square).
- * b. A string ("min" or "max") specifying whether you want the min or max assignment.
- * [It returns an assignment matrix[array.length][2] that contains the row and col of
- * the elements (in the original inputted array) that make up the optimum assignment.]
- *
- * [This version contains only scarce comments. If you want to understand the
- * inner workings of the algorithm, get the tutorial version of the algorithm
- * from the same website you got this one (http://www.spatial.maine.edu/~kostas/dev/soft/munkres.htm)]
- *
- * Any comments, corrections, or additions would be much appreciated.
- * Credit due to professor Bob Pilgrim for providing an online copy of the
- * pseudocode for this algorithm (http://216.249.163.93/bob.pilgrim/445/munkres.html)
- *
- * Feel free to redistribute this source code, as long as this header--with
- * the exception of sections in brackets--remains as part of the file.
- *
- * Requirements: JDK 1.5.0_01 or better.
- * [Created in Eclipse 3.1M6 (www.eclipse.org).]
- *
- */
-
-package org.openstreetmap.josm.plugins.utilsplugin2.replacegeometry;
-
-import static java.lang.Math.*;
-import java.util.*;
-
-public class HungarianAlgorithm {
-
- //********************************//
- //METHODS FOR CONSOLE INPUT-OUTPUT//
- //********************************//
-
- public static int readInput(String prompt) //Reads input,returns double.
- {
- Scanner in = new Scanner(System.in);
- System.out.print(prompt);
- int input = in.nextInt();
- return input;
- }
- public static void printTime(double time) //Formats time output.
- {
- String timeElapsed = "";
- int days = (int)floor(time)/(24 * 3600);
- int hours = (int)floor(time%(24*3600))/(3600);
- int minutes = (int)floor((time%3600)/60);
- int seconds = (int)round(time%60);
-
- if (days > 0)
- timeElapsed = Integer.toString(days) + "d:";
- if (hours > 0)
- timeElapsed = timeElapsed + Integer.toString(hours) + "h:";
- if (minutes > 0)
- timeElapsed = timeElapsed + Integer.toString(minutes) + "m:";
-
- timeElapsed = timeElapsed + Integer.toString(seconds) + "s";
- System.out.print("\nTotal time required: " + timeElapsed + "\n\n");
- }
-
- //*******************************************//
- //METHODS THAT PERFORM ARRAY-PROCESSING TASKS//
- //*******************************************//
-
- public static void generateRandomArray //Generates random 2-D array.
- (double[][] array, String randomMethod)
- {
- Random generator = new Random();
- for (int i=0; i 0.5) {array[i][j] = 0.5;} //eliminate outliers.
- if (array[i][j] < -0.5) {array[i][j] = -0.5;} //eliminate outliers.
- array[i][j] = array[i][j] + 0.5; //make elements positive.
- }
- }
- }
- }
- public static double findLargest //Finds the largest element in a positive array.
- (double[][] array)
- //works for arrays where all values are >= 0.
- {
- double largest = 0;
- for (int i=0; i largest)
- {
- largest = array[i][j];
- }
- }
- }
-
- return largest;
- }
- public static double[][] transpose //Transposes a double[][] array.
- (double[][] array)
- {
- double[][] transposedArray = new double[array[0].length][array.length];
- for (int i=0; icost[i][j])
- {
- minval=cost[i][j];
- }
- }
- for (int j=0; j=mask.length) //Should be cost.length but ok, because mask has same dimensions.
- {
- step=7;
- }
- else
- {
- step=4;
- }
-
- return step;
- }
- public static int hg_step4(int step, double[][] cost, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC)
- {
- //What STEP 4 does:
- //Find an uncovered zero in cost and prime it (if none go to step 6). Check for star in same row:
- //if yes, cover the row and uncover the star's column. Repeat until no uncovered zeros are left
- //and go to step 6. If not, save location of primed zero and go to step 5.
-
- int[] row_col = new int[2]; //Holds row and col of uncovered zero.
- boolean done = false;
- while (done == false)
- {
- row_col = findUncoveredZero(row_col, cost, rowCover, colCover);
- if (row_col[0] == -1)
- {
- done = true;
- step = 6;
- }
- else
- {
- mask[row_col[0]][row_col[1]] = 2; //Prime the found uncovered zero.
-
- boolean starInRow = false;
- for (int j=0; j= cost.length)
- {
- done = true;
- }
- }//end outer while
-
- return row_col;
- }
- public static int hg_step5(int step, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC)
- {
- //What STEP 5 does:
- //Construct series of alternating primes and stars. Start with prime from step 4.
- //Take star in the same column. Next take prime in the same row as the star. Finish
- //at a prime with no star in its column. Unstar all stars and star the primes of the
- //series. Erasy any other primes. Reset covers. Go to step 3.
-
- int count = 0; //Counts rows of the path matrix.
- int[][] path = new int[(mask[0].length*mask.length)][2]; //Path matrix (stores row and col).
- path[count][0] = zero_RC[0]; //Row of last prime.
- path[count][1] = zero_RC[1]; //Column of last prime.
-
- boolean done = false;
- while (done == false)
- {
- int r = findStarInCol(mask, path[count][1]);
- if (r>=0)
- {
- count = count+1;
- path[count][0] = r; //Row of starred zero.
- path[count][1] = path[count-1][1]; //Column of starred zero.
- }
- else
- {
- done = true;
- }
-
- if (done == false)
- {
- int c = findPrimeInRow(mask, path[count][0]);
- count = count+1;
- path[count][0] = path [count-1][0]; //Row of primed zero.
- path[count][1] = c; //Col of primed zero.
- }
- }//end while
-
- convertPath(mask, path, count);
- clearCovers(rowCover, colCover);
- erasePrimes(mask);
-
- step = 3;
- return step;
-
- }
- public static int findStarInCol //Aux 1 for hg_step5.
- (int[][] mask, int col)
- {
- int r=-1; //Again this is a check value.
- for (int i=0; i cost[i][j]))
- {
- minval = cost[i][j];
- }
- }
- }
-
- return minval;
- }
-
- //***********//
- //MAIN METHOD//
- //***********//
-
- public static void main(String[] args)
- {
- //Below enter "max" or "min" to find maximum sum or minimum sum assignment.
- String sumType = "max";
-
- //Hard-coded example.
- //double[][] array =
- //{
- // {1, 2, 3},
- // {2, 4, 6},
- // {3, 6, 9}
- //};
-
- // BELOW AND COMMENT BLOCK ABOVE TO USE A RANDOMLY GENERATED MATRIX
- int numOfRows = readInput("How many rows for the matrix? ");
- int numOfCols = readInput("How many columns for the matrix? ");
- double[][] array = new double[numOfRows][numOfCols];
- generateRandomArray(array, "random"); //All elements within [0,1].
- //
-
- if (array.length > array[0].length)
- {
- System.out.println("Array transposed (because rows>columns).\n"); //Cols must be >= Rows.
- array = transpose(array);
- }
-
- // TO AVOID PRINTING THE MATRIX FOR WHICH THE ASSIGNMENT IS CALCULATED
- System.out.println("\n(Printing out only 2 decimals)\n");
- System.out.println("The matrix is:");
- for (int i=0; i*/
-
- double startTime = System.nanoTime();
- int[][] assignment = new int[array.length][2];
- assignment = hgAlgorithm(array, sumType); //Call Hungarian algorithm.
- double endTime = System.nanoTime();
-
- System.out.println("The winning assignment (" + sumType + " sum) is:\n");
- double sum = 0;
- for (int i=0; i to avoid printing the elements that make up the assignment
- System.out.printf("array(%d,%d) = %.2f\n", (assignment[i][0]+1), (assignment[i][1]+1),
- array[assignment[i][0]][assignment[i][1]]);
- sum = sum + array[assignment[i][0]][assignment[i][1]];
- //
- }
-
- System.out.printf("\nThe %s is: %.2f\n", sumType, sum);
- printTime((endTime - startTime)/1000000000.0);
-
- }
-}
Index: applications/editors/josm/plugins/utilsplugin2/src/org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/ReplaceGeometryUtils.java
===================================================================
--- applications/editors/josm/plugins/utilsplugin2/src/org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/ReplaceGeometryUtils.java (revision 28045)
+++ applications/editors/josm/plugins/utilsplugin2/src/org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/ReplaceGeometryUtils.java (revision 28116)
@@ -1,4 +1,5 @@
package org.openstreetmap.josm.plugins.utilsplugin2.replacegeometry;
+import edu.princeton.cs.algs4.AssignmentProblem;
import java.awt.geom.Area;
import java.awt.geom.Point2D;
@@ -264,5 +265,5 @@
}
- boolean useHungarian = Main.pref.getBoolean("utilsplugin2.replace-geometry.robustAssignment", false);
+ boolean useRobust = Main.pref.getBoolean("utilsplugin2.replace-geometry.robustAssignment", true);
// Find new nodes that are closest to the old ones, remove matching old ones from the pool
@@ -270,8 +271,14 @@
Map nodeAssoc = new HashMap();
if (geometryPool.size() > 0 && nodePool.size() > 0) {
- if (useHungarian) { // use robust, but slower assignment
+ if (useRobust) { // use robust, but slower assignment
int gLen = geometryPool.size();
int nLen = nodePool.size();
- double cost[][] = new double[nLen][gLen];
+ int N = Math.max(gLen, nLen);
+ double cost[][] = new double[N][N];
+ for (int i = 0; i < N; i++) {
+ for (int j = 0; j < N; j++) {
+ cost[i][j] = Double.MAX_VALUE;
+ }
+ }
double maxDistance = Double.parseDouble(Main.pref.get("utilsplugin2.replace-geometry.max-distance", "1"));
@@ -286,8 +293,8 @@
}
}
- int[][] assignment = HungarianAlgorithm.hgAlgorithm(cost, "min");
- for (int i = 0; i < nLen; i++) {
- int nIdx = assignment[i][0];
- int gIdx = assignment[i][1];
+ AssignmentProblem assignment = new AssignmentProblem(cost);
+ for (int i = 0; i < N; i++) {
+ int nIdx = i;
+ int gIdx = assignment.sol(i);
if (cost[nIdx][gIdx] != Double.MAX_VALUE) {
nodeAssoc.put(geometryPool.get(gIdx), nodePool.get(nIdx));