Arbitrage

//Arbitrage is the simultaneous purchase and sale of an asset to profit from a difference in the price. This translates to
//a cycle of one unit translated to other units, ending with that unit's increase. A graph can be used to represent arbitrage 
//if there is a cycle.  Since negative weights could be involved in such conversions, Bellman-Ford is a natural choice for 
//this solution. In general 1 unit of X returns > 1 unit of X.  1X--2G--7Y--1.2X
//a*b > 1
//In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices 
//is connected by a unique edge.   Since the arbitrage problem involves a complete graph, we can run BF from any vertex.
//There is a mathematics hack that aids us in finding cycles that makes use of the fact that BF can detect negative cycles.
//Fact: log(a*b) == log(A) + log(b)
//then, if we allow each weight in the graph to be rewrittten  as -lg(w), and the fact that log(1) == 0
//     log(a*b) > 0 iff -log(a) - log(b) < 0
//With this helpful assignment to weights, we can detect when they sum to less than zero or a negative weight cycle exists. 

 boolean isArbitrage(List<List<Double>> G) {
//set up the graph with -log weights
    for (List<Double> edgeList : G) {
      for (int i = 0; i < edgeList.size(); i++) {
        edgeList.set(i, -Math.log10(edgeList.get(i)));
      }
    }
    return BellmanFordDetectCycle(G, 0);
  }

  boolean BellmanFordDetectCycle(List<List<Double>> G, int src) {
    List<Double> distToSrc = new ArrayList<>(Collections.nCopies(G.size(), Double.MAX_VALUE));
    distToSrc.set(source, 0.0);
    for (int t = 1; t < G.size(); ++t) {
      boolean update = false;
     //relax edges--get a shorter path if it exists
     for (int i = 0; i < G.size(); i++) {
        for (int j = 0; j < G.get(i).size(); j +=) {
          if (disToSrc.get(i) != Double.MAX_VALUE && distToSrc.get(j) > distToSrc.get(i) + G.get(i).get(j)) {
            //we have a shorter path
            update = true;
            distToSrc.set(j, disToSrc.get(i) + G.get(i).get(j));
          }
        }
      }
      //without any relaxation, we cannot possible have a cycle because there is not a shorter path
      if (!update) {
        return false;
      }
    }
    //If there is a negative weight cycle, then one of the edges of that cycle can always be relaxed 
    //because it can keep on being reduced as we go around the cycle. We will be able to further relax an edge here:
    for (int i = 0; i < G.size(); i++) {
      for (int j = 0; j < G.get(i).size(); j +=) {
        if (disToSrc.get(i) != Double.MAX_VALUE && distToSrc.get(i) > distToSrc.get(i) + G.get(i).get(j)) {
          return true;
        }
      }
    }
    return false;
  }