Курсовая работа: AGraph: библиотека классов для работы с помеченными графами

Библиотека 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). В настоящее время в библиотеке определен только ряд вспомогательных методов для работы с такими графами, однако в будущем планируется реализовать алгоритмы визуализации графов.

7. Реализованные алгоритмы

В библиотеке AGraph реализованы алгоритмы решения многих теоретико-графовых задач, в том числе:

• поиск путей с минимальным количеством промежуточных вершин между заданными вершинами графа;
• поиск путей минимальной длины во взвешенном графе;
• определение связности графа;
• определение отношения ребра к кольцевым системам;
• нахождение компонент связности графа;
• нахождение сильных компонент ориентированного графа;
• построение матрицы связности и обобщенной матрицы связности графа;
• построение матрицы достижимости графа;
• построение матрицы расстояний графа;
• поиск максимальных независимых множеств вершин графа;
• поиск системы независимых минимальных колец графа (исключая петли), покрывающих все кольцевые ребра графа;
• построение графа, дополнительного к заданному графу;
• построение реберного графа для заданного графа;
• построение кратчайшего остовного дерева для заданного взвешенного графа;
• поиск максимального потока в транспортной сети;
• поиск хроматического числа и оптимальной вершинной раскраски графа;
• поиск эйлерова цикла в графе;
• поиск гамильтоновых циклов в орграфе;
• решение задачи почтальона для взвешенного графа с неотрицательными весами ребер;
• определение планарности графа;
• распознавание изоморфизма графов с учетом атрибутов.

В качестве источников алгоритмов использовались монографии и статьи по теории графов. При решении задач, для которых известны алгоритмы полиномиальной сложности, использовались, в основном, алгоритмы, которые являются асимптотически оптимальными среди всех известных алгоритмов решения данной задачи, или близки к оптимальным. Для некоторых из задач, решаемых библиотекой, алгоритмы полиномиальной сложности не существуют или неизвестны. В таком случае приходится использовать переборные алгоритмы, приближенные алгоритмы или алгоритмы, обеспечивающие эффективное решение для частных случаев задачи. Библиотека AGraph предоставляет ряд алгоритмов, которые относятся ко второй и третьей из этих категорий (например, приближенный алгоритм вершинной раскраски графов). В то же время, основное внимание в библиотеке уделялось реализации универсальных алгоритмов. Для некоторых "трудных" задач переборные алгоритмы были реализованы самостоятельно; для решения других в библиотеку были перенесены наиболее эффективные программные реализации, которые удалось найти (разумеется, в том случае, когда авторы программ допускают такое использование). Так, функция распознавания изоморфизма графов основана на программе, разработанной М.Венто [5]; функция нахождения хроматического числа и оптимальной вершинной раскраски графа основана на программе, разработанной М.Триком [6].

Важнейшей проблемой при разработке программного обеспечения является обеспечение его корректности. Необходимой составляющей для достижения корректности является использование корректных алгоритмов, однако правильная и эффективная реализация алгоритмов также является нетривиальной задачей. При создании библиотеки AGraph принимались различные меры для обнаружения и исправления ошибок. Во-первых, в отладочном режиме методы классов библиотек AGraph и Vectors выполняют проверки предусловий и правильности передаваемых параметров; в случае обнаружения ошибки возбуждается исключительная ситуация (exception). Во-вторых, все изменения активно тестируются как в ручном, так и в автоматическом режиме, для чего были созданы соответствующие программные тесты. Разумеется, все эти методы не гарантируют отсутствие ошибок, однако их использование позволило значительно повысить надежность библиотеки.

С технологической точки зрения алгоритмы можно разделить на две категории: первые из них реализованы в виде методов класса TGraph (модуль graphs.pas), вторые - в отдельных модулях. Реализация алгоритмов в модуле graphs.pas позволяет достичь максимальной эффективности за счет доступа к деталям внутреннего представления графа (т.е. к защищенным полям и методам классов TVertex, TEdge и TGraph), поэтому таким способом реализованы, в основном, "базовые" алгоритмы: поиск путей, определение компонент связности графа и т.д.

8. Ввод/вывод графов

Одной из проблем при создании средств работы с помеченными графами является выбор внешнего файлового формата для хранения графов. До недавнего времени каждая программная система использовала свой собственный, уникальный формат, что приводило к сложностям при организации обмена данными. Относительно недавно разработчики системы Graphlet предложили универсальный переносимый формат файла для представления помеченных графов - GML (Graph Modelling Language) [7]. В настоящее время GML-формат поддерживается многими прикладными программами и библиотеками для работы с графами.

GML-файл состоит из пар ключ-значение. Примерами ключей являются стандартные ключи graph, node и edge. Значениями могут быть целые и вещественные числа, строки и списки; в свою очередь, списки также содержат пары ключ-значение, в том числе вложенные списки. Важным достоинством формата GML является его открытость и расширяемость: любой разработчик имеет право определять свои ключи для хранения необходимой информации. В настоящее время этот формат поддерживается многими прикладными программами и библиотеками для работы с графами. Библиотека AGraph также поддерживает запись и чтение графов в GML-формате, но с некоторыми ограничениями (для хранения строк не используется кодировка ISO 8859).

Наряду с форматом GML, библиотека поддерживает запись графов в поток и чтение их из потока с использованием двоичного формата (методы TGraph.WriteToStream и TGraph.ReadFromStream). Данный способ обеспечивает более высокую скорость записи/чтения графов и приводит к созданию файлов меньшего размера, однако не является переносимым.

9. Создание специализированных классов графов

Библиотека AGraph предоставляет гибкие средства (механизм поддержки динамических атрибутов и различных видов графов), позволяющие использовать ее для решения самых разных прикладных задач. Во многих случаях пользователю хватит возможностей, предоставляемых основным классом библиотеки TGraph. В то же время, создание специализированных классов графов оправдано, если это позволяет облегчить работу с библиотекой и/или повысить эффективность прикладных программ.

Примером специализированного класса графов является класс TChemGraph, предназначенный для работы с молекулярными графами. Данный класс является непосредственным потомком класса TGraph и поддерживает работу с молекулярными графами на уровне атомов и связей (см. пример 8). Для хранения необходимых данных используются атрибуты, но в целях ускорения доступа к ним вместо методов используется доступ по смещениям. TChemGraph обеспечивает также запись и чтение молекулярных графов с использованием распространенных MOL- и SDF-форматов.

// создание молекулярного графа

G:=TChemGraph.Create;

// добавление атомов и связей

A:=G.AddAtom(CarbonAtom); // добавить 'C'

G.AddAtom(AtomTbl.SearchName('N')); // добавить 'N'

G.AddAtom(AtomTbl.SearchName('Cl')); // добавить 'Cl'

G.AddBond(A, G[1], DoubleBond);

G.AddBond(A, G[2], SingleBond);

// свойства и методы, специфичные для молекулярных графов

G.Atom[1]:=CarbonAtom; // заменить 'N' на 'C'

S1:=G.AtomName[1]; // S1 = 'C'

S2:=G.BruttoFormula; // S2 = 'С2Сl1'

Пример 8. Использование класса TChemGraph.

10. Эффективность

При создании библиотеки AGraph в качестве основных целей были поставлены обеспечение универсальности и простоты использования библиотеки. Соображения эффективности учитывались в той мере, в какой это не противоречило достижению данных целей. В то же время, решение многих прикладных задач требует обработки графов большого размера, и возможность решения этих задач на доступных вычислительных средствах напрямую зависит от эффективности реализации тех или иных алгоритмов.

Для оценки эффективности средств библиотеки AGraph было осуществлено решение ряда тестовых задач; те же задачи решались с помощью библиотеки LEDA. Поскольку данные библиотеки используют разные внутренние представления графов, различные методы привязки атрибутов к вершинам и ребрам графа, а также способы передачи параметров и возвращения результатов, прямое сравнение результатов этих испытаний не совсем корректно. Тем не менее, результаты показывают, что скоростные характеристики библиотек AGraph и LEDA являются, по крайней мере, сопоставимыми (см. таблицу 1).

При тестировании использовались следующие программные и аппаратные средства.

• ЭВМ: персональный компьютер на процессоре AMD K6-2 400 (частота системной шины 100 MHz), кэш второго уровня 512 Kb, ОЗУ 64 Mb.
• ОС: Windows 95 OSR 2.1.
• Версии библиотек: AGraph v.990915, LEDA 3.8.
• Компиляторы: для AGraph - Delphi 3.0, для LEDA - MS Visual C++ 5.0 (в обоих случаях отладочные проверки были выключены, использовалась максимальная оптимизация).

* В библиотеке AGraph хранение графа такого размера потребовало около 26 Мб оперативной памяти и 21 Мб на диске в формате GML.

Литература

1. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск, Наука (сибирское отделение), 1990.
2. Mehlhorn K., Naher St. The LEDA Platform of Combinatorial and Geometric Computing. - Cambridge University Press, 1999.
3. Цыпнятов Е. Библиотека классов для программирования задач теории графов, дипломная работа. - Нижний Новгород, 1998.
4. Object Pascal Language Guide. Borland Delphi 3 for Windows 95 and Windows NT - Borland International Inc., 1997.
5. Cordella L.P., Foggia P., Sansone C., Vento M. An Efficient Algorithm for the Inexact Matching of ARG Using a Contextual Transformational Model. / Proc. of the 13th ICPR, IEEE Computer Society Press, 1996, vol.III, pp.180-184.
6. Mehrotra A., Trick M.A. A Column Generation Approach for Exact Graph Coloring / INFORMS Journal on Computing, 8:4, 1996.
7. Himsolt M. GML: A Portable Graph File Format / Technical Report, Universitat Passau, 1997, cf.; см. также краткое описание GML.