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