Оглавление:
Задание. 2
1. Схема взаимосвязи объектов графа. 3
2. АТД «Простой, статический граф». 4
3. АТД итератора графа. 6
4. Определение шаблонного класса для коллекции граф. 7
5. Задача №1. 8
6. Задача №2. 9
7. Интерфейс программы. 10
Заключение. 13
Список использованных источников. 13
Приложение. 14
Задание.
Спроектировать и реализовать универсальную программную коллекцию для АТД «Простой, статический граф» и использовать коллекцию для решения задач для неориентированных, ориентированных и взвешенных графов.
Разработать АТД «Простой, статический граф».
Интерфейс АТД «Простой, статический граф» включает операции:
Конструктор пустого графа для заданных числа вершин, типа, и формы представления
V( ) опрос числа вершин в графе,
E( ) опрос числа ребер в графе,
Directed( ) опрос типа графа (ориентированный / неориентированный)
Dense опрос формы представления графа (L - граф / M- граф),
K ( ) опрос коэффициента насыщенности графа,
ToListGraph() преобразование графа к L - графу,
ToMatrixGraph() преобразование графа к M - графу,
Insert(v1,v2) вставка ребра, соединяющего вершины v1, v2,
Delete (v1,v2) удаление ребра, соединяющего вершины v1, v2,
Edge(v1,v2) опрос наличия ребра, соединяющего вершины v1, v2,
Get Edge(v1,v2) чтение параметров ребра e,
SetEdge(v1,v2) запись параметров ребра e,
Iterator(v) создание итератора смежных ребер для вершины v,
Iterator. beg( ) установка итератора на первое смежное ребро,
Iterator. off( ) опрос окончания просмотра смежных ребер,
Iterator. next( ) переход к следующему смежному ребру,
operator * доступ к данным текущего ребра.
Задача №1
Определение непересекающихся простых путей, соединяющих две заданные вершины DAG – орграфа.
Задача №2
Определение списка вершин, которые лежат в пределах заданного расстояния d от заданной вершины взвешенного орграфа с отрицательной весовой функции на основе алгоритма Беллмана-Форда.
1. Схема взаимосвязи объектов графа.
Обозначение наследования классов.
Обозначение связи объектов классов.
v Graph – Интерфейсный класс, в котором определены основные методы для работы с графом.
v LMGraph – Абстрактный класс графа.
v LGraph – Класс описания структуры – список.
v MGraph – Класс описания структуры – матрица.
v Iterator – Класс итератора позволяющий обходить по графу, является общим для списка и для матрицы.
Основным классом графа является класс – Graph. Граф может быть представлен двумя структурами – список(L-граф) и матрица(M-граф). L-граф строится на базе списков смежности: массив списков (размерность массива равна количеству вершин в графе), в списке для вершины u хранятся все ребра исходящие из заданной вершины. M-граф строится на базе матрицы смежности: квадратная матрица размером kv*kv в наличие элемента в ячейке (i, j) соответствует связи между i-той и j-той вершиной в графе. Обход по графу осуществляется через итератор, который может обходить структуру, как на базе списков смежности, так и на базе матрицы смежности. Класс Edge предназначен для хранения ребер.
2. АТД «Простой, статический граф».
Граф – это структура, состоящая из элементов, называемыми вершинами и ребер связывающие эти вершины. По типу графа различают неориентированный, ориентированный и взвешенный граф. Структура графа может быть представлена в виде списка смежности или матрицы смежности, выбор которой может производиться пользователем.
Данные:
Параметры:
KV - количество вершин графа
KE - текущее количество ребер
typeLM - структура графа (список, матрица)
typeNOW – тип графа (неориентированный, ориентированный, взвешенный)
Структура данных: список смежности либо матрица смежности
Операции:
Создание структуры графа
Вход: kv-кол-во вершин и ke-кол-во ребер
Предусловие: Количество вершин в пределах от 2 до 20, и кол-во ребер пределах Emax.
Процесс: создание пустой структуры графа
Постусловия: Нет
Генерация графа
Вход: Граф
Предусловие: Нет
Процесс: Создание случайных ребер и вставка их в граф
Выход: Граф заполнен случайными ребрами
Постусловия: Нет
Вставка нового ребра
Вход: Граф, u-номер 1 вершины, v - номер 2 вершины, w-вес
Предусловие: Заданного ребра нет в графе, номера вершин корректны, граф создан
Процесс: вставка нового ребра
Выход: True –вставка успешная, false – неправильное значение вершин или ребро уже существует
Постусловия: В граф добавлено новое ребро KE+1
Получение веса ребра
Вход: Граф, u-номер 1 вершины, v - номер 2 вершины
Предусловие: заданное ребро есть в графе, номера вершин корректны, граф создан
Процесс: поиск ребра и возврат его веса
Выход: Вес искомого ребра – вставка успешная, x<0 – неправильное значение вершин или ребра не существует
Постусловия: нет
Получение коэффициента насыщенности
Вход: Граф
Предусловие: Граф создан
Процесс: Определение коэффициента
Выход: Коэффициент
Постусловия: Нет
Удаление ребра
Вход: Граф, u-номер 1 вершины, v - номер 2 вершины, w-вес
Предусловие: заданное ребро есть в графе, номера вершин корректны, граф создан
Процесс: удаление ребра (u;v)
Выход: True – удаление успешно, false – неправильное значение вершин или ребра не существует
Постусловия: Из графа удалено ребро KE-1
Изменение веса ребра
Вход: Граф, u-номер 1 вершины, v - номер 2 вершины, w-новый вес
Предусловие: Номера вершин находятся в пределах возможного диапазона, ребро существует и граф создан
Процесс: Изменение веса ребра
Выход: True –вставка успешная, false – неправильное значение вершин или ребра не существует
Постусловия: Изменение веса ребра находящегося графе
Поиск ребра
Вход: Граф, u-номер 1 вершины, v- номер 2 вершины
Предусловие: Номера вершин находятся в пределах возможного диапазона и граф создан
Процесс: поиск ребра
Выход: True – ребро найдено, false – не выполнено предусловие
Постусловия: нет
Опрос числа вершин в графе
Вход: Граф
Предусловие: граф создан
Процесс: возврат кол-ва вершин в графе
Выход: Возврат KV, если граф не создан возврат -1
Постусловия: нет
Опрос числа рёбер в графе
Вход: Граф
Предусловие: граф создан
Процесс: возврат кол-ва ребер в графе
Выход: Возврат KE, если граф не создан возврат -1
Постусловия: нет
Опрос типа представления графа
Вход: Граф
Предусловие: граф создан
Процесс: возврат типа представления графа
Выход: Возврат 0 или 1 при удачном выполнении, или -1 если граф не создан (0- список, 1 - матрица)
Постусловия: нет
Опрос типа графа
Вход: Граф
Предусловие: граф создан
Процесс: возврат типа графа
Выход: Возврат 0, 1 или 2 при удачном выполнении, или -1 если граф не создан(0 - неориентированный,1- ориентированный, 2- взвешенный)
Постусловия: нет
Конец АТД «Простой, статический граф»
3. АТД итератора графа.
Итератор содержит необходимые методы для организации прохода по всем ребрам графа, при этом итератору не важно какая структура графа сейчас используется. В качестве единицы информации, с которой работает итератор, является ребро. Итератор каждый раз фиксирует в переменной ie то ребро, на которое установлен итератор.
Данные:
Параметры:
ie - Текущее ребро
pos - Номер вершины, где создан итератор
ind - Номер вершины, где находится итератор
Операции:
Создание итератора (конструктор)
Вход: Граф, номер вершины s
Процесс: Установка pos=s, ind=-1
Постусловия: Нет
Установка итератора на начало
Вход: Нет
Предусловие: Нет
Процесс: Определение первого ребра исходящего из вершины pos и запись его в ie
Выход: Первое ребро
Постусловия: если первое ребро не найдено ind устанавливается в -1, ie – первое ребро
Переход к следующему
Вход: нет
Предусловие: нет
Процесс: переход к следующему ребру
Выход: Следующее ребро
Постусловия: если следующее ребро не найдено ind устанавливается в -1 (итератор не действителен) и ie = NULL, в противном случае в ie будет хранится следующее ребро
Проверка вышел ли итератор за пределы
Вход: нет
Предусловие: если ind!=-1, т. е. если итератор действителен
Процесс: Проверка вышел ли итератор за границы
Выход: true – итератор в конце, false – итератор не в конце
Постусловия: нет
Конец АТД итератора графа
4. Определение шаблонного класса для коллекции граф.
template <class data_t>
class Graph
{
int typeLM; //тип представления графа (M L)
int typeNOW; //тип графа (Неориентированный, ориентированный, взвешенный)
int KE, KV; //количество вершин и ребер
data_t *tops; //количество вершин и ребер
int *CV; //массив цветов вершин
int *D,*F; //дополнительные массивы
LMGraph *g; //указатель на абстрактный класс
int stime; //счетчик, используется для обхода
int maxKV; //максимальное количество вершин в графе
public:
Graph(){} // конструктор
~Graph(){} // деструктор
bool AddEdge(Graph *&g, int u, int v, int w, int color) {} //добавление ребра а граф
bool DelEdge(Graph *&g, int u, int v) {} //удаление ребра из графа
bool FindEdge(Graph *g, int u, int v){} //поис ребра
bool ChgEdge(Graph *g, int u, int v, int w, int color){}// изменение веса ребра
bool ChgEdgeColor(Graph *&g, int u, int v, int color){}// изменение цвета ребра
bool NewLGraph(Graph *&g, int kv, int ke) {} //граф на базе списка
bool NewMGraph(Graph *&g, int kv, int ke){} //граф на ьазе матрицы
bool GenGraph(Graph *&g){} // генератор графа
Graph *DelGraph(Graph *g){} //Удаление графа
bool GraphConvert(Graph *&g) {} //Преобразование структуры графа
Graph *SetAllCV(Graph *g, int color) {} //Изменение цвета для вершин
Graph *SetAllCE(Graph *g, int color) {} //Изменение цвета для ребер
bool BFSGraph(Graph *&g, int s) {} //Обход в ширину
Graph *DFSGraph_Visit(Graph *g, int s){} //Метод рекурсивного обхода
bool DFSGraph(Graph *&g, int s) {} //Обход в глубину (не полный)
bool DFSGraph_All(Graph *&g, int s) {} //Обход в глубину (полный)
int GetTypeLM (Graph *g) {} //Получение типа представления графа
int GetTypeNOW(Graph *g) {} //Получение типа графа
int GetKE(Graph *g) {} //Получение количества ребер
int GetKV(Graph *g) {} //Получение количества вершин
int GetKoef(Graph *g) {} //Получение коэф. насыщенности
friend class Iterator;
};
class Iterator
{
LMGraph *ig; //Граф
Edge *ie; //Ребро
int pos; //Главная вершина
int ind; //Смежная вершины
public:
Iterator(LMGraph *g, int s) {} // конструктор
Edge *Begin() {} //Установка итератора в начало
Edge *Next() {} //Установка на следующий
bool Off() {} //Итератор действителен?
};
5. Задача №1.
Определение непересекающихся простых путей, соединяющих две заданные вершины
DAG - орграфа
Данные:
g - Граф, с которым будет работать алгоритм
Операции:
Конструктор
Вход: Граф, на котором будет выполнен алгоритм
Процесс: создание экземпляра входного графа
Постусловия: Нет
Запуск алгоритма
Вход: Нет
Предусловие: Нет
Процесс: Поиск путей соединяющих 2 вершины
Выход: Произведена раскраска путей
Постусловия: TRUE – алгоритм отработал успешно, FALSE - в противном случае
Описание работы алгоритма
DAG граф – ориентированный ациклический граф (directed acyclic graph), т. е. орграф не содержащий циклов.
Изначально перед поиском простых путей необходимо произвести преобразование графа в DAG граф. Для этого вызывается алгоритм преобразования, который основан на обходе в глубину. При обходе в глубину если будет обнаружено ребро ведущее в вершину, которая уже была обработана, то следовательно обнаружен цикл. В данном случае при обнаружении данного ребра будет произведено удаление его из графа.
После того как графа преобразован в DAG граф вызывается алгоритм поиска простых путей. Алгоритм поиска построен на основе обхода в глубину. В котором производится фиксирование еще и того пути который был выполнен в результате обхода. И если будет обнаружена искомая вершина, следовательно путь найден.
Теоретическая трудоемкость для данного алгоритма соответствует 2-м трудоемкостям алгоритма DFS – т. е. для списка KV+KE и для матрицы KV^2
6. Задача №2.
Определение списка вершин, которые лежат в пределах заданного расстояния d от заданной вершины взвешенного орграфа с отрицательной весовой функции на основе алгоритма Беллмана-Форд
Данные:
g - Граф, с которым будет работать алгоритм
cicle - Найден ли отрицательный цикл
Операции:
Конструктор
Вход: Граф, на котором будет выполнен алгоритм
Процесс: создание экземпляра входного графа
Постусловия: Нет
Запуск алгоритма
Вход: Нет
Предусловие: Нет
Процесс: Вызов метода выполняющего алгоритм Беллмана-Форда и определение списка вершин
Выход: У графа подкрашены вершины у которых D < заданному
Постусловия: TRUE – алгоритм отработал успешно, FALSE- в противном случае
Описание работы алгоритма
Как известно алгоритм Беллмана-Форда позволяет обнаружить кратчайшие пути с отрицательными весами ребер. Следует отметить, что поскольку в графе имеются отрицательные ребра, то возможны случаи когда алгоритм войдет в оьработку отрицательного цикла, в этом случае произойдет его зацикливание. Чтобы этого не произошло в алгоритм вставлен код по обнаружению данного отрицательного цикла. При обнаружении которого будет остановлено выполнение алгоритма и возвращено false.
Далее производится обход по всем вершинам и сравнение значение длины пути с заданным. Если значение пути меньше или равно заданному, то данная вершина подкрашивается в особый цвет.
Трудоемкость (Tтеор.) для алгоритма: для алгоритма Беллмана-Форда KV*KE + раскраска вершин KV.
7. Интерфейс программы.
Внешний вид разработанной программы представлен на рис.2
Рис.2. Внешний вид основного окна программы.
Для создания графа указываем число ребер и вершин, тип графа: неориентированный, ориентированный или взвешенный и последнее задается структура: список или матрица. Далее нажимаем «создать граф» рис.3:
Рис.3. Создание графа (тип: ориентированный, структура: список, 5 вершин, 6 ребер).
Для того чтобы воспользоваться операциями: добавление, удаления, поиска и редактирования ребер необходимо в окне V1 указать начальную координату ребра, а в окне V2 конечную. При нажатии операции «обход BFS» над вершинами указывается на каком расстоянии стоит это вершина относительно заданной, т. е. в поле V1 в нашем случае это 0, рис.4.
Рис.4 Обхода BFS в графе относительно вершины 0.
Рис.5 Обхода DFS в графе относительно вершины 0.
Для выполнения «задания 1» граф должен быть ориентированный, путь выбирается от V1 до V2. рис.6
Рис.6. Поиск простых путей от вершины 0 до 2. найдены пути 0-4-2, 0-2, 0-1-2.
Для выполнения «задания 2» граф должен быть взвешенный, путь выбирается от V1 и в поле D, V2 указывается расстояние d. И далее происходит определение списка вершин, которые лежат в пределах заданного расстояния d, по алгоритму Беллмана-Форда, рис.7
Рис.7. Определение списка вершин, от вершины 0 на расстояние 20. найдены вершины 0,1,4,2.
Заключение.
В результате выполнения данной работы была разработана программа, позволяющая выполнять набор стандартных функций для работы с графом. Разработанная программа поддерживает визуализацию графа для удобства работы с ним. Также в работе реализованы 2 алгоритма для работы с неориентированный и взвешенный типом графа.
Список использованных источников.
1) Роберт Сэджвик. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах - М: DiaSoft, 2002 г. – 496 с.
Приложение.
Листинг программы.
//================= Класс ребра ===============================
class Edge //класс ребра
{
public:
int u;
int v;
int w;
int color;
Edge *prev,*next;
public:
Edge()
{
u=-1;
v=-1;
w=-1;
color=0;
prev=NULL;
next=NULL;
}
~Edge();
};
//==================== Класс графа =====================
template <class data_t>
class Graph
{
public:
int typeLM; //тип представления графа (M L)
int typeNOW; //тип графа (Неориентированный, ориентированный, взвешенный)
int KE, KV; //количество вершин и ребер
data_t *tops; //количество вершин и ребер
int *CV; //массив цветов вершин
int *D,*F; //дополнительные массивы
LMGraph *g; //указатель на абстрактный класс
int stime; //счетчик, используется для обхода
int maxKV; //максимальное количество вершин в графе
public:
Graph()
{
maxKV=20; //устанавливаем макс. Количество вершин в графе
stime=0; //сбрасываем счетчик
tops=NULL; //сбрасываем все записи ***
typeLM =-1;
typeNOW=-1;
KE =-1; KV =-1;
D =NULL; F =NULL;
CV=NULL;
g=NULL;
}
~Graph(){}
//Методы для работы с графом
//добавление нового ребра
bool AddEdge(Graph *&g, int u, int v, int w, int color)
{
if( !g ) return false; //проверка создан ли граф
if( (u<0 || u>g->KV-1) || (v<0 || v>g->KV-1)) return false;
if( FindEdge(g, u,v) ) return false;
g->g=g->g->AddEdge(u, v,w, color);
if(g->typeNOW==0) g->g=g->g->AddEdge(v, u,w, color);
if(u!=v) g->KE=g->KE+1;
return true;
}
bool DelEdge(Graph *&g, int u, int v)
{
if( !g ) return false; //проверка создан ли граф
if( (u<0 || u>g->KV-1) || (v<0 || v>g->KV-1)) return false;
if( !FindEdge(g, u,v) ) return false;
g->g=g->g->DelEdge(u, v);
if(g->typeNOW==0) g->g=g->g->DelEdge(v, u);
g->KE=g->KE-1;
return true;
}
bool FindEdge(Graph *g, int u, int v)
{
if( !g ) return false; //проверка создан ли граф
if( (u<0 || u>g->KV-1) || (v<0 || v>g->KV-1)) return false;
//Установка итератора
Iterator A(g->g, u);
Edge *t,*f=A. Begin();
for(t=f;A. Off()!=true;t=A. Next())
{
if(t->v==v) return true;
}
return false;
}
bool ChgEdge(Graph *g, int u, int v, int w, int color)
{
if( !g ) return false; //проверка создан ли граф
//проверка правильности номеров вершин
if( (u<0 || u>g->KV-1) || (v<0 || v>g->KV-1)) return false;
if( !FindEdge(g, u,v) ) return false;
g->g=g->g->ChgEdge(u, v,w, color);
return true;
}
bool ChgEdgeColor(Graph *&g, int u, int v, int color)
{
//проверка правильности номеров вершин
if( (u<0 || u>g->KV-1) || (v<0 || v>g->KV-1)) return false;
if( !FindEdge(g, u,v) ) return false;
g->g=g->g->ChgEdgeColor(u, v,color);
return true;
}
int GetWeightEdge(Graph *&g, int u, int v)
{
if( !g ) return -1; //проверка создан ли граф
//проверка правильности номеров вершин
if( (u<0 || u>g->KV-1) || (v<0 || v>g->KV-1)) return -2;
//Установка итератора
Iterator A(g->g, u); //содание итератора
Edge *t,*f=A. Begin();
for(t=f;A. Off()!=true;t=A. Next())
{
if(t->v==v) return t->w;
}
return -1;
}
bool NewLGraph(Graph *&g, int kv, int ke)
{
if(kv<2 || kv> maxKV) return false;
int Emax=kv*(kv-1)/2;
if(ke<1 || ke>Emax) return false;
g->g=new LGraph(kv, ke);
g->g->kv=kv;
g->typeLM=0;
g->KV=kv;
g->KE=ke;
tops CV=new <data_t>[kv];
CV=new int[kv];
D=new int[kv];
F=new int[kv];
for(int j=0;j<kv;j++)
{
D[j]=-1;F[j]=-1;
CV[j]=0;
}
return true;
}
bool NewMGraph(Graph *&g, int kv, int ke)
{
if(kv<2 || kv> maxKV) return false;
int Emax=kv*(kv-1)/2;
if(ke<1 || ke>Emax) return false;
g->g=new MGraph(kv, ke);
g->g->kv=kv;
g->typeLM=1;
g->KV=kv;
g->KE=ke;
tops CV=new <data_t>[kv];
CV=new int[kv];
D=new int[kv];
F=new int[kv];
for(int j=0;j<kv;j++)
{
D[j]=-1;F[j]=-1;
CV[j]=0;
}
return true;
}
bool GenGraph(Graph *&g)
{
if(!g) return false; //проверка создан ли граф
srand(time(NULL));
//-- Генератор случайного графа----
int u, v,w, r;
int ie=0,iv=0;
int sKE=g->KE;
g->KE=0;
//генератор случайных ребер
do
{
u=rand()%g->KV; //Откуда
v=rand()%g->KV; //Куда
if(u==v) continue; //Номера не должны совпадать
w=rand()%99; //Вес
r=g->FindEdge(g, u,v); //Поиск ребра
if(r!=1)
{
g->AddEdge(g, u,v, w,0);//Добавление ребра
ie++;
}
}
while(ie<sKE);
if(g->typeLM==1) //
{
for(int i=0;i<g->KV;i++) g->AddEdge(g, i,i,0,0);
}
return true;
}
Graph *DelGraph(Graph *g) //Удаление графа
{
g->g->DelGraph();
return g;
}
bool GraphConvert(Graph *&g) //Преобразование структуры графа
{
if(!g) return false; //проверка создан ли граф
LMGraph *h; //Создание новой структуры
if(g->typeLM==0) //Если был список
{
h=new MGraph(g->KV, g->KE); //Создаем матрицу
h->kv=g->KV;
g->typeLM=1;
}
else //Если была матрица
{
h=new LGraph(g->KV, g->KE); //Создаем список
h->kv=g->KV;
g->typeLM=0;
}
for(int i=0;i<g->KV;i++) //Производим обход по вершинам
{
Iterator A(g->g, i); //содание итератора
Edge *t,*f=A. Begin(); //Установка итератора на начало
for(t=f;A. Off()!=true;t=A. Next()) //Обход по ребрам
{ //Добавление новых ребер
h=h->AddEdge(i, t->v, t->w, t->color);
}
}
g->g=h;
return true;
}
Graph *SetAllCV(Graph *g, int color) //Изменение цвета для вершин
{ //Обход по все мвершинам
for(int i=0;i<g->KV;i++) g->CV[i]=color;
return g;
}
Graph *SetAllCE(Graph *g, int color) //Изменение цвета для ребер
{
g->g=g->g->SetAllCE(color); //Вызов методя изменения цвета ребер
return g;
}
bool BFSGraph(Graph *&g, int s) //Обход в ширину
{
if(!g) return false; //проверка создан ли граф
int *Q=(int*)calloc(g->KV+1,sizeof(int));//Очередь
for(int i=0;i<g->KV;i++) //Очищение очереди и
{ //сброс параметров
if(i==s) {g->D[i]=0;g->CV[i]=1;}
else {g->D[i]=-1;g->CV[i]=0;}
}
Q[0]=s;Q[1]=-1;
int nu, son;
//Обход по смежным вершинам
while (Q[0]!=-1)
{
nu=Q[0];
//Установка итератора
Iterator A(g->g, nu); //содание итератора
Edge *t,*f=A. Begin(); //Установка итератора на начало
for(t=f;A. Off()!=true;t=A. Next())
{
if(t==NULL) break;
if(t->v==-1) break;
son=t->v;
if(g->CV[son]==0) //Вершина не обработана
{
g->CV[son]=1; //Изменяем ее цвет
g->D[son]=g->D[nu]+1;
for(int k=0;Q[k]!=-1;k++);
Q[k]=son;
Q[k+1]=-1;
}
}
for(i=0;i<g->KV;i++) Q[i]=Q[i+1];
g->CV[nu]=2;
}
if(Q) free(Q);
return true;
}
Graph *DFSGraph_Visit(Graph *g, int s) //Метод рекурсивного обхода
{
if(!g) return false; //проверка создан ли граф
stime=0;
for(int i=0;i<g->KV;i++) //Обход по всем вершинам
{g->D[i]=0;g->F[i]=0;g->CV[i]=0;}
g=g->DFSGraph_Visit(g, s); //Вызов сетода рекурсивного обхода
return g;
}
bool DFSGraph(Graph *&g, int s) //Обход в глубину (не полный)
{
stime=0;
for(int i=0;i<g->KV;i++) //Обнуление массивов
{g->D[i]=0;g->F[i]=0;g->CV[i]=0;}
g=g->DFSGraph_Visit(g, s);
return g;
}
bool DFSGraph_All(Graph *&g, int s) //Обход в глубину (полный)
{
if(!g) return false; //проверка создан ли граф
for(int i=0;i<g->KV;i++) //Обнуление массивов
{g->D[i]=0;g->F[i]=0;g->CV[i]=0;}
stime=0; //сброс счетчика
for (i=s;i<g->KV;i++) //для всех вершин [s;KV]
{
if (g->CV[i]==0) g=g->DFSGraph_Visit(g, i);
}
for (i=0;i<=s;i++) //для всех вершин [0;s]
{
if (g->CV[i]==0) g=g->DFSGraph_Visit(g, i);
}
return true;
}
int GetTypeLM (Graph *g) //Получение типа представления графа
{
if(!g) return -1; //проверка создан ли граф
return g->typeLM; //Возврат типа
}
int GetTypeNOW(Graph *g) //Получение типа графа
{
if(!g) return -1; //проверка создан ли граф
return g->typeNOW; //Возврат типа графа
}
int GetKE(Graph *g) //Получение количества ребер
{
if(!g) return -1; //проверка создан ли граф
return g->KE;
}
int GetKV(Graph *g) //Получение количества вершин
{
if(!g) return -1; //проверка создан ли граф
return g->KV; //Возврат количетства вершин
}
int GetKoef(Graph *g) //Получение коэф. насыщенности
{
if(!g) return -1; //проверка создан ли граф
return g->KV*2/g->KE; //Определение и возврат
}
friend class Iterator;
};
class Iterator
{
public:
LMGraph *ig; //Граф
Edge *ie; //Ребро
int pos; //Главная вершина
int ind; //Смежная вершины
public:
Iterator(LMGraph *g, int s) //Создание итератора
{
ig=new LMGraph; //Инициализация переменных
ig=g;ie=NULL; //графа
pos=s; //Установка вершины относительно которой работает итератор
ind=-1; //Сброс номера смежной вершины
}
Edge *Begin() //Установка итератора в начало
{
ie=new Edge; //Новое ребро
ie=ig->IBegin(ig, pos);//Вызов метода определения первого ребра
if(ie==NULL) //Первое ребро существует
{
ind=-1; //сброс номера смежной вершины
return NULL;
}
ind=ie->v; //Первое ребро найдено, запоминаем омер вершины
return ie;
}
Edge *Next() //Установка на следующий
{
ie=ig->INext(ig, ie); //Вызов метода определения след. ребра
if(ie==NULL) //Ребро найдено
{
ind=-1; //Сброс номера смежной мершины
return NULL;
}
ind=ie->v; //Записываем номер смежной вершины
return ie;
}
bool End() //Проверка конца
{
return ig->IEnd(ig, pos, ind);
}
bool Off() //Итератор действителен?
{
if(ind==-1) return true;//Да
else return false; //Нет
}
};
//============== Абстрактный класс графа =====================
class LMGraph
{
public:
int kv; //Количество вершин
public:
LMGraph(){kv=0;} //Конструктор
~LMGraph(){} //деструктор
//Методы для итератора
//Установка итератора на начало
virtual Edge *IBegin(LMGraph *lm, int pos){return NULL;}
//Продвижение итератора к след вершине
virtual Edge *INext(LMGraph *lm, Edge *p){return NULL;}
Проверка итератора на конец
virtual bool IEnd(LMGraph *lm, int pos, int ind){return NULL;}
//Методы для работы с графом
virtual void DelGraph(){}
//Добавление нового ребра
virtual LMGraph *AddEdge(int u, int v, int w, int color){return NULL;}
//Удаление ребра
virtual LMGraph *DelEdge(int u, int v){return NULL;}
//Изменение параметров ребра
virtual LMGraph *ChgEdge(int u, int v, int w, int color){return NULL;}
//Изменение цвета ребра
virtual LMGraph *ChgEdgeColor(int u, int v, int color){return NULL;}
//Изменение цвета всех ребер
virtual LMGraph *SetAllCE(int color){return NULL;}
};
//================= Класс представление - список
class ListEdge
{
public:
Edge *first,*last; //Указатель на первое и последнее ребро
Edge *el; //Текущее ребро
int kol; //Количество ребер
public:
ListEdge() //Конструктор
{
first=NULL;
last=NULL;
kol=NULL;
el=NULL;
}
bool AddNewElem(ListEdge *&list, Edge *p)//Добавление ребра в список
{
if(list==NULL) //Список пуст
{
list=new ListEdge;
list->el=p;
list->first=p;list->last=p;
kol=1;
return true;
}
if(list->first==NULL)
{
list->el=p;
list->first=p;list->last=p;
kol=1;
return true;
}
Else //Вставка в конец
{
list->last->next=p;
p->prev=list->el;
p->next=NULL;
list->last=p;
kol++;
return true;
}
}
bool DelThisElem(ListEdge *&list, int v)//Удаление ребра из списка
{
if(list->first==NULL) return false;
Edge *p=new Edge;
for(p=list->first;p!=NULL;p=p->next)
if(p->v==v) break;
if(p->prev==NULL && p->next==NULL)//Это единственное ребро {
list->first=NULL;
list->last=NULL;
el=NULL;
return true;
}
if(p->prev==NULL) //Это первое ребро
{
p=p->next;
p->prev=NULL;
list->first=p;
kol--;
return true;
}
if(p->next==NULL) //Это последнее ребро
{
p=p->prev;
p->next=NULL;
list->last=p;
kol--;
return true;
}
else //ребро в середине
{
p->prev->next=p->next;
p->next->prev=p->prev;
kol--;
return true;
}
}
};
//========== Представление графа – список =================
class LGraph: public LMGraph
{
public:
ListEdge **g; //Массив указателей на списки
public:
LGraph(){} //Конструктор
LGraph(int kv, int ke) //Конструктор
{
g=new ListEdge *[kv];
for(int j=0;j<kv;j++) g[j]=new ListEdge;
}
~LGraph() //Деструктор
{
delete []g;
}
//Методы для итератора
//Установка итератора на начало
Edge *IBegin(LMGraph *lm, int pos);
//Переход к следующему
Edge *INext(LMGraph *lm, Edge *p);
//Проверка итератора на конец
bool IEnd(LMGraph *lm, int pos, int ind);
//Методы для работы с графом
void DelGraph();
//Добавление нового ребра
LMGraph *AddEdge(int u, int v, int w, int color);
//Удаление ребра
LMGraph *DelEdge(int u, int v);
//Изменение параметров ребра
LMGraph *ChgEdge(int u, int v, int w, int color);
//Изменение цвета ребра
LMGraph *ChgEdgeColor(int u, int v, int color);
//Изменение цвета всех ребер
LMGraph *SetAllCE(int color);
};
//================= Класс представление - матрица
class MGraph: public LMGraph
{
public:
Edge ***g;
public:
MGraph(){}
MGraph(int kv, int ke)
{
g=new Edge **[kv];
for(int i=0;i<kv;i++) g[i]=NULL;
}
~MGraph()
{
delete []g;
}
//Методы для итератора
//Установка на начало
Edge *IBegin(LMGraph *lm, int pos);
//Переход к следующему
Edge *INext(LMGraph *lm, Edge *p);
//Проверка итератора на конец
bool IEnd(LMGraph *lm, int pos, int ind);
//Методы для работы с графом
void DelGraph();
//Добавление нового ребра
LMGraph *AddEdge(int u, int v, int w, int color);
//Удаление ребра
LMGraph *DelEdge(int u, int v);
//Изменение параметров ребра
LMGraph *ChgEdge(int u, int v, int w, int color);
//Изменение цвета ребра
LMGraph *ChgEdgeColor(int u, int v, int color);
//Изменение цвета всех ребер
LMGraph *SetAllCE(int color);
};
//=== Методы для итератора
//--- Установка итератора в начало ------
Edge *LGraph::IBegin(LMGraph *lm, int pos)
{
LGraph *l;l=(LGraph *)lm;
if(l->g[pos]->first==NULL) return NULL;
l->g[pos]->el=l->g[pos]->first;
return l->g[pos]->first;
}
//--- Установка итератора на следующий --
Edge *LGraph::INext(LMGraph *lm, Edge *p)
{
if(p==NULL) return NULL;
return p->next;
}
//--- Проверка итератора на конец -------
bool LGraph::IEnd(LMGraph *lm, int pos, int ind)
{
LGraph *l;l=(LGraph *)lm;
if(l->g[pos]==NULL) return true;
if(l->g[pos]->el->next==NULL)
{
return true;
}
return false;
}
//=== Методы для работы с графом ==================================================
//--- Очищение структуры графа
void LGraph::DelGraph()
{
for(int i=0;i<this->kv;i++)
{
if(this->g[i]!=NULL)
{
this->g[i]=NULL;
}
}
}
//--- Добавление нового ребра
LMGraph *LGraph::AddEdge(int u, int v, int w, int color)
{
Edge *p=new Edge; //Создание ребра
p->u=u;p->v=v;p->w=w; //Установка параметров
p->color=color;
this->g[u]->AddNewElem(this->g[u],p); //Добавление в список
return (this);
}
//--- Удаление указанного ребра
LMGraph *LGraph::DelEdge(int u, int v)
{
LGraph *l=(LGraph *)this;
l->g[u]->DelThisElem(l->g[u],v); //Удаление ребра из списка
return l;
}
//--- Изменение параметров ребра
LMGraph *LGraph::ChgEdge(int u, int v, int w, int color)
{
if(this->g[u]->first==NULL) return false;
Edge *p=new Edge;
for(p=this->g[u]->first;p!=NULL;p=p->next) //Обход по ребрам
if(p->v==v) {p->w=w;p->color=color;} //Изменение параметров ребра
return this;
}
//--- Изменение параметров ребра
LMGraph *LGraph::ChgEdgeColor(int u, int v, int color)
{
if(this->g[u]->first==NULL) return false;
Edge *p=new Edge;
for(p=this->g[u]->first;p!=NULL;p=p->next) //Обход по ребрам
if(p->v==v) {p->color=color;} //Изменение цвета ребра
return this;
}
//--- Установка цвета для ребер
LMGraph *LGraph::SetAllCE(int color)
{
for(int i=0;i<kv;i++) //Обход по всем вершинам
{
if(this->g[i]->first==NULL)
{
continue;
}
Edge *p=new Edge;
for(p=this->g[i]->first;p!=NULL;p=p->next)//Обход по ребрам
p->color=color; //Изменение цвета ребер
}
return this;
}
//=== Методы для итератора ========================================================
//--- Установка итератора в начало ------
Edge *MGraph::IBegin(LMGraph *lm, int pos)
{
MGraph *m;m=(MGraph *)lm;
if(m->g[pos]==NULL) return NULL;
for(int i=0;i<lm->kv;i++) //Обход по строке матрицы
{ //Ищем первый не пустой элемент
if(m->g[pos][i]!=NULL && i!=pos) return m->g[pos][i];
}
return NULL;
}
//--- Установка итератора на следующий --
Edge *MGraph::INext(LMGraph *lm, Edge *p)
{
if(p==NULL) return NULL;
MGraph *m;m=(MGraph *)lm;
if(m->g[p->u]==NULL) return NULL;
for(int i=p->v+1;i<lm->kv;i++) //Обход по строке
{ //Поиск следующего ребра
if(m->g[p->u][i]!=NULL && p->u!=i) return m->g[p->u][i];
}
return NULL;
}
//--- Проверка итератора на конец -------
bool MGraph::IEnd(LMGraph *lm, int pos, int ind)
{
MGraph *m;m=(MGraph *)lm;
if(m->g[pos]==NULL) return true;
for(int i=ind;i<lm->kv;i++) //Обход по строке
{ //Если найден хотябы одна не
if(m->g[pos][i]!=NULL) return false; //пустая ячейка
}
return true;
}
//=== Методы для работы с графом ==================================================
//--- Очищение структуры графа
void MGraph::DelGraph()
{
for(int i=0;i<this->kv;i++)
{
if(this->g[i]!=NULL)
{
this->g[i]=NULL;
}
}
}
//--- Добавление нового ребра
LMGraph *MGraph::AddEdge(int u, int v, int w, int color)
{
if(this->g[u]==NULL)
{
this->g[u]=new Edge *[this->kv];
for(int i=0;i<this->kv;i++)
{
if(i==v) //Найдена ячейка для вставки
{
this->g[u][i]=new Edge;//Создаем ребро
this->g[u][i]->u=u; //Устанавливаем параметры
this->g[u][i]->v=v;
this->g[u][i]->w=w;
this->g[u][i]->color=color;
}
else this->g[u][i]=NULL;
}
}
else
{
this->g[u][v]=new Edge;
this->g[u][v]->u=u;
this->g[u][v]->v=v;
this->g[u][v]->w=w;
this->g[u][v]->color=color;
}
return (this);
}
//--- Удаление указанного ребра
LMGraph *MGraph::DelEdge(int u, int v)
{
this->g[u][v]=NULL; //Очищаем нужную ячейку
return this;
}
//--- Изменение параметров ребра
LMGraph *MGraph::ChgEdge(int u, int v, int w, int color)
{
if(this->g[u][v]!=NULL)
{
this->g[u][v]->w=w;
this->g[u][v]->color=color;
}
return this;
}
//--- Изменение параметров ребра
LMGraph *MGraph::ChgEdgeColor(int u, int v, int color)
{
if(this->g[u][v]!=NULL) //Проверяем существование данного ребра
{
this->g[u][v]->color=color; //Изменяем вес
}
return this;
}
//--- Установка цвета для ребер
LMGraph *MGraph::SetAllCE(int color)
{
for(int i=0;i<this->kv;i++) //Обход по всем вершинам
{
if(this->g[i]!=NULL)
{
for(int j=0;j<this->kv;j++) //Обход по строке
{ //Изменение цвета ребер
if(this->g[i][j]!=NULL) this->g[i][j]->color=color;
}
}
}
return this;
}
//============================================================================
template <class data_t>
class Task_1
{
public:
Graph<data_t> *g;
Graph<data_t> *DFS_SWVisit(Graph<data_t> *g, int s, int fv, int c);
bool Run(int u, int v);
public:
Task_1(Graph<data_t> *tg)
{
g=tg;
masKlast=NULL;
}
Graph<data_t> *DFS_SWVisit(Graph<data_t> *g, int s, int fv, int c)
{
if(s==fv)
{
swf=true;
return g;
}
g->CV[s]=1;
Iterator A(g->g, s);
Edge *t,*f=A. Begin();
for(t=f;A. Off()!=true;t=A. Next())
{
if(g->CV[t->v]==0)
{
g=DFS_SWVisit(g, t->v, fv, c);
if(swf==true)
{
t->color=c;
return g;
}
else g->CV[t->v]=0;
}
}
return g;
}
bool Run(int k)
{
if(!g) return false;
int *Q=(int*)calloc(g->KV, sizeof(int));
for(int i=0;i<g->KV;i++) {g->D[i]=0;g->F[i]=0;g->CV[i]=0;Q[i]=-1;}
int j=0;
Iterator A(g->g, u);
Edge *t,*f=A. Begin();
int c;
for(t=f;A. Off()!=true;t=A. Next(),j++)
{
Q[j]=t->v;
c=masColors[t->v];
t->color=c;
}
g->CV[u]=1;
c=0;
for(i=0;i<j;i++)
{
swf=false;
if(g->CV[Q[i]]==0)
{
c=masColors[Q[i]];
g=DFS_SWVisit(g, Q[i],v, c);
}
if(swf==false)
{
g->ChgEdge(g, u, Q[i],0,0);
}
}
return true;
}
};
//============================================================================
template <class data_t>
Task_2(Graph<data_t> *tg)
{
g=tg;
lpath=NULL;
ldist=NULL;
}
bool Bellman_Ford(int s)
{
int i, v1,v2,w;
for(i=0;i<g->KV;i++) {g->D[i]=1000;g->F[i]=0;}
PQ *pl=new PQ;
Iterator A(g->g, s);
Edge *t,*ft=A. Begin();
for(t=ft;A. Off()!=true;t=A. Next())
{
pl=pl->Add(pl, s,t->v, t->w);
}
g->D[s]=0;
g->F[s]=-2;
while(pl->first)
{
v1=pl->v1;v2=pl->v2;w=pl->w;
pl=pl->Get(pl);
if(g->F[v2]!=0 && g->D[v1]+w<=0 )
{
cicle=false;
for(int vv=v2;vv!=-2;)
{
if(vv==v1)
{
cicle=true; return false;
}
vv=g->F[vv];
}
}
g->D[v2]=g->D[v1]+w;
g->F[v2]=v1;
Iterator A(g->g, v2);
Edge *t,*ft=A. Begin();
for(t=ft;A. Off()!=true;t=A. Next())
{
if(g->D[v2]+t->w < g->D[t->v] )
{
pl=pl->Add(pl, v2,t->v, t->w);
}
}
}
return true;
}
//=======================================================
int Run(int s, int d)
{
if(!g) return -1;
if(!Bellman_Ford(s)) return -1000;
{
if(g->D[i]<d) g->CV[i]=RGB(255,0,0);
}
}
};
