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

                        Флаг содержания в графе циклов с отрицательным весом графа

                        Массив результатов (содержит спискок вершин, которые лежат в пределах заданного расстояния d от заданной вершины)

Операции:

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

Вход: Указатель на объект типа граф, номер вершины, расстояние

                Предусловия: граф не содержит отрицательных циклов.

Процесс: алгоритм Беллмана-Форда

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

Выход: нет.

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

template <class Graph>

class SPT

{

public:

      int ve;

      int ed;

      bool cycle;

      std::vector<int> res;

      SPT(Graph *G1,int s,int wmax);

      ~SPT()

};

Диаграмма взаимосвязи объектов, реализующих АТД «Граф», АТД задач 1 – 3.

представление гра-              представление гра-

фа списками смеж-              фа матрицей смеж-

ности                                     ности                        

 

              

                Абстрактный                                                       

                            базовый класс                                          определение непересекающихся

циклов

 «Простой граф»

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

«Простой итератор»                        DAG на основе очереди истоков

 

определение списка вершин, которые лежат в пределах заданного расстояния d от заданной вершины

Абстрактный                                      

                               базовый класс

итератор для спис-               итератор для мат-

ков смежности                     рицы смежности

Описание методики тестирования трудоемкости операций.

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

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

При тестировании трудоёмкости операций пользователем вводиться размер структуры данных (количество узлов и количество рёбер), после чего при помощи генератора графа, создаётся объект с заданными параметрами. Затем происходит выполнение нужного алгоритма на графе, в процессе чего подсчитывается трудоёмкость выполнения операции.

В задачах 1 и 2 усреднение не выполняется, в задаче 3 – выполняется.

Трудоёмкость подсчитывается для структур со следующими размерами:

V = 500; E = 50, 100, 1000, 5000, 10000, 50000,

V = 10000; E = 50, 100, 1000, 5000, 10000, 50000.

Задача 1

8)  определение непересекающихся циклов

Описание алгоритма:

При построении дерева обхода в глубину для каждой вершины сохраняется ее родитель в дереве. Если в дереве находится обратное ребро, то значит, существует цикл. Заносим цикл в массив. Также заносим вершины в массив использованных вершин. При нахождении следующих циклов, проверяем, что вершины этого цикла не лежат в массиве использованных вершин, этим гарантируется, что циклы не пересекаются.

В этой задаче тестировалась трудоемкость полного обхода в глубину на неорграфе.

Таблица 1