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

[_Ivana]

У меня есть самописная программка, генерирующая варианты электрических схем, состоящих из заданного набора компонентов и удовлетворяющих определенным критериям. В ней схема представляется как упорядоченный вектор соединений, где каждое соединение - множество выводов соединенных деталей. Каждая деталь имеет тип и порядковый номер, каждый вывод также имеет тип и/или номер в рамках детали. Например, транзистор 1 вывод базы, резистор 2 вывод 1. Проблема в том, что такое представление позволяет задать одну и ту же топологию схемы множеством формально различных вариантов, что приводит к 2 проблемам:

1) Увеличение числа перебиремых вариантов при поиске. Я частично решил этот вопрос добавлением ограничений вида "деталь с бОльшим номером располагается в векторе соединений правее" и "вывод (неполярной детали) с бОльшим номером располагается в векторе соединений правее" и т.п. Вот почему я выбрал вектор соединений а не множество. Но это решает вопрос лишь частично.

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

Собственно, вопрос в поиске такого представления. Буду рад, если подскажете что-то дельное.

[EUgeneUS]

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

перемены мест идентичных групп контактов у переключателей и т.п.

И вообще перемены мест идентичных (однотипных) элементов.
С группами выключателей (или, например, резисторными сборками) три типа преобразований приводят к одной и тоже топологии:
1. Реверс выводов одного элемента.
2. Перестановка элементов внутри группы\сборки
3. Перестановка самих групп\сборок (если они идентичны)

[_Ivana]

EUgeneUS, все так Вопрос что с этим делать. У меня возникают смутные ассоциации со страшными словами "изоморфизм графов", но я все еще надеюсь, что случится чудо и эта беда обойдет стороной.

[EUgeneUS]

_Ivana
Есть ли какие-то "элементы", которые присутствуют во всех схемах, но только один раз в каждой?
Примеры:
"общий провод"
"вход"
"выход"
"плюс (или минус) питания"
...

-- 29.08.2019, 11:58 --

Пока на уровне "мозгового штурма"

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

2. Для ускорения отсеивания различных топологий использовать "инварианты изоморфных графов".

[_Ivana]

Конечно. Все, что вы перечислили. Конкретные примеры схем, которые я сейчас рассматриваю, пассивные - не содержат источник питания, но все остальные уникальные элементы в них также есть в единственном экземпляре - земля, выход.

[EUgeneUS]

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

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

ИМХО, у Вас всё ещё хуже, из-за разнотипности элементов и довольно сложных правил возможных перестановок.
Но если на возможные схемы наложены какие-то ограничения, может и полегчает.

[Pavia]

_Ivana
У вас схемы аналоговые, или релейные, или цифровые?

[_Ivana]

Кстати, в качестве упрощенного примера можем рассмотреть схему, задачку про нахождение которой я размещал здесь и вы там активно участвовали :) topic130768.html

Как вы предлагаете нумеровать в ней контакты датчиков и переключателей?

-- 29.08.2019, 12:05 --

Pavia в сообщении #1412671 писал(а):

У вас схемы аналоговые, или релейные, или цифровые?

а разве есть какая-то принципиальная разница в плане топологии?

[Dmitriy40]

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

[_Ivana]

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

[EUgeneUS]

Нужна функция, которая сравнивает две схемы так:

1. На входе: две схемы, и заданное соответствие между узлами (точками соединения), но не между элементами.
2. Функция проверяет подключение всех элементов к узлам, "матчит" элементы между схемами, и выдает "схема такая же" (все элементы между схемами "сматчились")" или "схема другая".

Результат "схема такая же" однозначно говорит, что топология одинаковая, так как схемы просто совпали.
Результат "схема другая" ничего не говорит о совпадении топологий.

Далее действуем так:

1. Считаем узлы схемы, считаем элементы по типам. Если какое-то количество не совпало -- топологии разные. Если все совпали идем дальше.
2а. Каждый узел схемы описываем - перечисляем типы элементов и типы выводов элементов, подключенных к каждому узлу.
2б. Считаем хэши от описаний, сортируем список хэшей.
2в. Повторяем 2а и 2б для второй схемы.
2г. Если значения хэшей в сортированных списках где-то не совпали - топологии разные. Если совпали везде идем дальше.
3. Перебираем соответствия узлов: если хэш узла в рамках схемы уникальный, матчим узлы. Если не уникальный - перебираем варианты. Каждый вариант проверяем функцией сравнения схем. Если нашлась "такая же схема", то топология одинаковая, если все возможные варианты перестановок узлов перебрали, а такой же схемы не нашлось - топологии различаются.

[_Ivana]

В принципе для простых случаев (для части моих экспериментов хватило) я сейчас сделал сразу 3-й вариант - просто банальный перебор всех допустимых замен и перестановок в схеме, и таким образом проверяю, если вторая схема содержится в списке всех вариантов первой, полученной путем всех замен и перестановок элементов, то эти 2 схемы одной топологии. Работает, из 18 схем осталось только 3 уникальных топологии.

[EUgeneUS]

_Ivana

С небольшим различием - у меня в п3. перебираются только перестановки узлов, а "симметрии выводов элементов" "спрятаны" в функции сравнения схем и также учитываются при составлении описания узла.

Количество переборов $N = \prod\limits_{i=1}^{k}a_i!$
где $k$ - количество "групп" узлов, которые не смогли "различить", $a_i$ - количество узлов в $i$ - й группе.
Все приседания до пункта 3 - это попытка "как можно лучше различить узлы", то есть разбить их на как можно большее количество групп, содержащие как можно меньшее количество элементов.

[_Ivana]

Да, я примерно понял вашу идею. Я так же поступил в каком-то смысле - из всех 18 вариантов схем были те, в списке соединений которых было соединение 4 выводов, и те, в которых не было (максимум 3). Очевидно, что наборы уникальных топологий этих 2 групп не пересекаются, и так и получилось - первая группа дала 2 топологии, вторая 1. Но мне повезло, что сложность схем позволила во-первых перебор вариантов (пусть и с ограничениями и с отсечениями), а во-вторых проверку изоморфизма результатов простым брутфорсом за земные сроки

[EUgeneUS]

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

а во-вторых проверку изоморфизма результатов простым брутфорсом за земные сроки

есть брутфорс ($n!$) и и есть брутфорс ($2(\frac{n}{2}!)$, например).
Вполне может оказаться, что первое не посчитается за земные сроки, а второе посчитается