Od niejakiego czasu zaprzata mnie nastepujacy problem:

Dany jest skierowany graf acykliczny. Jak wiadomo, taki graf mozna
posortowac topologicznie. Takich porzadkow topologicznych jest
olbrzymia ilosc.

I teraz problem:

1. W praktycznych zadaniach ten graf moze byc bardzo duzy - setki
tysiecy wezlow
2. Graf nie musi byc spojny
3. Dane jest uporzadkowanie topologiczne, jedno z mozliwych
4. Chce sie zmienic polozenie N wezlow w tym porzadku, gdzie N jest
nieduze (kilka). Wezly sa wybrane przypadkowo

Pytanie:

1. Czy ta zmiana polozenia N wezlow narusza uporzadkowanie
topologiczne, to znaczy czy po przestawieniu otrzymamy znow porzadek
topologiczny czy nie
2. Takie sprawdzenie musi byc EXTREMALNIE wydajne, bo powtarzane jest
miliony razy, a program musi sie wykonywac bardzo szybko.

Oczywiscie, "brute force" jest trywialne. Ale "nie brute force"
niekoniecznie jest trywialne. Tyle ze "brute force" strasznie dlugo
sie wykonuje, nawet przy maksymalnej optymalizacji kodu

Rzecz potrzebna w pewnych algorytmach "constraint programming"
zwiazanymi z planowaniem kalendarzowym i routingiem. Dopuszczalny jest
"preprocessing" grafu w celu utworzenia struktur danych
przyspieszajacych proces. Pamiec nie jest ograniczeniem.

Jak ktos nie ma nad czym myslec, to proponuje nad tym

A.L.