3
\$\begingroup\$

I wanted to write a function paths that returns the possible routes between two nodes in a graph.

For example:

const graph = [
    ['a', 'b'],  // i.e. directed edge a => b
    ['a', 'c'],  // i.e. directed edge a => c
    ['b', 'a'],  // i.e. directed edge b => a
    ['b', 'c'],  // ...and so on
    ['c', 'a'],
    ['c', 'b']
];

paths({ graph, from: 'a', to: 'a' }); 

Should output:

[
  ["a","b","a"],
  ["a","b","c","a"],
  ["a","b","c","b","a"],
  ["a","c","a"],
  ["a","c","b","a"],
  ["a","c","b","c","a"]
]

Feedback on correctness and style welcome.

function paths({ graph = [], from, to }, path = []) {
    const linkedNodes = memoize(nodes.bind(null, graph));
    return explore(from, to);

    function explore(currNode, to, paths = []) {
        path.push(currNode);
        for (let linkedNode of linkedNodes(currNode)) {
            if (linkedNode === to) {
                let result = path.slice(); // copy values
                result.push(to);
                paths.push(result);
                continue;
            }
            // do not re-explore edges
            if (!hasEdgeBeenFollowedInPath({
                    edge: {
                        from: currNode,
                        to: linkedNode
                    },
                    path
                })) {                    
                explore(linkedNode, to, paths);
            }
        }
        path.pop(); // sub-graph fully explored            
        return paths;
    }
}

/** 
 * Get all nodes linked 
 * to from `node`.
 */
function nodes(graph, node) {
    return graph.reduce((p, c) => {
        (c[0] === node) && p.push(c[1]);
        return p;
    }, []);
}

/**
 * Has an edge been followed 
 * in the given path?
 */
function hasEdgeBeenFollowedInPath({ edge, path }) {
    var indices = allIndices(path, edge.from);
    return indices.some(i => path[i + 1] === edge.to);
}

/**
 * Utility to get all indices of 
 * values matching `val` in `arr`.
 */
function allIndices(arr, val) {
    var indices = [],
        i;
    for (i = 0; i < arr.length; i++) {
        if (arr[i] === val) {
            indices.push(i);
        }
    }
    return indices;
}

/**
 * Avoids recalculating linked 
 * nodes.
 */
function memoize(fn) {
    const cache = new Map();
    return function() {
        var key = JSON.stringify(arguments);
        var cached = cache.get(key);
        if (cached) {
            return cached;
        }
        cached = fn.apply(this, arguments)
        cache.set(key, cached);
        return cached;;
    };
}

/**
 * Example usage.
 **/
const graph = [
    ['a', 'b'],
    ['a', 'c'],
    ['b', 'a'],
    ['b', 'c'],
    ['c', 'a'],
    ['c', 'b']
];
document.write(JSON.stringify(paths({
    graph,
    from: 'a',
    to: 'a'
})));

\$\endgroup\$
  • \$\begingroup\$ This works great in Chrome using ES6. Is there a way to write this for IE10 or 11? It especially crashes on the const, let, and of keywords. \$\endgroup\$ – James Rollins Nov 22 '17 at 19:53
  • 1
    \$\begingroup\$ @JamesRollins You can always compile it with Babel. \$\endgroup\$ – RoToRa Nov 23 '17 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.