I'm writing a program where I have a bounded semilattice (it has a root element at the top, all edges point downwards, and a node may have multiple parents). I need to precompute each node's depth (the max number of edges from the root node) and height (the max number of edges to any leaf). I have a naive implementation for just the heights where every node is compared to all it's descendants, so probably O(n^2). What is a faster algorithm that computes both height and depth?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ How is the semilattice represented? As a graph in adjacency list format? Are there any basic operations that are available (e.g., join/meet)? Have you tried applying topological sorting and then visiting nodes in topologically sorted order? $\endgroup$– D.W. ♦Commented Dec 11, 2017 at 4:44
-
$\begingroup$ It's represented as vertices with pointers to other vertices, only in the downwards direction. The only operation is to traverse an edge. I didn't think of topological sorting so I'll look into that. $\endgroup$– BrentCommented Dec 11, 2017 at 4:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
If you do a topological sort and then traverse the nodes in reverse topologically sorted order, you can annotate each node with its height in linear time. Similarly, you can annotate each node with its depth in linear time by traversing in topologically sorted order. This achieves linear running time, which is significantly faster than the quadratic time approach you mention.
-
$\begingroup$ As I'm iterating over each node, how do I know what value to assign it? $\endgroup$– BrentCommented Dec 14, 2017 at 1:07
-
1$\begingroup$ @Brent, For height, its height is 1 + the max of the heights of its successors (children). For depth, you look at the predecessors. $\endgroup$– D.W. ♦Commented Dec 14, 2017 at 1:12
-
$\begingroup$ Wouldn't that put it back in O(n^2)? $\endgroup$– BrentCommented Dec 23, 2017 at 14:30
-
-
$\begingroup$ Awesome. Would you offer a guess as to what the asymptotic performance is? $\endgroup$– BrentCommented Dec 24, 2017 at 17:29