import { BigNumber } from "bignumber.js" ; import { AssetID } from "../../model" ; import { OffersGraph } from "./offers_graph" ; interface IPaths { [ sourceAsset ] : { amountNeeded : BigNumber ; path : AssetID [ ] ; } ; } const maxPathLength = 5 ; export class PathFinder { private readonly result : IPaths = { } ; constructor ( private readonly graph ) { } public findPaths ( sourceAssets , destAsset , destAmount ) { if ( destAsset === "native" && sourceAssets . length === 1 && sourceAssets [ 0 ] === "native" ) { return { native : { amountNeeded : destAmount , path : [ ] } } ; } const lowestCost = new Map < AssetID , BigNumber > ( ) ; const find = ( nextAsset , amountIn , currentPath = [ ] ) => { if ( currentPath . includes ( nextAsset ) || currentPath . length - 1 > maxPathLength ) { return ; } const cost = lowestCost . get ( nextAsset ) ; if ( ! cost || amountIn . lt ( cost ) ) { lowestCost . set ( nextAsset , amountIn ) ; } else { return ; } if ( sourceAssets . includes ( nextAsset ) ) { this . result [ nextAsset ] = { amountNeeded : amountIn , path : currentPath . slice ( 1 ) . reverse ( ) } ; } const edges = this . graph . getEdges ( nextAsset ) ; if ( ! edges ) { return ; } for ( const { vertex , data : { capacity , orderBook } } of edges ) { if ( capacity . gte ( amountIn ) ) { const amountOut = orderBook . buy ( amountIn ) ; find ( vertex , amountOut , currentPath . concat ( nextAsset ) ) ; } } } ; find ( destAsset , destAmount ) ; return this . result ; } }