How do I find all paths through a set of given nodes in a DAG?

Answer 1

Despite the fact that your graph is acyclic, the operations you cite remind me of similar aspects of control flow graph analysis. There is a rich set of algorithms based on dominance that may be applicable. For example, your third operation reminds me od computing dominance frontiers; I believe that algorithm would work directly if you temporarily introduce "entry" and "exit" nodes. The entry node connects the "given set of nodes" and the exit nodes connects the sinks.

Also see Robert Tarjan's basic algorithms.

Answer 2

It seems to me that its essentially the same operation for all 3 questions. You're always asking "Find all X below node(s) Y, where X is of type Z". All you need is a generic mechanism for 'locate all nodes below node', (solves Q3) and then you can filter the results for 'nodetype=sink' (solves Q1). For Q2, you have the starting-point (your node set) and your ending point (any sink below the starting point) so your solution set is all paths from starting node specified to the sink. So I would suggest that what you basically have a is a tree, and basic tree-traversal algorithms would be the way to go.

Answer 3

I have a very similar question with the graph given above (acyclic directed graph). I want to print out all the paths that begin from source nodes (green) and end at the sink nodes (blue). Could anybody suggest an easy and efficient way for doing this? Say suggest a data structure for storing the nodes and describe the algorithm for finding the paths? Thanks a lot in advance.