Программа 28. Интерфейс АТД графа

Этот интерфейс представляет собой отправную точку для реализации и тестирования алгоритмов обработки данных. Он определяет два типа данных: тривиальный тип данных Edge, включающий функцию конструктора, которая строит ребро по двум заданным вершинам, и тип данных GRAPH, определение которого дается в соответствии с методологией стандартного, независимого от представления интерфейса АТД. Конструктор GRAPH принимает два аргумента: целое, задающее число вершин, и булевское значение, которое показывает, является ли граф ориентированным или неориентированным (орграф), при этом неориентированный граф подразумевается по умолчанию.

Базовые операции, которые мы используем для обработки графов и орграфов, суть функции АТД, обеспечивающие их построение и уничтожение, функции для подсчета числа вершин и ребер, а также для добавления и удаления ребер. Класс итератора adjIterator позволяет клиентам проводить обработку любых вершин, смежных по отношению к заданной вершине.

struct Edge

{ int v, w;

Edge (int v =-1, int w = -1): v(v), w(w) { }

};

class GRAPH

{

private: // Код, зависящий от реализации

public:

GRAPH(int, bool);

-GRAPH(); int V () const;

int E() const;

bool directed() const;

int insert(Edge);

int remove(Edge);

bool edge (int, int);

class adjlterator {

public:

adjlterator (const GRAPH &, int);

int beg();

int nxt();

bool end();

};

};

АТД в программе 28 представляет собой основной механизм, который позволяет нам разрабатывать и осуществлять тестирование алгоритмов; это отнюдь не универсальный интерфейс. Как обычно, мы работаем с простейшим интерфейсом, который поддержи­вает базовые операции обработки графов, исследование которых мы намерены провес­ти. Определение такого интерфейса для использования в практических приложениях тре­бует достижения многочисленных компромиссов между простотой, эффективностью и универсальностью. Далее мы рассмотрим лишь некоторые из таких компромиссов; ос­тальные мы будем анализировать в контексте реализаций и приложений, которые будут встречаться на протяжении всей этой книги.

Конструктор графа принимает максимально возможное число вершин графа в каче­стве аргумента с тем, чтобы реализации могли выделять соответствующее пространство памяти. Мы принимаем это соглашение единственно с целью сделать программный код по возможности компактным и удобным для чтения. Более универсальный граф может включать в свой интерфейс возможность добавления и удаления как вершин, так и ре­бер; это обстоятельство налагает более строгие требования на структуры данных, исполь­зуемые для реализации АТД. Мы можем остановить свой выбор на некотором промежу­точном уровне абстракции и учитывать возможность разработки интерфейсов, поддерживающих высокоуровневые абстрактные операции для работы с графами, кото­рые можно использовать в реализациях.

В АТД графа общего вида следует учитывать параллельные ребра и петли, поскольку ничто не мешает клиентской программе вызвать функцию insert с использованием в ка­честве параметра ребра, которое уже существует (параллельное ребро), или ребра с оди­наковыми индексами вершин, его образующих. Возможно, что в некоторых приложени­ях придется запретить использование таких ребер, зато в других приложениях их включение желательно, а в некоторых приложениях они попросту игнорируются. Мани­пулирование петлями тривиально, в то время как поддержка параллельных ребер требу­ет существенных затрат ресурсов в зависимости от представления графа. В некоторых ситуациях целесообразно включить функцию АТД удалить параллельные ребра(remove parallel edges).Далее, реализации могут разрешить объединение параллельных ребер, а кли­ентские программы могут их удалять или выполнять над параллельными ребрами другие операции, если получат на то соответствующие полномочия.

Программа 29 представляет собой функцию, которая служит иллюстрацией исполь­зования класса итератора в АТД графа. Эта функция извлекает из графа некоторое мно­жество ребер и передает их функции vector из библиотеки STL (Standard Template Library — стандартная библиотека шаблонов) C++, которая выполняет построение век­тора. Сам граф есть ни что иное, как множество ребер, и нам довольно часто нужно по­лучить граф именно в такой форме, независимо от его внутреннего представления. По­рядок, в котором ребра располагаются в векторе, не играет роли и меняется от приложения к приложению. Мы используем шаблон этих функций с тем, чтобы обеспе­чить возможность использования различных реализаций АДТ графа.