Реализации планарных графов / карт (с вложениями)
Для целей данного поста под плоским графом или плоской картой я буду подразумевать абстрактный граф, который можно нарисовать на плоскости (или эквивалентно на сфере) вместе с круговым порядком ребер в каждой вершине в соответствии с к конкретному такому рисунку. Эта дополнительная информация определяет вложение на сферу (вплоть до перемещения вершин и ребер таким образом, что они никогда не пересекаются с какими-либо другими вершинами / ребрами). Я хочу разрешить петли и несколько ребер.
Например, предположим, что мы построили график следующим образом. Нарисуйте две вершины (A и B) в плоскости вместе с двумя ребрами, соединяющими эти две. Два ребра вместе образуют простую замкнутую кривую \ гамма. Теперь добавьте еще две вершины, A'и B', и соедините A и A 'с ребром, а также B и B'.
Этот абстрактный граф будет иметь два неэквивалентных вложения, в зависимости от того, разделены ли вершины A 'и B' кривой \gamma или нет.
Мой вопрос: есть ли пакет Python, который реализует такие плоские графы?
Меня интересует пакет, который может создать чертеж плоского графа (конечно, с учетом встраивания), а также выполнить некоторые стандартные операции (например, дать число граней, сформировать двойной граф и т. Д.)
Если такой пакет не существует в Python, я также был бы заинтересован в реализации на других языках.
Конечно, существуют различные пакеты, которые реализуют рисование графов и теоретико-графические алгоритмы. Тем не менее, я не заметил ни в одном из них возможности работы с графами, которые уже идут с вложением. Ссылка будет высоко ценится.
РЕДАКТИРОВАТЬ. Позвольте мне остановиться подробнее. Два вложения одного и того же графа в сферу эквивалентны, если они связаны гомеоморфизмом сферы с самим собой. Как упомянуто выше, вложение плоского графа, в общем, не уникально, так что я спрашиваю не то же самое, что проверка графа на плоскостность и отрисовка его вложения.
Существует несколько комбинаторных способов кодирования вложений вплоть до этой эквивалентности. Вероятно, самое простое - записать циклический порядок ребер в каждой вершине ("система вращения"), но есть много других. См. Статью о вложении графов в Википедии для обсуждения и ссылок.
Существуют очевидные операции, которые можно выполнить с таким комбинаторным вложением, например, найти грани графа, найти грани, к которым граничит вершина / вершина, вставить вершину грани, подразделить ребро, нарисовать картинку встраивания и т. д.
Есть ли в Python реализация одной или нескольких из этих структур данных, представляющих вложения комбинаторных графов? (Я отмечаю, что вложения графов имеют смысл на общих поверхностях, хотя меня в первую очередь интересует случай сферы.)
2 ответа
Я только что заметил, что networkx содержит класс для цели, которую я описываю, а именно PlanarEmbedding. См. https://networkx.github.io/documentation/latest/reference/algorithms/planarity.html
(Я не уверен, было ли это введено, так как я задал вопрос, или я пропустил это в то время.)
Методы, которые идут с классом, кажутся довольно простыми, и это только реализует одну из возможных структур данных для плоских вложений. Я буду расследовать дальше; если кто-то знает о других реализациях, эта информация будет оценена.
Я не уверен, что полностью понимаю ваше требование, но вы смотрели на эту библиотеку планарности. Это оболочка Cython для AC (++?) Реализации алгоритмов планарности, включая рисование. Я использовал это с networkX.