# Finding all paths between nodes in a graph

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 = []) {
return explore(from, to);

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

/**
* 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;
}

/**
* 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'
})));

• 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. – James Rollins Nov 22 '17 at 19:53
• @JamesRollins You can always compile it with Babel. – RoToRa Nov 23 '17 at 11:27