Currency Arbitrage using Bellman Ford Algorithm

currency_arbitrage.py

from typing import Tuple, List
from math import log

rates = [
    [1, 0.23, 0.26, 17.41],
    [4.31, 1, 1.14, 75.01],
    [3.79, 0.88, 1, 65.93],
    [0.057, 0.013, 0.015, 1],
]

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


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
    
    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]

    # 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]:
                print('Found arbitrage: {0} --> {1}'.format(currency_tuple[source_curr], currency_tuple[dest_curr]))
            else:
                print('No arbitrage')
    
if __name__ == "__main__":
    arbitrage(currencies, rates)

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

# Brute Force: O(N!)