Цели работы
Спроектировать и реализовать АТД «Граф».
Задание
Спроектировать, реализовать и протестировать АТД «Граф » для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой. Граф представляет совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).
Интерфейс АТД «Граф» включает операции:
● Конструктор пустого графа для заданных числа вершин, типа, и формы представления
● V() опрос числа вершин в графе,
● E() опрос числа ребер в графе,
● Insert(v1,v2) вставка ребра, соединяющего вершины v1, v2,
● Delete (v1,v2) удаление ребра, соединяющего вершины v1, v2,
● Edge(v1,v2) опрос наличия ребра, соединяющего вершины v1, v2,
● SetEdge(v1,v2, data) задание параметров ребра,
Для визуализации коллекции интерфейс АТД «BST – дерево» включает дополнительную операцию:
● вывод структуры графа на экран,
Реализация АТД «Взвешенный орграф». Граф представлен в виде списков смежности. Алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным эксцентриситетом).
Описание АТД «Граф»
Разработанный абстрактный тип данных представляет собой структуру, основанную на списках смежности. Доступ к данным осуществляется по значению индекса вершины
Данные:
Параметры:
size_t v_count – текущее количество вершин в графе
size_t max_v_count – текущий лимит выделенной памяти
Структура данных:
Граф на списках смежности Vertex<W, V> **vertices
Операции:
Конструктор класса Graph
Вход: нет
Предусловия: нет
Процесс: создание пустого графа
Выход: нет
Постусловия: создан пустой граф
Деструктор класса Graph
Вход: нет
Предусловия: нет
Процесс: удаление коллекции
Выход: нет
Постусловия: коллекция удалена
Вставка ребра в граф
Вход: вершина, из которой исходит ребро new_start; вершина, в которую входит ребро new_end; вес ребра new_weight
Предусловия: вершины существуют; начальная и конечные вершины различаются; между заданными вершинами не существует ребра
Процесс: вставка ребра в граф
Выход: возврат булевского true в случае успешной вставки, false в случае невыполнения предусловия
Постусловия: нет
Вставка вершины в граф
Вход: данные добавляемой вершины V
Предусловия: нет
Процесс: вставка вершины в граф
Выход: нет
Постусловия: увеличение счётчика вершин, вершина добавлена в конец списка вершин
Вывод графа на экран
Вход: нет
Предусловия: нет
Процесс: вывод графа на экран
Выход: нет
Постусловия: нет
Возврат значения количества вершин
Вход: нет
Предусловия: нет
Процесс: возврат значения количества вершин
Выход: число вершин
Постусловия: нет
Проверка существования ребра между вершинами
Вход: номеравершин start и end
Предусловия: нет
Процесс: поиск ребра между вершинами
Выход: true если ребро существует, false в противном случае
Постусловия: нет
Изменение веса ребра
Вход: номеравершин start и end; вес ребра weight
Предусловия: существование вершин start и end
Процесс: изменение веса ребра
Выход: возврат булевского true при успешном изменении; false в обратном случае
Постусловия: вес ребра изменён
Удаление ребра из графа
Вход: две вершины start и end;
Предусловия: существование вершин start и end
Процесс: удаление ребра из графа
Выход: возврат булевского true при успешном удалении; false в обратном случае
Постусловия: ребро удалено из графа
Установление новых данных для вершины
Вход: индекс вершины в графе key, новые данные для вершины V
Предусловия: существование вершины в графе
Процесс: установление новых данных для вершины
Выход: возврат булевского true при успешном изменении; false в обратном случае
Постусловия: установлены новые данные для вершины
Описание алгоритма определения центра взвешенного орграфа на основе алгоритма Флойда
Алгоритм Флойда-Уоршелла последовательно вычисляет все значения 
для 
от 1 до 
. Полученные значения 
являются длинами кратчайших путей между вершинами 
На каждом шаге алгоритм генерирует матрицу 
Матрица 
содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица заполняется длинами рёбер графа.
for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i][j] = min(W[i][j], W[i][k] + W[k][j])
Сложность алгоритма
Три вложенных цикла содержат операцию, исполняемую за константное время. 
то есть алгоритм имеет кубическую сложность.
После генерации матрица, содержащей кратчайшие расстояния между всеми вершинами, для каждой вершины определяется ее эксцентриситет. Центром графа является множество вершин, имеющих минимальный эксцентриситет.
4.КлиентскоеописаниеклассаGraph:
Graph() //конструктор
~Graph() //деструктор
bool insert_edge(unsigned int new_start, unsigned int new_end, W new_weight) //вставка ребра
void add_vertex(Vnew_data) //добавление вершины
void print() //вывод коллекции на экран
size_t vertex_count() //счётчик вершин
bool has_edge(unsigned int start, unsigned int end) //проверка существования ребра
bool set_edge(unsigned int start, unsigned int end, W weight) //изменение веса ребра
bool remove_edge(unsigned int start, unsigned int end) //удаление ребра
bool set_vertex(unsigned int key, V new_data) //изменение данных вершины
Клиентское описание класса Task:
Task(); //конструктор
void find_center(); // определение центра взвешенного орграфа на основе алгоритма Флойда
Выводы
В результате проделанной работы был создан абстрактный тип данных — граф. Работоспособность класса была проверена с помощью созданной программы-меню, дающей доступ ко всем публичным методам созданного класса.
Создан класс задачи, реализующий алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным эксцентриситетом).
Приложение А
Исходный код класса
Graph.h
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <vector>
using namespace std;
/*
1) Реализация АТД «Взвешенный орграф». Граф представлен в виде списков смежности. Алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным эксцентриситетом).
*/
template<typename W = float>
class Edge {
public:
W weight;
unsigned int start, end;
Edge<W> *next;
Edge(int, int, W);
~Edge();
};
template<typename W = float, typename V = int>
class Vertex {
public:
V data;
Edge<W> *incident_edges;
Vertex(V);
~Vertex();
};
template<typename W = float, typename V = int>
class Graph {
protected:
static const size_t INIT_COUNT = 2;
size_t v_count;
Vertex<W, V> **vertices;
size_t max_v_count;
public:
Vertex<W, V>* get_vertex(unsigned int);
size_t vertex_count();
bool insert_edge(unsigned int, unsigned int, W);
void add_vertex(V);
bool remove_edge(unsigned int, unsigned int);
bool has_edge(unsigned int, unsigned int);
Edge<W>* get_edge(unsigned int, unsigned int);
bool set_edge(unsigned int, unsigned int, W);
void print();
void print_spisok();
bool set_vertex(unsigned int, V);
Graph();
~Graph();
};
//---------------------------------------------------------------------------//
template<typename W, typename V> // Constructor Vertex
Vertex<W, V>::Vertex(V new_data)
{
this->incident_edges = 0;
this->data = new_data;
}
template<typename W, typename V> // Destructor Vertex
Vertex<W, V>::~Vertex()
{
if (incident_edges) delete incident_edges;
}
template<typename W> // Constructor Edge
Edge<W>::Edge(int new_start, int new_end, W new_weight): next(0)
{
this->start = new_start;
this->end = new_end;
this->weight = new_weight;
}
template<typename W> // Destructor Edge
Edge<W>::~Edge()
{
if (next) delete next;
}
template<typename W, typename V> // Constructor Graph
Graph<W, V>::Graph(): v_count(0)
{
max_v_count = INIT_COUNT;
vertices = new Vertex<W, V>*[max_v_count];
}
template<typename W, typename V> // Destructor Graph
Graph<W, V>::~Graph()
{
if (vertices) delete[] vertices;
}
template<typename W, typename V> // get_vertex()
Vertex<W, V>* Graph<W, V>::get_vertex(unsigned int index) {
if (index >= this->v_count) return 0;
return this->vertices[index];
}
template<typename W, typename V> // insert_edge()
bool Graph<W, V>::insert_edge(unsigned int new_start, unsigned int new_end, W new_weight) {
if (new_start >= this->v_count || new_end >= this->v_count) {
return false;
}
if (new_start == new_end) {
return false;
}
if (this->has_edge(new_start, new_end)) {
return false;
}
Edge<W> *new_edge = new Edge<W>(new_start, new_end, new_weight);
Vertex<W, V> *v_start = vertices[new_start];
Edge<W> *it_start = v_start->incident_edges;
if (!it_start) {
v_start->incident_edges = new_edge;
}
else {
while (it_start->next) it_start = it_start->next;
it_start->next = new_edge;
}
return true;
}
template<typename W, typename V> // add_vertex()
void Graph<W, V>::add_vertex(V new_data) {
if (this->v_count == this->max_v_count) {
Vertex<W, V> **new_vertices = new Vertex<W, V>*[max_v_count * 2];
unsigned int i;
for (i = 0; i<max_v_count; i++) {
new_vertices[i] = this->vertices[i];
}
new_vertices[i] = new Vertex<W, V>(new_data);
this->max_v_count *= 2;
delete this->vertices;
this->vertices = new_vertices;
}
else {
this->vertices[this->v_count] = new Vertex<W, V>(new_data);
}
this->v_count++;
}
template<typename W, typename V> // print()
void Graph<W, V>::print() {
cout << "Vertex(vertex data): incident edges" << endl;
unsigned int i;
for (i = 0; i<this->v_count; i++) {
Vertex<W, V> *v = this->vertices[i];
cout << i << "(" << v->data << "):\t";
if (!v->incident_edges) {
cout << "null";
}
else {
for (Edge<W> *it = this->vertices[i]->incident_edges; it; it = it->next) {
cout << it->start << ".." << it->end << "(" << it->weight << ") ";
}
}
cout << endl;
}
}
template<typename W, typename V> // print_spisok()
void Graph<W, V>::print_spisok() {
cout << "Vertex -> incident vertex" << endl;
unsigned int i;
for (i = 0; i<this->v_count; i++) {
Vertex<W, V> *v = this->vertices[i];
cout << i;
if (v->incident_edges)
{
for (Edge<W> *it = this->vertices[i]->incident_edges; it; it = it->next) {
cout << " -> " << it->end;
}
}
cout << endl;
}
}
template<typename W, typename V> // vertex_count()
size_t Graph<W, V>::vertex_count() {
return this->v_count;
}
template<typename W, typename V> // has_edge()
bool Graph<W, V>::has_edge(unsigned int start, unsigned int end) {
return!!(this->get_edge(start, end));
}
template<typename W, typename V> // get_edge()
Edge<W>* Graph<W, V>::get_edge(unsigned int start, unsigned int end) {
if (start >= this->v_count || end >= this->v_count)
return 0;
Edge<W> *it = this->vertices[start]->incident_edges;
while (it) {
if (it->start == start && it->end == end) return it;
it = it->next;
}
return 0;
}
template<typename W, typename V> // set_edge()
bool Graph<W, V>::set_edge(unsigned int start, unsigned int end, W weight) {
if (start > this->v_count || end > this->v_count) {
return false;
}
Edge<W> *edge = this->get_edge(start, end);
if (edge) {
edge->weight = weight;
return true;
}
else return false;
}
template<typename W, typename V> // remove()
bool Graph<W, V>::remove_edge(unsigned int start, unsigned int end) {
if (!has_edge(start, end))
return false;
Edge<W> *prev = this->vertices[start]->incident_edges;
if (prev->start == start && prev->end == end){
Edge<W> *it = prev->next;
this->vertices[start]->incident_edges = it;
}
else {
Edge<W> *it = prev;
while (it) {
if (it->start == start && it->end == end) {
prev->next = it->next;
break;
}
prev = it;
it = it->next;
}
}
return true;
}
template<typename W, typename V> // set_vertex()
bool Graph<W, V>::set_vertex(unsigned int key, V new_data) {
if (key+1 > this->v_count) {
return false;
}
this->vertices[key]->data = new_data;
return true;
}
#endif // GRAPH_H
Программа-меню
Main.cpp
// Graf.cpp: Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include "Graph.h"
#include "task1.h"
#include <iomanip>
#include <time.h>
#include <stdlib.h>
using namespace std;
// Вариант 1
// Реализация АТД «Взвешенный орграф». Граф представлен в виде списков смежности. Алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным эксцентриситетом).
int main()
{
srand(time(0));
int choice = -1;
Graph<float, int> *graph = 0;
unsigned int V_COUNT = 5, E_COUNT = 8;
unsigned int start = 0, end = 0, set_v = 0;
float weight = 0.0;
bool inserted = false, removed = false, has_edge = false, edge_set = false;
int data = 0;
Task *task = new Task();
while (true) {
choice = 0;
cout << endl << std::setfill('=') << std::setw(18) << " Graph " << std::setw(15) << ' ' << endl;
cout << "Available actions:" << endl;
cout << "1 - create sample graph," << endl << "2 - insert edge," << endl;
cout << "3 - add vertex," << endl << "4 - remove edge," << endl;
cout << "5 - check if edge exists," << endl << "6 - set edge parameters," << endl;
cout << "7 - print graph," << endl << "8 - set vertex." << endl;
cout << "9 - Floyd algorithm" << endl;
cout << "0 - exit." << endl << "Choice: ";
cin >> choice;
cout << endl;
switch (choice) {
case 1:
// create sample graph
if (graph) delete graph;
graph = new Graph<>();
for (unsigned int i = 0; i<V_COUNT; i++) {
graph->add_vertex(i);
}
for (unsigned int i = 0; i<E_COUNT; i++) {
unsigned int start = rand() % V_COUNT, end = rand() % E_COUNT;
int w = (rand() % 10);
graph->insert_edge(start, end, w);
}
cout << graph->vertex_count() << " vertices." << endl;
graph->print();
break;
case 2:
// insert edge
cout << "Enter start vertex (unsigned): "; cin >> start;
cout << "Enter end vertex (unsigned): "; cin >> end;
cout << "Enter edge weight (float): "; cin >> weight;
if (!graph) graph = new Graph<>();
inserted = graph->insert_edge(start, end, weight);
if (inserted) {
cout << "Inserted edge " << start << "-" << end << "(" << weight << ")" << endl;
}
else {
cout << "Cannot insert, start or end vertex doesnt exist in graph." << endl;
}
break;
case 3:
// add vertex
if (!graph) {
graph = new Graph<float, int>;
cout << "Enter new vertex data: "; cin >> data;
graph->add_vertex(data);
cout << "Added vertex (" << data << ")" << endl;
}
else {
cout << "Enter new vertex data: "; cin >> data;
graph->add_vertex(data);
cout << "Added vertex (" << data << ")" << endl;
}
break;
case 4:
// remove edge
if (graph) {
cout << "Enter start vertex (unsigned): "; cin >> start;
cout << "Enter end vertex (unsigned): "; cin >> end;
removed = graph->remove_edge(start, end);
if (removed) {
cout << "Removed edge " << start << "-" << end << endl;
}
else {
cout << "Cannot remove edge, edge doesnt exist." << endl;
}
}
else {
cout << "Empty graph." << endl;
}
break;
case 5:
// check if edge exists
if (graph) {
cout << "Enter start vertex (unsigned): "; cin >> start;
cout << "Enter end vertex (unsigned): "; cin >> end;
has_edge = graph->has_edge(start, end);
if (has_edge) {
cout << "Edge exists." << endl;
}
else {
cout << "Edge does not exist." << endl;
}
}
else {
cout << "Empty graph." << endl;
}
break;
case 6:
// set edge parameters
if (graph) {
cout << "Enter start vertex (unsigned): "; cin >> start;
cout << "Enter end vertex (unsigned): "; cin >> end;
cout << "Enter edge weight (float): "; cin >> weight;
edge_set = graph->set_edge(start, end, weight);
if (edge_set) {
cout << "Edge " << start << "-" << end << " set to weight " << weight << endl;
}
else {
cout << "Edge does not exist." << endl;
}
}
else {
cout << "Empty graph." << endl;
}
break;
case 7:
// print graph
if (graph) graph->print();
else cout << "Empty graph.";
cout << endl;
break;
case 8:
if (graph) {
cout << "Enter vertex index: "; cin >> set_v;
cout << "Enter new data: "; cin >> data;
inserted = graph->set_vertex(set_v, data);
if (inserted) {
cout << "Vertex data changed." << endl;
}
else {
cout << "Incorrect vertex index." << endl;
}
}
else {
cout << "Empty graph." << endl;
}
break;
case 9:
// Floyd algorithm
if (graph) {
task->graph = graph;
task->find_center();
}
else {
cout << "Empty graph." << endl;
}
break;
case 0:
return 0;
break;
default:
cout << "Incorrect command. Try again." << endl;
}
}
return 0;
}
Алгоритм Флойда
Task1.h
#ifndef TASK1_H
#define TASK1_H
#include "graph.h"
#include<climits>
/*
Алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным эксцентриситетом)
*/
class Task
{
public:
void find_center();
Graph<float, int>* graph;
};
//---------------------------------------------------------------------------//
void Task::find_center() {
// На каждом шаге алгоритм генерирует матрицу W, w_{ij}=d_{ij}^n. Матрица W содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица W заполняется длинами рёбер графа.
// fork = 1 ton
// for i = 1 to n
// for j = 1 to n
// W[i][j] = min(W[i][j], W[i][k] + W[k][j])
// for k from 1 to |V|
// for i from 1 to |V|
// for j from 1 to |V|
// if dist[i][j] > dist[i][k] + dist[k][j]
// dist[i][j] < dist[i][k] + dist[k][j]
// end if
cout << "Graph:" << endl;
graph->print();
unsigned int v_count = graph->vertex_count();
// Подготовка матрицы весов
int **dist = new int*[v_count];
for (unsigned int i = 0; i<v_count; i++) {
dist[i] = new int[v_count];
for (unsigned int j = 0; j<v_count; j++) {
Edge<float> *edge = graph->get_edge(i, j);
if (edge) {
dist[i][j] = edge->weight;
}
else if (i == j){
dist[i][j] = 0;
}
else dist[i][j] = 1000000;
}
}
// Вывод матрицы достижимости
cout << endl << "Reachability matrix:" << endl;
for (unsigned int i = 0; i<v_count; i++) {
for (unsigned int j = 0; j<v_count; j++) {
cout << dist[i][j] << "\t";
}
cout << endl << endl << endl;
}
// Вычисление расстояний
for (unsigned int k = 0; k<v_count; k++) {
for (unsigned int i = 0; i<v_count; i++) {
for (unsigned int j = 0; j<v_count; j++) {
if (dist[i][j] >(dist[i][k] + dist[k][j])) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// Вывод матрицы расстояний
cout << "Distances matrix:" << endl;
for (unsigned int i = 0; i<v_count; i++) {
for (unsigned int j = 0; j<v_count; j++) {
cout << dist[i][j] << "\t";
}
cout << endl << endl;
}
int *ecc = new int[v_count];
int min_ecc = 1000000;
for (unsigned int i = 0; i<v_count; i++) {
ecc[i] = -1;
for (unsigned int j = 0; j<v_count; j++) {
if (ecc[i] < dist[i][j]) ecc[i] = dist[i][j];
}
if (min_ecc > ecc[i]) min_ecc = ecc[i];
cout << ecc[i] << " ";
}
// Вывод вершин, составляющих центр графа
cout << endl << endl << "Graph center:" << endl;
for (unsigned int i = 0; i<v_count; i++) {
// Компенсируем погрешность округления
if ((int)ecc[i] * 100 == (int)min_ecc * 100 && min_ecc < 1000000 && ecc[i] < 1000000) {
Vertex<float, int> *v = graph->get_vertex(i);
cout << i << ":" << v->data << " (" << ecc[i] << ") ";
}
}
cout << endl;
}
#endif // TASK1_H