Interval

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

Interval --- интервал.

An interval is such an alt I that its initial node belongs to each strongly connected subgraph of I. The initial node of interval I is also called a header node.

An interval I is maximal if there is no such an interval Z that I is a proper subfragment of Z.

For a given control flow graph G with its initial node n_{0} and a given node n of G, the maximal interval with the header n, denoted I(n), can be constructed by the following three rules: (1) n is in I(n); (2) if all the predecessors of some node m \neq n_{0} are in I(n), then m is in I(n); (3) nothing else is in I(n).

The set of all maximal intervals of a cf-graph G form a partition of the set of its nodes.

A node p is a head of some maximal interval of a cf-graph G if and only if either p is the initial node of G or p is a terminal node of another maximal interval of G.