Матричное представление графов из модулей

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

В настоящей работе в качестве матричного представления используется матрица вызовов. Элемент матрицы т_ц определяет количество обращений (операторов вызова) из модуля, соответствующего индексу г, к модулю, соответствующему индексу j. Кроме матрицы вызовов для дальнейшего анализа используется характеристический вектор, для каждого компонента i которого Vj = х (д',). Для графа модульной структуры, приведенной на рис. 1.1, характеристический вектор и матрица вызовов имеют вид.

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

Только один элемент характеристического вектора равен единице и только в одной строке матрицы находятся ненулевые элементы. Для рис. 1.3 векторы и матрицы записываются в таком виде:

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

В комплексе программ характеристический вектор и матрица вызовов имеют следующий вид:

Здесь yf и Mi 0 = 1, п) обозначают характеристический вектор и матрицу вызовов для графа г-й программы, входящей в комплекс.

В дальнейшем матричное представление используется для анализа операций над модульными структурами.