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.

So if all tasks do not present in memory, then where do they reside? in a database? what is the db scheme? — Alexei Kaigorodov, Feb 12 '14 at 16:50
I liked following answer to similar question: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph/261621#261621 — Alexei Kaigorodov, Feb 12 '14 at 16:54

score 0 · Accepted Answer · edited May 23 '17 at 12:13

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.

Ensure that a list of dependent tasks dont have cycles

1 Answers1