Алгоритмы типизации

Разбиение схемы на конструктивные элементы различных типов с минимумом их номенклатуры (число типов).

Исходной схеме (функциональной, принципиальной, логической) проектируемого объекта (блока, БИС, ГИС и т.д.) ставится в соответствие граф G(X, U), где Х – отображает множество элементов; U – множество связей.

Необходимо выделить в графе множество подграфов, удовлетворяющих следующим условиям:

1. любые два подграфа G_i и G_j из этого множества должны быть изоморфны (подобны);

2. множество вершин подграфов G_i и G_j не должны пересекаться;

3. число вершин любого подграфа не должно превышать заданного;

4. суммарное число внешних выводов модулей, соответствующих вершинам каждого подграфа не должно превышать заданную величину.

Критерий типизации – минимальное число групп изоморфных подграфов.

Пример. Рассмотрим алгоритм типизации на конкретном примере. Задана схема, состоящая из элементов разных типов, и ее граф.

Рис.7. Функциональная схема

Рис.8. Граф схемы рис.7.

В скобках у вершин графа отражен тип интерпретируемого ею элемента. Матрица смежности А графа имеет вид:

Алгоритм состоит из следующих шагов:

1. Равноинвариантные вершины объединяются в группы (инвариантными являются тип элемента и степень вершины).

2. Рассматриваются все возможные объединения r^o_i U r^o_j пар групп равноинвариантных вершин и находится максимальное число изоморфных подграфов, состоящих из двух вершин.

Процесс выведения таких подграфов заключается в выборе максимального числа одинаковых (не нулевых) элементов подматрицы А [ r^o_i | r^o_j ], расположенных в разных строках и столбцах, рассматриваемой матрицы А (где А [ r^o_i | r^o_j ] – подматрица матрицы А, расположенная на пересечении строк, соответствующих вершинам a ϵ r_i , столбцов, соответствующих вершинам b ϵ r_j). Для данного примера:

Получаем три группы изоморфных подграфов r¹_i (варианты возможных независимых объединений)

где t – число вершин в изоморфном подграфе.

3. Для каждой группы r¹_i, находится исходный массив вершин M^o_i для дальнейшего рассмотрения изотропных подграфов данной группы. Такой массив составляется из вершин, не вошедших в рассматриваемую группу изоморфных подграфов, причем мощность исходного массива (число вершин, входящих в массив) должна быть не ниже двух.

Имеем:

4. Исходный массив M^o_i разбивается на группы равноинвариантных вершин r^o_ij и каждая группа изоморфных подграфов r¹_i поочередно объединяется со всеми группами r^o_ij исходного массива.

В нашем примере каждый исходный массив M^o_i содержит всего одну из инвариантных вершин, в которую он входит полностью.

Получили три группы изоморфных подграфов с числом вершин в каждом подграфе, равном трем:

5. Осуществляется дальнейшее наращивание изоморфных подграфов в группах, полученных в п.4, т.е. строим группы изоморфных графов r²_i

В примере процесс наращивания обрывается на п.4, т.к. ни для какой r²_i нет исходного массива.

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

х₁ х₂ х₃ , х₄ х₅ х₆ , х₇ х₈ х₉