[region] Поиск циклов (Re: Промежуточный отчёт)

[Vladislav Ivanishin]

Katya Drozdova <drozd_96 at mail.ru> writes:

> Здравствуйте,
> определенный прогресс есть: 
> есть понимание, как организовать структуру, сделан каркас, обычное выделение
> регионов-листьев. По сути нужно реализовать алгоритма поиска циклов в графе, я
> сначала почему-то зациклилась на том, чтобы это самой сделать и потратила на это
> довольно много времени впустую, но после поняла, что такого рода алгоритмы уже
> есть. 

А если бы обсуждали в рассылке, мы бы могли вам подсказать...

Предполагается, что вы рассматриваете только приводимые графы, в которых
циклы либо не пересекаются, либо один вложен в другой. Можно
переформулировать это свойство так: если циклы пересекаются, то один
вложен в другой (*).

Обычный поиск циклов (с бинарным ответом, есть ли циклы) делается с
помощью обхода графа, например, в глубину: если "уткнулись" в уже
помеченную вершину, обнаружен цикл.

Для поиска самих циклов и заодно информации о вложенности я вижу такой
алгоритм (это не истина в последней инстанции -- только что
придумал). Обходим граф в глубину, стек поддерживаем сами (наверное,
можно исхитриться и использовать и обычный стек вызовов, если есть
желание). На стек, как обычно, добавляется рассматриваемая вершина, а
после обработки всех её потомков она выталкивается. Таким образом, в
каждый момент весь стек целиком представляет текущий путь. Далее, как в
обычном поиске цикла: если потомок s текущей вершины v уже посещён, цикл
замкнулся. Его легко вывести: нужно дойти по стеку до предыдущего
посещения s. Всё, что между (включая границы) -- и есть искомый цикл.

Теперь нужно ещё запомнить отношение вложенности. Это можно делать и
после выделения циклов, но по-моему, сразу не только эффективнее, но и
проще. Будем поддерживать информацию о том, началами и концами каких
циклов являются вершины на стеке. Кроме этого, будем поддерживать ещё
один стек sc, куда будем добавлять идентификаторы циклов, "открытых"
(т.е. уже начавшихся) для текущего пути. Из стека sc будет выталкиваться
значение, когда мы вытолкнем из основного стека начало соответствующего
цикла. Тогда свежеобнаруженный цикл будет вложен во все циклы,
находящиеся в данный момент в sc. Это верно в силу (*).
Понятное дело, что встреченный конец уже открытого цикла выталкивает
этот цикл из sc (а если он встретился при движении "назад", т.е. при
выталкивании вершины из основного стека, то цикл следует снова добавить
в sc).

> Со временем есть определенные проблемы, но думаю, что в течение двух дней
> алгоритм адаптировать под нашу задачу получится.
> по тестам есть понимание того, какие конкретно нужно рассмотреть
> случаи. Пара простых случаев сделаны, чтобы можно было посмотреть, как
> работает каркас алгоритма. 
>
> Спасибо за материалы!
>
>>Четверг, 29 марта 2018, 0:39 +03:00 от Vladislav Ivanishin <vlad at ispras.ru>:
>>
>>Добрый день,
>>
>>Eugene Sharygin < eush at ispras.ru > writes:
>>
>>> Здравствуйте,
>>>
>>> Vladislav Ivanishin < vlad at ispras.ru > writes:
>>>
>>>> Katya Drozdova < drozd_96 at mail.ru > writes:
>>>>
>>>>> 1 неделя:
>>>>> реализация алгоритма выделения областей и написание тестов к алгоритму
>>>>> 2 неделя:
>>>>> реализация восходящего просмотра для анализа потока данных на основе областей:
>>>>> один делает для областей-тела, другой - областей-цикла
>>>>> 3 неделя:
>>>>> реализация нисходящего просмотра для анализа потока данных: аналогично 
>>>>> 4 неделя:
>>>>> написание тестов к анализу потока данных 
>>>>
>>>> Хорошо. Тогда пишите, пожалуйста, через неделю о продвижении в области
>>>> выделения областей.
>>>
>>> Предлагаю тогда назначить промежуточный отчёт на конец первой / начало
>>> второй недели.
>>>
>>> Согласно [1], промежуточный отчёт - это
>>>
>>>> письмо с перечислением всех задач с указанием текущего
>>>> статуса каждой задачи.
>>>
>>> [1]:  https://compilers.ispras.ru/pipermail/prac-sp-18/2018/000014.html
>>
>>Есть ли прогресс по выделению областей? Пожалуйста, пишите, если
>>возникли трудности или даже если ничего не успели.
>>
>>P.S.: мы выложили новые слайды лекций Сергея Суреновича, они доступны по сслыке
>>https://compilers.ispras.ru/materials/2018_%d0%a1%d0%bb%d0%b0%d0%b9%d0%b4%d1%8b%20pdf/
>>
>>-- 
>>Влад

-- 
Влад