Custom sorting/ path finding in JS

I’m trying to work out some sorting/ path finding algorithm. As a starting point I always have Start ID and Finish ID (id of starting + last node) in following format:

{"START_ID": "1z2x", "FINISH_ID":"cc2v"}

Next part is the array with my objects (edges) to be sorted/ found path. Each of the object is constructed in the following way:

{"ID_FROM": "1z2x", "ID_TO": "wdf3"}

As you can see each of this object has starting node and finish node. Since I always know Start Node and Finish Node for the whole path I’d like to compose path.

Examples:

Starting + Finish Nodes:

{"START_ID": "123v", "FINISH_ID":"8s6h"}

Array with edges:

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}, {"ID_FROM":"plnx", "ID_TO":"7777"}]

From the above the path I’d like to receive would be:

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"plnx", "ID_TO":"7777"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}]

Additionally, there can be multiple objects that point to the same edge (and they should be in following indexes), example:

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"plnx", "ID_TO":"7777"}]

And the path for that would be:

 [{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"13kj", "ID_TO":"plnx"},, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"plnx", "ID_TO":"7777"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}]

Few limitations/ informations: -> Start and end node is always known -> Number of edges can vary from 2 to 10 -> There can be multiple objects that point have the same ID_FROM and ID_TO <- they are not a duplicates and should be in following positions

Would be really grateful if anyone could help me with that.

Best regards and thank you in advance! Mat

EDIT:

I’d like to build a way that can go ID1 -> ID2 -> ID3 <- ID4. Assuming that I still know start and end (ID1 and ID4).

Example:

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"8542", "ID_TO":"13kj"}]

In the case when START_ID = 123v and FINISH_ID = 8542, the path should look like:

[{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"13kj", "ID_TO":"plnx"},  {"ID_FROM":"8542", "ID_TO":"plnx"}]

Answer

Using a simple DFS algorithm you find one path if it exists(not necessarily the shortest)

function recursive_DFS(nodes, El, head, finish){
  if(head === finish){
    nodes.push(head)
    return nodes;
  }else{
    nodes.push(head)
    for(const next of (El[head] || [])){
      t = recursive_DFS(nodes, El, next, finish)
      if(t) return t;
    }
    nodes.pop(head)
  }
}

// just make sure to produce the output in the format you want
function nodes_to_edges(nodes){
  edges = []
  for(let i = 1; i < nodes.length; ++i){
    edges.push({ID_FROM: nodes[i-1], ID_TO: nodes[i]})
  }
  return edges;
}

function find_route(path, E){
  El = {}
  // make it easier to lookup afterwards
  for(const {ID_FROM, ID_TO} of E){
    if(!El[ID_FROM]) El[ID_FROM] = [ID_TO]
    else El[ID_FROM].push(ID_TO)
  }
  return nodes_to_edges(recursive_DFS([], El, path.START_ID, path.FINISH_ID));
}

Testing:

console.log(find_route(
{"START_ID": "123v", "FINISH_ID":"8s6h"}, 
  [{"ID_FROM":"123v", "ID_TO":"985j"}, {"ID_FROM":"13kj", "ID_TO":"plnx"}, 
  {"ID_FROM":"985j", "ID_TO":"13kj"}, {"ID_FROM":"7777", "ID_TO":"8s6h"}, 
  {"ID_FROM":"plnx", "ID_TO":"7777"}]))

If you are interested in the best performance you may want to replace the recursive DFS by an iterative version. If you want to make sure to find the shortest path you can use a BFS instead, but that requires a first-in-first-out instead of a last-in-first-out data structure.

function annotate_paths(origin, El, head){
  for(const next of (El[head] || [])){
    if(!origin[next]){
      // keep track of where it comes from
      origin[next] = head;
      t = annotate_paths(origin, El, next)
    }
  }
}

// just make sure to produce the output in the format you want
function reconstruct(origin, node, START){
  edges = []
  prevNode = node;
  while(origin[node] !== START){
    const prevNode = node;
    node = origin[node];
    edges.push({ID_FROM: node, ID_TO: prevNode})
  }
  return edges.reverse();
}

function find_route(path, E){
  El = {}
  // make it easier to lookup afterwards
  for(const {ID_FROM, ID_TO} of E){
    if(!El[ID_FROM]) El[ID_FROM] = [ID_TO]
    else El[ID_FROM].push(ID_TO)
  }
  
  const {START_ID, FINISH_ID} = path;
  const START = {}
  origin1 = {}
  origin2 = {}
  origin1[START_ID] = START;
  origin2[FINISH_ID] = START;
  annotate_paths(origin1, El, START_ID)
  annotate_paths(origin2, El, FINISH_ID)

  for(const meetAt in origin1){
    if(origin2[meetAt]){
      path1 = reconstruct(origin1, meetAt, START) // Path from ID_FROM to meeting node
      path2 = reconstruct(origin2, meetAt, START) // Path from ID_TO to the meeting node
      return [...path1, ...path2.reverse()]
    }
  }
  return null;
}

// Original question
console.log(find_route(
  {"START_ID": "123v", "FINISH_ID":"8s6h"}, 
  [
    {"ID_FROM":"123v", "ID_TO":"985j"}, 
    {"ID_FROM":"13kj", "ID_TO":"plnx"}, 
    {"ID_FROM":"985j", "ID_TO":"13kj"}, 
    {"ID_FROM":"7777", "ID_TO":"8s6h"}, 
    {"ID_FROM":"plnx", "ID_TO":"7777"}
  ]))

// Updated question
console.log(find_route(
  {
    START_ID: '123v', 
    FINISH_ID: '8542'
  },
  [
    {"ID_FROM":"123v", "ID_TO":"985j"}, 
    {"ID_FROM":"13kj", "ID_TO":"plnx"}, 
    {"ID_FROM":"985j", "ID_TO":"13kj"}, 
    {"ID_FROM":"8542", "ID_TO":"13kj"}
  ]))