GNOME Bugzilla – Bug 139275
task predecessor loop check allows circles
Last modified: 2004-12-22 21:47:04 UTC
1. create four tasks (t1, t2, t3, t4) 2. indent t4 and t2 3. link t1 -> t3 4. link t4 -> t2 Thus a circular dependency is created, the graph ceases to be acyclic. Fiddling with tasks (adding some more tasks, linking them etc.) grows t1 by a couple of days each time, since the scheduling algorithm cannot handle a non-DAG. The problem is that the check doesn't include parents, only the tasks and their children. To fix this bug, one should fix mrp_task_manager_check_predecessor and related functions in libplanner/mrp-task-manager.c. #136044 may be related to this one. http://bugzilla.gnome.org/show_bug.cgi?id=136044
It actually tries to check for parents, but the checking code is broken and also very very inefficient. We need to rewrite it at some point.
I see that there is a check to see if one of the tasks is the parent of the other or not. But that's not enough. Every ancestor of both tasks should be checked against the whole subtree of the other task. I think something like the following should be done: Create a set consisting of the task, its children, its ancestors, their predecessors, their predecessors' predecessors and so on. Do this for both tasks in the new relation being checked. Check if the intersection of the two sets is not empty, in which case adding the relation creates a loop. What do you think about this? Or could we extend a standard DAG-check algorithm to take parent-child relationships into account?
That's what it already does, it adds parent->child relationships as well as depencencies to the graph. Although that code is very much half-baked, and I've been meaning to rework it for a long time but not really had the time. If you are interested in doing some work in this area, that would be great. I think I have a patch that starts to clean things up a bit, somewhere.
I'll try to find some time for this, but I can't promise anything... Does glib have an efficient way to take the intersection of two sets (and is there a set data type, or will I have to work with lists)?
Fixed in CVS.