Interval (graph theory)


In graph theory, an interval I in a directed graph is a maximal, single entry subgraph in which h is the only entry to I and all closed paths in I contain h. Intervals were described in 1970 by F. E. Allen and J. Cocke. Interval graphs are integral to some algorithms used in compilers, specifically data flow analyses.
The following algorithm finds all the intervals in a graph consisting of vertices N and the entry vertex n0, and with the functions pred and succ which return the list of predecessors and successors of a given node n, respectively.
H = // Initialize work list
while H is not empty
remove next h from H
create the interval I
I +=
while ∃n ∈ such that pred ⊆ I
I +=
while ∃n ∈ N such that n ∉ I and // find next headers
∃m ∈ pred such that m ∈ I
H += n
The algorithm effectively partitions the graph into its intervals.
Each interval can in turn be replaced with a single node, while all edges between nodes in different intervals in the original graph become edges between their corresponding nodes in the new graph. This new graph is called an interval derived graph. The process of creating derived graphs can be repeated until the resulting graph can't be reduced further. If the final graph consists of a single node, then the original graph is said to be reducible.