How would you check if a part of the graph is a tree


I have a directed graph that starting from a seed I know it is a tree up to certain level, but at some point it becomes a graph. I’m trying to write a query that tells me which nodes break the “tree-ness” property, ie. a node that has more than one incoming edge, but I don’t know how to write such query.
Could you help me on that?

Best regards.

You could check out a BFS or DFS style query, and then have your stopping condition in the traversal as something like IF node.outdegree() > 2 THEN PRINT node

I was thinking about that but I miss the node.indegree() function. I understand that node.outdegree()reports how many leafs a given node has, but in order to check if I’m in a tree I’m interested in checking if incoming edges are exactly 1 and I don’t know how to express that query.

Do you have reverse edges? If you have one, then you can do node.outdegree(“REVERSE_EDGE_TYPE”)

1 Like