# Multithreaded algorithm to traverse DAG

I have a DAG of tasks designed as:

DAG {
}
Node {
List<Node> Parents;
List<Node> Children;
}


This DAG is assumed to never change over time.

Now, I want to create an algorithm that, when given a NodeAddress, will execute the corresponding task, and all subsequent tasks in the graph. But the catch is that while this is running, I also want to allow another thread to be able to add another NodeAddress to the algorithm, and the algorithm will execute all the tasks and subchildren tasks of that node. If some tasks are children of both nodes, they should not be executed twice.

Does anyone know of a good algorithm to do this? The graph may be fairly big, so I want to use a memory size that is O(n) (n being the number of nodes in the graph). and then the faster the better...

Example:

Task A --> Task B --,


Scneario 1:

The caller asks: Execute('A'):

The algorithm executes A, then B, then D.

Scenario 2:

The caller asks: Execute('A'):

The algorithm executes A, then B, then while B is executing, the caller asks: Execute('C').

The algorithm executes C (while B is still executing), waits for both to finish, and then executes D.