Язык 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). Последний недостаток удалось частично преодолеть с помощью "псевдошаблонов".
2. Библиотека Vectors
Создание серьезных программных систем в настоящее время практически невозможно без использования вспомогательных программных компонент, реализующих базовые структуры данных и алгоритмы. Примером такой компоненты для C++ является стандартная библиотека шаблонов (С++ STL). Рассмотренные ранее С++-библиотеки для работы с графами демонстрируют различные подходы относительно создания или использования подобных базовых средств: в LEDA все необходимые структуры данных были реализованы "с нуля", библиотека GTL (University of Passau) базируется на C++ STL, библиотека GTL (Н-Новгород) основана на MFC 4.x.
При разработке библиотеки AGraph также возникла необходимость в базовых программных средствах. Поскольку готовых средств такого рода для Object Pascal не существовало (библиотека визуальных компонент Delphi VCL ориентирована на решение других задач), пришлось создавать их самостоятельно. Реализованные в ходе этой работы базовые структуры данных и алгоритмы вошли в состав библиотеки Vectors. В библиотеке реализованы векторы (динамические массивы) на базе основных типов Object Pascal, в том числе на базе всех целых и вещественных типов, логических переменных и строк. Векторы поддерживают большое количество операций; некоторые из которых являются общими для всех векторов, другие зависят от типа элементов данного вектора. В состав библиотеки входит также ряд производных и вспомогательных классов: разреженные векторы, матрицы, сбалансированные деревья поиска, приоритетные очереди, словари, потоки в памяти, файловые потоки и др.
При написании библиотеки Vectors учитывались соображения эффективности, надежности и переносимости. Многие векторные операции реализованы в нескольких вариантах: на Object Pascal и на встроенном ассемблере Object Pascal. Выбор между вариантами на Object Pascal и встроенном ассемблере осуществляется с помощью директив условной компиляции. Если программа компилируется в режиме, разрешающем использование ассемблерных вариантов, то при запуске программы средства времени исполнения автоматически определяют расширенные возможности процессора (в настоящее время проверяется поддержка MMX-инструкций) и выбирают наиболее эффективный вариант реализации той или иной операции с учетом возможностей процессора.
Для более эффективного поиска ошибок в прикладных программах библиотека поддерживает отладочный режим (также включаемый соответствующей директивой компиляции), в котором методы классов библиотеки осуществляют максимально полную проверку выполнения предусловий и корректности передаваемых им параметров. Кроме того, в отладочном режиме осуществляется контроль над операциями создания и уничтожения объектов, относящихся к классам библиотеки. Если при завершении программы какие-либо из этих объектов не уничтожаются, то пользователю выдается запрос на запись списка неуничтоженных объектов в файл.
Серьезным препятствием при написании библиотеки Vectors стало отсутствие в языке Object Pascal средств, аналогичных шаблонам C++. Очевидно, что независимая реализация векторов, отличающихся лишь типом элементов, привела бы к дублированию программного кода, многочисленным ошибкам и, в конечном счете, грозила бы потерей управляемости проектом. Решением данной проблемы могло бы стать использование внешнего макропроцессора, однако это значительно усложнило бы как разработку, так и использование библиотеки. Вместо этого в библиотеке был применен механизм "псевдошаблонов", основанный исключительно на средствах Object Pascal: директиве INCLUDE и переопределении типов.
3. Внутреннее представление графов
Существуют различные способы внутреннего представления графов в оперативной памяти ЭВМ, в том числе в виде списков (массивов) вершин и ребер, списков (массивов) смежности, матриц смежности, а также в виде комбинаций этих структур хранения. Выбор внутреннего представления оказывает решающее влияние на эффективность выполнения различных операций над графами и во многом определяет "технологию" использования той или иной библиотеки в прикладных программах.
Ниже перечисленные структуры хранения графов будут рассмотрены более подробно, но перед этим необходимо сделать следующее замечание. В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на пересечении i-ой строки и j-го столбца означает существование ребра (или дуги) между i-ой и j-ой вершинами графа. В то же время, во всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин "объект" употребляется в контексте объектно-ориентированного программирования), которые различаются, по крайней мере, тем, что каждый из них занимает отдельный участок в оперативной памяти ЭВМ. Объект-вершина может содержать или не содержать какие-либо данные; объект-ребро содержит, как минимум, указатели на инцидентные ему вершины. Если подходить с технологической точки зрения, то наличие уникальных объектов-вершин и объектов-ребер повышает удобство реализации и эффективность многих алгоритмов (хотя и неэкономично в смысле расхода оперативной памяти). Существует и более фундаментальная причина: при решении прикладных задач вершины графа, а иногда и его ребра, соответствуют реальным объектам предметной области. Таким образом, структуры хранения графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только "математического" графа, но и объектов, представляющих вершины и ребра этого графа. Еще одно замечание необходимо сделать относительно использования списков и/или массивов: эти структуры данных будут считаться взаимозаменяемыми, пока изложение не коснется конкретных библиотек.
Списки вершин и ребер
Граф представляется в виде двух списков, один из которых содержит указатели на его вершины, второй - на ребра (как всегда, каждое ребро хранит в себе указатели на инцидентные ему вершины). Данная структура хранения обеспечивает эффективное добавление в граф вершин и ребер, а также итерацию по вершинам и ребрам. В то же время, это представления неудобно, когда необходимо определить ребра, инцидентные заданной вершине графа.
Списки смежности
Граф представляется списком входящих в него вершин. В свою очередь, каждая вершина содержит список инцидентных ей ребер (или списки входящих и исходящих дуг в случае орграфов). Данное представление обеспечивает эффективное добавление в граф вершин и ребер, итерацию по вершинам графа и доступ к ребрам, инцидентным заданной вершине, но не поддерживает итерацию по ребрам графа.
Матрицы смежности
Граф задается квадратной матрицей размерности NxN, где N - количество вершин в графе; на пересечении i-го столбца и j-ой строки матрицы находится либо указатель на ребро, соединяющее вершины i и j, если эти вершины инцидентны, либо nil, если они не инцидентны. Вершины могут либо храниться в отдельном списке, либо только в составе инцидентных им ребер (в случае связных графов). Это представление удобно для реализации некоторых алгоритмов, но не обеспечивает эффективное добавление и удаление вершин. Кроме того, оно является самым неэкономичным по расходу памяти (за исключением графов, в которых количество ребер значительно превышает количество вершин).
Из приведенного анализа видно, что каждая из трех рассмотренных структур хранения графов обладает своими достоинствами и недостатками. Внутреннее представление графов в универсальной библиотеке должно обеспечивать эффективную реализацию большого числа разнообразных алгоритмов, поэтому такие библиотеки используют комбинированные представления, либо, как это сделано в GTL (Н-Новгород), позволяют явно указать внутреннее представление при создании объекта-графа.
Распространенным вариантом комбинированного внутреннего представления является объединение представлений в виде списков вершин/ребер и списков смежности. Такая структура хранения обеспечивает эффективное добавление и удаление вершин и ребер, итерацию по вершинам и ребрам и, в то же время, позволяет легко определить ребра, инцидентные заданной вершине графа. Подобное представление используется в библиотеках LEDA и GTL (University of Passau).
Библиотека AGraph также использует комбинированное представление, но вместо списков применяются динамические массивы указателей, реализованные в библиотеке Vectors (класс TPointerVector, он же TClassList). Сравнение списков и динамических массивов, реализованных в Vectors, с точки зрения эффктивности выполнения различных операций приведено в следующей таблице (n обозначает количество вершин в графе, m - количество ребер):