Čejtinov algoritam
Čejtinov algoritam je odozdo-nagore algoritam za bojenje grafova koji koristi alokaciju registara, a kao meru za pražnjenje registara koristi jedinicu cena/stepen. Ovaj algoritam osmislio je Gregori Čejtin, po kome nosi ime. Čejtinov algoritam je bio prvi algoritam, koji koristi alokaciju registara, koji je iskoristio bojenje grafova kako za alokaciju registara tako i za njihovo pražnjenje.
Čejtinov algoritam je predstavljen i objavljen 1982. na SIGPLAN Simpozijumu o konstrukciji kompilatora. To je bio nastavak ranijeg rada iz 1981. godine koji se bavio bojenjem grafova za alokaciju registara. Čejtinov algoritam predstavlja osnovu velikog dela istraživanja koja se bave alokacijom registara.
Pseudokod
[уреди | уреди извор]Neka je dat graf G, koji sadrži čvorove N stepena manjeg od R. Graf G je R-bojiv ukoliko graf G' (gde je G' graf G sa uklonjenim čvorom N) R-bojiv.[1]
Dokaz je očigledan.
- Pretpostavimo da je graf G R-bojiv. Onda nam je i graf G' sigurno R-bojiv.
- Pretpostavimo da nam je graf G' R-bojiv. Pošto nam je čvor N stepena manjeg od R mora postojati bar jedna boja kojom nije obojen nijedan susedni čvor čvora N. Tom bojom možemo obojiti N. Dakle G je R-bojiv.
Pseudokod algoritma glasi:
While G cannot be R-colored
While graph G has a node N with degree less than R
Remove N and its associated edges from G and push N on a stack S
End While
If the entire graph has been removed then the graph is R-colorable
While stack S contains a node N
Add N to graph G and assign it a color from the R colors
End While
Else graph G cannot be colored with R colors
Simplify the graph G by choosing an object to spill and remove its node N from G
(spill nodes are chosen based on object’s number of definitions and references)
End While
Složenost Čejtinovog algoritma je: [1]
