Несколько лет назад мне пришлось погрузиться в данную тему по работе. Погуглив, я, к удивлению своему, не нашёл каких-то готовых решений. Да и до сих пор, в общем-то, ничего не видно. Поэтому пришлось разрабатывать тему с нуля.
Чтобы было понятно о чем речь, приведу простейший пример.
Граф очень простой, и для такого рода графов несложно придумать алгоритм, выделяющий бесхордовые циклы (т.е. циклы, которые не имеют самопересечений, и которые нельзя разбить на более мелкие). Проблема в том, что графы могут быть гораздо более хитрыми, и все случаи надо предусмотреть. Путём обдумывания, написания кода, проб и ошибок, в конце концов и родился алгоритм, которые сейчас работает на благо инженерных изыскателей.
Текстовое описание:
- Для каждой вершины графа находим все смежные вершины и начинаем формировать цикл движением в сторону каждой смежной вершины поочередно.
- Если число смежных вершин (исключая ту, с которой вошли) =0, то идём обратно, формируя цикл ---> п.5
- Если число смежных вершин (исключая ту, с которой вошли) равно 1, то идём по ней, формируя цикл ---> п.5
- Если число смежных вершин (исключая ту, с которой вошли) >=2, то ищем самое правое ответвление (путем нормализации векторов и их перемножения), и идём по нему, формируя цикл ---> п.5
- Анализируем — вернулись в начальную точку? Если нет, то ---> п.2
- Если да, то завершаем формирование цикла и осуществляем проверки.
- Ищем в цикле повторяющиеся вершины, если такие есть, то удаляем все вершины между ними, оставляя только одну повторяющуюся.
- Ищем в числе уже сформированных циклов совпадающие с данным циклом, и если есть, то прерываем формирование цикла и переходим на ---> п.1 (проверять надо с учетом всех сдвигов и направлений)
- Ещё раз проходим по циклу и смотрим на левые ответвления от него. Найдя такие ответвления, для каждого организуем поиск в ширину (или в глубину, неважно). Если при этом мы попадаем в конце концов на вершину сформированного цикла (кроме текущего), то прерываем формирование цикла и переходим на ---> п.1
- Записываем цикл, и переходим на поиск нового ---> п.1
Укрупненный псевдокод:
Сначала для проверки алгоритма строились всё более и более изощрённые графы.
или
и, в конце концов, он был протестирован на всех реальных изыскательских графах типа такого:
Не думаю, что он оптимальный, но на данный момент (года 3 уже) он работает без сбоев и нареканий.
Код не привожу, вряд ли кому это будет интересно, да и вырвать кусок будет сложно, так как это всего лишь одна небольшая часть работы.
Автор: Владимир
