Ensure that a list of dependent tasks dont have cycles

Question

I want to make a CRUD app (SQL or document DB) for tasks: create them one at a time. Tasks may depend on one or more other tasks. Ideally this must be a directed acyclic graph.

How do I enforce that, when I create a new task (or modify the 'depends on'), there are no cycles? Its slow to load all the tasks to memory to traverse for cycles. Is there a better way to enforce them?

A simple way is to ensure that a task can depend only on previously created tasks. But this breaks in case we create task A, then we create task B which A depends on.

Answer 1

In the worst case, you'll definitely need to work with the whole graph - consider when there's a path from the new task through all the other tasks back to itself - you wouldn't be able to know this without processing the whole graph.

If you're primarily adding one task at a time, or modifying one relationship at a time, and the graph is fairly sparse (there aren't too many edges), one solution I can think of is to do a depth-first-search from the new task (perhaps in reverse, if that would have a smaller branching factor). If you get back to that task, you know there's a cycle. This would presumably result in only loading the required vertices one by one, which could be either a lot slower, or a lot faster, depending on how the data is stored (thus how long a single load would take), how many vertices need to be loaded in relation to the total number of vertices, and perhaps a few other factors.

If you make many changes at the same time, you're probably better off running a complete cycle detection algorithm on the graph.