5 min read
Next in trending

TodoDAG

// TODO: use new data structure for task mgmt

TodoDAG

// TODO: use new data structure for task mgmt


How do you prioritize your tasks? Chances are, you use some form of to-do list. Perhaps you use some kind of advanced to-do list like kanban (read: Trello). Well, my suggestion here is that you’re doing it wrong. The list is the wrong data structure to use.

If your task list has more than a few tasks in it, you may have found that the way you’ve ordered the list feels a bit arbitrary. That it doesn’t tell the whole story. And that it feels very … flat.

Why is “review Bob’s change to the FooBar” before “implement new login behavior” in the list? It might be that Bob’s change to the FooBar is a logically necessary precursor to starting work on the new login behavior. Or it might be that Bob’s changes to the FooBar are more important than those pesky logins. Or it might be that Bob snuck that task to the top of the list to get you to finally look at his work. Or there may be more than one reason. Or it might just be that, well, there is no good reason for Bob to be more important than those logins — the list just forced you to decide which to put first.

There are two undesirable things here: the list forces you to make time ordering decisions even when these are arbitrary, and it then loses track of why you made those decisions, or even what those decisions were.

What is the basic kind of fact that your scheduling system needs to store? I suggest that it is a time-ordering decision. “X has to be done before we can start doing Y.” “Signing off on Z requires that Y is finished.” “X is more important than Q, so we should do it first.” And so on.

These decisions are time-ordering constraints. If you have ever used a build tool like Make, you will be familiar with these. Let’s write AB to mean “do A before B.” Then in the example above, we have XY, YZ, and XQ.

How might we represent these constraints in our to-do application? We simply draw arrows between our task cards. The list you are using already has these arrows implicitly from one task card to the next in the list — you should just be free to manipulate these arrows yourself.

You should be able to draw arrows. You should be able to comment on them, just like you already comment on your tasks. You should be able to delete them if the justification doesn’t hold up.

Notice the properties of these arrows. Since we must do X before Y and Y before Z, we must do X before Z. Also, since we must do X before Y, we must not do Y before X: circular dependencies are bad! In other words, these time-ordering constraints are a strictpartial order,’ and our tasks and arrows form a ‘directed acyclic graph.’ Fancy terms.

A DAG is freer than a list. Not all tasks have a defined order. If we have XY and XQ, then the tasks Y and Q do not have to be done in any particular order — you just have to do X before either of them.

How might we represent this in our to-do application? Well, the strict top-to-bottom column of cards is no longer appropriate. Since Y and Q don’t have any order, they could sit next to each other. In general, we should be able to drag cards around on the ‘infinite workspace.’ It’s your screen, and you can put those cards wherever you want.

As well as neatly capturing logical dependencies and priorities, it turns out that those arrows also capture another idea: hierarchy. All tasks are decomposable into smaller chunks. Representing this using a list is hard — either you decompose the tasks too much, and the big ideas get lost in the little details, or to avoid that you don’t decompose the tasks enough, and you get big, unmanageable, week-long tasks.

Using a DAG, you can represent the fact that the big task T is composed of subtasks t1 and t2 by drawing arrows t1→T and t2→T. Once the subtasks are checked off, you’re free to check off T.

The DAG alleviates yet another problem with the list. When working in a team, multiple items in the list are being worked on at once. But you do not want two people working on tasks that interfere with each other. Are those two items at the top of the list independent, or is there some hidden dependency that means the second one can’t be done yet? The list won’t tell you, but the DAG will.

As said, the DAG is a partial order. Let’s be explicit about this ordering relation. Let Ts and Te be the start and end times of a task T. Then a dependency A→B is just a constraint Ae ≤ Bs.

We can introduce more constraints like this. A “subtask” relationship tT might be seen as two constraints: Tsts and te ≤ Te. “Deadlines” (if you use such a vague concept in your workplace) can be introduced as constraints Ted. Similarly, future events (“Tom said he will reply on Monday”) are constraints like monday ≤ Ts. Tasks that interfere with each other and so should not be done at the same time, but are not otherwise dependent on each other, can be modeled as a constraint Ae ≤ Bs Be ≤ As. More powerful constraint systems could assign tasks to people, prevent inappropriate people from being assigned to tasks, and prevent people from having too many tasks at any one time.

Depending on the power of this constraint system, and the size of the project, the system could be automatically solved. However, it would be simpler and probably less intimidating if the system only verified your solution: e.g. if you’ve placed one task before another, but this violates the constraints, the system will warn you, and you should then switch the tasks around.


Hopefully I’ve convinced you that this “To-do DAG” idea might be one worth pursuing. It is a modest modification to the way we currently manage task cards. It’s extremely simple. It manages to capture many facts that get lost in a list. It’s an obvious idea: everyone knows how to use arrows. It’s actually an old idea: Gantt charts are DAGs in disguise.

The only surprising thing is that I haven’t seen this implemented anywhere. If anyone is interested in helping me knock together a prototype over the New Year, get in touch.