БИБЛИОТЕКА СТРУКТУР ДАННЫХ И АЛГОРИТМОВ для задач САПР GRAPHLAB.

ПРОБЛЕМА

Задачи дискретной математики, и прежде всего задачи, связанные с алгоритмами на графах, очень часто встречаются в прикладных областях. Большинство таких задач требуют достаточно богатого набора структур данных: от простейших списков, стеков и очередей до графов, деревьев, множеств и более сложных структур. Универсальные системы программирования содержат обычно лишь наиболее простые структуры данных. В результате при программировании структурам данных уделяется недостаточно внимания, либо программист вынужден самостоятельно реализовывать такие структуры.

Анализ программ, написанных студентами математико-механического факультета УрГУ, показывает, что программы по курсам ВМП и САПР на 60-70% состоят из процедур, обеспечивающих поддержку структур данных (включая их ввод/вывод). При этом программы очень тяжело читать и модифицировать.

ОБЩЕЕ ОПИСАНИЕ

Для решения сформулированной проблемы служит библиотека GRAPHLAB. GRAPHLAB - это набор структур данных, открытых для использования и наращивания плюс комплект реализованных алгоритмов для классических задач сетевой оптимизации. По сути дела GRAPHLAB - это среда для разработки собственных алгоритмов в области САПР. Библиотека реализована в системе программирования Borland C++ с использованием всей мощи объектно-ориентированного подхода. Теоретической основой библиотеки является монография Тарьяна. (R.E. Tarjan "Data Structures and Network Algorithms", SIAM, 1983.)

СТРУКТУРЫ ДАННЫХ

Структуры данных составляют основу библиотеки. Далее перечислены основные структуры в порядке нарастания сложности.

Item

структура для представления элемента произвольной природы, обладающего ключом;

Vertex, Edge

структуры для представления соответственно вершин и ребер графа;

String

реализация строк;

List

двунаправленный список с реализацией как последовательного так и произвольного доступа;

Stack, Queue, Deque

структуры, представляющие стеки, очереди, деки. Все они реализованы на основе списков (List);

Graph, OrGraph, Network, UNetwork

обыкновенный граф, ориентированный граф, сеть, взвешенный граф;

DjSets

структура для представления семейства непересекающихся множеств с операцией объединения;

DHeap, LTHeap, LazyLTHeap

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

Предполагается также реализация бинарных деревьев поиска, деревьев общего вида и ряда других структур.

АЛГОРИТМЫM

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

• проверка графа на связность;
• проверка графа на двудольность;
• поиск эйлерова цикла в графе;
• поиск минимального остова (за время O(m log n) и O(m log log n) );
• поиск кратчайшего пути в бесконтурной сети.

Однако основную ценность представляют структуры данных, позволяющие просто записывать любые алгоритмы, не заботясь при этом о деталях реализации.

ДОКУМЕНТАЦИЯ

Описание системы GRAPHLAB включает:

• руководство пользователя;
• перевод задействованных глав из книги Тарьяна;
• гипертекстовая система помощи в формате Windows Help.

ПЕРСПЕКТИВЫ РАЗВИТИЯ

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