2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Структура данных представления топологии электрических схем
Сообщение29.08.2019, 10:35 


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

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

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

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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 11:23 
Аватара пользователя


11/12/16
13195
уездный город Н
_Ivana в сообщении #1412649 писал(а):
перемены мест идентичных групп контактов у переключателей и т.п.


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 11:27 


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 11:47 
Аватара пользователя


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

-- 29.08.2019, 11:58 --

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

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

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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 12:00 


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 12:03 
Аватара пользователя


11/12/16
13195
уездный город Н
_Ivana в сообщении #1412662 писал(а):
меня возникают смутные ассоциации со страшными словами "изоморфизм графов", но я все еще надеюсь, что случится чудо и эта беда обойдет стороной.

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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 12:04 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 12:04 


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

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

-- 29.08.2019, 12:05 --

Pavia в сообщении #1412671 писал(а):
У вас схемы аналоговые, или релейные, или цифровые?


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 13:03 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 13:48 


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 14:18 
Аватара пользователя


11/12/16
13195
уездный город Н
Нужна функция, которая сравнивает две схемы так:

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

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

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

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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 16:30 


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 16:50 
Аватара пользователя


11/12/16
13195
уездный город Н
_Ivana

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

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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 16:54 


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

 Профиль  
                  
 
 Re: Структура данных представления топологии электрических схем
Сообщение29.08.2019, 17:02 
Аватара пользователя


11/12/16
13195
уездный город Н
_Ivana в сообщении #1412720 писал(а):
а во-вторых проверку изоморфизма результатов простым брутфорсом за земные сроки


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group