Управляющий граф

Управляющий граф (Control flow graph, Flow graph) — основная модель программы, представляющая в виде орграфа поток управления (систему управляющих связей) в программе; в ней сохраняется только членение программы на операторы (команды, лучи), а также информация о тождественности операторов и возможных передачах управления между операторами.

В общем случае управляющий граф — это помеченный упорядоченный мультиграф с выделенными начальной вершиной (входом) и непустым множеством конечных вершин (выходов).

Обычно считается, что управляющий граф является правильным и не содержит кратных дуг, вершин с совпадающими пометками и разных конечных вершин, т.е. управляющий граф — это орграф с выделенными начальной [math]\displaystyle{ s }[/math] и конечной [math]\displaystyle{ t }[/math] вершинами, каждая вершина которого лежит хотя бы на одном [math]\displaystyle{ s-t }[/math]-пути.

Часто без ограничения общности можно считать, что из [math]\displaystyle{ t }[/math] не выходит и в [math]\displaystyle{ s }[/math] не заходит ни одна дуга управляющего графа, а из каждой вершины, отличной от [math]\displaystyle{ t }[/math], выходит одна или две дуги.

Другие названия — Граф переходов, Уграф, Схема Мартынюка.

См. также

• Альт,
• Аранжировка,
• Аранжируемый граф,
• Базисная нумерация,
• Гамак,
• Гамачное представление,
• Достоверные отношения частоты выполнения,
• Зона,
• Зонно-интервальное представление,
• Иерархия вложенных альтов,
• Иерархия вложенных зон,
• Интервал,
• Каркас уграфа,
• Крупноблочная схема программ,
• Линейная компонента,
• Линейный участок,
• Непосредственный обязательный преемник,
• Одновходовый уграф,
• Разборный граф,
• Регуляризуемый уграф,
• Сводимый управляющий граф,
• Стандартные схемы,
• Схема программ,
• Участок повторяемости,
• Фактор-уграф,
• Фрагмент,
• Циклический участок.

Литература

• Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

• Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.

• Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.