Routing Algorithms

Routing Algorithms

fXYZ Network routes FX conversions across a weighted directed graph where nodes are currencies and edges are exchange rate pairs. Three algorithms work in concert: Bellman-Ford finds optimal paths, the line-graph transformation improves routing on dense networks, and negative-cycle detection identifies arbitrage opportunities.

Implementation: packages/neo4j/src/services/routing-engine.ts GraphQL queries: findRoute, detectArbitrage, routingGraphInfo Paper references: C6, D6

Bellman-Ford Routing

Overview

Bellman-Ford finds the shortest (cheapest) path between any two currencies in the FX exchange graph. Unlike Dijkstra, Bellman-Ford handles negative edge weights — which is essential for arbitrage detection.

The routing engine converts exchange rates to log-space edge weights so that multiplicative rate chains become additive path weights:

edge weight w(u,v) = -log(rate(u → v))

A cheaper path (lower total weight) corresponds to a more favorable exchange rate sequence.

Algorithm

Initialize: d[source] = 0, d[v] = +inf for all other v
Repeat |V|-1 times:
  For each edge (u, v, w):
    if d[u] + w < d[v]:
      d[v] = d[u] + w
      predecessor[v] = u

Arbitrage check (iteration |V|):
  For each edge (u, v, w):
    if d[u] + w < d[v]:
      negative cycle detected → arbitrage opportunity

Complexity: O(|V| * |E|)

Mathematical Formulation

For an FX path through currencies c1 → c2 → ... → cn:

Total log-cost = sum(-log(rate(ci → ci+1)))
               = -log(product(rates along path))

Optimal path = argmin over all paths of total log-cost
             = argmax over all paths of product(exchange rates)

Implementation

// routing-engine.ts:104
bellmanFord(
  graph: Map<string, Map<string, number>>,
  source: string
): { distances: Map<string, number>; predecessors: Map<string, string> }

The function returns distances and predecessors for path reconstruction. The routing graph is built from live ECB FX rate data and crypto prices via buildRoutingGraph().

Line-Graph Transformation

Overview

The standard Bellman-Ford treats each currency node as the unit of routing. This ignores a real cost in FX trading: switching between currency pairs at an intermediate currency incurs spread costs that depend on which pair you came from and which pair you're entering.

The line-graph transformation (Paper D6) solves this by converting the FX graph into a line graph where edges become nodes. This allows edge-switching costs to be expressed as ordinary node weights, making the full bid-ask spread model compatible with standard shortest-path algorithms.

Transformation

Given the original FX graph G = (V, E):

Line graph L(G):
  Vertices of L(G) = edges of G
  Two vertices of L(G) are adjacent iff the corresponding
  edges of G share an endpoint (i.e., a currency hop)

For FX routing, this means:

• Each currency pair (e.g., EUR/USD) becomes a node in L(G)
• Adjacent nodes in L(G) share a common currency
• Edge weights in L(G) represent the cost of transitioning through that common currency (bid-ask spread, liquidity penalty)

Performance

Paper D6 reports that line-graph routing on dense FX networks achieves over 50% improvement in effective rate versus naive Bellman-Ford, because it properly accounts for spread accumulation at each currency hop.

Implementation

// routing-engine.ts:328
buildLineGraph(
  graph: Map<string, Map<string, number>>
): LineGraph

// Activated via useLineGraph parameter on findRoute query:
findRoute(from: "EUR", to: "JPY", useLineGraph: true)

Arbitrage Detection

Overview

In a correctly priced FX market, converting EUR → USD → JPY → EUR should return exactly the starting amount (minus spreads). When the product of exchange rates along a cycle exceeds 1.0, the cycle is profitable — a textbook arbitrage opportunity.

In the log-rate graph, this corresponds to a negative-weight cycle: a cycle where the sum of log-costs is negative.

Mathematical Formulation

For a cycle of currencies c1 → c2 → ... → cn → c1:

Profit = product(rate(ci → ci+1)) - 1
       = exp(-sum(log-weights along cycle)) - 1

Profitable cycle: sum(log-weights) < 0, which means product(rates) > 1.

After the standard |V|-1 Bellman-Ford relaxations, a |V|-th pass that still finds a shorter path indicates a negative cycle exists.

Algorithm

Run Bellman-Ford for |V|-1 iterations (standard shortest path)

On iteration |V|:
  For each edge (u, v, w):
    if d[u] + w < d[v]:
      v is in or reachable from a negative cycle
      → trace predecessor chain to extract the cycle
      → compute cycle profit
      → emit as arbitrage opportunity

Cycle Profit Calculation

// routing-engine.ts:199
findNegativeCycles(
  graph: Map<string, Map<string, number>>
): ArbitrageCycle[]

interface ArbitrageCycle {
  path: string[];          // e.g. ["EUR", "USD", "JPY", "EUR"]
  profitPercent: number;   // e.g. 0.12 for 0.12% profit
  rateProduct: number;     // product of exchange rates along cycle
}

Planned Extensions

Cyclic Arbitrage with AMM Pools (Paper D5, S4-cyclic)

CPMM (Constant Product Market Maker) pools have a non-linear exchange rate that depends on pool depth. Planned extension to detectArbitrage will incorporate pool liquidity into profit calculations for more accurate sizing.

Tropical Algebra Scanner (Paper C6)

Tropical (min-plus) algebra provides a unified algebraic framework for computing all shortest paths simultaneously. Planned tropicalArbitrageScan() in tropical-arbitrage.ts.

Genetic Algorithm Optimization (PaymentsCanada paper)

For large FX graphs (>100 currencies), exact cycle enumeration becomes expensive. Planned GA-based cycle optimizer in ga-arbitrage.ts uses evolutionary search to find high-profit cycles efficiently.

Paper References