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.

Directed acyclic graph.png
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 ().

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[уреди]

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(xx), antisimetričnosti(ako je xy i yx onda je x = y), i tranzitivnosti (ako je xy i yz, onda je xz).Relacija totalnog poretka je relacija poretka u kojoj su svaka dva objekta x i y iz skupa uporedivi, ili je xy ili je yx.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 xy u relaciji poretka onda je i xy 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 xy 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, Јуникс програм за тополошко сортирање

Reference[уреди]

Literatura[уреди]

Spoljašnje veze[уреди]