по графам :)

Задание
1)    Спроектировать и реализовать шаблонный класс для коллекции «Простой граф» и использовать коллекцию для решения задач для неориентированных, ориентированных и взвешенных графов.
Разработать АТД «Простой граф».
Интерфейс АТД «Простой граф» включает операции:

Конструктор ( ) по умолчанию: создает пустой L - граф с нулевым числом вершин и ребер,
Конструктор(V, D, F)  создает граф с V вершинами, без ребер, типа D(ориентированный / неориентированный), формы представления F(L- граф/M-граф),
Конструктор(V, E, D, F)  создает граф с V вершинами, с E случайными ребрами, типа
D(ориентированный / неориентированный), формы представления F (L- граф/M-граф),
Конструктор (G) - конструктор копирования создает объект – копию графа G,
Деструктор ( ) уничтожает внутренние структуры графа,
V( )    - возвращает число вершин в графе,
E( )    - возвращает число ребер в графе,
Directed( ) - возвращает тип графа (ориентированный / неориентированный)
Dense( ) - возвращает форму представления графа (L- граф / M- граф),
K( ) - возвращает коэффициент насыщенности графа,
ToListGraph()    преобразует граф к L- графу,
ToMatrixGraph()    преобразует граф к M- графу,
InsertV( )    добавляет вершину к графу и возвращает адрес дескриптора вновь созданной вершины,
DeleteV (v) -    удаляет вершину из графа, заданную адресом дескриптора v,
InsertE(v1, v2) - добавляет ребро (v1, v2) к графу, соединяющую вершины, заданные адресами дескрипторов v1 и v2, и возвращает адрес дескриптора вновь созданного ребра - e,
DeleteE (v1, v2)    удаляет ребро, соединяющее вершины, заданные адресами дескрипторов v1 и v2,
GetEdge(v1, v2)    возвращает адрес дескриптора ребра соединяющего вершины, заданные дескрипторами v1 и v2,

Разработать ассоциированные с графом типы:
АТД «Дескриптор вершины графа»
Дескриптор вершины содержит поля:
name – имя вершины,
data – данные, связанные с вершиной,
index – индекс вершины в структуре графа или -1,
Интерфейс АТД «Дескриптор вершины графа» включает операции:
Конструктор ():поле name не определено, поле data не определено,
Конструктор (name, data): name - имя вершины, data - данные, связанные с вершиной,
GetName( ) - возвращает имя вершины,
GetData( ) - возвращает данные, связанные с вершиной,
SetName(name ) – задает имя вершины,
SetData(data) – записывает данные data в дескриптор вершины.

АТД «Дескриптор ребра графа»
Дескриптор ребра содержит поля:
v1 - дескриптор вершины, из которой исходит ребро,
v2 - дескриптор вершины, в которую входит ребро,
w - вес ребра,
data - данные, связанные с ребром,
Интерфейс АТД «Дескриптор ребра графа» включает операции:
Конструктор (v1, v2): v1 - дескриптор вершины, из которой исходит ребро, v2 - дескриптор вершины, в которую входит ребро,
Конструктор (v1, v2, w ): v1 - дескриптор вершины, из которой исходит ребро, v2 - дескриптор вершины, в которую входит ребро, w - вес ребра,
Конструктор (v1, v2, w, data): v1 - дескриптор вершины, из которой исходит ребро, v2 - дескриптор вершины, в которую входит ребро, w - вес ребра, data - данные, связанные с ребром
v1( ) - возвращает дескриптор вершины, из которой исходит ребро,
v2( ) - возвращает дескриптор вершины, в которую входит ребро,
from (дескриптор вершины v) - возвращает признак исхода ребра из заданной вершины v,
other(дескриптор вершины v) - возвращает дескриптор вершины, связанной с вершиной v данным ребром,
GetW ( ) - возвращает вес ребра,
SetW (вес ребра) - изменение веса ребра,
GetData( ) - возвращает данные, связанные с ребром,
SetData(данные) - изменение данных, связанных с ребром.

АТД «Итератор вершин графа»
Интерфейс АТД «Итератор вершин графа» включает операции:
Конструктор ( ) - создает итератор вершин графа,
beg( ) - возвращает итератор, установленный на первую вершину графа,
end( ) - возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующей вершине графа,
operator * - возвращает дескриптор вершины графа, на которую указывает итератор.


АТД «Итератор ребер графа»
Интерфейс АТД «Итератор ребер графа» включает операции:
Конструктор ( ) - создает итератор ребер графа,
beg( ) - возвращает итератор, установленный на первое ребро графа,
end( ) - возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующему ребру графа,
operator * - возвращает дескриптор ребра графа, на которое указывает итератор.

АТД «Итератор исходящих ребер вершины»
Интерфейс АТД «Итератор исходящих ребер вершины» включает операции:
Конструктор (v) - создает итератор исходящих ребер графа для вершины, заданной дескриптором v,
beg( ) - возвращает итератор, установленный на первое исходящее ребро вершины,
end( ) - возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующему исходящему ребру,
operator * - возвращает дескриптор исходящего ребра вершины, на которое указывает итератор.

АТД «Итератор входящих ребер вершины»
Интерфейс АТД «Итератор входящих ребер вершины» включает операции:
Конструктор (v) - создает итератор входящих ребер графа для вершины, заданной дескриптором v,
beg( ) - возвращает итератор, установленный на первое входящее ребро вершины,
end( ) - возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующему входящему ребру,
operator * - возвращает дескриптор входящего ребра вершины, на которое указывает итератор.
Задача 1
Спроектировать и реализовать шаблонный класс для АТД «Задача 1» в соответствии с вариантом и использовать для решения задачи на неориентированном графе.

Интерфейс АТД «Задача 1» включает операции:
Конструктор (g) - создает объект задачи 1, ассоциированный с графом  g, и выполняет решение задачи для графа g,
Конструктор (T) - конструктор копирования создает копию объекта – задачи T,
Деструктор () - уничтожает внутренние структуры объекта задачи,
Set (g) – связывает объект задачи с графом g и выполняет решение задачи 1 для графа g,
Restart ( ) – повторно выполняет решение задачи 1 для графа g,
Result( ) –  возвращает результат решения задачи 1

Провести эмпирическое исследование времени и вычислительной сложности алгоритма для графов со следующими параметрами:
V = 100:
E = 1000,
E = 2500,
E = 4950.
V = 1000:
E = 10000,
E = 250000,
E = 499500.
Варианты задачи 1:
1)    сортировка ребер в порядке двухпроходного эйлерова цикла,
2)    формирование реберно-связного графа,
3)    определения остовного леса максимальной высоты, построенного методом поиска в глубину и методом поиска в ширину,
4)    определение вершин отделимости в графе,
5)    определение всех циклов,
6)    формирования двудольного графа с раскраской в два цвета,
7)    определение вершин, отстоящих на расстоянии d от заданной вершины (d – число рёбер),
8)    определение цикла максимальной длины,
9)    определение ребер – мостов в графе,
10)    определение диаметра граф связного графа,
11)    определение эйлерова цикла,
12)    формирование двусвязного графа.
Задача 2
Спроектировать и реализовать шаблонный класс для АТД «Задача 2» в соответствии с вариантом и использовать для решения задачи на ориентированном графе.

Интерфейс АТД «Задача 2» включает операции:
Конструктор (g) - создает объект задачи 2, ассоциированный с графом  g, и выполняет решение задачи для графа g,
Конструктор (T) - конструктор копирования создает копию объекта – задачи T,
Деструктор () - уничтожает внутренние структуры объекта задачи,
Set (g) – связывает объект задачи с графом g и выполняет решение задачи 2 для графа g,
Restart ( ) – повторно выполняет решение задачи 2 для графа g,
Result( ) –  возвращает результат решения задачи 2

Провести эмпирическое исследование времени и вычислительной сложности алгоритма для графов со следующими параметрами:
V = 100:
E = 1000,
E = 5000,
E = 9900.
V = 1000:
E = 10000,
E = 500000,
E = 999000.
Варианты алгоритмов:
1)    построение редуцированного графа сильносвязных компонент
2)    определение последовательности вершин на основе топологической сортировки ациклического орграфа DAG на основе очереди истоков,
3)    определение последовательности вершин на основе топологической сортировки ациклического орграфа DAG на основе поиска в глубину.
4)    вычисление транзитивного замыкания орграфа методом Уоршалла,
5)    поиск циклов, включающих заданную вершину,
6)    определение максимального цикла,
7)    построение остовного дерева графа в пределах заданной высоты за счёт добавления минимального числа рёбер,
8)    определение кратчайшего по числу ребер пути между заданной парой вершин на основе алгоритма Флойда – Уоршалла,
9)    определение гамильтонова цикла в орграфе,
10)    преобразование орграфа в ациклический орграф DAG за счет изменения ориентации обратных ребер,
11)    классификация всех рёбер относительно заданной вершины орграфа,
12)    определение последовательности вершин на основе обратной топологической сортировки ациклического орграфа DAG,

Задача 3
Спроектировать и реализовать шаблонный класс для АТД «Задача 3» в соответствии с вариантом и использовать для решения задачи на взвешенном графе.

Интерфейс АТД «Задача 3» включает операции:
    Конструктор (g) - создает объект задачи 3, ассоциированный с графом  g, и выполняет решение задачи для графа g,
Конструктор (T) - конструктор копирования создает копию объекта – задачи T,
Деструктор () - уничтожает внутренние структуры объекта задачи,
    Set (g) – связывает объект задачи с графом g и выполняет решение задачи 3 для графа g,
    Restart ( ) – повторно выполняет решение задачи 3 для графа g,
    Result( ) –  возвращает результат решения задачи 3

Провести эмпирическое исследование времени и вычислительной сложности алгоритма для графов со следующими параметрами:
V = 100:
E = 1000,
E = 2500 (граф) или 5000(орграф),
E = 4950(граф) или 9900(орграф).
V = 1000:
E = 10000,
E = 250000(граф) или 500000(орграф),
E = 499500 (граф) или 999000 (орграф).
Варианты алгоритмов:
1)    построение минимального остовного дерева взвешенного неориентированного графа методом Прима,
2)    определение радиуса и соответствующего радиусу пути взвешенного орграфа на основе алгоритма Дейкстры,
3)    приведение отрицательной весовой функции орграфа к положительной методом Джонсона,
4)    определение эксцентриситета заданной вершины взвешенного орграфа с отрицательной весовой функции на основе алгоритма Беллмана-Форда.
5)    разбиение вершин взвешенного неориентированного графа на кластеры, объединяющие вершины ребрами с длиной, большей d. Для разбиения использовать алгоритм Крускалла,
6)    определения кратчайших путей для всех пар вершин взвешенного орграфа на основе алгоритма Беллмана-Форда.
7)    определение периферии взвешенного орграфа на основе алгоритма Флойда,
8)    определение центра взвешенного орграфа на основе алгоритма Флойда,
9)    нахождения ребра (ребер), устранение которых вызывает максимальное возрастание кратчайшего пути из вершины u в вершину v во взвешенном орграфе на основе алгоритма Дейкстры,
10)    определение диаметра и пути, соответствующего диаметру, на основе алгоритма Флойда,
11)    определение списка вершин, которые лежат в пределах заданного расстояния d от заданной вершины взвешенного орграфа с отрицательной весовой функции на основе алгоритма Беллмана-Форда,
12)    определение входящих в заданную вершину кратчайших путей на основе алгоритма Дейкстры,
Методические указания.
1)    Граф реализуется в виде класса «Простой граф» и ассоциированных классов «Дескриптор вершины графа», «Дескриптор ребра графа», «Итератор вершин графа», «Итератор ребер графа», «Итератор исходящих ребер вершины», «Итератор входящих ребер вершины».
2)    Объект «Дескриптор вершины графа» реализуется в виде шаблонного класса. Параметрами шаблона являются тип, задающий имя вершины, и тип данных, связанных с вершиной.
3)    Объект «Дескриптор ребра графа» реализуется в виде шаблонного класса. Параметрами шаблона являются тип, задающий вес ребра, и тип данных, связанных с ребром.
4)    Объект «Простой граф» реализуется в виде шаблонного класса. Параметрами шаблона являются типы «Дескриптор вершины графа» и «Дескриптор ребра графа».
5)    Ассоциированные классы («Итератор вершин графа», «Итератор ребер графа», «Итератор исходящих ребер вершины», «Итератор входящих ребер вершины») реализовать, как вложенные в класс «Простой граф».
6)    Для реализации различных форм представления графа используются вспомогательные классы «L – граф» и «M – граф», вложенные в класс «Простой граф». Рекомендуется объединить эти классы в иерархию с использованием наследования и полиморфизма.
7)    Объект «Простой граф» содержит вектор дескрипторов вершин, вставленных в граф.
8)    Объект «Простой граф» содержит структуру графа в виде списков смежности (L-граф) или матрицы смежности(M-граф). Элементы списков смежности или матрицы смежности содержат дескрипторы ребер, вставленных в граф.
9)    Для согласования систем идентификации вершин в прикладной программе (имена вершин) и в объекте «Простой граф» (адреса дескрипторов вершин) рекомендуется использовать объект «Отображение имени на адрес дескриптора». Объект реализуется в виде шаблонного класса. Параметрами шаблона являются тип имени вершины графа и указатель на «Дескриптор вершины графа». Такой объект обеспечивает прямой доступ по имени вершины к адресу дескриптора вершины. Объект - отображение можно  реализовать на базе ассоциативной структуры (сбалансированное дерево, хеш-таблица), объекта  библиотеки STL - map или hash_map, где ключом является имя вершины.
10)    Для реализации задач 1 - 3, заданных в варианте задания, разработать классы – клиенты для АТД «Простой граф».
11)    Объект задачи связан с объектом графа, для которого решается задача, с помощью указателя на объект «Простой граф».
12)    Объект задачи для решения задачи использует интерфейс объекта «Простой граф» и интерфейс ассоциированных с графом объектов («Дескриптор вершины графа», «Дескриптор ребра графа», «Итератор вершин графа», «Итератор ребер графа», «Итератор исходящих ребер вершины», «Итератор входящих ребер вершины»).
13)    Объект задачи содержит все структуры, необходимые для решения задачи, сохранения результатов решения задачи.
14)    Решение задачи происходит в момент создания объекта задачи, в момент вызова методов Set (g) (связывание объекта задачи с другим графом g), вызова метода Restart( ) (повторное решение задачи  для графа).
15)    Метод Result( ) формирует результат решения задачи для клиентской программы в удобной форме, в соответствии с целью решаемой задачи.
16)    Разработать программу визуализации структуры графа (V  20). Программа должна обеспечивать визуальный просмотр структуры графа, результатов работы всех операций АТД «Простой граф» и ассоциированных объектов («Дескриптор вершины графа», «Дескриптор ребра графа», «Итератор вершин графа», «Итератор ребер графа», «Итератор исходящих ребер вершины», «Итератор входящих ребер вершины»), операций и результатов объектов задач 1 – 3. Должна обеспечиваться возможность модификации структуры графа (вставка или удаление вершин, ребер, изменение параметров, связанных с вершинами, ребрами).
17)    Для исследования времени и вычислительной сложности алгоритмов на графах с различным размером и насыщенностью разработать генератор случайного графа. Реализовать генератор, как внешнюю функцию по отношению к АТД «Простой граф».

8к и приз ваш

Amphibolin, гон, работа стоит 2 - 2.5к

Disolm, таки да, таки зависимость есть