Разработка компиляторов
Линейные компоненты
Линейной компонентой называется фрагмент L , обладающий следующими пятью свойствами:
- L является альтом
- L имеет не более одной конечной вершины
- Начальная вершина L не достижима из его конечной вершины
- Начальная и конечная вершины L принадлежат любому пути в графе от start до stop
- L - минимальный подграф, обладающий предыдущими свойствами
Множество всех линейных компонент образует разбиение множества вершин графа. Стягивание линейных компонент переводит граф в луч.
Можно также показать, что начальная вершина линейной компоненты есть либо start, либо конечная вершина другой линейной компоненты. Наконец, можно показать, что начальная вершина произвольной линейной компоненты является бивершиной.
Выделение линейных компонент в исходном графе позволяет применять к нему оптимизирующие преобразования, рассчитанные на линейный участок.
