25301-1 (AGraph: библиотека классов для работы с помеченными графами), страница 2

Серьезным препятствием при написании библиотеки Vectors стало отсутствие в языке Object Pascal средств, аналогичных шаблонам C++. Очевидно, что независимая реализация векторов, отличающихся лишь типом элементов, привела бы к дублированию программного кода, многочисленным ошибкам и, в конечном счете, грозила бы потерей управляемости проектом. Решением данной проблемы могло бы стать использование внешнего макропроцессора, однако это значительно усложнило бы как разработку, так и использование библиотеки. Вместо этого в библиотеке был применен механизм "псевдошаблонов", основанный исключительно на средствах Object Pascal: директиве INCLUDE и переопределении типов.

3. Внутреннее представление графов

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

Ниже перечисленные структуры хранения графов будут рассмотрены более подробно, но перед этим необходимо сделать следующее замечание. В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на пересечении i-ой строки и j-го столбца означает существование ребра (или дуги) между i-ой и j-ой вершинами графа. В то же время, во всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин "объект" употребляется в контексте объектно-ориентированного программирования), которые различаются, по крайней мере, тем, что каждый из них занимает отдельный участок в оперативной памяти ЭВМ. Объект-вершина может содержать или не содержать какие-либо данные; объект-ребро содержит, как минимум, указатели на инцидентные ему вершины. Если подходить с технологической точки зрения, то наличие уникальных объектов-вершин и объектов-ребер повышает удобство реализации и эффективность многих алгоритмов (хотя и неэкономично в смысле расхода оперативной памяти). Существует и более фундаментальная причина: при решении прикладных задач вершины графа, а иногда и его ребра, соответствуют реальным объектам предметной области. Таким образом, структуры хранения графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только "математического" графа, но и объектов, представляющих вершины и ребра этого графа. Еще одно замечание необходимо сделать относительно использования списков и/или массивов: эти структуры данных будут считаться взаимозаменяемыми, пока изложение не коснется конкретных библиотек.

Списки вершин и ребер

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

Списки смежности

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

Матрицы смежности

Граф задается квадратной матрицей размерности NxN, где N - количество вершин в графе; на пересечении i-го столбца и j-ой строки матрицы находится либо указатель на ребро, соединяющее вершины i и j, если эти вершины инцидентны, либо nil, если они не инцидентны. Вершины могут либо храниться в отдельном списке, либо только в составе инцидентных им ребер (в случае связных графов). Это представление удобно для реализации некоторых алгоритмов, но не обеспечивает эффективное добавление и удаление вершин. Кроме того, оно является самым неэкономичным по расходу памяти (за исключением графов, в которых количество ребер значительно превышает количество вершин).

Из приведенного анализа видно, что каждая из трех рассмотренных структур хранения графов обладает своими достоинствами и недостатками. Внутреннее представление графов в универсальной библиотеке должно обеспечивать эффективную реализацию большого числа разнообразных алгоритмов, поэтому такие библиотеки используют комбинированные представления, либо, как это сделано в GTL (Н-Новгород), позволяют явно указать внутреннее представление при создании объекта-графа.

Распространенным вариантом комбинированного внутреннего представления является объединение представлений в виде списков вершин/ребер и списков смежности. Такая структура хранения обеспечивает эффективное добавление и удаление вершин и ребер, итерацию по вершинам и ребрам и, в то же время, позволяет легко определить ребра, инцидентные заданной вершине графа. Подобное представление используется в библиотеках LEDA и GTL (University of Passau).

Библиотека AGraph также использует комбинированное представление, но вместо списков применяются динамические массивы указателей, реализованные в библиотеке Vectors (класс TPointerVector, он же TClassList). Сравнение списков и динамических массивов, реализованных в Vectors, с точки зрения эффктивности выполнения различных операций приведено в следующей таблице (n обозначает количество вершин в графе, m - количество ребер):

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

Достоинством динамических массивов является быстрый доступ к элементам по индексу. Наиболее "дорогой" операцией при использовании динамических массивов является добавление элемента, поскольку в худшем случае для этого требуется выделить новый блок памяти увеличенного размера, скопировать содержимое старого блока памяти в новый и освободить старый блок, причем, по крайней мере, этап копирования имеет сложность O(n). В то же время, в среднем операция добавления вершин (ребер) в AGraph выполняется более эффективно. Это достигается за счет того, что при увеличении размера динамического массива (вектора) в библиотеке Vectors память выделяется сразу для нескольких элементов, поэтому в большинстве случаев операция добавления элемента не требует фактического изменения размера вектора.

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

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, обеспечивающая эффективное получение для объекта-вершины (объекта-ребра) его индекса в массиве вершин (ребер).

// создание графа