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

Offical Documentation

Official Docs: