Несколько лет назад мне пришлось погрузиться в данную тему по работе. Погуглив, я, к удивлению своему, не нашёл каких-то готовых решений. Да и до сих пор, в общем-то, ничего не видно. Поэтому пришлось разрабатывать тему с нуля.
Чтобы было понятно о чем речь, приведу простейший пример.
Граф очень простой, и для такого рода графов несложно придумать алгоритм, выделяющий бесхордовые циклы (т.е. циклы, которые не имеют самопересечений, и которые нельзя разбить на более мелкие). Проблема в том, что графы могут быть гораздо более хитрыми, и все случаи надо предусмотреть. Путём обдумывания, написания кода, проб и ошибок, в конце концов и родился алгоритм, которые сейчас работает на благо инженерных изыскателей.
Текстовое описание:
Укрупненный псевдокод:
Сначала для проверки алгоритма строились всё более и более изощрённые графы.
или
и, в конце концов, он был протестирован на всех реальных изыскательских графах типа такого:
Не думаю, что он оптимальный, но на данный момент (года 3 уже) он работает без сбоев и нареканий.
Код не привожу, вряд ли кому это будет интересно, да и вырвать кусок будет сложно, так как это всего лишь одна небольшая часть работы.
Чтобы было понятно о чем речь, приведу простейший пример.
Граф очень простой, и для такого рода графов несложно придумать алгоритм, выделяющий бесхордовые циклы (т.е. циклы, которые не имеют самопересечений, и которые нельзя разбить на более мелкие). Проблема в том, что графы могут быть гораздо более хитрыми, и все случаи надо предусмотреть. Путём обдумывания, написания кода, проб и ошибок, в конце концов и родился алгоритм, которые сейчас работает на благо инженерных изыскателей.
Текстовое описание:
- Для каждой вершины графа находим все смежные вершины и начинаем формировать цикл движением в сторону каждой смежной вершины поочередно.
- Если число смежных вершин (исключая ту, с которой вошли) =0, то идём обратно, формируя цикл ---> п.5
- Если число смежных вершин (исключая ту, с которой вошли) равно 1, то идём по ней, формируя цикл ---> п.5
- Если число смежных вершин (исключая ту, с которой вошли) >=2, то ищем самое правое ответвление (путем нормализации векторов и их перемножения), и идём по нему, формируя цикл ---> п.5
- Анализируем — вернулись в начальную точку? Если нет, то ---> п.2
- Если да, то завершаем формирование цикла и осуществляем проверки.
- Ищем в цикле повторяющиеся вершины, если такие есть, то удаляем все вершины между ними, оставляя только одну повторяющуюся.
- Ищем в числе уже сформированных циклов совпадающие с данным циклом, и если есть, то прерываем формирование цикла и переходим на ---> п.1 (проверять надо с учетом всех сдвигов и направлений)
- Ещё раз проходим по циклу и смотрим на левые ответвления от него. Найдя такие ответвления, для каждого организуем поиск в ширину (или в глубину, неважно). Если при этом мы попадаем в конце концов на вершину сформированного цикла (кроме текущего), то прерываем формирование цикла и переходим на ---> п.1
- Записываем цикл, и переходим на поиск нового ---> п.1
Укрупненный псевдокод:
Сначала для проверки алгоритма строились всё более и более изощрённые графы.
или
и, в конце концов, он был протестирован на всех реальных изыскательских графах типа такого:
Не думаю, что он оптимальный, но на данный момент (года 3 уже) он работает без сбоев и нареканий.
Код не привожу, вряд ли кому это будет интересно, да и вырвать кусок будет сложно, так как это всего лишь одна небольшая часть работы.
wataru
Судя по алгоритму, у вас не просто граф, а планарный граф на плоскости. И задача у вас, похоже, не найти бесхордовые циклы, а выделить на плоскости простые замкнутые контуры, у которых нет "возможности срезать угол" строго внутри области.
Например, вот такой граф:
Massaraksh147 Автор
Спасибо, это интересно. Будет время, обязательно попробую и напишу.
Sergey_Kovalenko
Всегда очень приятно видеть статью, где автор описывает свой творческий опыт. Пока читал Вашу, на ум пришел тоже какой-никакой алгоритм. Не уверен, что он работает быстрее, но все же:
Предположим граф связен (иначе разбить на компоненты связности и применить алгоритм к каждой из них)
1)Игнорировать ориентацию в графе и построить в нем любое остовное дерево T.
Лемма 1: для любых двух вершин N_1, N_2 в дереве существует и притом единственный соединяющий их путь prim(N_1, N_2) без повторений ребер и вершин
Лемма 2: если пара вершин N_1, N_2 соединена каким-то ребром E, не входящим в остовное дерево, то присоединив его к prim(N_1, N_2), вы получите базисный относительно T цикл. Это цикл является простым, то есть, он проходит через все свои ребра и вершины ровно по одному разу.
Поскольку циклы — это ориентированные пути, то их можно складывать и вычитать друг из друга. Обратный для C цикл получается, если пройти его в обратном направлении. Сумма циклов C_1 С_2 с общей вершиной B определяется так: стартуя из B, вам нужно сначала пройти по C_1, а после возвращения в B — потом еще и по С_2. Если у циклов несколько общих вершин, можно начать обход из любой — на результат суммы это никак не повлияет. Разность определяется как сумма с обратным циклом.
Каждый цикл индуцирует циклический порядок на экземплярах тех ребер, через которые он проходит. Назовем цикл невозвратным, если в этом порядке два экземпляра одного ребра не стоят рядом. Вычеркивая рядом стоящие экземпляры, любой цикл можно привести к невозвратному, результат не зависит от порядка вычеркивания. Два цикла, которые приводятся к одному и тому же невозвратному будем считать эквивалентными
Лемма 3. Пусть простой цикл C образован ребрами остовного дерева T и еще k ребрами, которые не принадлежат T. Тогда C с точностью до эквивалентности можно представить в виде суммы некоторого базисного относительно T цикла и простого цикла С', у которого только (k-1) его ребро не входит в T
2) Итеративно найдем все простые циклы. Простые циклы первого G_0 поколения — это в точности все базисные циклы относительно T. Пусть у нас уже есть поколение G_(n-1). Если G_(n-1) пусто, то поиск простых циклов завершен и переходим к следующему пункту. Иначе составим всевозможные суммы (и разности) между циклами поколения G_(n-1) и циклами, которые являются базисными относительно T. Приведем результаты к безвозвратному виду. Те из сумм, которые окажутся простыми, даст нам следующие поколение G_n.
3) Каждый бесхордовый цикл, является в том числе и простым. Все простые циклы мы нашли. Остается вернуть графу его направленность и отобрать те простые циклы ненаправленного графа, которые к тому же являются циклами и в его направленном варианте.
Massaraksh147 Автор
Люблю конструктивные предложения. Обязательно попробую.
Sergey_Kovalenko
Свое знакомство с графовыми алгоритмами я начал с книг Ахо, Ульмана и Хопфорта «Алгоритмы. Построение и анализ» и с довольно устаревшей, но хорошо написанной монографии Кристофидеса «Теория графов. Алгоритмический подход». Возможно, они окажутся полезными и Вам тоже.
Massaraksh147 Автор
Спасибо. Нашёл, добавил в закладки.
Sergey_Kovalenko
Проснулся и понял, что к лемме 3 есть контрпример. Похоже, в таком виде алгоритм найдет не все бесхордовые циклы.
AlexKarpan
Передо мной стояла похожая задача с направленным графом: я писал декомпилятор — восстанавливал код высокоуровневого языка из ассемблерных инструкций. Посмотрю, как ваши идеи можно применить в моей случае. Спасибо!
wataru
Вряд ли это применимо к вашему графу. Тут используется, что граф нарисован на плоскости — у всех ребер есть направления и можно в каждой вершине повернуть "направо" при обходе.
AlexKarpan
А ведь действительно. Вы правы :(