Разработка абстрактного типа данных «Простой граф», страница 3

Установка итератора на начало:

                Вход: адрес для результата(rez).

                Предусловия: существует вершина с таким номером, вершина имеет исходящие рёбра.

            Процесс: установка итератора на первое исходящее ребро.

Постусловия: итератор установлен на первое исходящее ребро, в переменную rez записан номер первой смежной вершины.

Выход: true если итератор установлен, false если не выполнено предусловие.

Получение значения данных, связанных с текущим ребром:

                Вход: нет

                Предусловия: Итератор установлен, граф взвешеный.

                Процесс: Чтение значения данных по ребру

Постусловия: нет

Выход: если значение прочитано – данные, связанные с ребром, если не выполнено предусловие генерация исключения.

Переход к следующему смежному ребру:

                Вход: адрес для результата(rez).

                Предусловия: итератор установлен не на последнее смежное ребро.

Процесс: переход к следующему смежному ребру.

Постусловия: итератор установлен на следующее смежное ребро, либо итератор не установлен, если не выполнено предусловие, в переменную rez записан номер следующей смежной вершины

Выход: true если выполнено предусловие., false если не выполнено.

Проверка состояния итератора:

                Вход: нет.

                Предусловия: нет

            Процесс: проверка состояния итератора.

Постусловия: нет.

Выход: true если итератор не установлен, false если установлен.

Клиентское описание класса итератор.

            class Iterator              //интерфейс итератора

            {

            public:

                        Iterator(graph* g,int _v)//конструктор

                        ~Iterator()//деструктор

                        bool beg(int &rez)//   установка итератора на первую смежную вершину,

                        bool off()//     опрос окончания просмотра смежных вершин,

                        bool next(int &rez)// переход к следующей смежной вершине,

                        Ed* operator*()//       доступ к данным текущего ребра.

            };

АТД класса DFS

Данные:

          Параметры:

                        Указатель на объект типа простой граф.

                        Массив результатов (содержит непересекающиеся циклы)

Операции:

Конструктор:

Вход: Указатель на объект типа граф

                Предусловия: нет.

Процесс: обход в глубину с поиском непересекающихся циклов

Постусловия: заполнен массив результатов.

Выход: нет.

Клиентское описание класса DFS.

template <class Graph>

class DFS

{

public:

      int ve;

      int ed;

      std::vector<std::vector<int> > cycles;

      DFS(Graph *G1);

      ~DFS();

}

АТД класса TSORT

Данные:

          Параметры:

                        Указатель на объект типа простой граф.

                        Массив результатов (содержит номера отсортированных вершин)

Операции:

Конструктор:

Вход: Указатель на объект типа граф

                Предусловия: граф ориентированный, не взвешеный.

Процесс: топологическая сортировка на основе очереди истоков

Постусловия: нет

Выход: нет.

Топологическая сортировка:

Вход: нет

                Предусловия: граф является DAG

Процесс: топологическая сортировка на основе очереди истоков

Постусловия: массив результатов заполнен

Выход: нет.

Преобразование графа в DAG:

Вход: нет

                Предусловия: нет

Процесс: преобразование в DAG путем инвертирования обратных ребер

Постусловия: граф преобразован в DAG

Выход: нет.

Клиентское описание класса TSORT.

template <class Graph>

class TSORT

{

public:

      int ve;

      int ed;

      std::queue<int> Qsort;

      TSORT(Graph *G1);

      ~TSORT();

      void Do();

      void ToDAG();

};

 

АТД класса SPT

Данные:

          Параметры:

                        Указатель на объект типа простой граф.

                        Счетчики обращений к вершинам и к ребрам.