<HTML><BODY>Здравствуйте,<br>спасибо за подробно расписанный алгоритм. <br>Хотелось бы уточнить пару моментов. <br>Во-первых, возник вопрос со случаем на первой картинке: какой из вариантов выделения регионов верный? Вроде как первый вариант логичнее, так как раз циклы пересекаются, значит один вложен в другой, с другой стороны, эта вложенность не совсем очевидна.<br><br>Во-вторых, есть вопрос, связанный со второй картинкой, но тут, наверное, нужно сначала объяснить, с чего вдруг этот вопрос появился.<br>Выделенные регионы хотелось бы хранить как граф регионов, то есть есть структура Region, у которой следующие поля:<br>name - имя региона<br>s1, s2 - указатели на следующие регионы (как в блоках)<br>head - указатель на регион-заголовок<br>nodes - вектор указателей на регионы (блоки), которые входят в наш регион, но не являются заголовками<br>edges - вектор ребер<br>Тогда на третьей картинке выходит граф регионов (первые три прямоугольника), при этом все равно хранятся все выделенные регионы, которые при желании можно достать через head и nodes.<br>Но вот если рассмотреть случай на второй картинке, то по идеи мы выделяем в один регион блоки B2-B4-B6. Но тогда двух указателей s1, s2 на следующие регионы - недостаточно, ведь получается три указателя на блоки B3, B7, B8. Но по идеи разве может у региона три выходных ребра? В итоге возникает вопрос, может быть граф неверное нарисован, или, может быть, предложенная схема-структура хранения регионов изначально некорректна.<br>Спасибо,<br>Дроздова Катя<br><br><blockquote style="border-left:1px solid #0857A6; margin:10px; padding:0 0 0 10px;">
Четверг, 29 марта 2018, 13:01 +03:00 от Vladislav Ivanishin <vlad@ispras.ru>:<br>
<br>
<div id="">
<div class="js-helper js-readmsg-msg">
<style type="text/css"></style>
<div>
<base target="_self" href="https://e.mail.ru/">
<div id="style_15223177020000000404_BODY">Katya Drozdova <<a href="mailto:drozd_96@mail.ru">drozd_96@mail.ru</a>> writes:<br>
<br>
> Здравствуйте,<br>
> определенный прогресс есть: <br>
> есть понимание, как организовать структуру, сделан каркас, обычное выделение<br>
> регионов-листьев. По сути нужно реализовать алгоритма поиска циклов в графе, я<br>
> сначала почему-то зациклилась на том, чтобы это самой сделать и потратила на это<br>
> довольно много времени впустую, но после поняла, что такого рода алгоритмы уже<br>
> есть. <br>
<br>
А если бы обсуждали в рассылке, мы бы могли вам подсказать...<br>
<br>
Предполагается, что вы рассматриваете только приводимые графы, в которых<br>
циклы либо не пересекаются, либо один вложен в другой. Можно<br>
переформулировать это свойство так: если циклы пересекаются, то один<br>
вложен в другой (*).<br>
<br>
Обычный поиск циклов (с бинарным ответом, есть ли циклы) делается с<br>
помощью обхода графа, например, в глубину: если "уткнулись" в уже<br>
помеченную вершину, обнаружен цикл.<br>
<br>
Для поиска самих циклов и заодно информации о вложенности я вижу такой<br>
алгоритм (это не истина в последней инстанции -- только что<br>
придумал). Обходим граф в глубину, стек поддерживаем сами (наверное,<br>
можно исхитриться и использовать и обычный стек вызовов, если есть<br>
желание). На стек, как обычно, добавляется рассматриваемая вершина, а<br>
после обработки всех её потомков она выталкивается. Таким образом, в<br>
каждый момент весь стек целиком представляет текущий путь. Далее, как в<br>
обычном поиске цикла: если потомок s текущей вершины v уже посещён, цикл<br>
замкнулся. Его легко вывести: нужно дойти по стеку до предыдущего<br>
посещения s. Всё, что между (включая границы) -- и есть искомый цикл.<br>
<br>
Теперь нужно ещё запомнить отношение вложенности. Это можно делать и<br>
после выделения циклов, но по-моему, сразу не только эффективнее, но и<br>
проще. Будем поддерживать информацию о том, началами и концами каких<br>
циклов являются вершины на стеке. Кроме этого, будем поддерживать ещё<br>
один стек sc, куда будем добавлять идентификаторы циклов, "открытых"<br>
(т.е. уже начавшихся) для текущего пути. Из стека sc будет выталкиваться<br>
значение, когда мы вытолкнем из основного стека начало соответствующего<br>
цикла. Тогда свежеобнаруженный цикл будет вложен во все циклы,<br>
находящиеся в данный момент в sc. Это верно в силу (*).<br>
Понятное дело, что встреченный конец уже открытого цикла выталкивает<br>
этот цикл из sc (а если он встретился при движении "назад", т.е. при<br>
выталкивании вершины из основного стека, то цикл следует снова добавить<br>
в sc).<br>
<br>
> Со временем есть определенные проблемы, но думаю, что в течение двух дней<br>
> алгоритм адаптировать под нашу задачу получится.<br>
> по тестам есть понимание того, какие конкретно нужно рассмотреть<br>
> случаи. Пара простых случаев сделаны, чтобы можно было посмотреть, как<br>
> работает каркас алгоритма. <br>
><br>
> Спасибо за материалы!<br>
><br>
>>Четверг, 29 марта 2018, 0:39 +03:00 от Vladislav Ivanishin <<a href="mailto:vlad@ispras.ru">vlad@ispras.ru</a>>:<br>
>><br>
>>Добрый день,<br>
>><br>
>>Eugene Sharygin < <a href="mailto:eush@ispras.ru">eush@ispras.ru</a> > writes:<br>
>><br>
>>> Здравствуйте,<br>
>>><br>
>>> Vladislav Ivanishin < <a href="mailto:vlad@ispras.ru">vlad@ispras.ru</a> > writes:<br>
>>><br>
>>>> Katya Drozdova < <a href="mailto:drozd_96@mail.ru">drozd_96@mail.ru</a> > writes:<br>
>>>><br>
>>>>> 1 неделя:<br>
>>>>> реализация алгоритма выделения областей и написание тестов к алгоритму<br>
>>>>> 2 неделя:<br>
>>>>> реализация восходящего просмотра для анализа потока данных на основе областей:<br>
>>>>> один делает для областей-тела, другой - областей-цикла<br>
>>>>> 3 неделя:<br>
>>>>> реализация нисходящего просмотра для анализа потока данных: аналогично <br>
>>>>> 4 неделя:<br>
>>>>> написание тестов к анализу потока данных <br>
>>>><br>
>>>> Хорошо. Тогда пишите, пожалуйста, через неделю о продвижении в области<br>
>>>> выделения областей.<br>
>>><br>
>>> Предлагаю тогда назначить промежуточный отчёт на конец первой / начало<br>
>>> второй недели.<br>
>>><br>
>>> Согласно [1], промежуточный отчёт - это<br>
>>><br>
>>>> письмо с перечислением всех задач с указанием текущего<br>
>>>> статуса каждой задачи.<br>
>>><br>
>>> [1]: <a href="https://compilers.ispras.ru/pipermail/prac-sp-18/2018/000014.html" target="_blank">https://compilers.ispras.ru/pipermail/prac-sp-18/2018/000014.html</a><br>
>><br>
>>Есть ли прогресс по выделению областей? Пожалуйста, пишите, если<br>
>>возникли трудности или даже если ничего не успели.<br>
>><br>
>>P.S.: мы выложили новые слайды лекций Сергея Суреновича, они доступны по сслыке<br>
>><a href="https://compilers.ispras.ru/materials/2018_%d0%a1%d0%bb%d0%b0%d0%b9%d0%b4%d1%8b%20pdf/" target="_blank">https://compilers.ispras.ru/materials/2018_%d0%a1%d0%bb%d0%b0%d0%b9%d0%b4%d1%8b%20pdf/</a><br>
>><br>
>>-- <br>
>>Влад<br>
<br>
-- <br>
Влад</div></div></div></div></blockquote></BODY></HTML>