Below is the syntax highlighted version of Arbitrage.java.
/****************************************************************************** * Compilation: javac Arbitrage.java * Execution: java Arbitrage < input.txt * Dependencies: EdgeWeightedDigraph.java DirectedEdge.java * BellmanFordSP.java * Data file: https://algs4.cs.princeton.edu/44sp/rates.txt * * Arbitrage detection. * * % more rates.txt * 5 * USD 1 0.741 0.657 1.061 1.005 * EUR 1.349 1 0.888 1.433 1.366 * GBP 1.521 1.126 1 1.614 1.538 * CHF 0.942 0.698 0.619 1 0.953 * CAD 0.995 0.732 0.650 1.049 1 * * % java Arbitrage < rates.txt * 1000.00000 USD = 741.00000 EUR * 741.00000 EUR = 1012.20600 CAD * 1012.20600 CAD = 1007.14497 USD * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code Arbitrage} class provides a client that finds an arbitrage * opportunity in a currency exchange table by constructing a * complete-digraph representation of the exchange table and then finding * a negative cycle in the digraph. * <p> * This implementation uses the Bellman-Ford algorithm to find a * negative cycle in the complete digraph. * The running time is proportional to <em>V</em><sup>3</sup> in the * worst case, where <em>V</em> is the number of currencies. * <p> * This code is guaranteed to find an arbitrage opportunity in a * currency exchange table (or report that no such arbitrage * opportunity exists) under the assumption that all arithmetic * performed is without floating-point rounding error or arithmetic * overflow. Since the code computes the logarithms of the edge weights, * floating-point rounding error will be present, and it may fail on * some pathological inputs. * <p> * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/44sp">Section 4.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Arbitrage { // this class cannot be instantiated private Arbitrage() { } /** * Reads the currency exchange table from standard input and * prints an arbitrage opportunity to standard output (if one exists). * * @param args the command-line arguments */ public static void main(String[] args) { // V currencies int V = StdIn.readInt(); String[] name = new String[V]; // create complete network EdgeWeightedDigraph G = new EdgeWeightedDigraph(V); for (int v = 0; v < V; v++) { name[v] = StdIn.readString(); for (int w = 0; w < V; w++) { double rate = StdIn.readDouble(); DirectedEdge e = new DirectedEdge(v, w, -Math.log(rate)); G.addEdge(e); } } // find negative cycle BellmanFordSP spt = new BellmanFordSP(G, 0); if (spt.hasNegativeCycle()) { double stake = 1000.0; for (DirectedEdge e : spt.negativeCycle()) { StdOut.printf("%10.5f %s ", stake, name[e.from()]); stake *= Math.exp(-e.weight()); StdOut.printf("= %10.5f %s\n", stake, name[e.to()]); } } else { StdOut.println("No arbitrage opportunity"); } } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/