# Topological sort, but with some fixed values

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

• An ad hoc adaptation of the classical algorithm shouldn't be too difficult. Have you given it a shot? Apr 4, 2017 at 21:12
• If you restrain the integer labels to $1, \ldots, |V|$, then there must be paths between each of the fixed-label vertices and all other vertices, see cs.stackexchange.com/questions/71463/…. This property may be interesting to you, in thinking about this problem. Jun 28, 2018 at 13:00

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.