8
$\begingroup$

I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges to traverse in reverse to reach a vertex of height 0. enter image description here

I also know that the average degree of a node is a small constant, say 2 or so. To find the height of all vertices, I can think of two algorithms:

Walking Algorithm

  1. Go through and mark $h=0$ for vertices with no incoming edges.
  2. For each vertex with $h=0$, follow the outgoing edges, updating the height of each encountered vertex if it's previous height is smaller.

Frontier Algorithm

  1. Go through and mark $h=0$ for vertices with no incoming edges, and mark these as the frontier.
  2. For every frontier vertex, see if it's parent has children at or below the frontier, If it does, mark the parent as having $1$ plus the largest height among its children. Mark the parent as being on the frontier.
  3. Repeat 2 until there is nothing beyond the frontier.

My questions:

  1. Is there a name for this problem, and a well known fastest solution?
  2. I tend to think simply walking up from all the $h=0$ vertices is the fastest solution. Am I right?
$\endgroup$

migrated from cstheory.stackexchange.com Oct 11 '12 at 19:44

This question came from our site for theoretical computer scientists and researchers in related fields.

7
$\begingroup$

First of all, it depends a bit how you can access your data to say which algorithms works best.

Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that

$$\text{height}(v)=\begin{cases} \left(\max_{u\text{ child of }v}\text{height}(u)\right)+1 & \text{if $u$ is not a leaf} \\ \hskip4ex 0 & \text{otherwise} \end{cases}. $$

So you can scan for all roots, and then determine the heights by divide an conquer. You will touch every vertex at most twice (scanning for the roots + traversing). In the approach that you have suggested you might have to touch some vertices many times.

Btw, since you have a forest, you have less edges than vertices, so you know that you have average degree less than two (and therefore you can test for roots in linear time).

$\endgroup$
  • $\begingroup$ +1; recursive solutions are often easier to analyze. It also depends on whether you already have child pointers or not, and whether you want a loop-based or recursion-based solution. $\endgroup$ – Joe Oct 12 '12 at 19:01
  • $\begingroup$ I like the analysis! Can someone help the newbies pointing out how to convert this to the iterative form too? $\endgroup$ – highBandWidth Oct 12 '12 at 20:56
4
$\begingroup$

I don't know if this problem has an official name or not. Your title sums it up well enough. Walking up from the 0 height nodes will be fast, provided you take care to avoid duplicate work. Suppose you have a node with many children and a long path above this node to the root. Suppose also that the heights of each of the children are different. Each child may update the height of the node in question. That's ok. But you should avoid also updating the long path above that node until all its children have reported their heights.

The resulting algorithm will run in linear time, and the pseudo-code would look something like this:

initialize a queue Q
initialize all nodes to have a property: maxChildHeight = 0
initialize all nodes of in-degree 0 to have height = 0
Add all nodes of in-degree 0 to Q
while Q is non-empty:
  pop a node v from the front of Q
  subtract 1 from the indegree of the parent of v
  set parent.maxChildHeight = max(height(v), parent.maxChildHeight)
  if the indegree of the parent is 0:
      parent.height =  maxChildHeight + 1
      add the parent to Q
$\endgroup$
3
$\begingroup$

A problem so similar it might be of interest is "Parallel Prefix on Rooted Directed Trees." The algorithm finds the number of edges to the root from each node. So the roots ends up with a the value 0, while e.g. the bottom right node would end up with a value of two.

Note that the algorithm below solves the more general problem for weighted edges, but you can just initialize the W(i) to 1 for all i. And each node i's successor is given by P(i)=j.

for 1 ≤ i ≤ n do in parallel
    S(i) = P(i)
    while S(i) != S(S(i)) do
        W(i) = W(i) + W(S(i))
        S(i) = S(S(i))

The image below illustrates the "halving" of the path lengths and makes the logarithmic running time easy to understand. It does not show the node heights computed though.

enter image description here

(from "Introduction to Parallel Algorithms" by Joseph Jaja).

Using multiple processors, it is solvable in O(lg n) time, but uses O(n lg n) operations. There is a hack to get it down to linear work, but it is slightly involved.

$\endgroup$
  • $\begingroup$ Thanks! what does S(i) represent? $\endgroup$ – highBandWidth Oct 12 '12 at 20:54
  • $\begingroup$ The successor node. So in iteration one of the right tree, S(9) = 10, S(10)=11, S(11)=12, S(12)=13 and W(9) = 1, W(10)=1, W(11)=1, W(12)=1. In iteration two, S(9) = 11, S(10)=12, S(11)=13, S(12)=13 and W(9) = 2, W(10)=2, W(11)=2, W(12)=1. In iteration three, S(9) = 13, S(10)=13, S(11)=13, S(12)=13 and W(9) = 2 + 2, W(10)=2+1, W(11)=2, W(12)=1. $\endgroup$ – The Unfun Cat Oct 12 '12 at 21:13
  • $\begingroup$ You must imagine all the S(i) and W(i) are updated at the same time when you try to work out the details. This might be obscure, but I wanted to post it because it is a classic parallel problem and very close to what you described. $\endgroup$ – The Unfun Cat Oct 12 '12 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.