Программная реализация расширения построения индексов и вектор-индексов сложности

Программный комплекс «Сложность орграфов в ориентированных базисах» (далее — DCDB) предназначен для вычисления ПСС, вектор-индексов, индексов СС в базисе путей, полупутей, контуров, полуконтуров и ОЦФ орграфов с особой обработкой некоторых их подклассов (например, планарных орграфов). Он реализован в виде набора расширений АСНИ «Graph Model Workshop» (GMW).

Комплекс создан в среде Borland Developer Studio 2007 на языке Delphi. Объём авторского исходного кода DCDB — более 100 КБ, число строк исходного кода основных алгоритмов — 1288, всего компилируемых строк — 3170, объём машинного кода — 1391 КБ. Построенные модели структурной сложности хранятся в виде набора таблиц в базе данных результатов экспериментов GMW.

Параметризация построения индексов и вектор-индексов (рис. 3):

• · тип базиса для вычисления индекса, вектор-индекса CC;
• · длина максимального элемента базиса (для конструктивно перечисляемых базисов) или набор ОЦФ (для выбора базиса, задаваемого пользователем поэлементно);
• · значения сложности минимальных элементов базиса (для конструктивно перечисляемых базисов с автоматическим расчётом сложности остальных элементов) или всех элементов.

Рис. 3 Интерфейс расширения АСНИ «Graph Model Workshop»

Технологические ограничения подсистемы (обработка орграфов с числом вершин до 32 500, размер фрагмента до 255 вершин) несущественны на фоне высокой временной и емкостной сложности используемых алгоритмов.

Исследована сложность орграфов с использованием индексов, вектор-индексов и b-моделей. Расширена функциональность АСНИ «Graph Model Workshop» программным комплексом «DCDB». Получены оценки чувствительности индексов СС, вектор-индексов, ПСС и b-моделей в базисах ОЦФ для планарных, бесконтурных, планарных бесконтурных и семейств орграфов.