Currency Arbitrage using Bellman Ford Algorithm

currency_arbitrage.py

from typing import Tuple, List
from math import log

rates = [
    [1, 0.23, 0.25, 16.43, 18.21, 4.94],
    [4.34, 1, 1.11, 71.40, 79.09, 21.44],
    [3.93, 0.90, 1, 64.52, 71.48, 19.37],
    [0.061, 0.014, 0.015, 1, 1.11, 0.30],
    [0.055, 0.013, 0.014, 0.90, 1, 0.27],
    [0.20, 0.047, 0.052, 3.33, 3.69, 1],
]

currencies = ('PLN', 'EUR', 'USD', 'RUB', 'INR', 'MXN')


def negate_logarithm_convertor(graph: Tuple[Tuple[float]]) -> List[List[float]]:
    ''' log of each rate in graph and negate it'''
    result = [[-log(edge) for edge in row] for row in graph]
    return result


def arbitrage(currency_tuple: tuple, rates_matrix: Tuple[Tuple[float, ...]]):
    ''' Calculates arbitrage situations and prints out the details of this calculations'''

    trans_graph = negate_logarithm_convertor(rates_matrix)

    # Pick any source vertex -- we can run Bellman-Ford from any vertex and get the right result

    source = 0
    n = len(trans_graph)
    min_dist = [float('inf')] * n

    pre = [-1] * n
    
    min_dist[source] = source

    # 'Relax edges |V-1| times'
    for _ in range(n-1):
        for source_curr in range(n):
            for dest_curr in range(n):
                if min_dist[dest_curr] > min_dist[source_curr] + trans_graph[source_curr][dest_curr]:
                    min_dist[dest_curr] = min_dist[source_curr] + trans_graph[source_curr][dest_curr]
                    pre[dest_curr] = source_curr

    # if we can still relax edges, then we have a negative cycle
    for source_curr in range(n):
        for dest_curr in range(n):
            if min_dist[dest_curr] > min_dist[source_curr] + trans_graph[source_curr][dest_curr]:
                # negative cycle exists, and use the predecessor chain to print the cycle
                print_cycle = [dest_curr]
                # Start from the source and go backwards until you see the source vertex again
                while True:
                    source_curr = pre[source_curr]
                    if source_curr in print_cycle:
                        break
                    print_cycle.append(source_curr)
                print_cycle.append(dest_curr)
                print("Arbitrage Opportunity: \n")
                print(" --> ".join([currencies[p] for p in print_cycle[::-1]]))


if __name__ == "__main__":
    arbitrage(currencies, rates)

# Time Complexity: O(N^3)
# Space Complexity: O(N^2)

This results in seemingly impossible trips:

Arbitrage Opportunity:

RUB --> INR --> PLN --> RUB
Arbitrage Opportunity:

USD --> MXN --> USD --> RUB --> INR --> EUR --> PLN
Arbitrage Opportunity:

USD --> MXN --> USD --> PLN

In everything except the first trip the starting and ending currencies are different. Can you please explain why this is happening?

Thanks

manipulating source_curr in code is skipping few edges for negative cycle check.

@CodeForcer @prab-tri The issue is now fixed.

Output

Arbitrage Opportunity:  RUB --> INR --> RUB

Arbitrage Opportunity:  PLN --> MXN --> USD --> RUB --> INR --> PLN

Arbitrage Opportunity:  RUB --> USD --> MXN --> RUB

Arbitrage Opportunity: PLN --> USD --> MXN --> PLN

Typescript

class Graph {
    private vertices: string[];
    private edges: number[][];

    constructor(vertices: string[], edges: number[][]) {
        this.vertices = vertices;
        this.edges = edges.map(row => row.map(rate => -Math.log(rate)));
    }

    arbitrage() {
        const n = this.vertices.length;
        const minDist = new Array(n).fill(Infinity);
        const pre = new Array(n).fill(-1);

        minDist[0] = 0;

        for (let i = 0; i < n - 1; i++) {
            for (let src = 0; src < n; src++) {
                for (let dest = 0; dest < n; dest++) {
                    if (minDist[dest] > minDist[src] + this.edges[src][dest]) {
                        minDist[dest] = minDist[src] + this.edges[src][dest];
                        pre[dest] = src;
                    }
                }
            }
        }

        for (let src = 0; src < n; src++) {
            for (let dest = 0; dest < n; dest++) {
                if (minDist[dest] > minDist[src] + this.edges[src][dest]) {
                    let cycle = [this.vertices[dest]];
                    let j = src;
                    while (!cycle.includes(this.vertices[j])) {
                        cycle.push(this.vertices[j]);
                        j = pre[j];
                    }
                    cycle.push(this.vertices[dest]);
                    console.log("Arbitrage Opportunity: ", cycle.reverse().join(" --> "));
                    return;
                }
            }
        }

        console.log("No arbitrage opportunity found.");
    }
}

const currencies = ["USD", "EUR", "GBP", "CAD"];
const rates = [
    [1, 0.741, 0.657, 1.061],
    [1.349, 1, 0.888, 1.433],
    [1.561, 1.126, 1, 1.614],
    [0.942, 0.698, 0.619, 1]
];

const graph = new Graph(currencies, rates);
graph.arbitrage();

npx ts-node currency_arbitrage.ts
Arbitrage Opportunity: EUR --> GBP --> USD --> EUR

Real time currency arbitrage : https://gist.github.com/anilpai/08f3cedb60b7a3c9a3b4e27c0c022096