Skip to content
TypeScript

Currency Conversion with a Graph Data Structure

I was working on a hobby project where I had access to foreign exchange rates for currency pairs where the base asset was fixed to US Dollars (USD) (e.g., USD/EUR, USD/JPY, USD/GBP). Fortunately, for my project, I only need approximate conversions for display purposes, not pinpoint-accurate quotes to base something like foreign exchange trading on.

For example:

{
  "base": "USD",
  "quoted_at": "2022-11-29T20:02:43.405Z",
  "quotes": {
    "EUR": "0.97",
    "GBP": "0.84",
    "JPY": "138.68"
  }
}

Note: To better understand why many APIs return numbers as strings, and how to work with those (why I use big.js in these examples), refer to my guide on working with currency values in the browser

Defining the Problem and Solving a Simple Case#

Given the quotes in the response above, we know the rates for USD/EUR and USD/JPY, but we don't have a direct rate for EUR/JPY. We can calculate an approximate rate for EUR/JPY indirectly by doing the following:

import Big from 'big.js';

const USD_EUR = '0.97';
const USD_JPY = '138.68';

/*
 * First, flip the USD/EUR pair to EUR/USD. This will give us the number
 * of US Dollars we need to pay for 1 Euro.
 */
const eurUSD = new Big(1).div(USD_EUR); // (1 / USD_EUR) === 1.03092783505154639175

/**
 * Now that we know how many dollars you need to pay for 1 Euro, and how many Japanese Yen
 * you need to pay for 1 dollar, we can calculate approximately how many Japanese Yen you
 * need to pay for 1 Euro.
 */
const eurJPY = eurUSD.times(USD_JPY); // 1.03092783505154639175 * 138.68 = 142.989690721649484535725;

These conversions aren't perfect, and should not be used for providing quote data or building trading algorithms off of, but they can provide a close approximation in the absence of full pair data (for example, showing a rough net worth or account balance). Things like liquidity, transaction costs, and precision of the initial quotes vs. precision supported by the target pair can impact the accuracy of these indirect conversions. If you do in fact, find a market inefficiency that you are able to take advantage of, that would be called arbitrage. In that case, congratulations, and don't forget me once you've made it! 🎊 In all reality, there are trading desks that exist to hunt down and exploit these opportunities until they no longer exist. A prominent recent example would be the now-troubled Alameda Research, which took advantage of price differences for Bitcoin between U.S. and Japanese markets.

Complicating Things#

The use case above is pretty simple, but imagine we start getting cryptocurrency data from a different provider, and the only pair it gives us with a fiat currency in it is BTC/USD. Now, if we want to approximate a quote for LTC/EUR, it's going to take a longer path to come up with a conversion.

{
  "quoted_at": "2022-11-29T20:02:43.405Z",
  "pairs": {
    "BTC/USD": "16465.70",
    "ETH/BTC": "0.07410",
    "LTC/ETH": "0.06283"
  }
}

Converting from LTC to EUR using the two sets of JSON above would look something like this:

import Big from 'big.js';

const USD_EUR = '0.97';
const BTC_USD = '16465.7';
const ETH_BTC = '0.0741';
const LTC_ETH = '0.06283';

// Multiply the USD/EUR rate by the BTC/USD rate to get
const btcEUR = new Big(USD_EUR).times(BTC_USD); // 15971.729

// Multiply the BTC/EUR rate by the ETH/BTC rate to get
const ethEUR = btcEUR.times(ETH_BTC); // 1183.5051189

// Multiply the ETH/EUR rate by the LTC/ETH rate to get
const ltcEUR = ethEUR.times(LTC_ETH); // 74.359626620487

Programmatic Conversions with a Graph#

Given the example above, you can see that finding a path could become pretty tedious. This is where a graph data structure can come in handy.

We can use a Breadth-First Search (BFS) to find the shortest path to convert between currencies for which there's not a direct quote.

import Big from 'big.js';

class Edge {
  quoteCurrency: string;
  rate: Big;

  constructor(quoteCurrency: string, rate: Big) {
    this.quoteCurrency = quoteCurrency;
    this.rate = rate;
  }
}

export class CurrencyConversionGraph {
  // The key of the graph will be a currency ISO code, e.g., USD, EUR, MXN, BTC
  private graph: Record<string, Edge[]> = {};

  public addQuote(baseCurrency: string, quoteCurrency: string, rate: Big): void {
    if (!this.graph[baseCurrency]) {
      this.graph[baseCurrency] = [];
    }

    this.graph[baseCurrency].push(new Edge(quoteCurrency, rate));

    if (!this.graph[quoteCurrency]) {
      this.graph[quoteCurrency] = [];
    }

    // Set the rate for the reverse direction by finding the multiplicative inverse (divide rate by 1)
    this.graph[quoteCurrency].push(new Edge(baseCurrency, new Big(1).div(rate)));
  }

  public convertAmount(fromCurrency: string, toCurrency: string, amount: Big): Big {
    if (!this.graph[fromCurrency]) {
      throw new Error(`CurrencyConversionError: missing quote for ${fromCurrency}.`);
    }

    if (!this.graph[toCurrency]) {
      throw new Error(`CurrencyConversionError: missing quote for ${toCurrency}.`);
    }

    // visited will be keyed by currency ISO code
    const visited: Record<string, boolean> = {};

    /*
     * queue is the collection of edges that need to be analyzed to find
     * the shortest path (initialize with the fromCurrency with a rate of 1)
     */
    const queue: { currency: string; rate: Big }[] = [
      { currency: fromCurrency, rate: new Big(1) },
    ];

    while (queue.length) {
      const current = queue.shift()!;

      /*
       * If the current edge matches the currency we're converting the amount to,
       * multiply the amount by the rate to get the converted value
       */
      if (current.currency === toCurrency) {
        return amount.times(current.rate);
      }

      /*
       * If the currency node hasn't been visited yet, add its edges to the
       * queue and mark it as visited, else skip
       */
      if (!visited[current.currency]) {
        visited[current.currency] = true;

        for (const edge of this.graph[current.currency]) {
          if (!visited[edge.quoteCurrency]) {
            queue.push({ currency: edge.quoteCurrency, rate: current.rate.times(edge.rate) });
          }
        }
      }
    }

    throw new Error(`CurrencyConversionError: no path found to convert ${fromCurrency} to ${toCurrency}.`)
  }
}

Now we've got a graph set up, along with a breadth-first search to find the shortest path to convert from one currency to another. Let's test it out.

import Big from 'big.js';

const fiatQuotes = {
  base: 'USD',
  quoted_at: '2022-11-29T20:02:43.405Z',
  quotes: {
    EUR: '0.97',
    GBP: '0.84',
    JPY: '138.68',
  },
};

const cryptoQuotes = {
  quoted_at: '2022-11-29T20:02:43.405Z',
  pairs: {
    'BTC/USD': '16465.70',
    'ETH/BTC': '0.07410',
    'LTC/ETH': '0.06283'
  },
};

// Instantiate new CurrencyConversionGraph
const conversionGraph = new CurrencyConversionGraph();

// Add fiat quotes to the graph
Object.entries(fiatQuotes.quotes).forEach(([quoteCurrency, rate]) => {
  conversionGraph.addQuote(fiatQuotes.base, quoteCurrency, new Big(rate));
});

// Add crypto quotes to the graph
Object.entries(cryptoQuotes.pairs).forEach(([pair, rate]) => {
  const [baseCurrency, quoteCurrency] = pair.split('/');

  conversionGraph.addQuote(baseCurrency, quoteCurrency, new Big(rate));
});

// Now we're able to make these approximate conversions in one line
conversionGraph.convertAmount('LTC', 'EUR', new Big(1));

Other Considerations#

You could start adding other data sources, or re-fetch quotes on an interval, adding those quotes to your graph as they come in. In either of these cases, you may start to give preference to certain quote data, based on either the provider or the recency of the quote. This would start to explore the concept of giving your edges a "weight," which would require consideration for your search for the best and shortest path to conversion. For this use case, you'll likely want to leverage Djikstra's algorithm, which is more robust than a simple breadth-first search.

If you feel I missed something or made a mistake, please reach out to me on X. If you learned something, don't hesitate to share.