nchn27's blog

Topological Sort with Fixed Indices
By nchn27, history, 5 years ago, In English

The goal is to create a topological sorting except some vertices need to have specific indices in the final ordering. Is there a nice, fast way to do this?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nchn27 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Let's start with three pieces of pre-processing.

  1. Precompute a comparator so that given two vertices $$$u, v$$$, it tells us whether there exists a path $$$u\rightarrow v$$$, $$$v\rightarrow u$$$, or neither (basically, tells us what order they need to be in, or if it doesn't matter).

  2. Construct any topological sort of the vertices.

  3. Sort the $$$n$$$ special vertices by index. We can place them first, and then we have $$$n+1$$$ buckets (gaps between special vertices) in our final ordering that we can place the rest of the vertices in. For each non-special vertex, find the first and last bucket it could be placed in by comparing it to the special vertices. (If it can be placed in either of two buckets, it can also be placed in any bucket in between, assuming the graph is acyclic.)

Now, for each non-special vertex we have an interval of buckets it can be placed in, so we've reduced this to a classic problem of scheduling jobs/resources with intervals as our constraints, which we can solve by sorting the non-special vertices by their rightmost bucket and iterating through them to place them all into buckets. Within a bucket, we make sure they are sorted according to our topological sort from before.

This gives us a valid topological sort with some vertices in the desired spots, and the runtime is (runtime of step 1) + (runtime of step 2 / topological sort) + (runtime of step 3) + O(V log V) for the final matching algorithm.

Btw, this assume such an ordering exists, but I think you can simply modify the steps to check for contradictions and return early along the way.

I'm not sure of the best runtimes for steps 1 and 3, but they can all be done in $$$O(V^2)$$$.

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

By the way, what's the problem/application of this? Do you have a link?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I was reading a problem and seeing if i could make it harder and if it would be interesting at a higher level -- this is a problem where instead of a DAG + fixed indices, the ordering is just a list + fixed indices:

    Easy Problem Link

    [So no, I don't have a link to what I came up with :(]

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

I think it can be solved in $$$O(nlog(n))$$$

Assuming there are no cycles, you can do DP on DAG to find for each node, the lowest special node that can be reached by this node. By lowest I mean the one that should come first in the final ordering. Let's call that $$$low[v]$$$.

Now, we can do something similar to the BFS topological sort but instead of a queue we have a set of nodes sorted by $$$low[v]$$$. If we are currently at the index of a special vertex, we check if it's in the set. Otherwise, we choose the node with minimum $$$low[v]$$$.

I'm not 100% sure it works, but I can't see how we would need to remove a node with a high value of $$$low[v]$$$ before a node with a low value of $$$low[v]$$$ because:

1) If two nodes have the same value of $$$low[v]$$$, it shouldn't matter which one we remove first since they both have to be removed before the next special node anyways.

2) If $$$low[v]<low[u]$$$ and an ordering where node $$$u$$$ comes before node $$$v$$$ exists, then we were able to remove $$$u$$$ and all of its dependencies and $$$v$$$ and all of it's dependencies before removing $$$low[v]$$$. In this case we should be able to remove $$$v$$$ and all of its dependencies before removing $$$u$$$ and all of its dependencies before removing $$$low[v]$$$ (which should come before $$$low[u]$$$ anyways) so the ordering would still be valid.

Please correct me if I'm wrong.

→ Reply