javascript - List all possible cycles in DFS

Question

I am attempt to implement a currency arbitrage system. I have a set of rates like this (excerpted):

{
  WETH: { USDC: 1251.412454, USDT: 1247.922038, DAI: 1248.889170853253, GRT: 2564.449143585127 },
  USDC: { USDT: 0.997184, GRT: 2.047075466264398 },
  UNI:  { WETH: 0.011422976592904394 },
  UST:  { USDT: 1.006223 },
  DAI:  { USDC: 0.996408 },
  LINK: { WETH: 0.016572361615010835 },
  AAVE: { WETH: 0.22086511962970312 },
  YFI:  { WETH: 22.127349619001087 },
  WNXM: { WETH: 3.198146952589934 },
  COMP: { WETH: 0.178430488180767 },
  SNX:  { WETH: 0.012523661095285127 },
  CVP:  { WETH: 0.002145308148869976 },
  MKR:  { WETH: 1.06714037595511 },
  ANT:  { WETH: 0.002866589268616632 },
  BAND: { WETH: 0.006611859609454254 },
  GNO:  { WETH: 0.08678180778916264 },
  REN:  { WETH: 0.000417608062873623 },
  UMA:  { WETH: 0.00805809579069431 },
}

And I want to list all possible cycles (begins and ends with the same token), for example:

1 WETH -> 1251.412454 USDC -> 2.047075466264398*1251.412454=2561.73573 GRT -> 2561.73573/2564.449143585127 = 0.998941912 WETH

I want to find cycles that total above 1 because they are profitable (theoretically).

I think I'm supposed to use Bellman-Ford but I couldn't get some implementations I tried to work with this data because not every pair has corresponding matches (for instance there is no AAVE-USDC pair, you have to do AAVE->WETH->USDC).

I'm using javascript but pseudocode or anything else is fine.

question from:https://stackoverflow.com/questions/65948392/list-all-possible-cycles-in-dfs

Answer 1

Waitting for answers