001package algs44; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac Arbitrage.java 005 * Execution: java Arbitrage < input.txt 006 * Dependencies: EdgeWeightedDigraph.java DirectedEdge.java 007 * BellmanFordSP.java 008 * Data file: http://algs4.cs.princeton.edu/44sp/rates.txt 009 * 010 * Arbitrage detection. 011 * 012 * % more rates.txt 013 * 5 014 * USD 1 0.741 0.657 1.061 1.005 015 * EUR 1.349 1 0.888 1.433 1.366 016 * GBP 1.521 1.126 1 1.614 1.538 017 * CHF 0.942 0.698 0.619 1 0.953 018 * CAD 0.995 0.732 0.650 1.049 1 019 * 020 * % java Arbitrage < rates.txt 021 * 1000.00000 USD = 741.00000 EUR 022 * 741.00000 EUR = 1012.20600 CAD 023 * 1012.20600 CAD = 1007.14497 USD 024 * 025 *************************************************************************/ 026 027public class Arbitrage { 028 029 public static void main(String[] args) { 030 031 // V currencies 032 int V = StdIn.readInt(); 033 String[] name = new String[V]; 034 035 // create complete network 036 EdgeWeightedDigraph G = new EdgeWeightedDigraph(V); 037 for (int v = 0; v < V; v++) { 038 name[v] = StdIn.readString(); 039 for (int w = 0; w < V; w++) { 040 double rate = StdIn.readDouble(); 041 DirectedEdge e = new DirectedEdge(v, w, -Math.log(rate)); 042 G.addEdge(e); 043 } 044 } 045 046 // find negative cycle 047 BellmanFordSP spt = new BellmanFordSP(G, 0); 048 if (spt.hasNegativeCycle()) { 049 double stake = 1000.0; 050 for (DirectedEdge e : spt.negativeCycle()) { 051 StdOut.format("%10.5f %s ", stake, name[e.from()]); 052 stake *= Math.exp(-e.weight()); 053 StdOut.format("= %10.5f %s\n", stake, name[e.to()]); 054 } 055 } 056 else { 057 StdOut.println("No arbitrage opportunity"); 058 } 059 } 060 061}