Find path between two nodes in JavaScript in a custom data structure
Hi I have an array of connections as shown below:
var connections =[
{
"source": "l1",
"target": "l2"
},
{
"source": "l2",
"target": "l4"
},
{
"source": "l2",
"target": "l3"
},
{
"source": "l4",
"target": "l5"
},
]
This continues with source and purpose. Now you want to find the path between two nodes using some function. let the function findConnections("l2", "l5")
return an array like below
var answer =[
{
"source": "l2",
"target": "l4"
},
{
"source": "l4",
"target": "l5"
},
]
I have no idea how can I achieve this? I tried simple JavaScript but failed. I think using underscore.js or lodash.js can we achieve this? Would it really be helpful if someone could provide a solution or give hints?
+3
source to share
4 answers
Use recursion and traverse the "list"
function find(list, from, to) {
// find the current "source"
let current = list.find(v => v.source === from);
if (!current) // no current? u got problems
throw new Error("No from in list");
// are we there yet?
if (current.target === to)
return current;
// no we're not ... so keep searching with new "source"
return [current].concat(find(list, current.target, to));
}
+1
source to share
I'm a little late to the party, but here's a simple solution:
-
build a graph from the given edges:
-
use simple advanced search to find the path
const addNode = (graph, node) => {
graph.set(node, {in: new Set(), out: new Set()});
};
const connectNodes = (graph, source, target) => {
graph.get(source).out.add(target);
graph.get(target).in.add(source);
};
const buildGraphFromEdges = (edges) => edges.reduce(
(graph, {source, target}) => {
if (!graph.has(source)) {
addNode(graph, source);
}
if (!graph.has(target)) {
addNode(graph, target);
}
connectNodes(graph, source, target);
return graph;
},
new Map()
);
const buildPath = (target, path) => {
const result = [];
while (path.has(target)) {
const source = path.get(target);
result.push({source, target});
target = source;
}
return result.reverse();
};
const findPath = (source, target, graph) => {
if (!graph.has(source)) {
throw new Error('Unknown source.');
}
if (!graph.has(target)) {
throw new Error('Unknown target.');
}
const queue = [source];
const visited = new Set();
const path = new Map();
while (queue.length > 0) {
const start = queue.shift();
if (start === target) {
return buildPath(start, path);
}
for (const next of graph.get(start).out) {
if (visited.has(next)) {
continue;
}
if (!queue.includes(next)) {
path.set(next, start);
queue.push(next);
}
}
visited.add(start);
}
return null;
};
// A --* B
// / | \
// * | *
// C | D --* E
// \ | / *
// * * * /
// F------/
const graph = buildGraphFromEdges([
{ source: 'A', target: 'B' },
{ source: 'B', target: 'C' },
{ source: 'B', target: 'D' },
{ source: 'B', target: 'F' },
{ source: 'C', target: 'F' },
{ source: 'D', target: 'E' },
{ source: 'D', target: 'F' },
{ source: 'F', target: 'E' },
]);
console.log('A -> A', findPath('A', 'A', graph)); // []
console.log('A -> F', findPath('A', 'F', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'F'}]
console.log('A -> E', findPath('A', 'E', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'D'}, {source: 'D', target: 'E'}]
console.log('E -> A', findPath('E', 'A', graph)); // null
Note that I understood your input to form an oriented graph . If it were instead an undirected graph, the solution could be simplified a bit.
+1
source to share
Next, a JSON object will be returned as stated in the question. It will also check for the existence of both arguments, as well as the JSON relationship between them. I'll leave that to the author to test other edge cases.
var findConnections = function(json,from,to) {
// JSON is an unordered structure, so let compile two arrays for ease of searching
var sources = [], targets = [];
for ( node of json ) {
sources.push(node.source);
targets.push(node.target);
}
// Select each 'from' element from the 'sources' array, get its target...
for(var i=0;i<sources.length;i++) {
if( (fromIndex = sources.indexOf(from,i)) < 0 ) { throw new Error('Connection could not be established.'); }
var fromTarget = targets[fromIndex];
// ...then look for the connected 'to' in the 'targets' array
for(var j=0;j<sources.length;j++) {
if( (toIndex = sources.indexOf(fromTarget,j)) < 0 ) { continue; }
// If we have a match, compile and return a JSON object. If not, we'll keep looping and if we loop out, an error will be thrown below
if( targets[toIndex] == to ) {
return [
{
'source':sources[fromIndex],
'target':targets[fromIndex]
},
{
'source':sources[toIndex],
'target':targets[toIndex]
}
];
}
}
}
throw new Error('Connection could not be established.');
}
Test it like this:
var answer = findConnections(connections,'l2','l5');
console.log(answer);
0
source to share
I spent waaaaay too much time on this and I'm sure there is a more elegant solution out there, but I'll see if I can add comments and explain myself.
// Add some more connections. Make some of them out
// of order just for fun
let connections = [{
source: 'l1',
target: 'l2'
},
{
source: 'l1',
target: 'l3'
},
{
source: 'l2',
target: 'l4'
},
{
source: 'l2',
target: 'l3'
},
{
source: 'l4',
target: 'l5'
},
{
source: 'l3',
target: 'l6'
},
{
source: 'l3',
target: 'l5'
},
{
source: 'l4',
target: 'l6'
}
];
// I just realized that I didn't call this
// function what you wanted it called but
// it should be fine
let answers = findPaths(connections, 'l1', 'l5');
console.log(JSON.stringify(answers, null, 2));
function findPaths(connections, start, end) {
// first, build a tree, for loads of connections,
// this is probably slow as hell
let tree = buildTree(
connections,
findConnection(connections, start),
null
);
// make the tree into all the different paths
// also probably slow as hell. Could prune the
// tree if I could figure out how to implement
// a backtracking algoritm in javascript but
// I couldn't figure it out from the wikipedia
// article so I skipped it
let allPaths = buildPaths(tree, []);
// pare down the paths to ones that fit the start
// and end points
let goodPaths = verifyPaths(allPaths, start, end);
// reformat that thing to match what you wanted
return format(goodPaths);
}
// so this thing just runs through the connections
// array and returns an array of elements where the
// source property matches the source argument
function findConnection(connections, source) {
return connections.filter(conn => conn.source === source);
}
// So this returns an array that contains a tree
// Probably a better way to do this, but...
function buildTree(connections, nodes, parent) {
// for each node...
return nodes.map(node => {
// had to cheat here, just add the node parent
// to the node. That way, we don't have to think
// about it later
node.parent = parent;
// find any other connections whose source property
// matches our target property.
node.path = findConnection(connections, node.target);
// if some were found, then...
if (node.path && node.path.length > 0) {
// build that sub-tree. Here, I cheated big-time
// and made the third param (parent) an object
// that had the properties I wanted later.
// It just easier.
buildTree(connections, node.path, {
source: node.source,
target: node.target,
parent: node.parent
});
}
// done slapping this around, return it
return node;
});
}
// so this is a part could be better. Probably could be
// replaced by Array.reduce, but I'm too lazy. This
// turns the "tree" into an array of all of the paths
// from beginning to end. Many of the paths will be
// filtered out later so it could be made more efficient
function buildPaths(tree, prev) {
tree.forEach(step => {
if (step.path.length > 0) {
buildPaths(step.path, prev);
} else {
prev.push(step);
}
});
return prev;
}
// filter out the paths that don't match the specified
// start and end. We should have good paths now...in
// the wrong format, but we'll fix that up later...
function verifyPaths(paths, start, end) {
return paths.filter(path => path.target === end).filter(path => {
while (path.parent) {
path = path.parent;
}
return path.source == start;
});
}
// alright, go ahead and flatten out the good paths
// into the requested format
function format(arr) {
return arr.map(el => {
let temp = [];
temp.unshift({
source: el.source,
target: el.target
});
while (el.parent) {
el = el.parent;
temp.unshift({
source: el.source,
target: el.target
});
}
return temp;
});
}
0
source to share