Interval (graph theory)

This article is about a concept in graph-theoretic data flow analysis. For graphs defined from intersections of intervals, see Interval graph. For the set of elements in a DAG that are reachable from one vertex and can reach another vertex, see Partially ordered set § Interval.

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 1976 by F. E. Allen and J. Cooke.[1] 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(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

  1. ↑ F.E. Allen, J. Cooke (March 1976). "A Program Data Flow Analysis Procedure". Comm. ACM. 19 (3): 137–147. doi:10.1145/360018.360025.
This article is issued from Wikipedia - version of the 8/29/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.