Find the Path between two nodes in JavaScript on custom data structure

Question

Hi I have a connections array as below:

var connections =[

    {
      "source": "l1",
      "target": "l2"
    },
    {
      "source": "l2",
      "target": "l4"
    },
    {
      "source": "l2",
      "target": "l3"
    },
    {
      "source": "l4",
      "target": "l5"
    },   

]

It goes on with source and target. Now want to find the path between two nodes using some function. let's say function findConnections("l2", "l5") will return the 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 we can achieve this? It will be really helpful if anyone provide solution or give hints?

Answer 1

I'm a bit late to the party, but here's a simple solution:

1. build a graph from the given edges:

   

2. use simple breadth-first-search to find a 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 a directed graph. If instead it's meant to be a undirected graph the solution could be simplified a bit.