Is there any Algorithm to check a vertex\node's partial order in terms of other vertices\nodes for a given graph?

Question

For the given figure, let's consider vertex v3. For v3, v0 has a higher partial order,v1 & v2 has the same partial order, and v4 & v5 have lower order than v3, e.g., higher: {v0}, same: {v1,v2} and lower: {v4, v5}. I am looking for an algorithm to recognize these three sets. Is there any proven algorithm to find them?

**Note: ** I have looked into topological sorting. However, it is hard to recognize these three set from topological sorting. This graph can have the following topological sorting:

v0 v1 v2 v3 v4 v5

v0 v1 v3 v2 v4 v5

v0 v1 v3 v4 v2 v5

v0 v3 v1 v2 v4 v5

v0 v3 v1 v4 v2 v5

Looking at all those topological sorts, you can see recognizing if v2 belongs to the same order as v3 or lower order than v3 would be tough, as v2 can appear both before and after v3.

I looked into DFS, BFS, and Kahn's algorithm. But I couldn't figure out if I could manipulate one of them to get my desired result. It seems like if I get a sort like the first one(v0 v1 v2 v3 v4 v5 ), I can get my desired set. However, given a random graph structure, I wonder can I generate a specific partial ordering to recognize those three sets?

Answer 1

I am assuming that you're graph $G$ is a DAG. Let $v$ be your reference vertex. Perform a DFS starting at $v$ to find all vertices reachable from $v$. These vertices must have a lower order from $v$. Then reverse the graph, and perform another DFS in this reversed graph starting at $v$. All vertices reachable from $v$ must have a higher order. Finally, all vertices that was not reached in both DFS must have the same order as $v$.