I have a large directed, acylic graph (DAG) from which I would like to efficiently draw a sample node according to the following criteria:
- I specify a fixed node A that must never be sampled
- Nodes that directly or indirectly refer to A are never sampled
- All other nodes are sampled with equal probability
Nodes are stored as objects with pointers to the other nodes that they refer to, the entire graph can be reached from a single root node that refers to everything else directly or indirectly.
Is there a good algorithm to do this? Ideally without requiring large amounts of additional memory since the DAG is large!