Interval (graph theory)

In graph theory, an interval I(h) in a directed graph is a maximal, single entry subgraph in which h is the only entry to I(h) and all closed paths in I(h) 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 n₀, and with the functions pred(n) and succ(n) which return the list of predecessors and successors of a given node n, respectively.

   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  

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.

References

• Hecht, Matthew S. (1972). "Flow graph reducibility". Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. doi:10.1145/800152.804919.  cites the notion to two papers: F. E. ALLEN, Control flow analysis, SIGPLAN Notices, 5 (1970), pp. 1-19. and to J. Cocke, Global common subexpression elimination, SIGPLAN Notices, 5 (1970), pp. 20-24.
• Hecht, M. S. (1974). "Characterizations of Reducible Flow Graphs". Journal of the ACM 21 (3): 367–375. doi:10.1145/321832.321835.  additional characterizations of reducible flow graphs, including via natural loops