Наряду с форматом 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).
При тестировании использовались следующие программные и аппаратные средства.
| 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.
Литература