CODEWITHSUNDEEP
graphtransitive-closure
Michael Kay
Michael Kay

Reputation: 163262

Transitive closure: should it include the null transition?

I'm trying to design a general purpose transitive closure implementation: find all the nodes in a graph reachable in one or more steps from a given start node.

Or should it be zero or more steps?

That is, should the result automatically include the start node?

I can see applications for both.

Is there a universally-accepted definition of the term "transitive closure" that tells me which of these is correct?

If I interpret it as one-or-more steps, then it's easy for the user to add the start node back in to the result if they want, whereas if I make it zero-or-more, there's no easy way for them to find out if there was a non-trivial path back to the origin. So I'm inclined to the one-or-more definition. Would that cause surprises?

Upvotes: 1

Views: 37

Answers (1)

Michael Kay
Michael Kay

Reputation: 163262

It appears that the term "transitive closure" refers to the set of nodes that can be reached in one or more steps. The set that can be reached in zero or more steps is called the "reflexive transitive closure".

Unfortunately most sites that explain this don't explain it in plain English, they rely on mathematical notation which you first have to master.

Please correct me if I have misunderstood or over-simplified!

Upvotes: 0

Related Questions