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

в 22:14, , рубрики: Алгоритмы

Несколько лет назад мне пришлось погрузиться в данную тему по работе. Погуглив, я, к удивлению своему, не нашёл каких-то готовых решений. Да и до сих пор, в общем-то, ничего не видно. Поэтому пришлось разрабатывать тему с нуля.

Чтобы было понятно о чем речь, приведу простейший пример.

image

Граф очень простой, и для такого рода графов несложно придумать алгоритм, выделяющий бесхордовые циклы (т.е. циклы, которые не имеют самопересечений, и которые нельзя разбить на более мелкие). Проблема в том, что графы могут быть гораздо более хитрыми, и все случаи надо предусмотреть. Путём обдумывания, написания кода, проб и ошибок, в конце концов и родился алгоритм, которые сейчас работает на благо инженерных изыскателей.

Текстовое описание:

  1. Для каждой вершины графа находим все смежные вершины и начинаем формировать цикл движением в сторону каждой смежной вершины поочередно.
  2. Если число смежных вершин (исключая ту, с которой вошли) =0, то идём обратно, формируя цикл ---> п.5
  3. Если число смежных вершин (исключая ту, с которой вошли) равно 1, то идём по ней, формируя цикл ---> п.5
  4. Если число смежных вершин (исключая ту, с которой вошли) >=2, то ищем самое правое ответвление (путем нормализации векторов и их перемножения), и идём по нему, формируя цикл ---> п.5
  5. Анализируем — вернулись в начальную точку? Если нет, то ---> п.2
  6. Если да, то завершаем формирование цикла и осуществляем проверки.
  7. Ищем в цикле повторяющиеся вершины, если такие есть, то удаляем все вершины между ними, оставляя только одну повторяющуюся.
  8. Ищем в числе уже сформированных циклов совпадающие с данным циклом, и если есть, то прерываем формирование цикла и переходим на ---> п.1 (проверять надо с учетом всех сдвигов и направлений)
  9. Ещё раз проходим по циклу и смотрим на левые ответвления от него. Найдя такие ответвления, для каждого организуем поиск в ширину (или в глубину, неважно). Если при этом мы попадаем в конце концов на вершину сформированного цикла (кроме текущего), то прерываем формирование цикла и переходим на ---> п.1
  10. Записываем цикл, и переходим на поиск нового ---> п.1

Укрупненный псевдокод:
image

Сначала для проверки алгоритма строились всё более и более изощрённые графы.
image
или
image
и, в конце концов, он был протестирован на всех реальных изыскательских графах типа такого:
image
Не думаю, что он оптимальный, но на данный момент (года 3 уже) он работает без сбоев и нареканий.

Код не привожу, вряд ли кому это будет интересно, да и вырвать кусок будет сложно, так как это всего лишь одна небольшая часть работы.

Автор: Владимир

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js