Interval (graph theory)

From Infogalactic: the planetary knowledge core
(Redirected from Reducible flow graphs)
Jump to: navigation, search

<templatestyles src="Module:Hatnote/styles.css"></templatestyles>

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[dubious ] 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. Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found. 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.
  • Lua error in package.lua at line 80: module 'strict' not found. additional characterizations of reducible flow graphs, including via natural loops