mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a single-entry single-exit (SESE) region in a given

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

is an ordered edge pair. For example, with the ordered edge pair, (''a'', ''b'') of distinct

control-flow In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''imp ...

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 In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

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''.The program structure tree: computing control regions in linear time
/ref>

References

Graph theory {{compu-prog-stub