I'm trying to figure out all the paths of all the nodes up to K depth. It seems to be a dynamic programming problem, my attempt seems to be working however its slower than I expected

I would think that I would just have to:

Iterate over all the nodes, add the node neighbors as a path Foreach additional iteration, iterate over all the possible input/output combinations from the depth before and then append all of the neighbors for the last output in each path.

export type Map<TValue> = {[key:string]:TValue }
export type PathMap = Map<Map<Map<string[][]>>>
export type EdgeIOMap = Map<InputNode>
export type OutputDetailMap = Map<OutputDetail>

 interface InputNode {
    input: Node
    outputMap: OutputDetailMap

 interface OutputDetail {
    output: Token

export function buildPathMap(poolByTokenAddress: ArbitrageInputMap,  maxDepth: number = 7) {
   const pathMap: PathMap = {}
   for(let inputKey in poolByTokenAddress) {
      pathMap[inputKey] = {}; 
      for(let outputKey in poolByTokenAddress) {
        pathMap[inputKey][outputKey] = {};
        pathMap[inputKey][outputKey][0] = [];
        if(poolByTokenAddress[inputKey].outputMap[outputKey]) {

   for(let i = 1; i < maxDepth; i++) {
      for(let inputKey in poolByTokenAddress) {
        for(let outputKey in poolByTokenAddress) {
            const ioPathMap = pathMap[inputKey][outputKey] || {};
            //Initialize depth if it doesn't exist
            ioPathMap[i] = ioPathMap[i] || [];
            const previousIOPathMap = ioPathMap[i-1];
            // All the new paths are equal to all the previous paths 
            // plus all of the neighbors of the node which the previous path ended with

            for(let ppi in previousIOPathMap) {
                const previousPaths = previousIOPathMap[ppi]
                const [pathEnd] = previousPaths.slice(-1);
                console.log(`Adding Paths to ${poolByTokenAddress[inputKey].inputToken.symbol}-${poolByTokenAddress[inputKey].outputMap[outputKey].outputToken.symbol} at depth ${i}`);
                console.log(`key: ${poolByTokenAddress[inputKey].inputToken.address}`);
                for(let neighbor in poolByTokenAddress[pathEnd].outputMap) {
                    //Initialize Map if it doesn't exist
                    pathMap[inputKey][neighbor][i] = pathMap[inputKey][neighbor][i] || [];
                    const newPath = previousPaths.slice(0);
                    console.log(`\t Path: ${newPath.join('->')}`);

I tried searching for a simpler solution, this seemed semi optimized since it doesn't rely on computing the previous paths, however its still taking pretty long to go beyond depth 4, with about 50 nodes, where almost all nodes are connected.

The only optimization (which might be a major one) would be instead of copying the array during each path creation, use an reference map and at the end calculate all the paths just once?

TBH I would way rather just use a library, but I couldn't find anything which did what I specifically needed.

EDIT: Turns out there was a bug where I was adding the paths to the wrong bucket, now that I've fixed it its alot faster, however I still would appreciate a code review!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.