Name

global.CycleDetector

Description

Cycle Detector for Project Diagnosis

Script

var CycleDetector = Class.create();
CycleDetector.prototype = {
  tasks: [],
  taskSysIds: [],
  relations: [],
  taskProcessStack: [],
  cyclicTasks: [],
  cycleDetected: false,

  initialize: function() {
      gs.info("Into CycleDetector");
  },

  isNil: function(value) {
      if( !value || value == "" || value == null ) {
          return true;
      }
      return false;
  },

  getTaskObject: function(gr) {
      if( gr.isValid()) {
          return {
              sys_id: gr.getValue("sys_id"),
              parent: gr.getValue("parent"),
              top_task: gr.getValue("tap_task"),
              number: gr.getValue("number"),
              short_description: gr.getValue("short_description"),
              start_date: gr.getValue("start_date"),
              end_date: gr.getValue("en_date"),
              duration: gr.getValue("duration"),
              children: [],
              predecessors: [],
              successors: [],
              processed: false
          };
      }
      return;
  },

  getRelationObject: function(gr) {
      if( gr.isValid()) {
          return {
              sys_id: gr.getValue("sys_id"),
              parent: gr.getValue("parent"),
              child: gr.getValue("child"),
              lag: gr.getValue("lag"),
              type: gr.getValue("type"),
              sub_type: gr.getValue("sub_type"),
              processed: false
          };
      }
      return;
  },

  glideRecord: function() {
      var gr = new GlideRecord("planned_task");
      return gr;
  },

  getTasks: function(sysId) {
      var plannedTasks = this.glideRecord();
      plannedTasks.addQuery("top_task", sysId).addOrCondition("parent", sysId);
      plannedTasks.query();
      return plannedTasks;
  },

  getRelations: function(sysIds) {
      var taskRelations = new GlideRecord("planned_task_rel_planned_task");
      taskRelations.addQuery("parent", "IN", sysIds).addOrCondition("child", "IN",  sysIds);
      taskRelations.query();

      return taskRelations;
  },

  loadTask: function(gr) {
      var task = this.getTaskObject(gr);
      this.tasks.push(task);
      this.taskSysIds.push(task.sys_id);
  },

  loadTasks: function(sysId) {
      var tasks = this.getTasks(sysId);
      gs.info("Tasks Count: " + tasks.getRowCount());
      while( tasks.next() ) {
          this.loadTask(tasks);
      }
  },

  loadRelation: function(gr) {
      var relation = this.getRelationObject(gr);
      this.relations.push(relation);
  },

  loadRelations: function() {
      var relations = this.getRelations(this.taskSysIds.join(","));
      gs.info("Relations Count: " + relations.getRowCount());
      while( relations.next() ) {
          this.loadRelation(relations);
      }
  },

  getTaskBySysId: function(sysId) {
      for (var i = 0; i < this.tasks.length; i++) {
          if(this.tasks[i].sys_id == sysId) {
  
              return this.tasks[i];
          }
      }
  },

  processParentChild: function() {
      if( this.tasks.length > 0) {
          for (var i = 0; i < this.tasks.length; i++) {
              var task = this.tasks[i];
              if( !this.isNil(task.parent)) {
                  var parentTask = this.getTaskBySysId(task.parent);
                  parentTask.children.push(task.sys_id);    
              }
          }
      } else {
          gs.info("*** No Tasks Found ***");
      }
  },

  proccessPredecessorSuccessor: function() {
      if(this.relations.length > 0) {
          for (var i = 0; i < this.relations.length; i++) {
              var relation = this.relations[i];
              if( !this.isNil(relation.parent)) {
                  var predecessorTask = this.getTaskBySysId(relation.parent);
                  if( predecessorTask )
                      predecessorTask.successors.push(relation);
              }
              if( !this.isNil(relation.child)) {
                  var successorTask = this.getTaskBySysId(relation.child);
                  if( successorTask )
                      successorTask.predecessors.push(relation);
              }
          }
      } else {
          gs.info("*** No Relations Found ***");   
      }
  },

  processForDetectCycles: function(sysId) {
      this.propagateParentRelationsToLeafTasks();
      this.propagateParentAsSuccessors();
      this.startDetectCycles(sysId);
  },

  startDetectCycles: function(sysId) {
      
      var leafTasks = this.getSubTreeLeafs(sysId);
      for (var i = 0; i < leafTasks.length; i++) {
          if( this.detectCycle(leafTasks[i]) ) {
              this.cycleDetected = true;
              break;
          }
      }
  },

  detectCycle: function(sysId) {
      // Add the task 
      this.taskProcessStack.push(sysId);
      while( this.taskProcessStack.length > 0) {
          var lastTaskInStack = this.taskProcessStack[this.taskProcessStack.length-1];

          // Get the next successors
          var nextSuccessorSysId = this.getSuccessorForTask(lastTaskInStack);
          if( !this.isNil(nextSuccessorSysId) ) {
              if( this.taskProcessStackContains(nextSuccessorSysId) ) {
                  var message = this.printTaskProccessStack(nextSuccessorSysId);
                  this.cyclicTasks.push({sys_id: nextSuccessorSysId, 
                                          message: message});
                  return true; // Cycle Detected
              } else {
                  this.taskProcessStack.push(nextSuccessorSysId);
              }
          } else {
  
              // pop the last task
              this.taskProcessStack.pop();
          }
      }
      this.resetAllTaskSuccessors();
      return false;
  },

  getSuccessorForTask: function(sysId) {
      var task = this.getTaskBySysId(sysId);
      var successors = task.successors;
      for (var i = 0; i < successors.length; i++) {
          var successor = successors[i];
          if( !successor.processed ) {
              successor.processed = true;
  
              return successor.child;
          }
      }
      return;
  },

  taskProcessStackContains: function(sysId) {
      for (var i = 0; i < this.taskProcessStack.length; i++) {
          if( sysId == this.taskProcessStack[i]) {
              return true;
          }
      }
      return false;
  },

  resetAllTaskSuccessors: function() {
      /*for (var i = 0; i < this.tasks.length; i++) {
          gs.info("Resetting task: " + this.tasks[i].short_description + " - " + this.tasks[i].sys_id);
          var successors = this.tasks[i].successors;
          for (var i = 0; i < successors.length; i++) {
                 successors[i].processed = false;
          }   
      }*/
  },

  printTaskProccessStack: function(sysId) {
      var cycleString = "";
      for (var i = 0; i < this.taskProcessStack.length; i++) {
          var task = this.getTaskBySysId(this.taskProcessStack[i]);
          cycleString = cycleString + task.number + " -> ";
      }
      var recursiveTask = this.getTaskBySysId(sysId);
      gs.info( cycleString + recursiveTask.number);
      return cycleString + recursiveTask.number;
  },

  getCloneRelation: function( parent, child, type ) {
      return {
          sys_id: undefined,
          parent: parent,
          child: child,
          lag: undefined,
          type: type,
          sub_type: type,
          processed: false
      };
  },

  propagateParentAsSuccessors: function() {
      for (var i = 0; i < this.tasks.length; i++) {
          var task = this.tasks[i];
          if( !this.isNil(task.parent) ) {
              var parentTask = this.getTaskBySysId(task.parent);
              var cloneRelation = this.getCloneRelation(task.sys_id, task.parent, "child");
              task.successors.push(cloneRelation);
              parentTask.predecessors.push(cloneRelation);
          }
      }
  },

  propagateParentRelationsToLeafTasks:  function() {
      for (var i = 0; i < this.tasks.length; i++) {
          var task = this.tasks[i];

          //     " | children -> " + task.children.length);
          if( task.predecessors.length > 0 && task.children.size > 0 ) {
              var subTreeLeafTasks = this.getSubTreeLeafs(task.sys_id);
  
              var predecessorRelations = task.predecessors;
              for (var i = 0; i < subTreeLeafTasks.length; i++) {
                  var subTreeLeafTask = subTreeLeafTasks[i];
                  for (var i = 0; i < predecessorRelations.length; i++) {
                      var predecessorRelation = predecessorRelations[i];
                      var cloneRelation = this.cloneRelation(predecessorRelation.parent, subTreeLeafTask.sys_id, "parent_clone");
                      var predecessorTask = this.getTaskBySysId(task.parent);
                      predecessorTask.successors.push(cloneRelation);
                      subTreeLeafTask.predecessors.push(cloneRelation);
                  }
              }
          }
      }
  },

  getSubTreeLeafs: function(sysId) {
      var subTreeLeafTasks = [];
      this.addSubTreeLeaf(sysId, subTreeLeafTasks);
      return subTreeLeafTasks;
  },

  addSubTreeLeaf: function(sysId, subTreeLeafTasks) {
      var task = this.getTaskBySysId(sysId);
      if(task.children.length > 0) {
          var childSysIdes = task.children;

          for (var i = 0; i < childSysIdes.length; i++) {
  
              if( sysId != childSysIdes[i]) {
                  this.addSubTreeLeaf(childSysIdes[i], subTreeLeafTasks);    
              } else {
                  gs.info("***** Parent it self is mapped to child *****");
              }
          }
      } else {
          subTreeLeafTasks.push(sysId);
      }
  },

  processProject: function(sysId) {
      this.loadTasks(sysId);
      this.loadRelations();
      this.processParentChild();
      this.proccessPredecessorSuccessor();
      this.processForDetectCycles(sysId);
  },
  
  isCyclic: function() {
  	return this.cycleDetected;
  },

  getCyclicTasks: function () {
      return this.cyclicTasks;
  },

  type: 'CycleDetector'
};

Sys ID

6f20d2539f75220088265bb0657fcf22

Offical Documentation

Official Docs: