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

Thu Apr 5 00:20:08 MSK 2018

Здравствуйте,

Katya Drozdova <drozd_96 at mail.ru> writes:

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

Здесь ошибка в самом примере. Процитирую себя:

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

На этом же рисунке циклы 9-10-11-12 (опускаю префикс "B") и 12-13
пересекаются (имеют общую вершину B12), и ни один из них не вложен в
другой.

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

Вернее, B{2-4-6}, B7 и B8?

> Но по идеи разве может у региона три выходных ребра? В итоге возникает
> вопрос, может быть граф неверное нарисован, или, может быть,
> предложенная схема-структура хранения регионов изначально некорректна.

Выходит, что может быть три выходных ребра. Храните массив или список.

Это вполне естественно. Раз несколько вершин "схлопнулись" в одну, все
исходящие из региона рёбра теперь будут исходить из этой одной вершины.

На изображении "после шага 4" в слайде 24 лекций этого года (подраздел
9.1.5) есть аналогичная ситуация с той лишь разницей, что из трёх рёбер
два оказались параллельными.

> Спасибо,
> Дроздова Катя
>
>>Четверг, 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/
>>>>
>>>>-- 
>>>>Влад
>>
>>-- 
>>Влад
>
>
>

-- 
Влад