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

Wed Apr 4 22:54:53 MSK 2018

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

Во-вторых, есть вопрос, связанный со второй картинкой, но тут, наверное, нужно сначала объяснить, с чего вдруг этот вопрос появился.
Выделенные регионы хотелось бы хранить как граф регионов, то есть есть структура Region, у которой следующие поля:
name - имя региона
s1, s2 - указатели на следующие регионы (как в блоках)
head - указатель на регион-заголовок
nodes - вектор указателей на регионы (блоки), которые входят в наш регион, но не являются заголовками
edges - вектор ребер
Тогда на третьей картинке выходит граф регионов (первые три прямоугольника), при этом все равно хранятся все выделенные регионы, которые при желании можно достать через head и nodes.
Но вот если рассмотреть случай на второй картинке, то по идеи мы выделяем в один регион блоки B2-B4-B6. Но тогда двух указателей s1, s2 на следующие регионы - недостаточно, ведь получается три указателя на блоки B3, B7, B8. Но по идеи разве может у региона три выходных ребра? В итоге возникает вопрос, может быть граф неверное нарисован, или, может быть, предложенная схема-структура хранения регионов изначально некорректна.
Спасибо,
Дроздова Катя

>Четверг, 29 марта 2018, 13:01 +03:00 от Vladislav Ivanishin <vlad at ispras.ru>:
>
>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/
>>>
>>>-- 
>>>Влад
>
>-- 
>Влад
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://compilers.ispras.ru/pipermail/region/attachments/20180404/daf8a93b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 1.jpg
Type: image/jpeg
Size: 102944 bytes
Desc: not available
URL: <http://compilers.ispras.ru/pipermail/region/attachments/20180404/daf8a93b/attachment-0003.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2.jpg
Type: image/jpeg
Size: 78917 bytes
Desc: not available
URL: <http://compilers.ispras.ru/pipermail/region/attachments/20180404/daf8a93b/attachment-0004.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 3.jpg
Type: image/jpeg
Size: 118219 bytes
Desc: not available
URL: <http://compilers.ispras.ru/pipermail/region/attachments/20180404/daf8a93b/attachment-0005.jpg>