3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ An ad hoc adaptation of the classical algorithm shouldn't be too difficult. Have you given it a shot? $\endgroup$ Apr 4, 2017 at 21:12
  • $\begingroup$ 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. $\endgroup$ Jun 28, 2018 at 13:00

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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