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.
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:
- Go through and mark $h=0$ for vertices with no incoming edges.
- For each vertex with $h=0$, follow the outgoing edges, updating the height of each encountered vertex if it's previous height is smaller.
- Go through and mark $h=0$ for vertices with no incoming edges, and mark these as the frontier.
- 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.
- Repeat 2 until there is nothing beyond the frontier.
- Is there a name for this problem, and a well known fastest solution?
- I tend to think simply walking up from all the $h=0$ vertices is the fastest solution. Am I right?