Получить все сетки (окна) в графике

Question

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

Я использую Python с библиотекой NetworkX, но ее функция cycle_basis не возвращает сетки (они, очевидно, не совпадают с основой цикла). График не ориентирован, поэтому я не могу использовать функцию simple_cycles. Я пытался изменить BFS для этой задачи, но я не мог гарантировать, что в другом цикле не содержится ни одного цикла.

Мне, вероятно, нужно что-то вроде этого: Алгоритм для нахождения минимальных циклов в графе , но у этого вопроса нет никакого доказательства алгоритма в последнем комментарии, и я надеюсь, что ответ на мою проблему проще чем «реализовать алгоритм Хортона».

Answer 1

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

Гораздо проще найти, чем минимальную основу цикла, но какой список вы получите, зависит от того, какой планарный чертеж вы используете.

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

В противном случае вы можете сделать что-то вроде:

1. Создание связующего дерева
2. Для каждого ребра, которое не в дереве, создайте цикл, содержащий только это ребро и ребра, которые находятся в остовном дереве.

Поскольку каждый цикл содержит одно ребро, которого нет ни в одном другом цикле, гарантируется, что ни один цикл не содержится ни в одном другом ... в зависимости от того, что вы подразумеваете под «содержащимся». Важным моментом является то, что эти циклы будут работать для анализа, если вы внимательно относитесь к любым текущим источникам. Может быть, вы хотите избежать их в связующем дереве.

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