0
$\begingroup$

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?

Figure: Graph

**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?

$\endgroup$
1
  • 1
    $\begingroup$ Yes. an ordering with respect to a given node. One thing to notice that v3 has the same partial order in respect to v1 and v2. But, v1 and v2 has different ordering among them. I don't care about the ordering between v1 and v2. I only looking for the three ordering in respect to my given node v3. $\endgroup$
    – skdr
    Oct 27 at 2:02

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.