Bellman Ford algorithm for triangular arbitrage in JS

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

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

• Ahoy- given “The above code for some reason returns the cycle even if it is positive” is the code not working as expected? Commented Apr 23, 2023 at 23:39
• There might be a bug in the loop where I am trying to find the negative cycles. Commented Apr 24, 2023 at 5:35

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.

  // 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.