Finding the Reachability Count for all vertices of a DAG

I am trying to find a fast algorithm with modest space requirements to solve the following problem.

For each vertex of a DAG find the sum of its in-degree and out-degree in the DAG's transitive closure .

Given this DAG:

I expect the following result:

Vertex #   Reacability Count  Reachable Vertices in closure
   7             5            (11, 8, 2, 9, 10)
   5             4            (11, 2, 9, 10)
   3             3            (8, 9, 10)
  11             5            (7, 5, 2, 9, 10)
   8             3            (7, 3, 9)
   2             3            (7, 5, 11)
   9             5            (7, 5, 11, 8, 3)
  10             4            (7, 5, 11, 3)

It seems to me that this should be possible without actually constructing the transitive closure. I haven't been able to find anything on the net that exactly describes this problem. I've got some ideas about how to do this, but I wanted to see what the SO crowd could come up with.

---

For each node, use BFS or DFS to find the out-reachability.

Do it again for the reversed direction to find the in-reachability.

Time complexity: O(MN + N2), space complexity: O(M + N).

---

OMG IT'S WRONG! SORRY!

I'll leave this up until a good alternative is available. CW-ed so feel free to discuss and expand on this if possible.

---

Use dynamic programming.

for each vertex V
   count[V] = UNKNOWN
for each vertex V
   getCount(V)


function getCount(V)
   if count[V] == UNKNOWN
      count[V] = 0
      for each edge (V, V2)
        count[V] += getCount(V2) + 1          
   return count[V]

This is O(|V|+|E|) with adjacency list. It counts only the out-degree in the transitive closure. To count the in-degrees, call getCount with edges reversed. To get the sum, add up the counts from both calls.

---

To see why this is O(|V|+|E|) , consider this: each vertex V will be visited exactly 1 + in-degree(V) times: once directly on V , and once for every edge (*, V) . On subsequent visits, getCount(V) , simply returns the memoized count[V] in O(1) .

Another way to look at it is to count how many times each edge will be followed along: exactly once.

---

For an exact answer, I think it's going to be hard to beat KennyTM's algorithm. If you're willing to settle for an approximation, then the tank counting method ( http://www.guardian.co.uk/world/2006/jul/20/secondworldwar.tvandradio ) may help.

Assign each vertex a random number in the range [0, 1). Use a linear-time dynamic program like polygenelubricants's to compute for each vertex v the minimum number minreach(v) reachable from v. Then estimate the number of vertices reachable from v as 1/minreach(v) - 1. For better accuracy, repeat several times and take a median of means at each vertex.

链接地址: http://www.djcxy.com/p/45146.html

上一篇: TFSBuild / MSBuild和项目参考与文件参考

下一篇: 查找DAG所有顶点的可达性计数