Структура данных представления топологии электрических схем

[realeugene]

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

-- 01.09.2019, 00:24 --

_Ivana в сообщении #1412649 писал(а):

Но это решает вопрос лишь частично.

Все компоненты схемы можно представить в виде дерева, где под корнем располагаются все узлы, соответствующие отдельным компонентам. Под узлом компонента располагаются узлы группы пинов. Под узлами групп пинов располагаются пины. Схема расширяема - можно добавить промежуточные уровни.

Естественно потребовать, что два взаимозаменяемых потомка любого узла должны быть корнями одинаковых поддеревьев. Дерево упорядоченное (или как оно там называется, сейчас нет под рукой учебника).

Отдельные пины - листья в дереве. Каждому пину прописываем индекс в векторе состояния. Таким образом, каждому узлу дерева соотвествует цепочка индексов в порядке обхода листьев поддерева.

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

[realeugene]

Dmitriy40 в сообщении #1412683 писал(а):

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

Все такие компоненты будут под корнем дерева. ОБработаем такую ситуацию следующим образом:

1. Потребуем, чтобы в нашем дереве эквивалентные узлы шли подряд в списке детей любого узла. Назовём это отношение эквивалентности эквивалентностью типа.
2. Добавляем понятие временных отношений эквивалентности, являющихся следствием конкретной схемы. Все элементы в каждой последовательной цепочке в схеме считаем временно эквивалентными. Это другое отношение эквивалентности.
3. Потребуем, чтобы цепочки индексов временно эквивалентных узлов, также, располагались в лексикографическом порядке. Чтобы этого добиться, сортируем цепочки индексов узлов сначала с использованием временной эквивалентности, а потом с использованием эквивалентности типа. Так как эквивалентные по типу узлы расположены в дереве последовательно, сортировка их цепочек индексов не нарушит лексикографический порядок цепочек индексов временно эквивалентных узлов.

Все сортировки проводим для каждого узла в дереве при обходе дерева в обратном порядке.

UPD Нет, это работает только с одиночными последовательно включенными компонентами, но не с группами параллельных компонентов.

UPD2 есть ещё симметрии, связанные с возможностью произвольной перенумерации проводов.

[EUgeneUS]

realeugene
Насколько понимаю, Вы описали структуру данных, для описания набора элементов, но не самой схемы. Но это не решает задачу сравнения схем.

Очевидно, что
а) схема из резисторов одинакового номинала эквивалентна неориентированному графу.
б) схема из резисторов разного номинала эквивалентна неориентированному взвешенному графу.

Насколько знаю, на данный момент не доказано, что задача изоморфности графов решается лучше, чем $O(N!)$
Поэтому всё, что можно придумать на практике, это уменьшение $N$, от которого считается факториал.

[arseniiv]

И сравнения по более простым критериям. (Которые вы предлагали на той странице.)

Хотел тоже что-нибудь предложить, но с нижних полок уже всё взяли; и рассказать сугубо теоретическую схему (скорее всего, никак пока не полезную на практике даже с учётом успехов в алгоритмах свёртки тензоров по уму) с тензорами, но на полпути понял, что она даже сюда не втыкается из-за того, что могут быть соединены более чем два вывода элементов, и вводить семейство тензоров-коннекторов, притом удовлетворяющих естественным соотношениям (типа $g_{ijkl} = g_{ijm} g^{mn} g_{nkl}$ — соединение четырёх эквивалентно соединению их сначала подвое — плюс симметрии каждого $g$), было уже выше меня (не факт, что такое семейство существует, и мне даже пришлось выдумать «контравариантный коннектор», необходимость которого я не видел в прошлый раз, то есть всё ещё хуже). Хм, хотя можно и без соотношений обойтись, наверно. Если будет кому интересно, опишу, но пользы от этого скорее всего нету.