find all path in a digraph

get-all-paths.js

// find list of all paths in a digraph defined by a set of edges
// create a list of candidates.
// repeat until is not stable:
// for each edge: try to extends the candidate: at the end, at the begin
// after first turn, also split paths if necessary
// if a whole edge turn is stable, break the loop.

// Complexity: enough

let edges = [];

const addEdge = (from, to) => {
    edges.push([from,to]);
}

let candidates = [];

const aClone = data=>JSON.parse(JSON.stringify(data));

const calcIntersect = (ed) => {
    let inters = [];
    for(let i in candidates) {
        let c = candidates[i];
        if(c.find(v=>v==ed[0]) || c.find(v=>v==ed[1])) {
            inters.push({i,c});
        }
    }
    return inters;
}

let calcPaths = () => {
    let turns = 0;
    let edi = 0;
    let turn_stable = true;
    while(1) {
        if(edi>=edges.length) {
            turns++;
            if(turn_stable && turns>1) {
                //console.log("DOING BREAK",turns);
                break;
            }
            if(turns>100) {
                console.log("baby safety protection", turns);
                break;
            }
            turn_stable = true;
            edi = 0;
        }
        //if(turns>4) break;
        let stable = true;
        let edge = edges[edi];
        edi++;
        let iSet = calcIntersect(edge);
        if(iSet.length == 0) {
            candidates.push(aClone(edge));
            stable = false;
            turn_stable = false;
            continue;
        }
        let isCompletelyIn = false;
        const possibleToDup = [];
        for(let mat of iSet) {
            let last_of_c = mat.c.length - 1;
            // edge `ed` extends the end of a candidate path
            if(mat.c[last_of_c] == edge[0]) {
                // extend the candidate directly then reset new paths
                stable = false;
                mat.c.push(edge[1]);
            } else if(mat.c[0] == edge[1]) {
                stable = false;
                mat.c.unshift(edge[0]);
            } else if(mat.c.indexOf(edge[0])>=0 && mat.c.indexOf(edge[0])+1 == mat.c.indexOf(edge[1])) {
                isCompletelyIn = true;
            } else {
                // duplica il candidato
                //console.log("EDGE", edge, mat);
                possibleToDup.push(mat);
            }
        }
        if(stable && !isCompletelyIn && turns>0) {
            //console.log("I HAVE", turns, edge, possibleToDup, candidates);
            for(let mat of possibleToDup) {
                let c = mat.c;
                let startMatch = c.indexOf(edge[0]);
                let endMatch = c.indexOf(edge[1]);
                let newPath = [];
                if(startMatch != -1) {
                    for(let x=0; x<=startMatch; x++) {
                        newPath.push(c[x]);
                    }
                    newPath.push(edge[1]);
                } else {
                    newPath.push(edge[0]);
                    for(let x=endMatch; x<c.length; x++) {
                        newPath.push(c[x]);
                    }
                }
                candidates.push(newPath);
            }
            //console.log("NOT STABLE", turns)
            stable = false;
        }
        if(!stable) {
            turn_stable = false;
        }
    }
    return candidates;
}


module.exports = {
    calcPaths,
    addEdge,
    resetData: ()=>{candidates = []; edges=[]},
}

testit.js

let edges = [
    ["ftpFileRetriever", "dataReader"],
    ["vcsCheck2", "vcsRead"],
    ["vcsRead", "invoicepdfGen"],
    ["amzInventoryBake", "amzInventoryCheck"],
    ["amzInventoryCheck", "dataReader"],
    ["vcsCheck", "vcsRead"],
    ["amzVcs", "vcsBake"],
    ["hasPdfService", "invoicepdfGen"],
    ["vcsBake", "vcsCheck"],
    ["vcsBake", "vcsCheck2"],
    ["invoicepdfGen", "amzIdu"],
    ["invoicepdfGen", "emailPdf"],
    ["DataImport", "amzInventoryBake"],
    ["DataImport", "ftpFileRetriever"],
];

let getAllPaths = require('./get-all-paths');

for(let edge of edges) {
    getAllPaths.addEdge(edge[0], edge[1])
}

let paths=getAllPaths.calcPaths();
console.log(paths)