Войти
В теории графов, интервал 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Алгоритм эффективно разбивает граф на его интервалы.
Каждый интервал, в свою очередь, может быть заменен одним узлом, в то время как все ребра между узлами в разных интервалах в исходном графе становятся ребрами между соответствующими им узлами в новом графе. Этот новый график называется интервальным производным графиком . Процесс создания производных графиков можно повторять до тех пор, пока результирующий график не будет уменьшен. Если конечный граф состоит из единственного узла, то исходный граф называется приводимым .
