Path Finding Algorithms - Part II

Introduction

In this document, we explore basic path-finding algorithms for asset conversion routes. Specifically, we'll examine Depth-First Search (DFS) and Breadth-First Search (BFS). These algorithms are foundational in graph traversal and are used to explore possible paths between nodes (assets) in a graph where edges represent possible trades or conversions.

For simplicity, in this section, we'll focus on asset conversion routes without considering cost optimization (i.e., ignoring transaction fees, slippage, liquidity, etc.). We'll highlight the limitations of these basic approaches and set the stage for more advanced algorithms.

---

Dataset and Data Models

We'll define a simple dataset representing a few assets and the available conversion pairs between them. Each conversion will be represented as a directed edge in the graph.

Dataset

from dataclasses import dataclass, field
from typing import List, Dict, Tuple

# Define the trading pair and the conversion route
@dataclass
class TradePair:
    from_asset: str
    to_asset: str

# Define the conversion route
@dataclass
class ConversionRoute:
    pairs: List[TradePair] = field(default_factory=list)

# Asset pairs and routes between them (without costs)
conversion_pairs = [
    TradePair("USD", "BTC"),
    TradePair("USD", "ETH"),
    TradePair("BTC", "ETH"),
    TradePair("BTC", "EUR"),
    TradePair("ETH", "EUR"),
    TradePair("USD", "EUR")
]

Here we are modeling asset conversion pairs using a TradePair dataclass where each pair represents a directed edge from one asset to another.

---

Depth-First Search (DFS)

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It's useful for exploring all possible paths between two nodes (assets in our case). However, DFS does not guarantee the shortest path, nor does it account for any costs or constraints.

DFS Algorithm

def dfs(graph: Dict[str, List[str]], start: str, end: str, path: List[str] = None) -> List[List[str]]:
    if path is None:
        path = []
    path = path + [start]
    
    if start == end:
        return [path]
    
    paths = []
    for node in graph.get(start, []):
        if node not in path:
            new_paths = dfs(graph, node, end, path)
            for new_path in new_paths:
                paths.append(new_path)
    
    return paths

Running DFS on Asset Conversion Graph

We need to construct the graph where assets are nodes and trading pairs are directed edges.

# Define the graph structure based on conversion pairs
graph = {
    "USD": ["BTC", "ETH", "EUR"],
    "BTC": ["ETH", "EUR"],
    "ETH": ["EUR"]
}

# Find all paths from USD to EUR using DFS
all_dfs_paths = dfs(graph, "USD", "EUR")
print("All DFS Paths from USD to EUR:")
for path in all_dfs_paths:
    print(path)

Output

All DFS Paths from USD to EUR:
['USD', 'EUR']
['USD', 'BTC', 'EUR']
['USD', 'BTC', 'ETH', 'EUR']
['USD', 'ETH', 'EUR']

Discussion

DFS successfully explores all possible paths from USD to EUR, including longer paths like USD → BTC → ETH → EUR and shorter direct paths like USD → EUR. However, DFS does not differentiate between "good" and "bad" paths; it just explores all possible paths.

---

Breadth-First Search (BFS)

Unlike DFS, BFS explores all nodes at the present "depth" level before moving on to the nodes at the next depth level. BFS is useful for finding the shortest path in an unweighted graph (i.e., where all edges have equal cost).

BFS Algorithm

from collections import deque

def bfs(graph: Dict[str, List[str]], start: str, end: str) -> List[str]:
    queue = deque([[start]])
    
    while queue:
        path = queue.popleft()
        node = path[-1]
        
        if node == end:
            return path
        
        for adjacent in graph.get(node, []):
            if adjacent not in path:
                new_path = list(path)
                new_path.append(adjacent)
                queue.append(new_path)
    
    return []

Running BFS on Asset Conversion Graph

# Find the shortest path from USD to EUR using BFS
shortest_bfs_path = bfs(graph, "USD", "EUR")
print("Shortest BFS Path from USD to EUR:")
print(shortest_bfs_path)

Output

Shortest BFS Path from USD to EUR:
['USD', 'EUR']

Discussion

BFS provides the shortest path from USD to EUR, which is the direct path USD → EUR. This is the shortest in terms of the number of hops, but not necessarily the best path when considering costs such as slippage, liquidity, and fees. In its current form, BFS does not account for these factors.

---

Problems with Basic Path-Finding Algorithms

Both DFS and BFS are powerful tools for exploring all possible paths or finding the shortest path in simple scenarios. However, when applied to asset conversion in financial markets, they have several limitations:

1. No Cost Awareness:

   • Neither DFS nor BFS takes into account the costs associated with each conversion, such as slippage, transaction fees, or market liquidity. In real-world asset conversion, these costs are critical to determining the best path.

2. Equal Weighting of Paths:

   • BFS always finds the shortest path in terms of hops, but in a financial market context, fewer hops do not always equate to lower costs. A path with fewer conversions might involve higher fees or greater slippage, making it less optimal.

3. Inefficient for Complex Graphs:

   • Both algorithms become inefficient for very large and complex graphs. As the number of assets and possible conversions increases, the number of possible paths grows exponentially, making DFS and BFS impractical for real-time decision-making in large markets.

4. Lack of Real-Time Adjustments:

   • These algorithms are static in nature and do not adjust dynamically to market conditions such as volatility, liquidity changes, or price fluctuations. In contrast, real-time optimization requires continuous adjustment based on current market data.

Conclusion

DFS and BFS serve as basic tools for path-finding in asset conversion, but their lack of cost-awareness and real-time adaptability make them suboptimal for use in financial markets. In the next document, we'll explore more advanced algorithms such as Dijkstra's Algorithm and A*, which introduce cost optimization and can provide more realistic solutions for asset conversion routes in a dynamic market environment.