How can I find the shortest path between two currencies?

Question

I have table currency_pair(c1, c2); values are (usd,bnb), (cake,bnb), (cake,eth).

I need to find the shortest path that allows me to compare usd to eth.

The result here would be those same values. I can then use the first pair to establish a usd-bnb relationship, which I can then use to calculate a usd-cake relationship, which I can then use to compute usd-eth.

Since order is not determinate, the first step I did was create a materialized view, currency_pair_map(c1, c2), which is a union of select c1, c2 union select c2, c1. This would seem to simplify the logic.

If I am thinking about this correctly, what I need to do is use WITH RECURSIVE? I should also have some sort "depth_limit" parameter that ensures that a query fails if it is impossible to establish a pair.

Thinking about this out loud, we should always begin with:

SELECT *
FROM currency_pair
WHERE
  c1 = 'usd' AND
  c2 = 'eth'

If there is a result, we should end there.

If there is not, then we need to find all usd-* pairs and continue search until we find one that ends with eth.

Using this logic, so far I have:

WITH RECURSIVE pair_route AS (
  SELECT
    1 depth,
    cp1.id,
    cp1.c1,
    cp1.c2
  FROM currency_pair cp1
  WHERE
    cp1.c1 = 'usd'
  UNION
  SELECT
    pr1.depth + 1,
    cp2.id,
    cp2.c1,
    cp2.c2
  FROM pair_route pr1
  INNER JOIN currency_pair cp2 ON cp2.c1 = pr1.c2
  WHERE
    pr1.depth < 4
)
SELECT *
FROM pair_route;

I think this is correct. Now I just need to track path (IDs) and identify the shortest paths.

Answer 1

You could use this recursive query:

WITH RECURSIVE c AS (
      SELECT c1, c2 FROM currency_pair
   UNION
      SELECT c2, c1 FROM currency_pair
), curr_path AS (
      SELECT ARRAY[c1, c2] AS path
      FROM c
      WHERE c2 = 'usd'
   UNION ALL
      SELECT c.c1 || p.path
      FROM c
         JOIN curr_path AS p
            ON c.c2 = (p.path)[1]
      WHERE c.c1 <> ALL (p.path)
)
SELECT path
FROM curr_path
WHERE path[1] = 'eth'
ORDER BY cardinality(path)
LIMIT 1;

First, I calculate the symmetric closure.

Then I construct arrays of "conversion paths" by starting with the pairs we have, then prepending new currencies to arrays that can be converted to the first array element and do not yet appear in the array.

Once I have got all conversion chains that end up in 'usd', I pick the shortest chain that starts with 'eth'.

Answer 2

While Laurenz answer is great, it is not the most efficient.

I found that the best way to do this in production is:

1. start with trying to find the direct pair
2. then try to find pair by looking up the first leg, the last leg, and all connections
3. then fallback to Laurenz solution

The query mentioned in #2 would look something like this:

WITH
  pair_symmetric_closure AS (
    SELECT
      cp1.c1,
      cp1.c2
    FROM currency_pair cp1
    UNION
    SELECT
      cp1.c2,
      cp1.c1
    FROM currency_pair cp1
  )
SELECT *
FROM pair_symmetric_closure psc1
INNER JOIN pair_symmetric_closure pcp2 ON pcp2.c1 = psc1.c2
INNER JOIN pair_symmetric_closure pcp3 ON pcp3.c1 = pcp2.c2
WHERE
  psc1.c1 = 'usd' AND
  pcp3.c2 = 'eth';