Topological sort, but with some fixed values

Question

I'm working on a problem similar to topological sorting, but with an additional constraint: I want to order the nodes by assigning a positive integer index to each, and, in additional to the relative constraints the graph defines, some nodes have a predefined index assigned.

That is, the input is a set of nodes $V$, a set of relative constraints each of the form $X_a < X_b; a \in V, b \in V$, and a set of absolute constraints $X_a = i, i \in \mathbb{Z}^+$.

The output is a map $X$ such that $X_a \in \mathbb{Z}^+$ for each $a \in V$, and all relative and absolute constraints specified in the input are satisfied. The values $X_a$ need not be unique; it's acceptable that $X_a = X_b$ given $a \neq b$, so long as all the specified constraints are satisfied. If no such $X$ exists, the output is an error value.

Not sure what to search for; does such an algorithm exist? If not, is there a good way to map this problem to a known problem? I'm working on it, too, but just wanted to see if this set off any lightbulbs for anyone in the community before I go too deep :)

(In case this helps, I'm working on a solver to manage the z-indexes of my web application.)

Answer 1

There's a natural algorithm:

1. Arbitrarily pick any vertex all of whose predecessors have already been labelled; call it $v$.

2. If $v$ is constrained to have a specific index, label $v$ with that integer. Otherwise, pick the smallest integer greater than all of the labels on the predecessors of $v$, and label $v$ with that integer.

3. If at least one vertex remains unabelled, go to step 1.

This is an adaptation of Kahn's algorithm for topological sorting, and it can be implemented so it runs in linear time.

The crucial thing that makes your problem feasible is that the labels don't need to be unique. If the labels need to be unique, I suspect the problem becomes much harder; at least, this algorithm doesn't work, and a generalization of the problem becomes NP-hard.