Интервал (теория графов)

редактировать

В теории графов, интервал I (h) в ориентированном графе - это максимальный подграф с одной записью в который h является единственным входом в I (h) и все закрыты пути в I (h) содержат h. Интервалы были описаны в 1970 году Ф. Э. Аллен и Дж. Кок. Графики интервалов являются неотъемлемой частью некоторых алгоритмов, используемых в компиляторах, в частности, анализа потоков данных.

Следующий алгоритм находит все интервалы в графе, состоящем из вершин N и вершины входа n 0, и с функциями pred (n)и succ (n), которые возвращают список предшественников и наследников данного узла n соответственно.

H = {n0} // Инициализируем рабочий список, пока H не пуст, удаляем следующий h из H, создаем интервал I (h) I (h) + = {h}, пока ∃n ∈ {succ (I (h)) - I (h)} такой, что pred (n) ⊆ I (h) I (h) + = {n}, а ∃n ∈ N такой, что n ∉ I (h) и // найти следующие заголовки ∃ m ∈ pred (n) такое, что m ∈ I (h) H + = n

Алгоритм эффективно разбивает граф на его интервалы.

Каждый интервал, в свою очередь, может быть заменен одним узлом, в то время как все ребра между узлами в разных интервалах в исходном графе становятся ребрами между соответствующими им узлами в новом графе. Этот новый график называется интервальным производным графиком . Процесс создания производных графиков можно повторять до тех пор, пока результирующий график не будет уменьшен. Если конечный граф состоит из единственного узла, то исходный граф называется приводимым .

Ссылки

  • Hecht, Matthew S. (1972). «Сводимость потокового графа». Материалы четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72. doi : 10.1145 / 800152.804919.цитирует это понятие в двух статьях: Ф. Э. АЛЛЕН, Анализ потока управления, SIGPLAN Notices, 5 (1970), стр. 1-19. и J. Cocke, Global common subexpression elimination, SIGPLAN Notices, 5 (1970), pp. 20-24.
  • Hecht, M. S. (1974). «Характеризация приводимых потоковых графов». Журнал ACM. 21 (3): 367–375. doi : 10.1145 / 321832.321835.дополнительные характеристики приводимых потоковых графов, в том числе через
Последняя правка сделана 2021-05-24 05:22:36
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте