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.

do góry

Szkic:

Wstępne przetwarzanie: liczymy domknięcie przechodnie wejściowego grafu G, odwracamy
w nim kierunki wszystkich krawędzi i otrzymany graf (oznaczmy go G') zapamiętujemy
jako listę zbiorów incydencji.

Algorytm: rozbijamy naszą zmianę porządku topologicznego na złożenie inwersji, czyli
zamian miejscami dwóch elementów porządku. Intuicyjnie, jeśli zmiana była niewielka,
to i inwersji będzie mało. Teraz dla każdej inwersji elementu i-tego z j-tym, i < j,
rozważamy zbiór wierzchołków {a_{i+1}, a_{i+2}, ..., a_{j-1}} i liczymy jego
teoriomnogościowe przecięcie ze zbiorem krawędzi wychodzącym w G' z wierzchołka a_j.
Jeśli któreś przecięcie wyjdzie niepuste, to psuje ono porządek topologiczny, w
przeciwnym wypadku otrzymana permutacja dalej jest porządkiem.

Wydaje mi się, że to działa, choć mogłem coś pochrzanić. Sprawdzenie poprawności i
szczegóły implementacyjne takie jak wybór reprezentacji zbiorów pozostawiam jako
ćwiczenie.

--D.

do góry

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"

Rozumiem, że brute force to przejście od naszych N przesuwanych
wierzchołków krawędziami w przód i w tył (ok, trzeba mieć
krawedzie wstaczne) i sprawdzenie, czy nie odwróciliśmy
kierunku w porządku.


> 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


Ciężko będzie szybciej:) Mam coś, co samo sprawdzenie robi
w O(N) + sprawdzenie czy w nasze N wierzchołkow jest ok,
ale potem i tak trzeba 'poprawić dane' we wszystkich
wierzchołkach z którymi styka się zbiór N. Więc
jeśli nie wpadne, jak ro zrobić 'leniwie' wychodzi
to samo co BF powyżej. (Trzymam listę krawędzi
posortowaną po pozycjach w porządku. Sprawdzenie
czy przesuniecie wierzchołka zachowuje porzadek
jest natychmiastowe, ale trzeba jeszcze rozpropagować
informacje o zmianie swojej pozycji).



pzdr
bartekltg

do góry

On Wed, 22 Feb 2012 13:20:15 +0100, bartekltg <b...@g...com>
wrote:

>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"
>
>Rozumiem, że brute force to przejście od naszych N przesuwanych
>wierzchołków krawędziami w przód i w tył (ok, trzeba mieć
>krawedzie wstaczne) i sprawdzenie, czy nie odwróciliśmy
>kierunku w porządku.
>
>
>> 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
>
>
>Ciężko będzie szybciej:) Mam coś, co samo sprawdzenie robi
>w O(N) + sprawdzenie czy w nasze N wierzchołkow jest ok,
>ale potem i tak trzeba 'poprawić dane' we wszystkich
>wierzchołkach z którymi styka się zbiór N. Więc
>jeśli nie wpadne, jak ro zrobić 'leniwie' wychodzi
>to samo co BF powyżej. (Trzymam listę krawędzi
>posortowaną po pozycjach w porządku. Sprawdzenie
>czy przesuniecie wierzchołka zachowuje porzadek
>jest natychmiastowe, ale trzeba jeszcze rozpropagować
>informacje o zmianie swojej pozycji).
>

BF to takie ze dla kazdego wezla oblicze sei "follower set" czyli
zbior wezlow ktore musa byc pozniej niz dany wezel, i "predecessor
set" ktory zawiera zbior wierzcholkow ktore musza byc wczesniej. Gdy
sie chce pzrestawic wezly, tzreba zprawdzic czy ktoryz z wezlow by nie
"wypadl" z follower set czy predecessor set. Co wymaga sprawdzenia
wszystkich wezlow.

Pytanei wiec, czy nei da sie testowac tylko niektorych wezlow, a
jezeli tak, to ktore?

A.L.

do góry

On Tue, 21 Feb 2012 18:48:01 -0800 (PST), Daniel Janus
<n...@g...com> wrote:

>Szkic:
>
>Wstępne przetwarzanie: liczymy domknięcie przechodnie wejściowego grafu G, odwracamy
w nim kierunki wszystkich krawędzi i otrzymany graf (oznaczmy go G') zapamiętujemy
jako listę zbiorów incydencji.
>
>Algorytm: rozbijamy naszą zmianę porządku topologicznego na złożenie inwersji, czyli
zamian miejscami dwóch elementów porządku. Intuicyjnie, jeśli zmiana była niewielka,
to i inwersji będzie mało. Teraz dla każdej inwersji elementu i-tego z j-tym, i < j,
rozważamy zbiór wierzchołków {a_{i+1}, a_{i+2}, ..., a_{j-1}} i liczymy jego
teoriomnogościowe przecięcie ze zbiorem krawędzi wychodzącym w G' z wierzchołka a_j.
Jeśli któreś przecięcie wyjdzie niepuste, to psuje ono porządek topologiczny, w
przeciwnym wypadku otrzymana permutacja dalej jest porządkiem.
>
>Wydaje mi się, że to działa, choć mogłem coś pochrzanić. Sprawdzenie poprawności i
szczegóły implementacyjne takie jak wybór reprezentacji zbiorów pozostawiam jako
ćwiczenie.
>

Tego sie nei da zrobic "parami", bo para moze naruszac porzadek, ale
dodanie drugiej pary powoduje ze czworka juz nie narusza porzadku. Nie
da sie robic sekwencyjnie parami. To byl pierwszy blad ktory
popelnilem na samym poczatku.

Neijaki Ruskey pokazal ze nei da sie wygenerowac wszystkich porzadkow
przez transpozycje

http://webhome.cs.uvic.ca/~ruskey/Publications/

Frank Ruskey, Generating Linear Extensions of Posets by
Transpositions, Journal of Combinatorial Theory (B), 54 (1992) 77-101.
G. Pruesse and F.Ruskey, Generating the Linear Extensions of Certain
Posets by Transpositions, SIAM J. Discrete Mathematics 4 (1991)
413-422.

Mozna sciagnac ze strony autora

A.L.

do góry

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

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.


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

do góry

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

do góry

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?

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

--
Pozdr

do góry

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

do góry

W dniu 2012-02-23 00:24, n...@m...invalid pisze:
>>> 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?

Jeszcze wyjaśnienie dlaczego pisałem o liczbach wymiernych - pomiędzy
dwie dowolne liczby wymierne można zawsze wstawić trzecią, co w tym
przypadku pozwala nie dotykać znakowania wierzchołków, których nie
przesuwamy.

do góry