Find paths between nodes in JS object graph

Question

How can I get this result:

[
  {Paris,Amsterdam,Berlin},
  {Paris,Bruxelles,Amsterdam,Berlin},
  {Paris,Bruxelles,Berlin}
]

from this array:

[
  { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
  { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
  { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' } 
]

I want to map data from this array to get all the possibilities of paths to get from a city to another, from 'Paris' To 'Berlin' for example.

Answer 1

let data = [
    {HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20'},
    {HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20'},
    {HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10'},
    {HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10'},
    {HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20'}
];

function getDuration(hd, d) {
    let time1 = hd.split(":");
    let time2 = d.split(":");
    let h1 = parseInt(time1[0]);
    let m1 = parseInt(time1[1]);
    let h2 = parseInt(time2[0]);
    let m2 = parseInt(time2[1]);
    if (h2 < h1) {
        h2 += 12;
    }
    let time = (h2 * 60 + m2) - (h1 * 60 + m1);
    let offset = (time % 60) * 0.01;
    return Math.floor(time / 60) + offset;
}

let mapper = {};
let durations = {};

data.forEach(item => {
    if (!mapper[item.V1]) {
        mapper[item.V1] = [];
    }
    mapper[item.V1].push(item.V2);
    durations[item.V1 + "_" + item.V2] = getDuration(item.HD, item.D);
});

let generatedRoutes = [];

function routeGenerator(starting, destination, path) {
    if (starting === destination) {
        generatedRoutes.push(path);
        return;
    }
    if (!mapper[starting]) return;
    let routes = mapper[starting];
    routes.forEach(route => {
        routeGenerator(route, destination, path + "," + route);
    })
}

routeGenerator("Paris", "Berlin", "Paris");

function calculateTimeDuration() {
    let minDuration = 100000;
    let minDurationPath = "";
    generatedRoutes.forEach(path => {
        let paths = path.split(",");
        let d = 0;
        for (let i = 0; i < paths.length - 1; i++) {
            let firstCity = paths[i];
            let secondCity = paths[i + 1];
            let key = firstCity + '_' + secondCity;
            d += durations[key];
        }
        if (d < minDuration) {
            minDuration = d;
            minDurationPath = path;
        }
    });
    return {
        duration: minDuration,
        path: minDurationPath
    }
}

console.log(calculateTimeDuration());

OK, It's a kinda graph problem to solve. First of all, you need to map all the routes you have starting from a certain V1. mapper objects contain every routes for a certain path.

then, just a normal recursive function to generate the routes.

Console Output:

{ 
    duration: 11.4,
    path: 'Paris,Amsterdam,Berlin'
}

I have generated the paths as string and you can split them if you need and pushed them into the array.

if you need to generate paths for any other entry point, you can do that. Just change the parameters passing through routeGenerator. For example, if you change it to,

routeGenerator("Amsterdam", "Berlin", "Amsterdam");

you will get:

{ 
    duration: 5.4,
    path: 'Amsterdam,Berlin'
}

Answer 2

The input graph is a DAG and looks like this:

  +-----------------------+
  |                       |
  |                       v
Paris -> Bruxelles -> Amsterdam -> Berlin
             |                       ^
             |                       |
             +-----------------------+

We can build an object with source strings mapped to an array of their possible destinations which is much more convenient to use than the input object, then run a DFS on the graph and yield each result path.

function *findPaths(graph, src, dst, path=[]) {
  if (src === dst) {
    yield path.concat(dst);
  }
  else if (graph[src]) {
    path.push(src);
    
    for (const neighbor of graph[src]) {
      yield *findPaths(graph, neighbor, dst, path);
    }
    
    path.pop(src);
  }
};

const graphify = routes => {
  const graph = {};
  
  for (const node of routes) {
    if (!graph[node.V1]) {
      graph[node.V1] = [];
    }
    
    graph[node.V1].push(node.V2)
  }
  
  return graph;
};

const routes = [
  { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
  { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
  { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' } 
];

console.log(...findPaths(graphify(routes), "Paris", "Berlin"));

If you anticipate cycles in your graph, add a Set to keep track of visited nodes to avoid re-visiting them during a traversal:

function *findPaths(graph, src, dst, path=[], visited=(new Set())) {
  if (src === dst) {
    yield path.concat(dst);
  }
  else if (graph[src] && !visited.has(src)) {
    visited.add(src);
    path.push(src);
    
    for (const neighbor of graph[src]) {
      yield *findPaths(graph, neighbor, dst, path, visited);
    }
    
    visited.delete(src);
    path.pop(src);
  }
};

const graphify = routes => {
  const graph = {};
  
  for (const node of routes) {
    if (!graph[node.V1]) {
      graph[node.V1] = [];
    }
    
    graph[node.V1].push(node.V2)
  }
  
  return graph;
};

const routes = [
  { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
  { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
  { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Paris', D: '6:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Paris', D: '9:20' } 
];

console.log(...findPaths(graphify(routes), "Paris", "Berlin"));

If you wish to account for travel time (edge weights), use Dijkstra's Algorithm. The implementation is more involved because we need a priority queue (min/Fibonacci heap) to efficiently extract the shortest tentative distance.

Answer 3

Without using map Function

JS Seems to get confused with map in this case

var result = Object.keys(obj).map(function(key) {
  return [Number(key), obj[key]];
});

Here is a way using a for statement

    var obj =    [
      { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
      { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
      { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
      { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
      { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' }
    ]
    console.log(obj);
    let NewArray = [];
    for (i=0;i<obj.length ;i++){
         console.log(obj[i].HD);

        let HD = obj[i].HD;
        let V1 = obj[i].V1;
        let V2 = obj[i].V2;
        let D = obj[i].D;
        
        NewArray[i] = {HD,V1,V2,D};
    }
    console.log(NewArray);