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 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