# How do I find depth and height of all nodes in a bounded semilattice?

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?

• 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?
– D.W.
Commented Dec 11, 2017 at 4:44
• 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. Commented Dec 11, 2017 at 4:53