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]