View source

''This page describes the algorithm to check cyclicity when a task is connected to a deliverable.''

== Introduction ==

When connecting a task to a deliverable to make it a dependency or deliverable of the task, it must be checked whether this does not create a cyclic path. To do this, it must be determined whether there is a path between the task and a task that has a deliverable that is a dependency of the task.

Segments of the path consists of Deliverable &rarr; Task &rarr; Deliverable &rarr; Task.

== Algorithm ==

A recursive method is used as described in the following.

The algorithm is implemented by the method:

<syntaxhighlight lang="cpp">
bool AdminC::Cyclic
(
  TaskC *beginTask,
  TaskC *endTask
)
</syntaxhighlight>

After a connection is made to a certain task, this method is called with <tt>Cyclic(task,task)</tt>. The steps are as follows:
# Determine all the ''deliverables'' of this beginning task.
# For each deliverable, determine whether there are tasks in the current container that are depending on this deliverable.
# If such a task is found, check if this task is not the <tt>endTask</tt> as given as a parameter of the method or if this is not the case (conditional or) if the recursive call to <tt>Cyclic</tt> returns <tt>true</tt>. If this is the case, then the created connection resulted in a cyclic path and the method can return with <tt>true</tt>
# If such a task is not found then the method can return with <tt>false</tt>.

== Implementation ==

The implementation of the [[Administration]] method is given below.

<syntaxhighlight lang="cpp">
bool AdminC::Cyclic
(
  TaskC *beginTask,
  TaskC *endTask
)
{
  // Find and check all deliverables of the task.
  DeliverableC *taskDeliverable;
  for( uint i=0; i<beginTask->Deliverables->NumElements; i++)
  {
    taskDeliverable = DeliverablesAdmin->FindDeliverable(beginTask->Deliverables->Element[i]);
    if( taskDeliverable != NULL )
    {
      // Now check the tasks that are dependent on this deliverable are the end task.
      TaskC *nextTask = TasksAdmin->First();
      while( nextTask != NULL )
      {
        if( nextTask != beginTask && nextTask->Container == beginTask->Container && nextTask->Dependencies->Find(taskDeliverable->Id) )
        {
          // Task is depending on the deliverable.
          // Check if deliverable of the task is the specified deliverable.
          if( nextTask == endTask || Cyclic( nextTask, endTask ) )
          {
            // Cyclic path found!
            return true;
          }
        }
        nextTask = nextTask->next();
      }
    }
  }
  return false;
}
</syntaxhighlight>
----