Как проверить, есть ли у графа пересекающиеся ребра в networkx?

Я создаю генетический алгоритм для решения проблемы коммивояжера, используя python и networkx. И я добавляю условие сходимости к удовлетворительному решению: путь не должен иметь пересекающихся ребер. Интересно, есть ли в networkx быстрая функция для проверки наличия в графе пересекающихся ребер или, по крайней мере, для того, чтобы узнать, возможно ли их создать.

График создается со списком точек (path), каждая точка имеет координату в x и координату в y. Последовательность точек указывает путь к туру. Я создал объект nx.Graph(), как показано ниже:

        G = nx.Graph()
        for i in range(len(path)):
            G.add_node(i, pos=(path[i].x, path[i].y))
            
        for i in range(len(path)-1):
            G.add_edge(i, i+1)
        G.add_edge(len(path)-1, 0)

Один пример сходящегося не оптимального решения:

Как проверить, есть ли у графа пересекающиеся ребра в networkx?

распечатать точки с nx.get_node_attributes(G,'pos'):

{0: (494, 680), 1: (431, 679), 2: (217, 565), 3: (197, 581), 4: (162, 586), 5: (90, 522), 6:(138, 508), 7: (217, 454), 8: (256, 275), 9: (118, 57), 10: (362, 139), 11: (673, 89), 12: (738, 153), 13: (884, 119), 14: (687, 542), 15: (720, 618), 16: (745, 737), 17: (895, 887), 18: (902, 574), 19: (910, 337), 20: (823, 371), 21: (601, 345), 22: (608, 302), 23: (436, 294), 24: (515, 384), 25: (646, 495)}

Вот статья, подтверждающая условие сходимости: http://www.ams.org/publicoutreach/feature-column/fcarc-tsp

Это выглядит как хорошая отправная точка: en.wikipedia.org/wiki/Multiple_line_segment_intersection

0x5453 11.10.2022 19:43

Я бы использовал shapely, чтобы найти пересекающиеся линии.

Tom McLean 11.10.2022 19:49
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
3
157
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Я не уверен, подходит ли это для вашей задачи, но мне кажется, что это связано с планарностью графа.

Вы можете проверить, является ли граф планарным с помощью:

nx.is_planar(G)

который возвращает True, если это так. Смотрите документацию.

На самом деле я пробовал это раньше, и он всегда возвращал True, я не знаю, почему.

Fabricio Brum 13.10.2022 14:41
Ответ принят как подходящий

Мое первое прочтение было таким же, как у @AveragePythonEngineer. Обычно в задаче о коммивояжере и в теории графов нас не слишком заботит положение вершин, а только расстояния между ними. И я подумал, что вы, возможно, путаете рисунок графика с графиком (это всего лишь одна реализация бесконечных возможных рисунков). Таким образом, хотя вы можете нарисовать планарный граф с пересекающимися ребрами, если хотите (как в вашем примере), дело в том, что вы можете нарисовать его на плоскости.

При повторном прочтении вашего вопроса я думаю, что вы фактически вводите «непересекающиеся пути» в качестве ограничения. Другими словами, используя жаргон: путь не должен пересекаться сам с собой. Если это так, то я думаю этот вопрос в GIS Stack Exchange вам поможет. Он использует shapely, очень полезный инструмент для 2D-геометрических вопросов. Из первого ответа:

[Проверить] .is_simple

Возвращает True, если функция не пересекается сама с собой.

from shapely.wkt import loads
l = loads('LINESTRING (9603380.577551289 2719693.31939431, 9602238.01822002 2719133.882441244, 9601011.900844947 2718804.012436028, 9599670.800095448 2718931.680117098, 9599567.204161201 2717889.384686942, 9600852.184025297 2721120.409265322, 9599710.80929024 2720511.270897166, 9602777.832940497 2718125.875545334)')
print(l.is_simple) # False

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

Спасибо за ответ, согласен с вашей оценкой.

AveragePythonEnjoyer 13.10.2022 11:14

Решение ее с помощью алгоритма Бентли-Оттмана кажется идеальным способом. Я адаптирую график к форме и сравню их. Большое спасибо! Для любопытства мой алгоритм находится на github.com/onofabricio/caixeiroViajante. (Это на португальском языке) Просто запустите скрипт main.py и найдите случайные точки.

Fabricio Brum 13.10.2022 15:00

Другие вопросы по теме