Обзор существующих ОО-библиотек для работы с графами

2. Обзор существующих ОО-библиотек для работы с графами

В настоящее время существует несколько объектно-ориентированных библиотек, предоставляющих средства для работы с графами. Среди них можно отметить:

LEDA (Library of Efficient Data types and Algorithms); GTL (Graph Template Library, University of Passau); GTL (Graph Template Library, Евгений Цыпнятов, Нижний Новгород), далее - GTL (Н-Новгород).

Все эти библиотеки написаны на языке C++.

Библиотека LEDA (последняя версия - 3.8) [2] разрабатывается с 1988 г. в Институте Информатики Макса Планка (Сарабрюккен, ФРГ). Библиотека предлагает различные абстрактные типы данных (стеки, очереди, приоритетные очереди, отображения, списки, множества, разбиения, словари, интервальные множества и др.), специализированные числовые типы данных (рациональные числа, большие вещественные числа, алгебраические числа и др.), графы и вспомогательные структуры данных для работы с графами. В LEDA реализованы алгоритмы решения ряда комбинаторных, алгебраических, геометрических и теоретико-графовых задач, средства графического ввода и вывода. Институт Информатики Макса Планка бесплатно предоставляет библиотеку, включая исходные тексты, по лицензии, которая дает право использовать LEDA для академических исследований и/или обучения, но не допускает коммерческое использование.

Программный интерфейс приложений (API) для работы с графами, реализованный в LEDA, послужил образцом для создания других библиотек, в том числе GTL (University of Passau) (последняя версия - 0.3.1). В отличие от LEDA, GTL базируется на STL (C++ Standard Template Library) - мощной библиотеке классов-контейнеров и стандартных алгоритмов. Существует GTL-Java интерфейс, позволяющий Java-программам использовать графовые структуры данных и алгоритмы, реализованные в GTL. По своим функциональным возможностям и надежности GTL в настоящее время значительно уступает LEDA.

Библиотека GTL (Евгений Цыпнятов, последняя версия - 1.0R8) [3] существенно отличается от других библиотек по своей идеологии. Во-первых, библиотека поддерживает несколько внутренних представлений для графов - в виде массивов вершин и ребер, списков смежности, матрицы смежности. Существует также представление, которое объединяет все три перечисленные выше структуры хранения графов и обеспечивает их автоматическую синхронизацию. Представления реализованы в виде шаблонных классов; выбор нужного представления осуществляется при создании графа. Во-вторых, библиотека использует оригинальный способ придания необходимых "свойств" вершинам и ребрам графа (фактически, "свойства" - это атрибуты вершин и ребер) - механизм классов-"привкусов" (Flavor). Этот способ основан на использовании множественного наследования и параметризуемых (шаблонных) классов графов. Механизм "привкусов" будет рассмотрен при сравнении с аналогичными средствами библиотек LEDA и AGraph. В настоящее время GTL доступна только на платформе Win32, т.к. она существенно зависит от библиотеки MFC (Microsoft Foundation Classes).

§3. Библиотека AGraph

1. Общая характеристика

При разработке библиотеки AGraph были поставлены следующие цели:

охват широкого круга теоретико-графовых задач; простота использования; эффективность.

Библиотека AGraph написана на языке Object Pascal [4], который используется в Delphi - среде быстрой разработки приложений (RAD) фирмы Inprise (бывшей Borland), и является, вероятно, единственной развитой библиотекой для работы с графами на Object Pascal. В то же время, используемый язык программирования - не главное отличие AGraph от других библиотек. При необходимости библиотека AGraph может быть переписана с использованием таких объектно-ориентированных языков программирования, как C++, Eiffel или Java. Перенос облегчается тем обстоятельством, что AGraph не использует стандартную библиотеки классов Delphi VCL (Visual Component Library), за исключением классов исключительных ситуаций (Exception).

В пользу выбора языка Object Pascal как средства создания библиотеки для работы с графами можно привести следующие соображения. К настоящему времени разработано немало объектно-ориентированных языков программирования (ООЯП): Smalltalk, C++, Java, Object Pascal, Eiffel, Oberon-2, Modula-3 и другие. Если исходить из достоинств и недостатков самих языков программирования, не принимая во внимание распространенность языка и качество его конкретных реализаций, то одним из лучших "кандидатов", на мой взгляд, является Eiffel. Однако, если учитывать конкретную платформу, которая имеется в распоряжении (персональный компьютер на процессоре семейства Intel 386, работающий под управлением операционных систем Windows или Linux), а также практически доступные системы программирования коммерческого качества, то выбор значительно сужается: остаются языки C++, Java и Object Pascal. Языки Smalltalk и Java не подходят по соображениям эффективности. Наиболее распространенный в настоящее ООЯП, C++, поддерживается на большинстве платформ и является мощным языком программирования. Важное значение имеет существование стандарта языка C++ (к сожалению, многие компиляторы C++ не вполне соответствуют этому стандарту). К недостаткам С++ можно отнести его значительно большую, по сравнению с Object Pascal, сложность. Учитывая цели, которые ставились при разработке библиотеки AGraph, в первую очередь - соображения простоты использования, выбор был сделан в пользу Object Pascal.

Язык Object Pascal в той его версии, которая реализована в Delphi, также является развитым объектно-ориентированным языком программирования. По сравнению с ранними версиями языка (Turbo Pascal и Borland Pascal), в Object Pascal некоторые изменения претерпела объектная модель, был реализован механизм свойств объектов (object property), добавлены средства обработки исключительных ситуаций (конструкции try...except и try...finally), появилась возможность передавать в процедуры и функции переменное количество параметров (open array параметры). В Delphi 4.0 появились динамические массивы, перегрузка (overloading) процедур и функций, а также возможность указывать для параметров процедур и функций значения, принимаемые по умолчанию. Среди важных языковых средств C++, которые не реализованы в Object Pascal, следует отметить множественное наследование и механизм шаблонов (templates). Последний недостаток удалось частично преодолеть с помощью "псевдошаблонов".