Name
sn_irm_shared_cmn.DirectedGraph
Description
This is a class to build a directed graph and perform operations on them like 1. Add a connection between two nodes. 2. Detect a circular dependency.
Script
var DirectedGraph = Class.create();
DirectedGraph.prototype = (function() {
var directedGraph = {};
var nodes = {};
var totalNodes = 0;
/**
* Private recursive method to do DFS to detect cycle in the directed graph.
* @param {String} node - current node under processing.
* @param {Object} visited, Object to store the visited nodes.
* @param {Object} stack, Object to store the recursion stack.
* @return {boolean} Returns true if cycle is detected, false if not.
*/
function _isCycleDetectedUsingDFS(node, visited, stack) {
if (stack[node]) {
return true;
}
if (visited[node]) {
return false;
}
visited[node] = true;
stack[node] = true;
var childNodes = directedGraph[node] || [];
for (var i = 0; i < childNodes.length; i++) {
var childNode = childNodes[i];
if (_isCycleDetectedUsingDFS(childNode, visited, stack)) {
return true;
}
}
stack[node] = false;
return false;
}
return {
initialize: function(nodesArray) {
nodes = nodesArray;
totalNodes = nodes.length;
for (var i = 0; i < totalNodes; i++) {
var node = nodes[i];
directedGraph[node] = [];
}
},
/**
* Method to make a directed connection between source and destination.
* @param {String} source - source node.
* @param {String} destination - destination node.
*/
addEdge: function(source, destination) {
if (gs.nil(source) || gs.nil(destination)) {
return;
}
directedGraph[source].push(destination);
},
/**
* Method to detect cycle in the directed graph.
* @return {boolean} Returns true if cycle is detected, false if not.
*/
isCycleDetected: function() {
var visited = {};
var recStack = {};
if (totalNodes <= 1) {
return false;
}
for (var i = 0; i < totalNodes; i++) {
visited[nodes[i]] = false;
recStack[nodes[i]] = false;
}
for (i = 0; i < totalNodes; i++) {
if (_isCycleDetectedUsingDFS(nodes[i], visited, recStack)) {
return true;
}
}
return false;
},
type: 'DirectedGraph',
};
})();
Sys ID
ed8d98ebeb572110fba682f2385228d9