Intervall (grafteori)

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 n₀, 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.