Suppose there are
These nodes are connected by
m unique directed edges. Sets of these edges may form cycles.
Each node has an associated quantity.
r of these nodes are selected as root nodes.
a can be said to reach node
- there exists a directed path from
The goal: For each root node, find the sum of the quantities of all nodes which it can reach and no other root can reach.
This includes the root itself. For example, if root 2 can reach root 1, then root 1's associated quantity will be counted to neither root 1 nor root 2's sum. On the other hand, if no root other than root 1 can reach root 1, then root 1's associated quantity will be counted toward root 1's sum.
I'm trying to puzzle out how to do this with the minimum number of calculations, but I think I need to brush up on my graph theory. This problem is quite a lot easier on a tree, but I've found dealing with cycles makes things much more complicated. I'm having a tough time finding a solution which doesn't incessantly re-traverse the graph.