Bellman Ford algorithm for triangular arbitrage in JS

Question

function bellmanFord(start, graph) {
  const distances = {};
  const predecessors = {};

  // Initialize distances and predecessors
  for (const node in graph) {
    distances[node] = Infinity;
    predecessors[node] = null;
  }
  distances[start] = 0;

  // Relax edges repeatedly
  for (let i = 0; i < Object.keys(graph).length - 1; i++) {
    for (const node in graph) {
      for (const edge of graph[node]) {
        const weight = -Math.log(edge.weight);
        const nextNode = edge.node;
        if (distances[node] + weight < distances[nextNode]) {
          distances[nextNode] = distances[node] + weight;
          predecessors[nextNode] = node;
        }
      }
    }
  }
  // Check for negative cycles
  let cycle = [];
  let cycleExists = false;
  let conversionRate = [];

  for (let i = 0; i < Object.keys(graph).length - 1; i++) {
    for (const node in graph) {
      for (const edge of graph[node]) {
        const weight = -Math.log(edge.weight);
        const nextNode = edge.node;
        if (distances[node] + weight < distances[nextNode]) {
          cycleExists = true;
          // Negative cycle found, return its path and weight
          let current = node;
          while (!cycle.includes(current)) {
            cycle.push(current);
            current = predecessors[current];
          }
          cycle.push(current);
          cycle.reverse();
          // Calculate the weight of the cycle
          let cycleWeight = 0;
          for (let i = 0; i < cycle.length - 1; i++) {
            for (const edge of graph[cycle[i]]) {
              if (edge.node === cycle[i + 1]) {
                conversionRate.push(edge.weight);
                cycleWeight += -Math.log(edge.weight);
              }
            }
          }
          console.log("conversionRate: ", conversionRate);
          return { path: cycle, weight: cycleWeight };
        }
      }
      if (cycleExists) {
        break;
      }
    }
  }

  // No negative cycle found, return null
  return null;
}

bellmanFord("USD", graphData);

sample graph

const graphData = {
  USD: [
   {node: "Euro", weight: 3 }, 
   {node: "AED", weight: -2}
  ], 
  Euro: [{node: "USD", weight: -6}], 
  AED: [{node: "USD", weight: 3}]
}

I have written the bellman Ford algorithm to find the triangular arbitrage opportunity by using the negative weight cycle. Let's say there is a negative cycle of USD=> Euro=>USD I want the above code to do

1. it should return to the path of the cycle.
2. path of the cycle should start and end at the same node (eg if it starts from USD it should come back to USD)
3. it should return the weights of edges (that will be used for currency conversion).
4. it should return the weight of the cycle.
5. should return null if no negative cycle is found instead of returning cycle with positive weight
6. possible optimization

The above code for some reason returns the cycle even if it is positive

Answer 1

There might be a bug in the loop where I am trying to find the negative cycles.

This is a giant blob of code.

It is not easy for the author to reason about, nor the reviewer. There is an opportunity to extract small helpers, and individually test each of those units. There is an opportunity to include example input / output pairs, ideally in the form of automated tests.

This code should cite its reference(s), perhaps wikipedia.

If the design goal truly is to identify just "triangular" arbitrage cycles, then a far simpler combinatoric approach would be a better match to the use case.

---

We see several comments:

  // Relax edges repeatedly
  ...
  // Check for negative cycles
  ...
          // Calculate the weight of the cycle

They are helpful -- much better to include them than not!

They are unhelpful, in the sense that the code would be simpler if the author introduced

• function relaxEdgesRepeatedly(...)
• function checkForNegativeCycles(...)
• function findWeightOfCycle(...)

---

Competing algorithms could be used to help assess the robustness of this code.

For example, given a Dijkstra or Floyd–Warshall implementation, the test suite could examine graphs from a subset of the input space and verify that competing algorithms report the same result. Input graphs would be free of ties, free of negative cycles, and in the case of Dijkstra would be free of negative edge weights. Verifying behavior in this limited subset would instill greater confidence in the correctness of this code, compared to the OP submission.

---

It is unclear whether this code achieves its design goal of identifying instantaneous cyclic arbitrage opportunities. It succeeds on at least one example input graph.

I would not be willing to delegate or accept maintenance tasks while the codebase lacks an effective test suite.