One of the things I'm trying to learn about these days (along with genetic algorithms and I forget what else) is dependency graphs. I'm surprised at how little I've found about this online, particularly given that popular things like make and Puppet make heavy use of them.
For instance, the directed graph below represents a set of tasks. Tasks c and d depend upon the completion of task a, and task f depends upon both c and d having completed:
However, task h depends upon e and a, and e also depends upon a. For purposes of simplification, edge ah is superfluous, since e's completion means a is already complete.
So what I'm trying to figure out right now is how to detect such superfluities in order to delete them from the graph. Unfortunately, I don't [yet] even know what such an operation is called, and the book I'm reading on graph theory is really tough going.
This will probably occupy me for a little while, anyway.
