Determining the "root" of a tree/graph

I need to create a directed acyclic graph of an organization which of course amounts to a tree.

What approach could I use to determine the “apex node” to which all others descend from (and also the Nth layer under it)?

For the first the only idea I have is to iterate through all vertices and stop when I find a node with no incoming edges, but maybe there’s a cleverer way?

Thank you very much.

If you have a graph which you know to be a directed out-tree, then you just need to find the single vertex with zero in-degree. There is absolutely no need to traverse vertices.

1 Like

Thank you this makes a lot of sense :slight_smile:
Unfortunately with my specific data there’s an anomaly that prevents this simple approach :frowning:

The data I have are records that describe a person (including its unique id) and their manager_id but only for a single country.

The country manager (and also approx 0,1% of these country records) have a manager_id that is out of country for which there’s no detailed/full record. Those ids only exist as a manager_id and therefore I am not creating a vertex for them.

What I was thinking is to create a fictitious “abroad” vertex and when I find a record that reports out of country associate the people to this node.

So the only node with zero in-degree will be this “abroad” vertex to which I will have a 0.1% of vertexes referring to of which ONE of them will then have 99.9% of the other vertexes reporting to it. THAT will be the country manager :slight_smile:

Not sure how to algorithmically identify it automatically.