Глава 17. Свойства и типы графов. Конструктор графа принимает максимально возможное число вершин графа в каче­стве аргумента с тем, чтобы реализации могли выделять соответствующее

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

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

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