let routes = [
{ start: "mumbai", end: "paris" }
,{ start: "mumbai", end: "dubai" }
,{ start: "mumbai", end: "boston" }
,{ start: "paris", end: "boston" }
,{ start: "dubai", end: "paris" }
,{ start: "paris", end: "ny" }
,{ start: "dubai", end: "ny" }
,{ start: "boston", end: "ny" }
,{ start: "ny", end: "dubai" }
]
/* we want a graph like this
*
{
mumbai:[paris, dubai, ny],
paris: [dubai, ny]
}
*/
const queue = [];
const hasPath = (graph, src, dest) => {
if (src === dest) {
queue.push(src)
return true;
}
for (let neighbor in graph[src]) {
queue.push(src)
if (hasPath(graph, graph[src][neighbor], dest)) {
return true;
}
}
console.log("return false");
queue.shift()
return false;
}
const buildGraph = (edges) => {
const graph = {};
edges.forEach(edge => {
if (!graph.hasOwnProperty(edge.start)) graph[edge.start] = []; // this is 1 directional graph.
graph[edge.start].push(edge.end)
});
console.log(graph);
return graph;
}
const buildGraphUndirected = (edges, src, dest) => {
const graph = {};
for (let edge in edges) {
if (!graph.hasOwnProperty(edges[edge]["start"]))graph[edges[edge]["start"]] = [];
if (!graph.hasOwnProperty(edges[edge]["end"]))graph[edges[edge]["end"]] = []; // this would become non-directed graph
graph[edges[edge]["start"]].push(edges[edge]["end"])
graph[edges[edge]["end"]].push(edges[edge]["start"]); // this would become non-directed graph
}
//console.log(graph);
return graph;
}
hasPath(buildGraph(routes), "mumbai", "boston");
console.log("----------------------------------------");
console.log(queue)
//buildGraphUndirected(routes);
console.log("----------------------------------------");
/*
* alternate for of loop ...but doesn't work in IE
* if input was of tuples we could have used iterable syntax
* need to put up another code block for that type
for (let edge of edges) {
}
*/
