Рассматривается последовательно-итерационный алгоритм размещения вершин графа на плоскости с минимизацией СДС.
Задан граф (, ), отображающий схему и коммутационное пространство (КП), на котором размещен граф (дискретная сетка посадочных мест элементов на типовой плате). Необходимо разместить все вершины в узлы сетки с минимизацией суммарной длины ребер . Часть элементов размещена вручную (если нет, то первый элемент закрепляется произвольно). Разместим вершину в (+1)-ю позицию, где — число занятых позиций. Введем понятие коэффициента связности Δ()=, где — число ребер, соединяющих вершину с подмножеством ранее размещенных вершин графа, =ρ()— — число ребер, соединяющих вершину с неразмещенными вершинами графа. Тогда Δ()=2—ρ(), где ρ() — степень вершины .
Идея алгоритма заключается в определении коэффициента связности для всех неразмещенных вершин и в помещении в первую свободную позицию рядом с размещенной вершиной вершины с максимальным значением Δ(). Последовательно просматривая все вершины графа, выполняют их размещение.
Алгоритм может быть использован при размещении разногабаритных элементов, но с кратными размерами. В этом случае КП покрывается масштабной сеткой, линейные размеры дискретов которой равны минимальным размерам элементов. При размещении элемента, кратного нескольким дискретам, в список занятых позиций заносят все те элементарные позиции, которые он занимает.
Итерационная часть алгоритма заключается в парной перестановке некоторых вершин графа (, ) и оценке СДС при каждой замене. Замена целесообразна, если СДС при этом уменьшается. Среди всех вершин графа выбираются претенденты для замены. Для этого просматривается матрица расстояний , отображающая расстояния между элементами как результат размещения вершин графа схемы (, ) на дискретном поле последовательным алгоритмом. Множество инцидентных ребер * каждой вершины разбивается на два непересекающихся подмножества и . К подмножеству - (α-ребра) относятся «короткие» ребра, вес которых не превышает некоторого значения α, равного 2—3. Вес ребра отражает расстояние между связываемыми им вершинами. К подмножеству (β-ребра) относятся остальные ребра («длинные» ребра). Для каждой вершины подсчитывается разность Δi- = ||-||.
Поиск вершин, которые являются претендентами на замену, осуществляется среди тех вершин, для которых Δi>0. Первым претендентом (вершина ) является вершина, имеющая наибольшее положительное значение .
Для поиска второй вершины (вершина ) — претендента на замену с вершиной — множество всех вершин разбивается на два подмножества: (включаются, кроме вершины все отстоящие от нее на расстояние, не больше α) и (все остальные вершины). Вторая вершина выбирается среди тех вершин подмножества , которые инцидентны β-ребрам вершины . Для каждой такой вершины подсчитывается число ребер "j, инцидентных вершинам подмножества , и число ребер "j, инцидентных вершинам подмножества . Для каждой вершины подсчитывается разность σj=|"j-| — |'j|. Претендентом на замену является вершина , имеющая наибольшее значение σj-.
Перестановка вершин и приводит к уменьшению числа β-ребер и увеличению числа α-ребер, т. е. к уменьшению суммарной длины ребер графа.
Если невозможно выбрать перестановку вершин, уменьшающую суммарную длину соединений, то производят перестановку групп вершин. Для этого производится факторизация графа : разбивая все подмножество вершин на классы , , ..., , строим новый граф (мультиграф ), в котором вершинами являются классы , а ребрами — связи между классами. Далее производится перестановка групп элементов (классов), каждая из которых принимается за вершину мультиграфа.