Incremental Detection of Dominants in DAG Groups

Question

Suppose we have a single-source DAG. I would like to find the nodes of n , so that any full path from the source goes through n (i.e. n dominates all receivers). In other words: if we removed all succesors from n , then all paths would end in n . The problem is that the nodes are phased marked as deleted in the DAG. Since nodes are marked as remote, other nodes may begin to satisfy the above property. How can I effectively detect this when this happens?

Bonus points if a data structure can do this with multiple sources in a more efficient way than running an algorithm for one source separately for each source.

Answer 1

Topologically sort this DAG to set some order for your nodes. For each node, its value will be the number of outgoing edges from all previous nodes minus the number of incoming edges for all previous nodes and the current node. The value for the "dominator" node is always zero.

After some nodes are marked as “deleted”, put its predecessors and successors in the priority queue. The priority is determined by the topological sort order. Update the values ​​for all nodes after the “deleted” node (add the number of incoming nodes and subtract the number of outgoing nodes for this node). At the same time (in the same order), the decrement value for each node is between the predecessor node in the priority queue and the “remote” node and the increment value for each node, starting from the successor node in the priority queue. Stop when some node value is reduced to zero. This is the new "dominant" node. If you need all the "dominant" nodes, continue to the end of the graph.

 delete(delNode): for each predecessor in delNode.predecessors: queue.add(predecessor) for each successor in delNode.successors: queue.add(successor) for each node in DAG: if queue.top.priority == node.priority > delNode.priority: ++accumulator node.value += accumulator if node.value == 0: dominatorDetected(node) if node.priority == delNode.priority: accumulator += (delNode.predecessors.size - delNode.successors.size) node.value = -1 if queue.top.priority == node.priority: queue.pop() if node.priority < delNode.priority: --accumulator if queue.empty: stop 

For the case with multiple sources, you can use the same algorithm, but keep a list of "values" for each node, one for each source. The complexity of the O(Nodes * Sources) algorithm is the same as for an independent search on each of the sources. But using vectorization, a program can be more efficient. "values" can be processed in parallel with SIMD instructions. Modern compilers can perform automatic vectorization to handle this.