Выделение бесхордовых циклов из ненаправленного графа

Судя по алгоритму, у вас не просто граф, а планарный граф на плоскости. И задача у вас, похоже, не найти бесхордовые циклы, а выделить на плоскости простые замкнутые контуры, у которых нет "возможности срезать угол" строго внутри области.

Например, вот такой граф:

Бесхордовых циклов тут три (идем вправо по одному из трех путей и возвращаемся обратно по любому из остальных, 6 вариантов делим на два, ибо обошли каждый цикл в двух направлениях). Если требовать, чтобы не было более короткого пути между двумя вершинами в цикле, то цикл только один — внешние ребра. Если же требовать, чтобы вообще лишних путей между вершинами не было, то циклов вообще нет. Но мне кажется, что вы хотите видеть тут 2 цикла — вокруг нижней и верхней замкнутой области, так?

Эта задача очень похожа на известную задачу выделения граней у планарного графа. С тем лишь дополнением, что надо удалить "петли" если цикл проходит по каким-то вершинам несколько раз. Ну, и компоненты связности внутри граней разрешены и игнорируются. В приведенном алгоритме они ничего не ломают — просто он в случае их наличия выдает не совсем грани графа, а просто замкнутые циклы, как вам и надо.

Ваше решение, судя по всему, в n раз медленнее, чем описанное по ссылке: вы начинаете обход с каждого ребра пока не вернетесь в вершину и таким образом получаете каждый цикл много раз со всеми сдвигами. Следует, во-первых, работать с направленными ребрами (каждое ребро вашего графа — это 2 направленных ребра в разные стороны). Во-вторых, надо помечать обойденные ребра и начинать обход с любого не помеченного направленного ребра.

Единственное усложнение тут, что вы можете получить цикл с касаниями с каким-то произвольным сдвигом. Тогда просто удалять вершины между двумя повторениями одной вершины нельзя — вы можете удалить внешность цикла, оставив только внутренность. Но это лечится нахождением самой нижней-левой вершины в цикле. Если начинать обход цикла с нее, то уже можно спокойно удалять все вершины между двумя повторениями одной и той же вершины. Главное, чтобы эта самая нижняя-левая вершина оставалась в ответе.

Всегда очень приятно видеть статью, где автор описывает свой творческий опыт. Пока читал Вашу, на ум пришел тоже какой-никакой алгоритм. Не уверен, что он работает быстрее, но все же:

Предположим граф связен (иначе разбить на компоненты связности и применить алгоритм к каждой из них)
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) Каждый бесхордовый цикл, является в том числе и простым. Все простые циклы мы нашли. Остается вернуть графу его направленность и отобрать те простые циклы ненаправленного графа, которые к тому же являются циклами и в его направленном варианте.

Передо мной стояла похожая задача с направленным графом: я писал декомпилятор — восстанавливал код высокоуровневого языка из ассемблерных инструкций. Посмотрю, как ваши идеи можно применить в моей случае. Спасибо!