Чејтинов алгоритам
Чејтинов алгоритам је одоздо-нагоре алгоритам за бојење графова који користи алокацију регистара, а као меру за пражњење регистара користи јединицу цена/степен. Овај алгоритам осмислио је Грегори Чејтин, по коме носи име. Чејтинов алгоритам је био први алгоритам, који користи алокацију регистара, који је искористио бојење графова како за алокацију регистара тако и за њихово пражњење.
Чејтинов алгоритам је представљен и објављен 1982. на СИГПЛАН Симпозијуму о конструкцији компилатора. То је био наставак ранијег рада из 1981. године који се бавио бојењем графова за алокацију регистара. Чејтинов алгоритам представља основу великог дела истраживања која се баве алокацијом регистара.
Псеудокод[уреди | уреди извор]
Нека је дат граф G, који садржи чворове N степена мањег од R. Граф G је R-бојив уколико граф G' (где је G' граф G са уклоњеним чвором N) R-бојив.[1]
Доказ је очигледан.
- Претпоставимо да је граф G R-бојив. Онда нам је и граф G' сигурно Р-бојив.
- Претпоставимо да нам је граф G' R-бојив. Пошто нам је чвор N степена мањег од R мора постојати бар једна боја којом није обојен ниједан суседни чвор чвора N. Том бојом можемо обојити N. Дакле G је R-бојив.
Псеудокод алгоритма гласи:
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
Сложеност Чејтиновог алгоритма је: [1]
