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.[1] 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[rediger | rediger kilde]
- ^ F.E. Allen, J. Cocke (mars 1976). «A Program Data Flow Analysis Procedure». Comm. ACM. 19 (3): 137–147. doi:10.1145/360018.360025.