How to traverse "linked list" like structure with parallel nodes

Question

I am working on a signal processing project that allows for parallel processing on data streams as well as inputs and outputs to and from multiple endpoints.

The signal chain is broken down into "endpoints" and "nodes".

Endpoints can be declared either input or output, and nodes are anything in between.

The two types of objects can be declared to depend upon each other, all types can hold dependencies except for endpoints declared as inputs.

An example of a signal chain could be:

input1 --  + --  node1 --  + -- node3 --output1
input2 -- /    \ node2 -- /          \--output2

A textual version:

• output1 depends on node 3
• output2 depends on node 3
• node3 depends on nodes 1 & 2 (summed)
• nodes 1&2 depend on inputs 1 & 2 (summed)

The nodes/endpoints currently hold a pointer to the object(s) they depends on.

I am trying to develop an algorithm that can trace through the graph starting from the outputs and determine the order that data must be processed accounting for data that can be processed in parallel.

Example result:

1. read input1 & input2 (parallel)
2. sum inputs
3. run processes on nodes 1 & 2 (parallel)
4. sum results of nodes 1 & 2
5. run processes on node 3
6. write outputs 1 & 2 (parallel)

I am not sure where to start when developing an algorithm to parse this, or if the manor that I have connected the nodes is sufficient to do this. It is currently set up akin to a singly linked list where each object knows the previous object(s)

I am working in C++.

Answer 1

This is a simple directed acyclic graph, which means that evaluating the nodes shouldn't be terribly complicated. The algorithms mentioned in the "Topological sorting and recognition" section of the Wikipedia article allow you to break the graph evaluation into a linear sequence of steps. Also see this answer.