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

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	LEDA
количество вершин |V|=100000, количество ребер |E|=200000*
нахождение пути минимальной длины	0.4 с	0.6 с
нахождение пути минимального суммарного веса (граф интерпретировался как неориентированный)	1.5 с (вещественные веса)	1.9 с (целые веса); 3.2 с (вещественные веса)
нахождение пути минимального суммарного веса (граф интерпретировался как ориентированный)	1.3 с (вещественные веса)	1.1 с (целые веса); 1.9 с (вещественные веса)
нахождение связных компонент	0.6 с	0.4 с
нахождение сильных компонент (граф интерпретировался как ориентированный)	0.7 с	ошибка времени исполнения (переполнение стека)
построение минимального остовного дерева	5.8 с	4.8 с

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

Литература

Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск, Наука (сибирское отделение), 1990. Mehlhorn K., Naher St. The LEDA Platform of Combinatorial and Geometric Computing. - Cambridge University Press, 1999. Цыпнятов Е. Библиотека классов для программирования задач теории графов, дипломная работа. - Нижний Новгород, 1998. Object Pascal Language Guide. Borland Delphi 3 for Windows 95 and Windows NT - Borland International Inc., 1997. 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. Mehrotra A., Trick M.A. A Column Generation Approach for Exact Graph Coloring / INFORMS Journal on Computing, 8:4, 1996. Himsolt M. GML: A Portable Graph File Format / Technical Report, Universitat Passau, 1997, cf.; см. также краткое описание GML.