Построение общего рисунка соединений в плоских конструктивах

Введение

Будем рассматривать задачу определения пересечений соединений в плоском конструктиве. Предложенная статья является дальнейшим развитием работ [6] и [7]. В качестве основы положим один из рисунков плоской части графа принципиальной электрической схемы (рис. 1) [1, 6]. Основное внимание в данной работе будет уделено вопросу определения пересечений соединений топологического рисунка на основе выбранной плоской части графа (рис. 2) [5, 6, 12].

Рис. 1. Представление принципиальной электрической схемы в виде графа Кенига с циклическими фрагментами

Рис. 2. Топологический рисунок плоской части графа

Выделим подмножество единичных циклов для плоской части графа:

с2 = {u12,u13,u14,u40,u41,u42} → < x21,x20,x47,x7,x6,x42 >;
с16 = {u8,u9,u10,u13,u30,u31,u42} → < x6,x5,x4,x46,x15,x21,x42 >;
с46 = {u6,u7,u9,u57,u59,u60,u62,u65} → < x32,x31,x30,x29,x46,x4,x3,x43 >;
с50 = {u15,u16,u19,u28,u32,u33,u35,u52,u53,u55} → < x27,x26,x50,x17,x16,x45,x9,x8,x14,x43 >;
с58 = {u43,u44,u47,u54,u55,u76,u77,u79} → < x39,x38,x48,x23,x22,x28,x27,x43 >;
с61 = {u26,u27,u28,u64,u65,u67} → < x14,x13,x51,x33,x32,x43 >;
с78 = {u18,u19,u21,u29,u31,u33} → < x16,x15,x46,x10,x9,x45 >;
с86 = {u1,u2,u5,u14,u69,u70,u73,u82} → < x2,x1,x7,x47,x36,x35,x41,x45 >;
с92 = {u20,u21,u22,u24,u27,u58,u59,u66,u67} → < x29,x34,x33,x51,x13,x12,x11,x10,x46 >;
с107 = {u38,u39,u41,u72,u73,u74,u77} → < x20,x19,x48,x38,x37,x36,x47 >;
с108 = {u36,u37,u39,u46,u47,u49} → < x19,x18,x49,x24,x23,x48 >;
с117 = {u34,u35,u37,u48,u49,u50,u53} → < x18,x17,x50,x26,x25,x24,x49 >;
с132 = {u1,u2,u4,u6,u8,u10,u12} → < x1,x2,x3,x4,x5,x6,x7 >;
с133 = {u15,u16,u18,u20,u22,u24,u26} → < x8,x9,x10,x11,x12,x13,x14 >;
с134 = {u29,u30,u32,u34,u36,u38,u40} → < x15,x16,x17,x18,x19,x20,x21 >;
с135 = {u43,u44,u46,u48,u50,u52,u54} → < x22,x23,x24,x25,x26,x27,x28 >;
с136 = {u57,u58,u60,u62,u64,u66} → < x29,x30,x31,x32,x33,x34 >;
с137 = {u69,u70,u72,u74,u76,u78,u80} → < x35,x36,x37,x38,x39,x40,x41 >.

Обод плоской части графа:

с0 = с2 ⊕ с16 ⊕ с46 ⊕ с50 ⊕ с58 ⊕ с61 ⊕ с78 ⊕ с86 ⊕ с92 ⊕ с107 ⊕ с108 ⊕ ⊕ с117 ⊕ с132 ⊕ с133 ⊕ с134 ⊕ с135 ⊕ с136 ⊕ с137 = {u4,u5,u7,u78,u79,u80,u82} → < x41,x40,x39,x43,x3,x2,x5 >.

Плоская часть графа представлена на рис. 2.

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

соединение (х6,х35) = с2 ⊕ с86 ⊕ с107 = < x21,х20,х19,х23,х38,х37,х36,х35,х41,х2,х1,х7,х6 >;
соединение (х28,х35) = с86 ⊕ с107 ⊕ с58 = < x2,х1,х7,х20,х19,х23,х22,х28,х27,х39,х38,х37,х36,х35,х41 >;
соединение (х28,х34) = c58 ⊕ с46 ⊕ с92 = < x39,х38,х23,х22,х28,х27,х32,х31,х30,х29,х34,х33,х13,х12,х11,х10,х15,х4,х3 >;
соединение (х8,х21) = c16 ⊕ с46 ⊕ с78 ⊕ с50 = < x6,х5,х4,х3,х39,х27,х32,х31,х30,х29,х10,х9,х8,х14,х32,х27,х26,х17,х16,х15,х21 >;
соединение (х12,х25) = c117 ⊕ с50 ⊕ с61 ⊕ с92 = < x18,х17,х16,х9,х8,х14,х13,х12,х11,х10,х29,х34,х33,х32,х27,х26,х25,х24 >;
соединение (х25,х40) = c0 ⊕ с46 ⊕ с50 ⊕ с117 = < x41,х40,х39,х27,х26,х25,х24,х18,х17,х16,х9,х8,х14,х32,х31,х30,х29,х10, х15,х4,х3,х2 >;
соединение (х2,х16) = c46 ⊕ с0 ⊕ с78 = < x32,х31,х30,х29,х10,х9,х16,х15,х4,х3,х2,х41,х40,х39,х27 >;
соединение (х22,х15) = c16 ⊕ с2 ⊕ с107 ⊕ с58 = < x6,х5,х4,х15,х21,х20,х19,х23,х22,х28,х27,х39,х38,х37,х36,х7 >;
соединение (х23,х30) = c58 ⊕ с46 = < x39,х38,х23,х22,х28,х27,х32,х31,х30,х29,х10,х15,х4,х3 >;
соединение (х11,х18) = c92 ⊕ с61 ⊕ с50 ⊕ с117 = < x29,х34,х33,х32,х27,х26,х25,х24,х18,х17,х16,х9,х8,х14,х13,х12,х11,х10 >;
соединение (х1,х17) = c86 ⊕ с107 ⊕ с108 ⊕ с117 = < x2,х1,х7,х20,х19,х18,х17,х26,х25,х24,х23,х38,х37,х36,х35,х41 >
или = c86 ⊕ с46 ⊕ с0 ⊕ с78 ⊕ с50 = < x2,х1,х7,х36,х35,х41,х40,х39,х27,х32,х31,х30,х29,х10,х9,х8,х14,х32,х27, х26,х17,х16,х15,х4,х3 >;
соединение (х26,х31) = c46 ⊕ с50 = < x32,х31,х30,х29,х10,х15,х4,х3,х39,х27,х26,х17,х16,х9,х8,х14 >;
соединение (х5,х37) = c16 ⊕ с2 ⊕ с107 = < x6,х5,х4,х15,х21,х20,х19,х23,х38,х37,х36,х7 >;
соединение (х5,х13) = c16 ⊕ с46 ⊕ с92 = <x6,х5,х4,х3,х39,х27,х32,х31,х30,х29,х34,х33,х13,х12,х11,х10,х15,х21 >.

Определение пересечения соединений

В зависимости от конструктивно-технологических ограничений и цели конечного топологического рисунка (получить рисунок с минимальным числом пересечений связей, либо получить рисунок с минимальным числом переходных отверстий, либо получить минимальное количество планарных слоев) выбирают способ построения общего топологического рисунка графа. Однако в любом случае пересечение связей рассматривается как появление новых мнимых вершин на основе топологического рисунка плоской укладки графа Г. Рингеля [10].

В качестве примера рассмотрим построение общего топологического рисунка, где основой для построения является модифицированный топологический рисунок плоской части графа, представленный на рис. 3.

Рис. 3. Модифицированный рисунок плоской части графа схемы и проведение соединения (х26, х32)

После решения задачи расслоения соединений производится их укладка.

Поставим в соответствие каждому слою цвет соединения [11, 12]. Соединения 1‑го слоя раскрасим зеленым цветом, соединения 2‑го слоя — красным, а соединения 3‑го слоя обозначим фиолетовым цветом.

Сначала последовательно укладываются соединения 1‑го, зеленого слоя. При укладке изменяется вращение вершин самого соединения и вершин пересекаемых соединений согласно теории вращений вершин [10].

Для примера на рис. 3 показано изменение топологического рисунка как изменение вращения вершин в случае укладки соединения (х₂₆,х₃₂). Поскольку соединение зеленого слоя (х₂₆,х₃₂) пересекает соединение (х₂₇,х₃₁) плоской укладки, то изменяется вращение вершин х₂₆,х₂₇,х₃₁,х₃₂ и вводится новая вершина х₅₂ как результат пересечения (табл. 1).

Далее укладывается ребро (х₆,х₃₅) как ребро с меньшим числом пересечений среди зеленых соединений, и изменяется диаграмма вращений вершин (рис. 4). Соединение (х₆,х₃₅) пересекает уже два соединения плоской части графа. Это соединения (х₇,х₂₀) и (х₇,х₃₆). Соответственно, изменяется вращение вершин х₆,х₇,х₂₀,х₃₅,х₃₆ и вводятся новые вершины х₅₃,х₅₄, характеризующие пересечения соединений (табл. 2).

Рис. 4. Проведение соединения (х6,х35)

Последовательно подключаются и другие соединения зеленого цвета (рис. 5). Затем осуществляется укладка красных (рис. 6) и фиолетовых соединений (рис. 7).

Рис. 5. Проведение всех зеленых соединений (1 й слой)

Рис. 6. Проведение всех красных соединений

Рис. 7. Проведение фиолетовых соединений

После укладки всех соединений получаем вращение вершин, характеризующих топологический рисунок графа с пересечением (рис. 8).

Рис. 8. Топологический рисунок графа с пересечением ребер

Будем рассматривать топологический рисунок с определенным вращением вершин и раскраской ребер (рис. 8). Понятно, что вращение вершин индуцирует систему независимых единичных циклов.

Изменим данный топологический рисунок путем введения в определенные места дополнительных узлов (вершин), характеризующих электрические цепи (рис. 9). Тем самым подготовим топологический рисунок к перекраске ребер и введению переходных отверстий (рис. 10–12).

Рис. 9. Топологический рисунок графа с вращающимися вершинами

Рис. 10. Топологический рисунок графа с добавленными вершинами

Рис. 11. Перекраска ребер и введение переходных отверстий

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

Следующий этап — определение пересечения соединений топометрическими линиями. Здесь определяется порядок проведения соединений относительно топометрических линий. Алгоритмом поиска в ширину находим топометрические линии как минимальные пути между заданными вершинами и последовательность их пересечения с проложенными соединениями (ребрами).

Поиск путей, характеризующих топометрические линии, представлен на рис. 13–14.

Рис. 13. Примеры проведения топометрических линий (х15,х11) и (х8,х18)

Рис. 14. Проведение топометрических линий (х18,х26), (х26,х34) и (х8,х34)

После проведения топометрических линий осуществляется геометрическое проведение соединений для выбранного макродискрета, ограниченного топометрическими линиями (рис. 15). В качестве макродискрета можно выбирать любую подходящую выпуклую область. Например, треугольную, прямоугольную, квадратную или другую область (рис. 16–21).

Рис. 15. Проведение геометрических соединений исходя из выбранных топометрических соединений

Рис. 16. Совместный рисунок соединений в пространстве прямоугольников

Рис. 17. Рисунок соединений для 1 го слоя в пространстве прямоугольников

Рис. 18. Рисунок соединений для 2 го слоя в пространстве прямоугольников

Рис. 19. Совместный рисунок соединений в триангулированном пространстве

Рис. 20. Рисунок соединений в триангулированном пространстве для 1 го слоя

Рис. 21. Рисунок соединений в триангулированном пространстве для 2 го слоя

Если количество пересечений не критично, можно объединить несколько макродискретов в единую дискретную область (канал) и воспользоваться уже разработанными методами канальной трассировки (алгоритм Соукупа). В последнее время применяются методы проведения соединений в свичбоксе. Свичбокс, или «распределительный щит», — это прямоугольная область, покрытая сеткой, на любой стороне которой в узлах сетки расположены выводы цепей. Она возникает, например, при пересечении каналов. Свичбокс является обобщением канала, но размеры области менять нельзя. Задача трассировки состоит в проведении соединений между одноименными выводами по ребрам сетки в двух слоях, с переходом из одного слоя в другой в ее узлах (рис. 22).

Рис. 22. Проведение соединений в свичбоксе

Выводы

В данной работе представлен алгоритм определения пересечений и проведения соединений, удаленных в процессе планаризации. Завершением работы алгоритма является создание общего топологического рисунка графа соединений и рисунка соединений для каждого слоя относительно заданной плоской части графа (рис. 12–21).