GraphTraversal.js

var scripts = [
    'https://ajax.googleapis.com/ajax/libs/jquery/1.6.3/jquery.min.js',
    'https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js'
];

scripts.forEach(source => {
    var script = document.createElement('script');
    script.src = source;
    document.getElementsByTagName('head')[0].appendChild(script);
});

function visualizeGraph(edgeMap, vertices) {
	const reverseMap = {};
	const distances = {};
	vertices.forEach(n => distances[n] = 0);
	const parents = {};
	let sinkVertices = _.difference(vertices, Object.keys(edgeMap).map(n => Number.parseInt(n)));
	Object.keys(edgeMap).map(n => Number.parseInt(n)).forEach( (u) => {
		let destVertices = edgeMap[u];
		destVertices.forEach( (v) => { 
			if (!reverseMap[v])
				reverseMap[v] = [];
			reverseMap[v].push(u);
		});
	}); 
	const order = [];
	const traverse = (v) => {
	    if(reverseMap[v])
		  reverseMap[v].forEach( (u) => {
		  	   traverse(u);
		  	   if(distances[u] + 1 > distances[v]){
		  	       distances[v] = distances[u] + 1;
		  	       parents[v] = u;
		  	   }
		  });
		if(!order.includes(v))
		  order.push(v);
	};
	sinkVertices.forEach( (v) => {
        traverse(v);
	});
	console.log("order ", order);
    console.log("distances ", distances);
	console.log("parents ", parents);
}

function flipMap(edgeMap) {
	const reverseMap = {};
	Object.keys(edgeMap).map(n => Number.parseInt(n)).forEach( (u) => {
		let destVertices = edgeMap[u];
		destVertices.forEach( (v) => { 
			if (!reverseMap[v])
				reverseMap[v] = [];
			reverseMap[v].push(u);
		});
	});
	return reverseMap;
}

function simplifyGraph(edgeMap, vertices) {
	const newMap = {};
	const reverseMap = flipMap(edgeMap);
	const distances = {};
	vertices.forEach(n => distances[n] = 0);
	const parents = {};
	let sinkVertices = _.difference(vertices, Object.keys(edgeMap).map(n => Number.parseInt(n)));
	const order = [];
	const traverse = (v) => {
	    if(reverseMap[v])
		 	reverseMap[v].forEach( (u) => {
		  		traverse(u);
		  			if(distances[u] + 1 > distances[v]) {
		  	    		distances[v] = distances[u] + 1;
		  	    		parents[v] = u;
		  	    		newMap[v] = [u];
		  	  		} else if (distances[u] + 1 === distances[v]) {
		  	   	 	 	if(!newMap[v])
		  	   				newMap[v] = [];
		  	   			newMap[v].push(u);
		  	   }
		  });
		if(!order.includes(v))
		  order.push(v);
	};
	sinkVertices.forEach( (v) => {
        traverse(v);
	});
	console.log("Simplified Graph:");
	console.log("order ", order);
    console.log("distances ", distances);
	console.log("parents ", parents);
	console.log("original map", edgeMap);
	console.log("newMap", flipMap(newMap));
}

setTimeout(() => {
    visualizeGraph(
        {
            0: [1, 3],
            1: [2],
            2: [3]
        },
        [0, 1, 2, 3]
    );

    simplifyGraph(
        {
            0: [1, 3, 4],
            1: [2],
            2: [3],
        	4: [5],
        	5: [3]
        },
        [0, 1, 2, 3, 4, 5]
    );
}, 1000);