I am building a dependency based scheduler where my tasks/nodes form a directed acyclic graph. I have the following constraints and am trying to decide on the most appropriate algorithm:
- New tasks can be added (with or without dependencies) at any time
- Some tasks can run in parallel
Two algorithms are mentioned repeatedly with regards to topological sorting; depth first search and Kahn's algorithm.
- What are the pro's and con's of these two algorithms?
- Is one algorithm objectively better for my scenario?
- Is there an alternate that better fits my scenario?
I have one further question about vocabulary. Given dependencies such as:
c->b
b->a
e->d
Is this considered to be a single directed acyclic graph, 2 acyclic graphs (since e and d are not dependent on the other tasks) or an acyclic graph with sub acyclic graphs?