// определение класса CWEdge (взвешенное ребро)template class CWEdge:public CEdge,CWeightFlavor{protected: double m_dWeight;public... virtual void SetWeight(double dWeight) {m_dWeight=dWeight;} virtual double GetWeight() const {return m_dWeight;}...};// определение синонимов для вершин и ребер#define V CVertex#define E CWEdge...// создание ориентированного графа с использованием представления в виде списков смежностиCGraphAdjList xGraphAL(TRUE);// создание графа с использованием макросовVPOS xPos1,xPos2,xPos3;AL_ADDVERTEX(&xGraphAL,new V,xPos1);AL_ADDVERTEX(&xGraphAL,new V,xPos2);AL_ADDVERTEX(&xGraphAL,new V,xPos3);AL_ADDEDGE(&xGraphAL,xPos1,xPos2,new E(1.0));AL_ADDEDGE(&xGraphAL,xPos1,xPos3,new E(3.0));// доступ к весу ребра (методы GetWeight и SetWeight определены в классе CWeightFlavor)E* e = xGraphAL.GetIncidEdgeAt(xPos1, 0);double w = e->GetWeight;e->SetWeight(1.0);
Пример 5. Использование классов-"привкусов" в GTL (Н-Новгород).
Смысл в использовании Flavor проявляется, когда объект должен обладать несколькими свойствами: например, требуется "взвешенное ребро с пропускной способностью". Если использовать обычное наследование, то можно построить два различных класса, которые фактически представляют один и тот же вид ребра. Множественное наследование от классов "взвешенное ребро" и "ребро с пропускной способностью" также не помогает, т.к. при этом класс "ребро" будет наследоваться дважды. Проблема легко решается с помощью Flavors: достаточно определить Flavor "пропускная способность" и породить требуемый класс от класса TEdge и двух Flavor.
Методы привязки атрибутов к элементам графа с помощью параметризуемых классов графов, реализованные в библиотеке LEDA, или с помощью классов-"привкусов", реализованные в GTL (Н-Новгород), используют средства языка C++, которые отсутствуют в Object Pascal - шаблоны и множественное наследование. Данное обстоятельство привело к реализации в библиотеке AGraph собственного механизма поддержки атрибутов. С одной стороны, это решение является единственно возможным; с другой стороны, данный механизм является более высокоуровневым и обладает большей гибкостью, чем средства других библиотек.
Атрибуты в AGraph фактически являются переменными, определенными на элементах графа. Каждый атрибут имеет уникальное имя и тип, относящийся к одному из нескольких предопределенных типов. Типы атрибутов соответствуют основным типам языка программирования Object Pascal (Integer, Boolean, Char, Double, String и др.). Библиотека позволяет динамически создавать и уничтожать атрибуты вершин и ребер графа, причем можно создавать как общие для всех вершин (ребер) графа атрибуты, так и локальные атрибуты, определенные только для отдельных вершин (ребер) графа (см. пример 6). Доступ к атрибутам осуществляется с помощью реализованного в Object Pascal механизма свойств (property). Для каждого из поддерживаемых типов атрибутов определены свои методы доступа (AsBool, AsChar, AsInt8, AsInt16, AsInt32, AsFloat, AsString и т.д.), благодаря чему на атрибуты распространяется контроль типов. Поскольку граф "владеет" всеми своими атрибутами, их сохранение, восстановление и копирование при выполнении соответствующих операций над графом осуществляется автоматически, полностью "прозрачно" для программиста - пользователя библиотеки.
// создание графаG:=TGraph.Create;// создание общего атрибута вершин графа типа String с именем 'Name'G.CreateVertexAttr('Name', AttrString);// присваивание значений атрибуту 'Name' вершин 0 и 1 графаG[0].AsString['Name']:='Moscow';G[1].AsString['Name']:='Minsk';// уничтожение общего атрибута вершин графа с именем 'Name'G.DropVertexAttr('Name');// создание локального атрибута типа Integer с именем 'Color' для вершины 0 графа и присваивание ему значенияG[0].Local.Map.CreateAttr('Color', AttrInteger);G[0].Local.AsInteger['Color']:=1;Пример 6. Работа с атрибутами в библиотеке AGraph.
Для поддержки атрибутов в библиотеке используется собственный механизм распределения памяти, который обеспечивает высокую эффективность операций создания и уничтожения атрибутов и малый расход памяти для хранения атрибутов. Единственным недостатком данного подхода является относительно медленный доступ к атрибутам: основным способом идентификации атрибута является его имя, поэтому при каждом обращении к атрибуту по имени осуществляется поиск в таблице имен атрибутов. Библиотека AGraph предоставляет низкоуровневые средства, позволяющие значительно понизить "накладные расходы" на доступ к атрибутам (ценой некоторого усложнения программирования и потенциального снижения надежности). Так, можно один раз вычислить смещение некоторого атрибута в блоке памяти, отведенном для хранения атрибутов, для того, чтобы впоследствии обращаться к данному атрибуту по смещению, а не по имени. Благодаря этому исключается относительно медленный этап поиска в таблице имен атрибутов, но снижается надежность. Существует и другой способ повышения производительности, наиболее эффективный при интенсивном использовании атрибутов: перед началом работы некоторой процедуры следует скопировать атрибуты во временную структуру данных, которая поддерживает прямой доступ (например, динамический массив), и в дальнейшем работать с этой структурой, т.е. использовать на "локальном уровне" способ привязки данных к графу, который уже был рассмотрен. Разумеется, в этом случае необходимо помнить о синхронизации графа и временной структуры данных.
Атрибуты в библиотеке AGraph предназначены не только для привязки пользовательских данных, но и активно используются внутри самой библиотеки. Например, для ребер графа (класс TEdge) определен метод RingEdge, который проверяет, является ли ребро кольцевым (т.е. при удалении данного ребра количество связных компонент графа не увеличивается). Поскольку эта проверка является относительно дорогой операцией (время выполнения может достигать O(n+m)), нежелательно осуществлять ее при каждом обращении к методу RingEdge. В библиотеке используется следующий прием: при первом обращении к методу RingEdge библиотека выполняет соответствующий алгоритм, создает глобальный атрибут ребер графа и запоминает в нем результат работы алгоритма. До тех пор, пока граф не подвергнется изменениям, которые могут повлечь нарушение правильности запомненных значений, при последующих обращениях к методу RingEdge возвращается запомненное значение. Если граф подвергнется таким изменениям, то атрибут будет автоматически уничтожен. То же самое можно было бы сделать, добавив в класс TEdge дополнительное поле для запоминания результатов выполнения метода RingEdge, однако в таком случае при отсутствии обращений к методу RingEdge память, необходимая для хранения данного поля, расходовалась бы напрасно.
6. Поддержка различных видов графов
Одна из проблем, которые возникают при разработке универсальной библиотеки для работы с графами - как реализовать поддержку различных видов графов: ориентированных и неориентированных графов, взвешенных графов, деревьев и т.д. Вид графа, во-первых, задает набор атрибутов, которые определены для вершин и ребер данного графа (например, вес ребра для взвешенного графа или указатель на родительскую вершину для дерева), во-вторых, определяет, какие методы можно применять к этому графу, и, в-третьих, может влиять на их выполнение (например, метод поиска кратчайшего пути между заданными вершинами графа выполняется по-разному для ориентированных и неориентированных графов).
Библиотеки LEDA явно поддерживает два вида графов - ориентированные и неориентированные графы: в библиотеке определены параметризуемые классы (GRAPH и UGRAPH) для каждого из этих видов. Какие-либо средства для поддержки других видов графов не предусмотрены. Если процедура или функция являются специфичной для графа определенного вида (например, функция нахождения максимального потока в транспортной сети), то все необходимые параметры (в последнем примере - пропускные способности дуг сети) непосредственно передаются в эту процедуру или функцию (например, с помощью динамических массивов).
Библиотека GTL (Н-Новгород) также непосредственно поддерживает ориентированные и неориентированные графы - конструкторы классов-графов по умолчанию строят неориентированный граф, однако существуют варианты конструкторов с явным заданием "ориентированности" графа. В то же время, библиотека поддерживает и другие виды графов с помощью классов-"привкусов". Алгоритмы, специфичные для конкретных видов графов, реализованы как обычные функции-члены (методы) параметризуемых классов графов, но в этих функциях неявно предполагается, что классы-вершины и классы-ребра, используемые при конкретизации данного параметризуемого класса графов, предоставляют необходимые интерфейсные функции. Это, в свою очередь достигается наследованием классов-вершин и классов-ребер от соответствующих классов-"привкусов".
Библиотека AGraph предлагает высокоуровневый (хотя и не вполне универсальный) подход к решению проблемы поддержки различных видов графов, использующий возможности библиотеки по динамическому созданию и уничтожению атрибутов. В библиотеке определен набор "свойств" графа, которые соответствуют конкретным видам графов. Текущая версия библиотеки поддерживает ориентированные графы, деревья, транспортные сети, взвешенные графы, геометрические графы. Не все "свойства" являются независимыми: так, транспортная сеть всегда является ориентированным графом.
Поддержка всех "свойств" реализована в одном и том же классе TGraph, который имеет свойство (в смысле property языка Object Pascal) Features типа "множество". В процессе исполнения графу можно присвоить любую комбинацию предопределенных "свойств" графов (см. пример 7). При этом библиотека автоматически создает необходимые атрибуты и разрешает использование специфичных для данного "свойства" методов (в противном случае попытка их применения приводит к возбуждению исключительной ситуации). Благодаря тому, что библиотеке известно, к каким видам относится данный граф, операции записи графа в поток и чтения из потока, а также копирования графов отрабатываются корректно (с сохранением всей "видовой" информации), причем это не требует дополнительной работы со стороны программиста - пользователя библиотеки. Поддерживаемые нынешней версией библиотеки AGraph виды не исчерпывают всех возможных разновидностей графов, которые могут понадобиться при решении прикладных задач, однако даже этот набор способен значительно облегчить работу прикладного программиста.