Topološko uređenje

U informatici, topološko sortiranje (skraćeno topsort ili toposort) ili topološko uređenje usmerenog grafa je linearno uređenje njegovih čvorova tako da svaka usmerena grana UV od čvora U ka čvoru V, U dolazi pre V u uređenju. Na primer, čvorovi grafa predstavljaju zadatke koje treba izvršiti, a grane predstavljaju ograničenja da neki zadataka mora biti izvršen pre nekog drugog; u ovoj aplikaciji, topološko uređenje je samo validan raspored izvršavanja zadataka. Topološko uređenje je moguće, ako i samo ako graf nema usmerene cikluse, odnosno da je usmereni acikličan graf (UAG). Svaki UAG ima najmanje jedno topološko uređenje, i poznat je algoritam za konstruisanje topološkog uređenja bilo kog UAG u linearnom vremenu.

Primeri

Kanonska aplikacija topološkog sortiranja (topološkog uređenja) je u planiranju rasporeda poslova ili zadata na osnovu njihove zavisnosti; algoritmi topološkog sortiranja su prvi put proučavani ranih 1960-ih godina u kontekstu PERT tehnike planiranja upravljanja projektima (^[1]). Poslovi su predstavljeni čvorovima i postoji grana od A ka B, ako posao A mora biti izvršen pre nego što se posao B može zapoceti (primer: kod pranja veš mašine, mašina mora da završi sa pranjem veša da bi ga mi satvili na sušenje). Dakle, topološko sortiranje nam daje redosled kojim treba da izvršavamo poslove.

U informatici, aplikacije ovog tipa prerastaju u instrukcije organizacije, uređenju formula ćelija evaluacije pri reizračunavanju formula valuacije u tabelama, logičke sinteze, određivanje rasporeda zadataka kompilacije koji se izvršavaju u mejkfajlovima, serijalizaciji podataka i određivanju zavisnosti simbola u linkerima.

Graf prikazan sa leve strane se može na mnogo načina topološki sortirati, uključujući:

7, 5, 3, 11, 8, 2, 9, 10 (vuzuelno sa leva na desno, sa vrha ka dnu)
3, 5, 7, 8, 11, 2, 9, 10 (prvo čvorovi sa najmanjom vrednošću)
3, 7, 8, 5, 11, 10, 2, 9
5, 7, 3, 8, 11, 10, 9, 2 (najkrace grane prvo)
7, 5, 11, 3, 10, 8, 9, 2 (prvo čvorovi sa največom vrednošću)
7, 5, 11, 2, 3, 8, 9, 10

Algoritmi

Uobičajeni algoritmi sa topološkim sortiranjem imaju linearnu složenost po broju grana plus broju čvorova ( $O(\left|{V}\right|+\left|{E}\right|)$ ).

Jedan od ovih algoritama, koji je opisao Kahn 1962, radi tako što odabira čvorove u istom redosledu kao i eventualno topološko sortiranje.Prvo nade listu „početnih čvorova“ koji nemaju ulazne grane i ubacuje ih u S; barem jedan takav čvor mora postojati u acikličnom grafu. Zatim:

L ← Prazna lista koja će sadržati sortirane elemente
S ← Skup svih čvorova bez ulaznih grana
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (Graf ima bar jedan ciklus)
else 
    return L (Topološki sortirani)

Ako je graf UAG, rešenje ce se nalaziti u listi L(rešenja ne moraju biti jedinstvena). U suprotnom, graf ima bar jedan ciklus i topološko sortiranje se ne može uraditi.

Napomenimo da, zbog ne-jedinstvenosti rezultata sortiranja, struktura S može biti jednostavno skup, red ili stek.U zavisnosti od redosleda kojim se čvorovi n izbacuju iz skupa S, dobijamo različita rešenja.Varijacije Kahn-ovog algoritma koji razbije veze leksikografskih oblika, ključna je komponenta Kafman-Grahamovog algoritma za paralelno planiranje i slojevito crtanje grafa.

Alternativni algoritam za topološko sortiranje je zasnovan na pretraživanju u dubinu.Kod ovog algoritma, grane su usmerene u suprotnom smeru od prethnog algoritma(a u suprotnom smeru nego sto su prikazane na dijagramu uznad). Postoji grana od A ka B ako posao A zavisi od posla B(ako posao B mora biri izvršen pre nego sto posao A može da se započne). Algoritam se kreće kroz svaki čvor grafa, u proizvoljnom redosledu, započinjući pretragu u dubinu koja se zaustavlja kada se dođe do čvora koji je već posećen.

L ← Prazna lista koja će sadržati sortirane čvorove
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(čvor n)
    if n has a temporary mark then stop (nije UAG)
    if n is not marked (nije posećen) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        add n to head of L

Primetimo da se svaki čvor n dodaje u izlaznu listu L tek nakon što se razmotre svi čvorovi od kojih n zavisi(svi potomci čvora n u grafu).Posebno, kada algoritam doda čvor n, zagarantovano je da su svi čvorovi od kojih zavisi n već dodati u izlaznu listu L:dadati su u L ili prethodnim rekurzivnim pozivom visit() ili ranijim pozicom visit(). Kako su svi čvorovi i svaka grana posećeni jednom, algoritam se izvršava u linearnom vremenu. Ovaj algoritam, zasnovan je na pretrazi u širinu, opisao ga je Cormen et al. 2001, ali ga je pre njega opisao Tarjan 1976 u stampi.

Složenost

Računarska kompleksnost izračunavanja u usmerenom grafu je NC²; što znači da se može izračunati za O(log² n) vremena na paralelnom računaru pomoću polinomijalnog broja od O(n^k)procesora, za istu konstantu k^[2].

Jedinstvenost

Kada bi topološko sortiranje imalo osobinu da sve parove uzastopnih čvorova u sortiranom poretku poveže granama, dobili bismo usmeren Hamiltonov put u UAG. Ako Hamiltonov put postoji, topološki poredak je jedinstven; nijedan drugi poredak ne zadovoljava ivice puta.Obrnuto, ako topološko sortiranje ne formira Hamiltonov put, UAG će imati dva ili više validna topološka poretka, jer je u ovom slučaju uvek moguće formirati drugi ispravan poredak zamenom dva uzastopna čvora koji nisu povezani granom. Dakle, moguće je proveriti u linearnom vremenu da li postoji jedinstveni poredak, i da li postoji Hamiltonov put, uprkos NP-težini problema Hamiltonovog puta za neke opštije usmerene grafove^[3].

Odnos prema relaciji poretka

Topološka sortiranja su usko povezana sa konceptom lineanog istezanja relacije poretka u matematici.

Parcijalno uredjen skup je skup objekata sa definicijom relacije manje ili jednako "≤", zadovoljavajući aksiome refleksivnosti(x ≤ x), antisimetričnosti(ako je x ≤ y i y ≤x onda je x = y), i tranzitivnosti (ako je x ≤ y i y ≤ z, onda je x ≤ z).Relacija totalnog poretka je relacija poretka u kojoj su svaka dva objekta x i y iz skupa uporedivi, ili je x ≤ y ili je y ≤ x.Totalna uređenja se koriste u informatici kako bi operatori poređenja mogli da izedu upoređivanje kod algoritama za sortiranje.Za konačne skupove, totalna uređenja se mogu identifikovati kao linearan niz objekata gde je "≤" relacija tačna kad god prvi objekat prethodi drugom u redu;algoritmi za sortiranje upoređivanjem se mogu iskoristiti za pretvaranje totalnog uređenja u niz na ovaj način. Linearno istezanje relacije poretka je totalni poredak koji je usaglašen sa njim, u smislu ako je x ≤ y u relaciji poretka onda je i x ≤ y u totalnom poretku takođe.

Može se definisati relacija poretka iz bilo kog DAL-a tako što ćemo postaviti da skup objekata budu čvorovi DAL-a i definišemo da je x ≤ y tačno za bilo koja dva čvora x i y', kad god postoji usmeren put od x ka y,tj. kad god iz x možemo da stignemo do y. Ovako definisano, topološko uređenje DAL-a je isto što i linearno istezanje ove relacije poretka. Obrnuto, svaka relacija poretka može biti definisana kao relacija domašaja u DAL-u. Jedan način da se ovo izvede je da se definiše DAL koje ima čvor za svaki objekat iz skupa relacije poretka i granu xy za svaki par objekata za koje važi x ≤ y. Alternativan način da se uradi ovo je da se koristi tranzitivno zatvorenje relacije poretka;u celini, ovako dobijamo DAL-ove sa manje grana ali je relacija domašaja i dalje ista relacija poretka. Ovako se algoritmi za topološko sortiranje mogu koristiti za nalaženje linearnih istezanja relacije poretka.

Vidi još

tsort, Јуникс програм за тополошко сортирање

Literatura

Cook, Stephen A. (1985). A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control. 64. стр. 2—22. doi:10.1016/S0019-9958(85)80041-3. .
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „Section 22.4: Topological sort”. Introduction to Algorithms (2nd изд.). MIT Press and McGraw-Hill. стр. 549-552. ISBN 978-0-262-03293-3. .
Jarnagin, M. P. (1960). Automatic machine methods of testing PERT networks for consistency. Technical Memorandum No. K-24/60. Dahlgren, Virginia: U. S. Naval Weapons Laboratory. .
Kahn, Arthur B. (1962). Topological sorting of large networks. Communications of the ACM. 5. стр. 558—562. doi:10.1145/368996.369025. .
Tarjan, Robert E. (1976). Edge-disjoint spanning trees and depth-first search. Acta Informatica. 6. стр. 171—185. doi:10.1007/BF00268499. .
Vernet, Oswaldo; Markenzon, Lilian (1997). „Hamiltonian problems for reducible flowgraphs”. Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97). стр. 264—267. doi:10.1109/SCCC.1997.637099. .

Spoljašnje veze

NIST Dictionary of Algorithms and Data Structures: topological sort
dep-trace Orders basic dependencies and unfolds nested ones. (basic: without 2D graphical presumption)

[1] Jarnagin 1960

[2] Cook 1985

[3] Vernet & Markenzon 1997

[1]

[2]

[3]