W dniu 2012-02-23 00:24, n...@m...invalid pisze:
> W dniu 22.02.2012 r. 20:21, Piotr Chamera pisze:
>> W dniu 2012-02-22 19:03, Piotr Chamera pisze:
>>> W dniu 2012-02-21 22:52, A.L. pisze:
>>>> 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.
>>>
>>> 1. Każdy węzeł grafu reprezentujemy tak, że znane są listy jego
>>> poprzedników i następników w grafie.
>>>
>>> 2. Znakujemy węzły rosnąco liczbami wymiernymi wg kolejności w
>>> wyjściowym porządku (to można zrobić raz dla wielu kolejnych
>>> przekształceń, może być potrzeba dokładnej arytmetyki).
> 1: 1/2; 2: 2/3; 3: 3/4; ... ? Co to daje, mogę prosić o objaśnienie?

Poniżej przedstawiam mój tok myślenia, może się gdzieś pomyliłem, jeśli
tak, to proszę o wskazanie błędów.


Załóżmy tak graf reprezentowany jako lista węzłów,
gdzie węzeł to (,,nazwa węzła" (lista następników) (lista poprzedników))

przykładowy graf: ((a (b c) ())
(b (c d) (a))
(c () (a b))
(d () (b)
jest w tej chwili posortowany topologicznie w kolejności a b c d.

numerujemy go liczbami naturalnymi (dla uproszczenia)
(a 1) (b 2) (c 3) (d 4)
zauważmy, że wszystkie poprzedniki dowolnego węzła mają znakowanie
mniejsze od niego, a następniki większe, czyli mamy prosty sposób
sprawdzenia, czy dowolny inny węzeł jest poprzednikiem czy następnikiem
danego (lub jest w części grafu niezależnej od danego węzła).

W prostym przypadku pojedynczego węzła: jeśli przeniesiemy węzeł w_x
wstecz przed w_y i taka zmiana zachowuje sortowanie, to nadal wszystkie
poprzedniki w_x powinny mieć znakowanie mniejsze od niego, bo jeśli nie
to w nowym porządku istnieje krawędź z wierzchołka, który leży teraz
pomiędzy w_x a w_y do w_x (czyli wstecz, wbrew porządkowi).

Przy przenoszeniu pojedynczego węzła w przód należy sprawdzić jego
następniki, czy nie mają teraz numeracji mniejszej od niego.

Wychodzi mi, że w ogólnym przypadku przenoszenia N węzłów trzeba
(1) sprawdzić następniki i poprzedniki wszystkich przenoszonych węzłów
i (2) czy same te węzły nadal są w porządku topologicznym (choć to może
wynikać z (1) - nie przemyślałem tego).


Przykłady:

1) po przeniesieniu węzła c przed b mamy
(a 1) (c 3/2) (b 2) (d 4)
w zbiorze poprzedników (c 3/2) mamy (a 1) i (b 2) co wskazuje na
istnienie krawędzi z b do c, która w nowym porządku wskazuje wstecz.
Przy przenoszeniu wstecz w zbiorze następników nic się nie zmieni.

2) po przeniesieniu węzła c poza d mamy
(a 1) (b 2) (d 4) (c 5)
w zbiorze następników (c 5) był pusty, więc nic się nie mogło zepsuć.
Przy przenoszeniu wprzód w zbiorze poprzedników nic się nie zmieni.

3) po przeniesieniu węzła a poza d mamy
(b 2) (c 3) (d 4) (a 10)
w zbiorze następników (a 10) mamy (b 2) i (c 3) co wskazuje na istnienie
teraz 2 krawędzi wstecz (czyli znów zepsuliśmy porządek).
Przy przenoszeniu wprzód w zbiorze poprzedników nic się nie zmieni.










>
>>> 3. Typujemy N wierzchołków do zmiany miejsca.
>>>
>>> 4. Dla każdego z N wierzchołków wyliczamy nowe znakowanie jako liczbę
>>> pośrednią między poprzednikiem i następnikiem w docelowym porządku (np
>>> średnia arytmetyczna ze znakowań poprzednika i następnika w porządku
>>> docelowym).
>>>
>>> 5. Dla każdego z N wierzchołków bierzemy listę jego poprzedników w
>>> grafie.
>>>
>>> 5a Dla każdego poprzednika z powyższej listy sprawdzamy, czy na liście
>>> jego następników nie ma wierzchołka ze znakowaniem mniejszym niż jego
>>> własne.
>>
>> Mam problem z 5 punktem, to czy powinniśmy sprawdzić poprzedniki czy
>> następniki zależy od kierunku przesunięcia węzła w grafie.
>> Jeśli dany węzeł wędruje ,,do tyłu" względem wyjściowego porządku trzeba
>> sprawdzić następniki jego poprzedników. Jeśli ,,do przodu", to należy
>> porównać poprzedniki jego następników.
>>
>> Ale być może bredzę - dziś już zmęczony jestem... może jest jeszcze
>> więcej możliwych przypadków...
>>
>>> Jeśli to zadziała, to w najgorszym wypadku mamy do sprawdzenia N x m x o
>>> porównań, gdzie m to max liczba poprzedników, a o max liczba następników
>>> węzła w zbiorze węzłów N.
>>>
>>> Rysowałem sobie to na kartce, mogłem jakiś przypadek pominąć lub źle
>>> zrozumieć zadanie...
>