4. Базовые средства
К базовым средствам библиотеки для работы с графами относятся средства, обеспечивающие выполнение наиболее общих операций над графом и его элементами, в том числе создание и уничтожение объектов-графов, добавление в граф вершин и ребер, удаление их из графа, итерацию по вершинам и ребрам и т.д. Базовые средства библиотеки AGraph в основном соответствуют аналогичным средствам других библиотек (см. пример 1). При создании программного интерфейса приложений (API) библиотеки AGraph первоочередное внимание уделялось обеспечению максимальных функциональных возможностей библиотеки при сохранении простоты ее использования. Имена классов библиотеки, их полей, методов и свойств (property) соответствуют распространенной англоязычной терминологии теории графов и общепринятым соглашениям языка Object Pascal.
// создание графа
G:=TGraph.Create;
// добавление вершин и ребер
V:=G.AddVertex;
G.AddVertices(5);
E:=G.AddEdge(G[0], G[1]); // ребро (v0, v1)
G.AddEdgeI(0, 3); // ребро (v0, v3)
G.AddEdges([1, 2, 2, 4]); // ребра (v1, v2) и (v2, v4)
// итерация по вершинам графа
for I:=0 to G.VertexCount - 1 do begin
V:=G.Vertices[I];
// итерация по ребрам, инцидентным заданной вершине графа
for J:=0 to V.Degree - 1 do
With V.IncidentEdge[J] do {...} ;
end;
// итерация по ребрам графа
for I:=0 to G.EdgeCount - 1 do
With G.Edges[I] do {...} ;
// удаление ребра (v0, v1)
E.Free;
// удаление ребра (v1, v2)
G.GetEdgeI(1, 2).Free;
// удаление вершины (с инцидентными ребрами)
G.Vertices[2].Free;
// уничтожение графа
G.Free;
Пример 1. Базовые операции над графами в библиотеке AGraph.
Если сравнивать библиотеки AGraph и LEDA, то можно отметить два существенных отличия. Первое из них связано с использованием динамических массивов для внутреннего представления графов в библиотеке AGraph. Массивы позволяют применять простой for-цикл для итерации по вершинам и ребрам графа. В библиотеке LEDA, использующей списки для хранения вершин и ребер, для той же цели необходимо использовать специальные макросы, а в библиотеке GTL (Passau), основанной на STL, - итераторы STL [библиотека LEDA также поддерживает "STL-style" итераторы (пока в качестве экспериментальной возможности)]. Второе отличие заключается в том, что в AGraph для удаления вершин и ребер из графа используется стандартный способ уничтожения объектов Object Pascal - вызов метода Free, в то время как в библиотеке LEDA для удаления вершин и ребер из графа приходится использовать специальные методы классов-графов.
Наиболее важным различием между библиотеками AGraph и GTL (Н-Новгород) является то, что в библиотеке GTL вершины и ребра существуют отдельно от графов и могут принадлежать сразу нескольким графам либо ни одному из графов. Для удаления неиспользуемых вершин (ребер) из памяти в GTL используется техника счетчиков ссылок (reference count): когда объект (вершина или ребро) присоединяется к графу или другой структуре (метод AddRef), счетчик увеличивается, когда удаляется из структуры (метод Release) - уменьшается. При удалении ссылки на объект из последней структуры, он должен удалить себя из памяти. Такое решение позволяет сэкономить память в тех случаях, когда графы конструируются из уже существующих объектов. Одновременно снимается проблема отождествления объектов "родственных" графов: например, в GTL порожденный подграф графа содержит те же вершины, что и сам граф (а не копии этих вершин!). В то же время, такая интерпретация вершин и ребер может затруднить использование библиотеки. Во-первых, проблемы могут возникнуть, когда с вершинами и ребрами графа связаны какие-либо атрибуты (см. ниже) - изменение атрибута вершины (ребра) одного графа может вызвать неожиданное для пользователя изменение атрибута вершины (ребра) другого графа. Во-вторых, возможность существования "автономных" вершин и ребер, на мой взгляд, противоречит интуитивному пониманию графа.
5. Использование атрибутов
Во многих случаях необходимо связать с вершинами и ребрами графа дополнительные данные - атрибуты (метки) вершин и ребер графа. Так, во взвешенном графе каждое ребро имеет целый или вещественный атрибут - вес ребра; в молекулярном графе с вершинами и ребрами может быть связан целый ряд атрибутов (для вершин - номер атома, представляемого данной вершиной графа, в периодической таблице элементов Д.И.Менделеева, заряд атома и др., для ребер - тип валентной связи, которой соответствует данное ребро).
Существует несколько способов привязки атрибутов к вершинам и ребрам графа. Наиболее простым из них является использование для хранения каждого атрибута вспомогательной структуры данных, между элементами которой, с одной стороны, и вершинами (ребрами) графа, с другой стороны, существует взаимно-однозначное соответствие (см. пример 2). В данном примере используется особенность библиотеки AGraph, обеспечивающая эффективное получение для объекта-вершины (объекта-ребра) его индекса в массиве вершин (ребер).
// создание графа
G:=TGraph.Create;
V:=G.AddVertex;
E:=G.AddEdge(V, G.AddVertex);
// создание динамического массива для хранения целого
атрибута вершин графа (первый параметр - количество
элементов, второй - значение по умолчанию)
AttrVector1:=TIntegerVector.Create(G.VertexCount, 0);
// создание динамического массива для хранения строкового
атрибута ребер графа
AttrVector2:=TStrLst.Create;
AttrVector2.Count:=G.EdgeCount;
// присваивание значений атрибутам вершины V и ребра E графа
AttrVector1[V.Index]:=1;
AttrVector2[E.Index]:='AGraph';
Пример 2. Использование динамического массива для хранения атрибутов вершин и ребер графа в библиотеке AGraph.
В библиотеке LEDA для реализации аналогичного способа привязки атрибутов к вершинам и ребрам графа необходимо использовать специальные структуры данных - классы node_array и edge_array (либо отличные от них по реализации, но эквивалентные в данном контексте классы node_map и edge_map). Это связано с тем, что в LEDA объекты-вершины и объекты-ребра хранятся в списках, а не в динамических массивах.
// создание графа
graph G;
node v = G.new_node();
edge e = G.new_edge(v, G.new_node());
// создание структуры node_arrray для хранения атрибута типа int
для вершин графа G
node_array attr1(G);
// создание структуры edge_arrray для хранения атрибута типа
string для ребер графа G
edge_array attr2(G);
// присваивание значений атрибутам вершины v и ребра e графа G
attr1[v]:=5;
attr2[e]:="Saarbruecken";
Пример 3. Использование классов node_array и edge_array для хранения атрибутов вершин и ребер графа в библиотеке LEDA.
Описанный способ хранения атрибутов подходит только для статических графов, т.к. при модификации графа соответствие между вершинами (ребрами) графа и элементами вспомогательной структуры данных теряется. Кроме того, определенные таким образом атрибуты не могут автоматически сохраняться при записи графа в поток или копироваться при копировании графов. Наиболее естественным способом "надежной" привязки атрибутов к вершинам (ребрам) графа является хранение атрибутов (или ссылок на атрибуты) непосредственно в объектах-вершинах (объектах-ребрах) графа. Библиотеки LEDA и GTL (University of Passay) предлагают для этого параметризуемый класс графов, библиотека GTL (Н-Новгород) - использование классов-"привкусов" (Flavor) и множественного наследования. Оба этих метода хорошо работают, когда набор атрибутов вершин (ребер) графа известен во время компиляции программы. В библиотеке AGraph реализованы еще более гибкие средства, позволяющие создавать и уничтожать атрибуты динамически, в процессе исполнения.
Параметризуемый класс графов в LEDA позволяет создавать графы, с каждой вершиной и каждым ребром которого связан атрибут заданного типа (см. пример 4). Доступ к таким атрибутам является в LEDA более эффективным, чем доступ к атрибутам, определенным с помощью node_array и edge_array.
// создание графа
GRAPH H;
node v = H.new_node();
edge e = H.new_edge(v, H.new_node());
// присваивание значений атрибутам вершины v и ребра e графа G
H[v]:=5;
H[e]:="Saarbruecken";
Пример 4. Использование параметризуемого класса графов LEDA.
В библиотеке GTL (Н-Новгород) для создания вершин и ребер с заданными свойствами используется механизм классов-"привкусов" (Flavor). Данный механизм может использоваться для привязки атрибутов к вершинам и ребрам графа, хотя его возможности этим не ограничиваются. Flavor - это абстрактный (чисто виртуальный в терминологии С++) класс, который применяется в качестве "добавки" при порождении новых классов с использованием множественного наследования. Flavor требует, чтобы объект обладал некоторыми свойствами, но не привносит их в объект сам. Например, класс CWeightedEdge ("взвешенное ребро") порождается от классов CEdge ("ребро") и специального класса CWeightFlavor. В классе CWeightFlavor определены два абстрактных виртуальных метода - SetWeight и GetWeight, которые должны быть перекрыты в классе CWeightedEdge. GTL предоставляет ряд "привкусов" для построения распространенных типов объектов (при необходимости пользователи могут расширить набор Flavor). Порожденные с помощью Flavor классы, в свою очередь, используются в качестве параметров шаблонных классов графов для создания классов графов, вершины и ребра которых обладают заданными свойствами (см. пример 5).
// определение класса 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 память, необходимая для хранения данного поля, расходовалась бы напрасно.
0 комментариев