graph: [proposal] add algorithm for finding intervals in flow graphs
Created by: mewmew
Background
There exist a number of core concepts in graph theory that are general enough to be useful outside of specific application use cases. Concepts such as strongly connected regions, shortest path, dominance relationships in flow graphs, etc.
Related to flow graphs there is the notion of intervals, which are similar to strongly connected regions, but differ in definition and thus application.
The definition of a an interval is as follows:
From Allen, Frances E. "Control flow analysis." ACM Sigplan Notices. Vol. 5. No. 7. ACM, 1970. (ref: http://www.cs.columbia.edu/~suman/secure_sw_devel/p1-allen.pdf)
Given a node h, an interval I(h) is the maximal, single entry subgraph for which h is the entry node and in which all closed paths contain h. The unique interval node h is called the interval head or simply the header node.
Proposal
Implement algorithm for finding intervals in rooted flow graphs. The specific algorithm is outlined in these papers (with slight variations between the papers, but the output is identical).
- Allen, Frances E., and John Cocke. "A program data flow analysis procedure." Communications of the ACM 19.3 (1976): 137.
- Figure 1 "Interval Algorithm" in C. Cifuentes, "A Structuring Algorithm for Decompilation", 1993.
- Figure 6-8 "Interval Algorithm" in C. Cifuentes, "Reverse Comilation Techniques", 1994.
Potential impact of proposal
It should be enough to introduce the following API to the graph/path
package, which already contains control flow graph algorithms (e.g. calculation of dominance trees).
Of course, these API additions are open for suggestions. Mainly plotting them down, so we can get a feel for what it may look like.
// Intervals returns the unique set of intervals in the given control flow
// graph rooted at the node with ID eid.
func Intervals(g graph.Directed, eid int64) []*Interval {
}
// An Interval I(h) is the maximal, single entry subgraph for which h
// is the entry node and in which all closed paths contain h. The
// unique interval node h is called the interval head or simply the
// header node.
type Interval struct {
// Interval head.
head graph.Node
// Interval nodes.
nodes []graph.Node
}
// Head returns the header node of the interval.
func (i *Interval) Head() graph.Node {
}
// Nodes returns all the nodes in the interval.
func (i *Interval) Nodes() graph.Nodes {
}
// Edge returns the edge from u to v, with IDs uid and vid,
// if such an edge exists between the nodes of the interval
// and nil otherwise. The node v must be directly reachable
// from u as defined by the From method.
func (i *Interval) Edge(uid, vid int64) graph.Edge {
}
The intention is to have *Interval
implement the graph.Directed
interface.
Thoughts and comments? I'd be submitting a PR with the implementation, once we've settled on if this is an algorithm we wish to include in the Gonum graph package, and once we've discussed what the API should look like.
Cheers, Robin