Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
(pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
Obrazowo można myśleć o obiektach jak o stworzonych ale nie
wystartowanych service'ach.

Listę (tablicę, obojętne) takich obiektów posortować.
a) pewnie algorytmika zna coś gotowego
b) mili widziane (bardzo, nawet można pomyśleć o zerwaniu algorytmu
wyjątkiem), kontrola czy z tych zależnościach nie ma sprzeczności.

Obiekty dziedziczą ze wspólnego przodka.

Ewentualnie
c) algorytm bez sortowania, wykonuj wyżej wspomnianą czynność dla
wszystkich zaczynając od przypadkowego obiektu, poprzedzając
rekurencyjnie akcją dla wymaganych, (profilaktycznie odnotowując co już
było wykonane). Nie jest zbyt brutal-force?
W razie sprzeczności, "jakoś" się to wykona. Sortowanie bardziej mi się
podoba, bo da wyjątek bardzo wcześnie.

do góry

On Sat, 21 May 2011 16:10:01 +0200, Jacek Czerwinski <...@...z.pl> wrote:

>Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
>(pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
>Obrazowo można myśleć o obiektach jak o stworzonych ale nie
>wystartowanych service'ach.
>
>Listę (tablicę, obojętne) takich obiektów posortować.
>a) pewnie algorytmika zna coś gotowego
>b) mili widziane (bardzo, nawet można pomyśleć o zerwaniu algorytmu
>wyjątkiem), kontrola czy z tych zależnościach nie ma sprzeczności.
>
>Obiekty dziedziczą ze wspólnego przodka.
>
>Ewentualnie
>c) algorytm bez sortowania, wykonuj wyżej wspomnianą czynność dla
>wszystkich zaczynając od przypadkowego obiektu, poprzedzając
>rekurencyjnie akcją dla wymaganych, (profilaktycznie odnotowując co już
>było wykonane). Nie jest zbyt brutal-force?
>W razie sprzeczności, "jakoś" się to wykona. Sortowanie bardziej mi się
>podoba, bo da wyjątek bardzo wcześnie.
>

Jakbys napisal tak zeby bylo wiadomo o co chodzi, to moze by ktos
odpowiedzial. Ja, mimo kilkukrotnego czytania, nie wiem o co ci
chodzi.

A.L.

do góry

Dnia 21-05-2011 o 16:10:01 Jacek Czerwinski <...@...z.pl> napisał(a):

> Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
> (pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
> Obrazowo można myśleć o obiektach jak o stworzonych ale nie
> wystartowanych service'ach.
>
> Listę (tablicę, obojętne) takich obiektów posortować.
> a) pewnie algorytmika zna coś gotowego
> b) mili widziane (bardzo, nawet można pomyśleć o zerwaniu algorytmu
> wyjątkiem), kontrola czy z tych zależnościach nie ma sprzeczności.
>
> Obiekty dziedziczą ze wspólnego przodka.
>
> Ewentualnie
> c) algorytm bez sortowania, wykonuj wyżej wspomnianą czynność dla
> wszystkich zaczynając od przypadkowego obiektu, poprzedzając
> rekurencyjnie akcją dla wymaganych, (profilaktycznie odnotowując co już
> było wykonane). Nie jest zbyt brutal-force?
> W razie sprzeczności, "jakoś" się to wykona. Sortowanie bardziej mi się
> podoba, bo da wyjątek bardzo wcześnie.

moze tak:

dany jest zbior serwisow.
wysciowa lista jest pusta.
poki zbior wejsciowy cos zawiera:
dla kazdego elementu zbioru:
jesli wszystkie wymagane serwisy aktualnego serwisu sa juz na liscie
wyjsciowej:
dopisz aktualny serwis na koniec listy wyjsciowej i usun ze
zbioru wejsciowego.
jesli nic nie dopisano w tym przebiegu:
rzuc wyjatkiem.
koniec.

zlozonosc pesymistyczna wyglada mi na kwadratowa, czyli chyba nie jest
tragicznie

--
Jordan Szubert

do góry

W dniu 2011-05-21 16:10, Jacek Czerwinski pisze:
> Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
> (pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
> Obrazowo można myśleć o obiektach jak o stworzonych ale nie
> wystartowanych service'ach.
>
> Listę (tablicę, obojętne) takich obiektów posortować.
> a) pewnie algorytmika zna coś gotowego
> b) mili widziane (bardzo, nawet można pomyśleć o zerwaniu algorytmu
> wyjątkiem), kontrola czy z tych zależnościach nie ma sprzeczności.
>
> Obiekty dziedziczą ze wspólnego przodka.
>
> Ewentualnie
> c) algorytm bez sortowania, wykonuj wyżej wspomnianą czynność dla
> wszystkich zaczynając od przypadkowego obiektu, poprzedzając
> rekurencyjnie akcją dla wymaganych, (profilaktycznie odnotowując co już
> było wykonane). Nie jest zbyt brutal-force?
> W razie sprzeczności, "jakoś" się to wykona. Sortowanie bardziej mi się
> podoba, bo da wyjątek bardzo wcześnie.

Może tak: zbudować graf skierowany, sprawdzić czy jest acykliczny (jeśli
jest cykl, to sprzeczność w zależnościach), posortować topologicznie.

do góry

On May 21, 4:10 pm, Jacek Czerwinski <x...@...z.pl> wrote:
> Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
> (pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
> Obrazowo można myśleć o obiektach jak o stworzonych ale nie
> wystartowanych service'ach.
>
> Listę (tablicę, obojętne) takich obiektów posortować.
> a) pewnie algorytmika zna coś gotowego
> b) mili widziane (bardzo, nawet można pomyśleć o zerwaniu algorytmu
> wyjątkiem), kontrola czy z tych zależnościach nie ma sprzeczności.
>
> Obiekty dziedziczą ze wspólnego przodka.
>
> Ewentualnie
> c) algorytm bez sortowania, wykonuj wyżej wspomnianą czynność dla
> wszystkich zaczynając od przypadkowego obiektu, poprzedzając
> rekurencyjnie akcją dla wymaganych, (profilaktycznie odnotowując co już
> było wykonane). Nie jest zbyt brutal-force?
> W razie sprzeczności, "jakoś" się to wykona. Sortowanie bardziej mi się
> podoba, bo da wyjątek bardzo wcześnie.

Uhh, ale zamotales :)

Zdaje sie ze taki algorytm to rozwiaze:
Twoje obiekty
Obiekt obiekty[N];
for( i=1 ; i<N ; i++ ) {
Obiekt swp = obiekty[i];
for( j=i-1 ; j>=0 && tmp.Zalezy( obiekty+0 , obiekty+j ) ; j-- )
obiekt[j+1] = obiekt[j];
obiekt[++j] = tmp;
for( j++ ; j<=i ; j++ )
if( obiekt[j].Zalezy( tmp ) )
WYJATEK();
}

Indeksy moglem zle wyliczyc, piszac "na kolanie". Ale
powinno zadzialac, bo sortowanie jest stabilne. Po kazdym
przestawieniu sprawdzamy czy nie zabuzylismy wczesniej
dobrze ustawionej realcji "Zalezy". Jesli zaburzylismy to
rzucamy wyjatkiem.

Nie jestem pewien na 100%, ale mysle ze zadziala.

Pozdrawiam

do góry

W dniu 2011-05-22 01:03, Mariusz Marszałkowski pisze:

> Indeksy moglem zle wyliczyc, piszac "na kolanie". Ale
> powinno zadzialac, bo sortowanie jest stabilne. Po kazdym
> przestawieniu sprawdzamy czy nie zabuzylismy wczesniej
> dobrze ustawionej realcji "Zalezy". Jesli zaburzylismy to
> rzucamy wyjatkiem.

Dzięki Tobie i Kolegom za za wszystkie wypowiedzi. Zarówno algorytmy i
wiodące słowa (sortowanie topologiczne itd).

Co do stabilności sortowania, wymyśliłem sobie w 'komparatorze' dodać
jakiś prosty warunek który by skutkował w razie pustej lub banalnej
listy zalezności, nie dającej rozstrzygnięcia. Np alfabetyczna nazwa
usługi itd.

do góry

W dniu 2011-05-21 17:37, Piotr Chamera pisze:
> W dniu 2011-05-21 16:10, Jacek Czerwinski pisze:
>> Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
>> (pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
>> Obrazowo można myśleć o obiektach jak o stworzonych ale nie
>> wystartowanych service'ach.
>>
>> Listę (tablicę, obojętne) takich obiektów posortować.
>> a) pewnie algorytmika zna coś gotowego
>> b) mili widziane (bardzo, nawet można pomyśleć o zerwaniu algorytmu
>> wyjątkiem), kontrola czy z tych zależnościach nie ma sprzeczności.
>>
>> Obiekty dziedziczą ze wspólnego przodka.
>>
>> Ewentualnie
>> c) algorytm bez sortowania, wykonuj wyżej wspomnianą czynność dla
>> wszystkich zaczynając od przypadkowego obiektu, poprzedzając
>> rekurencyjnie akcją dla wymaganych, (profilaktycznie odnotowując co już
>> było wykonane). Nie jest zbyt brutal-force?
>> W razie sprzeczności, "jakoś" się to wykona. Sortowanie bardziej mi się
>> podoba, bo da wyjątek bardzo wcześnie.
>
> Może tak: zbudować graf skierowany, sprawdzić czy jest acykliczny (jeśli
> jest cykl, to sprzeczność w zależnościach), posortować topologicznie.

Nie wiem jaki dokładnie jest cel, ale w ramach nauki Lispu wypociłem
coś jak poniżej (w Common Lispie) na bazie przeglądania grafu wszerz
(wg Cormena).
Procedura sprawdza czy graf jest acykliczny, ale na tej bazie można
wykonać i inne operacje na grafie (np. wylistować wszystkie zależności
danego wierzchołka - wywołać dfsa? dla żądanego wierzchołka i
kolekcjonować informacje o odwiedzonych obiektach).

Przykładowe obiekty mają taką strukturę
(defstruct obj
name ;nieużywany, ale przydaje się kiedy chcemy wydrukować graf
dep ;krawędzie grafu
)

(obj-dep x) jest akcesorem do listy zależności (krawędzi grafu)



(defun check (objects)
(let ((markers (make-hash-table :test 'eq)))
(labels ((work-on (x)
"oznacz wierzchołek jako obecnie przetwarzany"
(setf (gethash x markers) 'working))
(finish-with (x)
"oznacz wierzchołek jako przetworzony wraz z dziećmi"
(setf (gethash x markers) 'finished))
(get-marker (x)
"sprawdz co wiemy o wierzchołku (domyślnie - jeszcze nieodwiedzony)"
(gethash x markers 'virgin))
(dfsa? (v)
"test czy graf widoczny z wierzchołka v jest acykliczny"
(work-on v)
(loop :for x :in (obj-dep v) :do
(case (get-marker x)
(virgin (dfsa? x))
(working (return-from check
(format nil "w grafie jest cykl")))
(finished nil)))
(finish-with v)))
(loop :for v :in objects :do
(when (eq 'virgin (get-marker v))
(dfsa? v)))))
(format nil "w grafie nie ma cykli"))

do góry

W dniu 2011-05-21 17:37, Piotr Chamera pisze:
> W dniu 2011-05-21 16:10, Jacek Czerwinski pisze:
>> Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
>> (pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
>> Obrazowo można myśleć o obiektach jak o stworzonych ale nie
>> wystartowanych service'ach.
>>
>
> Może tak: zbudować graf skierowany, sprawdzić czy jest acykliczny (jeśli
> jest cykl, to sprzeczność w zależnościach), posortować topologicznie.


Zdecydowałem się, na tym etapie, na 'topologiczne' odpalanie wymaganych
zależności PRZED sobą (z zaznaczaniem co już odpalone i z jakim skutkiem
pełny / ostrzeżenie / wyjątek). Jest to 'prawie' rekurencja.

Ciekawe o tyle, że mam:
a) analizę nie tylko statyczną, ale dynamiczną (co się UDAŁO odpalić)
b) pojawiły mi się zapowiedzi 'miękkich' zależności, czyli nie wymagane
ale 'mile widziane'.
c) efekt uboczny, próba odpalenie czegoś, co już było startowane ale się
nie udało, do przemyślenia
d) efekt uboczny, da się w to włączyć coś co nie było wcześniej
zarejestrowane (zadeklarowane), np przyniesione przez jakiś moduł z
leniwą inicjacją.

do góry