Et intervall, I(h), i en rettet graf er innen grafteori en maksimal undergraf med en enkel inngang hvor h er den eneste inngangen til I(h) og alle lukkede stier i I(h) som inneholder h. Intervaller ble beskrevet i 1976 av Frances E. Allen og John Cocke. Intervallgrafer er integrerte i enkelte algoritmer som benyttes av kompilatorer, særlig i dataflytanalyser.
Den følgende algoritme finner alle intervallene i en graf som består av N toppunkter og inngangspunkt n0, og med funksjonene pred(n) og succ(n) som returnerer listen over henholdsvis forgjengere og etterfølgere av en gitt node n.
H = { n0 } // Initialize work list while H is not empty remove next h from H create the interval I(h) I(h) += { h } while ∃n ∈ { succ(I(h)) — I(h) } such that pred(n) ⊆ I(h) I(h) += { n } while ∃n ∈ N such that n ∉ I(h) and // find next headers ∃m ∈ pred(n) such that m ∈ I(h) H += n
Algoritmen partisjonerer grafen opp i intervaller.
Referanser
Kategori:Grafteori Kategori:Kompilatorer