Timeline for Topological sort where some nodes can't come in between two other nodes
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 26, 2020 at 21:01 | history | edited | elbrunovsky | CC BY-SA 4.0 |
Add warning and fix edge typos
|
| Aug 26, 2020 at 21:00 | comment | added | elbrunovsky | Hmm, nice catch. It still feels though like it should not need much more work than than just generating a modified graph and running a topo sort on it... | |
| Aug 26, 2020 at 20:49 | comment | added | Bernardo Subercaseaux | I don't think this works. Imagine nodes are numbers 1,2,3, and you have no original edges but only restrictions NotBetween(1,2,3) and NotBetween(3,1,2). Then in your approach the resulting graph has a cycle $1 \to 2 \to 3 \to 1$. And yet $3,2,1$ is a valid sort. Perhaps you meant to add edges $v \to u$ and $w \to v$? But this would also fail, as your adding both edges, when the restriction is an or. | |
| Aug 26, 2020 at 20:39 | history | answered | elbrunovsky | CC BY-SA 4.0 |