6. Поддержка различных видов графов
Одна из проблем, которые возникают при разработке универсальной библиотеки для работы с графами - как реализовать поддержку различных видов графов: ориентированных и неориентированных графов, взвешенных графов, деревьев и т.д. Вид графа, во-первых, задает набор атрибутов, которые определены для вершин и ребер данного графа (например, вес ребра для взвешенного графа или указатель на родительскую вершину для дерева), во-вторых, определяет, какие методы можно применять к этому графу, и, в-третьих, может влиять на их выполнение (например, метод поиска кратчайшего пути между заданными вершинами графа выполняется по-разному для ориентированных и неориентированных графов).
Библиотеки LEDA явно поддерживает два вида графов - ориентированные и неориентированные графы: в библиотеке определены параметризуемые классы (GRAPH и UGRAPH) для каждого из этих видов. Какие-либо средства для поддержки других видов графов не предусмотрены. Если процедура или функция являются специфичной для графа определенного вида (например, функция нахождения максимального потока в транспортной сети), то все необходимые параметры (в последнем примере - пропускные способности дуг сети) непосредственно передаются в эту процедуру или функцию (например, с помощью динамических массивов).
Библиотека GTL (Н-Новгород) также непосредственно поддерживает ориентированные и неориентированные графы - конструкторы классов-графов по умолчанию строят неориентированный граф, однако существуют варианты конструкторов с явным заданием "ориентированности" графа. В то же время, библиотека поддерживает и другие виды графов с помощью классов-"привкусов". Алгоритмы, специфичные для конкретных видов графов, реализованы как обычные функции-члены (методы) параметризуемых классов графов, но в этих функциях неявно предполагается, что классы-вершины и классы-ребра, используемые при конкретизации данного параметризуемого класса графов, предоставляют необходимые интерфейсные функции. Это, в свою очередь достигается наследованием классов-вершин и классов-ребер от соответствующих классов-"привкусов".
Библиотека AGraph предлагает высокоуровневый (хотя и не вполне универсальный) подход к решению проблемы поддержки различных видов графов, использующий возможности библиотеки по динамическому созданию и уничтожению атрибутов. В библиотеке определен набор "свойств" графа, которые соответствуют конкретным видам графов. Текущая версия библиотеки поддерживает ориентированные графы, деревья, транспортные сети, взвешенные графы, геометрические графы. Не все "свойства" являются независимыми: так, транспортная сеть всегда является ориентированным графом.
Поддержка всех "свойств" реализована в одном и том же классе TGraph, который имеет свойство (в смысле property языка Object Pascal) Features типа "множество". В процессе исполнения графу можно присвоить любую комбинацию предопределенных "свойств" графов (см. пример 7). При этом библиотека автоматически создает необходимые атрибуты и разрешает использование специфичных для данного "свойства" методов (в противном случае попытка их применения приводит к возбуждению исключительной ситуации). Благодаря тому, что библиотеке известно, к каким видам относится данный граф, операции записи графа в поток и чтения из потока, а также копирования графов отрабатываются корректно (с сохранением всей "видовой" информации), причем это не требует дополнительной работы со стороны программиста - пользователя библиотеки. Поддерживаемые нынешней версией библиотеки AGraph виды не исчерпывают всех возможных разновидностей графов, которые могут понадобиться при решении прикладных задач, однако даже этот набор способен значительно облегчить работу прикладного программиста.
// создание взвешенного ориентированного дерева
G:=TGraph.Create;
G.Features:=[Directed, Tree, Weighted];
// добавление корня и двух листьев
V:=G.AddVertex;
// свойства (property) и методы, специфичные для деревьев
G.Root:=V;
V.AddChild;
U:=V.AddChild;
P:=U.Parent; // P = V
// свойства (property), специфичные для взвешенных графов
G.Edges[0].Weight:=5.1;
G.Edges[1].Weight:=2.2;
// метод FindMinWeightPath интерпретирует граф как ориентированный
// или неориентированный в зависимости от Features
T:=G.FindMinWeightPath(V[0], V[1], nil); // T = 2.2
Пример 7. Использование "свойств" (Features) графа.
Ниже все поддерживаемые библиотекой AGraph виды графов будут рассмотрены более подробно.
Ориентированные графы
Граф интерпретируется как ориентированный, если во множество Features графа входит флаг Directed (Directed in Features = True). Поддержка орграфов не требует хранения каких-либо дополнительных данных: один из концов ребра TEdge.V1 считается началом дуги, а другой конец TEdge.V2 - концом дуги. Многие методы класса TGraph учитывают свойство ориентированности графа; в то же время, доступны методы, которые рассматривают граф как ориентированный или неориентированный независимо от значения Features.
Деревья
Граф является деревом, если в его множество Features входит флаг Tree (Tree in Features = True). Указание на то, что граф является деревом (Directed in Features = True), позволяет упростить работу с древовидными структурами. Одна из вершин дерева помечается как корень. Для того, чтобы сделать вершину корнем, надо присвоить свойству IsRoot вершины значение True или, что то же самое, присвоить свойству Root графа указатель на эту вершину. Каждая вершина дерева, кроме корня, содержит ссылку на родительскую вершину (Parent). Для построения дерева следует использовать метод TVertex.AddChild.
Транспортные сети
Транспортная сеть (Network in Features = True) - это ориентированный граф с двумя выделенными вершинами: истоком (TGraph.NetworkSource) и стоком (TGraph.NetworkSink). Исток обладает тем свойством, что в него не входит ни одна дуга; из стока, напротив, не исходит ни одна дуга. Каждой дуге сети приписано неотрицательное вещественное число - максимальный поток, который может быть пропущен через эту дугу. Одной из наиболее известных задач на сетях является задача нахождения максимального потока в сети. В библиотеке реализовано решение этой задачи; для этого необходимо построить граф - транспортную сеть, указать с помощью свойств графа NetworkSource и NetworkSink исток и сток сети (то же самое можно сделать, присвоив значение True свойствам IsNetworkSource и IsNetworkSink соответствующих вершин сети), задать максимальные потоки на дугах сети с помощью свойства TEdge.MaxFlow и вызвать метод TGraph.FindMaxFlowThroughNetwork. Если построенная сеть корректна (IsNetworkCorrect = True), то этот метод возвращает значение максимального потока в сети и устанавливает свойства TEdge.Flow в значения потоков на дугах, при которых достигается максимальный поток.
Взвешенные графы
Взвешенный граф (Weighted in Features = True) - неориентированный или ориентированный граф, ребрам (дугам) которого поставлено в соответствие вещественное число, называемое весом. Вес ребра доступен с помощью свойства TEdge.Weight. Классической задачей на взвешенном графе является задача нахождения кратчайшего пути (пути с минимальной суммой весов входящих в этот путь ребер или дуг) между заданными вершинами, либо между всеми парами вершин. Задача нахождения кратчайшего пути между заданными вершинами во взвешенном графе с неотрицательными весами решается в библиотеке методами TGraph.FindMinWeightPathCond / TGraph.FindMinWeightPath, в которых используется алгоритм Дейкстры. В библиотеке реализован также алгоритм Флойда (TGraph.CreateMinWeightPathsMatrix), позволяющий найти кратчайшие пути между всеми парами вершин. Алгоритм Флойда применим к ографам с дугами отрицательного веса; при наличии контуров отрицательной длины алгоритм их обнаруживает.
Геометрические графы
В геометрических графах для каждой вершины графа определены вещественные координаты: двумерные (X, Y) или трехмерные (X, Y, Z) (соответственно, Geom2D или Geom3D). В настоящее время в библиотеке определен только ряд вспомогательных методов для работы с такими графами, однако в будущем планируется реализовать алгоритмы визуализации графов.
0 комментариев