Finding the Best Currency Exchange Rate with Depth First Search Algorithm

date

Apr 5, 2023

slug

finding-the-best-currency-exchange-rate-with-depth-first-search-algorithm

status

Published

The Problem

In our financial product, we strive to provide the best currency conversion options to our customers. Despite not having direct Australia Dollar conversions to all currencies, we employ strategic currency trading to achieve optimal results by trading currencies for other currencies. It is possible to navigate through multiple currency conversions, certain currencies may appear repeatedly throughout the process

Example: Convert AUD to EUR AUD → GBP → EUR

It is essential to avoid any cycles in the conversion path

AUD → EUR → GBP → EUR

Notes

You have access to a web service equipped with a database of currency exchange rates

Get all available exchange rates by calling a REST API

The best possible conversion rate for every currency we can get, assuming we start with AUD 100. It is required to have no "cycle" or loop of the same Fiat currency in the trading chain (example of the cyclic path: AUD → EUR → GPB → EUR)

Solutions

We need to build a Graph of currency codes. In the graph, one vertex is connected to the other by an edge with a defined direction. According to the requirement, this must be an acyclic graph, meaning that for any given vertex, if we follow one edge which connects that vertex to another, there is no path in the graph to get back that initial vertex.

With the above rates, 100 AUD for EUR => 100 * (0.68 * 0.92) = 62.56 EUR

The Directed Acyclic Graph (DAG) describes the relationships between currencies in the exchange rates data set: • Unique currency codes will correspond to vertices of the DAG • Available exchange rates with "from"-"to" pairs correspond to the direction of the graph's edges

Finding the best possible currency conversion

There are two approaches to resolving the current problem:

Approach 1

Look for all possible paths in the Directed Acyclic Graph (DAG), and compare the amounts of expected currency received from each conversion path

Approach 2

Look for the longest path in the Weighted Directed Acyclic Graph. It is DAG with weighted edges that represent the exchange rate between currencies

In this article, we will focus on implementing the solution using the 1st approach We use Depth First Search (DFS) to look for all possible paths from source to destination:

"source" is the input currency, and "destination" is the expected output currency of the trade order.

Recursive DFS: • Maintain an array of visited vertices • Maintain visited vertices of the current path, and reset its value once found a complete path • Start DFS traversal from the source node, visit each vertex in the graph and iterate over all of it its adjacent vertices to recursively start DFS traversal on the sub-graph with the source node as the adjacent node of the current visiting vertex. • Mark the current visiting vertex as visited before starting new recursion to avoid having a cycle in the path

Further Improvement

Replace Recursive DFS with Iterative DFS

Interactive DFS with a user-defined Stack data structure should be used as a replacement for the Recursive DFS algorithm. It offers scalability and flexibility, helps avoid possible stack overflow errors from Recursive DFS