Sorting Algorithm for Tasks with Dependencies in a Gantt Chart

I’m building a Gantt Chart with dhtmlx-gantt that contains parent and child tasks.

1. A parent task can be a dependent on another parent or child task
2. A child task can be dependent on another child or parent task
3. Tasks can have multiple dependencies
4. A dependent task can only begin once it’s ruling task is complete

If a dependency is added to a task under Parent A to Parent C, this will move the shift the start date to all tasks in Parent C, like so

Here’s how my data is structured

const tasks = [
    { id: 'parent-a', text: 'Parent A', duration: null },
    { id: 'child-a-1', text: 'Child 1', parent: 'Parent A', duration: 5 },
    { id: 'child-a-2', text: 'Child 2', parent: 'Parent A', duration: 5 },
    // ...
]

const dependencies = [
    { id: 1, source: 'child-a-1', target: 'child-a-2' },
    { id: 1, source: 'parent-b', target: 'parent-c' },
    // ...
]

To calculate the start date for each task, loop through each task and set the date dynamically based on the duration of the task

let startDate = new Date()
tasks.forEach((task, i, array) => {
   const correspondingDependency = dependencies.find(d => d.id === task.id)
   if (correspondingDependency) {
       array[i].start_date = new Date(startDate.setDate(startDate.getDate() + duration))
   }
})

The problem with this method is it won’t update any start_dates for prior tasks if a dependency is found at the end of the dependencies array (i.e., child-c-1 is dependent on child-a-3)

I feel like I may need to use recursion here, but not quite sure. Hope this all makes sense – any help is appreciated

Answer

As I understand, you’re developing an auto planning logic, similar to the Auto Scheduling that is available in paid versions of dhtmlx Gantt.

FUI, I work for DHTMLX, which sells this product, so I can’t go deeply into how to develop a free alternative:) But I think I can give you some general considerations.

1. I strongly advise against the usage of recursion for auto planning. Implementations of such an approach I’ve seen have been difficult to debug and required constant maintenance. From my experience, implementing an intuitive algorithm that will work with any possible structure of the gantt is quite challenging.
2. What definitely works – and is used in different Gantt engines available on the market – is the approach when you consider Tasks and Links of the Gantt as Directed Graph: https://en.wikipedia.org/wiki/Directed_graph Where Tasks are vertices, and Links are the edges of the Graph.

Once you are able to represent your data in the form of a graph, everything else is really simple:

• you can detect loops in your dependencies
• you’ll be able to order elements in such a way, that you always process dependent tasks only after you process tasks they depend on – Topological Sorting
• after you order the dataset topologically, you can iterate and calculate the start date of each task as ‘predecessor.start_date + predecessor.duration + link.lag’, where ‘predecessor’ is guaranteed to be processed in one of the previous iterations, without needing any recursion.

The challenging part is to convert your data structure from the parent-child hierarchy of Gantt to the flat structure of Directed Graph. Basically, it means you want to get rid of projects in your dataset and convert relations that involve projects with relations between their subtasks.

It may sound complicated at the start, but the code will be easy to understand and easy to debug.

If you limit the scope of what you’re doing, e.g. disallow relations between projects, you may get away with a simpler and more intuitive approach. But for a general-purpose solution, I think the approach I’ve outlined is the safest bet.

P.S. If you’re implementing auto scheduling similar to that in dhtmlxGantt ( https://docs.dhtmlx.com/gantt/desktop__auto_scheduling.html ) and if you plan to use it commercially, it might be worthwhile to get a paid version of dhtmlxGantt where auto-scheduling is available out of the box. Implementing a reliable auto-scheduling algorithm may take a lot of time and effort, so getting a ready solution may be less expensive than developing it from scratch.