Factor-control-flow-graph

Перейти к:навигация, поиск

Factor-control-flow-graph --- фактор-уграф.

Let $R$ be a set of alts of a cf-graph $G$ such that every node of $G$ belongs to a single alt from $R$, i.e. $R$ forms a partition of $V(G)$.

The cf-graph $G'$ in which $V(G')=R$ is said to be obtained by reduction of alts $R$ into nodes (notation $G'=R(G)$) if the following properties hold:

(1) for any $C_1,C_2\in R$, $(C_1,C_2)\in A(G')$ if and only if there are $p_1\in C_1$ and $p_2\in C_2$ such that $(p_1,p_2)\in A(G)$,

(2) $C\in R$ is the initial node of $G'$ if and only if $C$ contains the initial node of $G$,

(3) $C\in R$ is the terminal node of $G'$ if and only if $C$ contains the terminal node of $G$.

The cf-graph $G'$ is called a factor-control-flow-graph (or factor-cf-graph) of the cf-graph $G$ with respect to $R$.

Let $R$ be a set of mutually disjoint alts of a cf-graph $G$ that form a partitation of some subset $Y\subset V(G)$. Then $R(G)$ is defined as cf-graph $R'(G)$, where $R'=R\bigcup \{ \{p\}: p\in V(G)\setminus Y\}$.