Python script which makes a matrix of exchange rates (USD to EUR, etc.), deletes some entries, and then fills-in the gaps (as much as possible)

exchange_rates.py

import random
import copy


def make_exchange_matrix(N=3, seed=2017):
    '''In this function, we make an exchange matrix
    for testing purposes by randomly picking exchange 
    rates from the first currency to all the other
    currencies. '''

    random.seed(seed)  # Make this "reproducibly" random.
    
    # NOTE: Don't do [[0]*N]*N -- it's not the same.
    M = [[0]*N for _ in range(N)]  
    # Initially, we do not know any entries. Let 0 
    # represent this. 
    
    '''M looks like
    0 0 0
    0 0 0
    0 0 0'''

    # Fill in the diagonal.
    for i in range(N):
        M[i][i] = 1

    '''M looks like
    1 0 0
    0 1 0
    0 0 1'''

    # Fill in the rest of the first row with random
    # exchange rates from the first currency to all
    # the other currencies. 

    low_price = 1
    high_price = 10
    for i in range(1, N):
        M[0][i] = random.randint(low_price, high_price)

    '''M looks like
    1 4 8
    0 1 0
    0 0 1'''

    # At this point, we know that our graph is connected.
    # You can get from any currency to another currency
    # via an exchange rate to the first currency. 
    # We can now run our algorithm on this matrix to
    # finish making an exchange matrix for testing purposes.

    return M


def fill_in_gaps(M):
    '''We treat M as a special kind of an adjacency matrix.
    We say special because the matrix defines a directed 
    graph, but there is an additional condition. The price
    of an outgoing edge must be the reciprocal of an 
    incoming edge. So any exchange matrix must be 
    "reciprocal symmetric." So the first thing that this function
    has to do is to fill in the reciprocals if one of the
    pair of numbers is missing. '''

    N = len(M)

    # Fill-in the diagonal (maybe some of these were deleted?)
    for i in range(N):
        M[i][i] = 1

    # Fill-in reciprocals.
    for row in range(N):
        for column in range(row+1, N):
            if M[row][column] == 0 and M[column][row] != 0:
                M[row][column] = 1/M[column][row]
            if M[row][column] != 0 and M[column][row] == 0:
                M[column][row] = 1/M[row][column]

    '''M looks like
    1.00 4.00 8.00
    0.25 1.00 0.00
    0.13 0.00 1.00'''

    # Now to solve the heart of the problem...
    # We want to find a path from every currency to every 
    # other currency. This is the implied exchange rate. 
    # Once we have the implied exchange rate, we can
    # simply fill that (i,j) cell in the matrix with this
    # rate. 

    # For every row i (currency), if there are missing rates 
    # (0's in the row), we do a depth-first search while
    # keeping a "current" (or implied) exchange rate as we jump from one
    # currency to another. When we arrive at a node, we fill
    # in the (i,j) cell with the current/implied exchange rate.

    for start_currency in range(N):  # Start from every currency. 
        # Do a depth-first search.
        current_rate = 1
        nodes_in_path = set([start_currency])
        dfs(M, start_currency, start_currency, nodes_in_path, current_rate)

    return M


def dfs(M, current_node, starting_node, nodes_in_path, current_rate=1):
    # This is where we can fill-in the exchange rate. 
    # NOTE: We don't care if the exchange rate already existed in the cell.
    M[starting_node][current_node] = current_rate
    M[current_node][starting_node] = 1/current_rate

    # Get all the neighbors, i.e., currencies for which we know the exchange
    # rate for from current_node. 
    neighbors = [i for i, rate in enumerate(M[current_node]) if rate != 0]

    nodes_in_path.add(current_node)

    for neighbor_node in neighbors:
        if neighbor_node not in nodes_in_path:
            new_rate = current_rate * M[current_node][neighbor_node]
            dfs(M, neighbor_node, starting_node, nodes_in_path, new_rate)
    return


def delete_k_entries(M, k=0):
    N = len(M)
    assert k <= N*N  # Check we aren't trying to delete more than we have
    deleted = set()
    while len(deleted) < k:
        # Pick a random cell.
        i, j = random.randint(0, N-1), random.randint(0, N-1)
        M[i][j] = 0
        deleted.add((i, j))

    return M


def pretty_print(M):
    for row in M:
        row = ['%.2f'%i for i in row]  # Print a row on its own line. 
        row = '  '.join(row)
        print(row)


if __name__ == '__main__':
    M = make_exchange_matrix(N=7)
    M = fill_in_gaps(M)
    print('Before deleting entries:\n')
    pretty_print(M)
    print()
    M = delete_k_entries(M, k=20)
    # NOTE: It should be clear that the only reason that we will not
    # be able to fill-in implied exchange rates is only in the case that
    # we happen to delete enough edges so there is no path from some
    # node to another node. This can only happen with k larger than N-1. 
    # Even if k is larger than N-1, we still have some probability that
    # there is always a path from one node to the other. 
    print('After deleting entries:\n')
    pretty_print(M)
    print()
    M = fill_in_gaps(M)
    print('After filling-in entries:\n')
    pretty_print(M)
    print()