Single-entry single-exit
Encyclopedia
In graph theory
, a single-entry single-exit (SESE) region in a given graph
is an ordered edge pair (a, b) of distinct control flow
edges a and b where:
where a node x is said to dominate node y in a directed graph
if every path from start to y includes x. A node x is said to postdominate a node y if every path from y to end includes x.
So, a and b refer to the entry and exit edge, respectively. The first condition ensures that every path from start into the region passes through the region’s entry edge, a. The second condition ensures that every path from inside the region to end passes through the region’s exit edge, b. The first two conditions are necessary but not enough to characterize SESE regions: since backedges do not alter the dominance or postdominance relationships, the first two conditions alone do not prohibit backedges entering or exiting the region. The third condition encodes two constraints: every path from inside the region to a point 'above' a passed through b, and every path from a point 'below' b to a point inside the region passes through a.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a single-entry single-exit (SESE) region in a given graph
Graph
Graph may refer to:* A graphic depicting the relationship between two or more variables used, for instance, in visualising scientific data.In mathematics:* Graph , is a set of vertices and edges....
is an ordered edge pair (a, b) of distinct control flow
Control flow graph
A control flow graph in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution.- Overview :...
edges a and b where:
- a dominates b
- b postdominates a
- Every cycle containing a also contains b and vice versa.
where a node x is said to dominate node y in a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
if every path from start to y includes x. A node x is said to postdominate a node y if every path from y to end includes x.
So, a and b refer to the entry and exit edge, respectively. The first condition ensures that every path from start into the region passes through the region’s entry edge, a. The second condition ensures that every path from inside the region to end passes through the region’s exit edge, b. The first two conditions are necessary but not enough to characterize SESE regions: since backedges do not alter the dominance or postdominance relationships, the first two conditions alone do not prohibit backedges entering or exiting the region. The third condition encodes two constraints: every path from inside the region to a point 'above' a passed through b, and every path from a point 'below' b to a point inside the region passes through a.