Проектирование программной коллекции 'Простой, статический граф'
1. Вводная
часть
граф
программный статический
1.1 Цель
работы
Проектирование и реализация универсальной программной коллекции для АТД
«Простой, статический граф» и использование коллекции для решения задач для
неориентированных, ориентированных и взвешенных графов.
1.2
Постановка задания
Необходимо спроектировать и реализовать универсальную программную
коллекцию для АТД «Простой граф» и использовать коллекцию для решения задач для
неориентированных, ориентированных и взвешенных графов.
Разработать АТД «Простой граф».
Интерфейс АТД «Простой, статический граф» включает операции:
Конструктор ( ) по умолчанию: создает пустой 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(v)добавляет к графу вершину c заданным номером v,
DeleteV
(v) -удаляет из графа вершину c заданным номером v,
InsertE(v1, v2) - добавляет ребро (v1, v2) к графу, соединяющую вершины,
заданные номерами v1 и v2,
DeleteE
(v1, v2)удаляет ребра (v1, v2), соединяющего вершины,
заданные номерами v1 и v2,
Is_Edge(v1, v2)возвращает признак существования в графе ребра
соединяющего вершины, заданные номерами v1 и v2,Weight(v1,v2)возвращает
вес ребра (v1, v2), соединяющего вершины,
заданные номерами v1 и v2,Weight (v1,v2, w)задает вес ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2, равным w.Data(v1,v2)возвращает данные ребра (v1, v2), соединяющего вершины,
заданные номерами v1 и v2,Data (v1,v2, w)задает данные ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2, равным w.
Разработать ассоциированные с графом типы:
«Дескриптор ребра графа»
Дескриптор ребра содержит поля:
v1 -
номер вершины, из которой исходит ребро,
v2 -
номер вершины, в которую входит ребро,
w -
вес ребра,
data -
данные, связанные с ребром,
АТД «Итератор вершин графа»
Интерфейс АТД «Итератор вершин графа» включает операции:
Конструктор ( ) - создает итератор вершин графа,
beg( )
- возвращает итератор, установленный на первую вершину графа,
end( )
- возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующей вершине графа,
operator * - возвращает номер вершины графа, на которую указывает итератор.
АТД «Итератор ребер графа»
Интерфейс АТД «Итератор ребер графа» включает операции:
Конструктор ( ) - создает итератор ребер графа,
beg( )
- возвращает итератор, установленный на первое ребро графа,
end( )
- возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующему ребру графа,
operator * - возвращает дескриптор ребра графа, на которое указывает итератор.
АТД «Итератор исходящих ребер вершины»
Интерфейс АТД «Итератор исходящих ребер вершины» включает операции:
Конструктор (v) - создает
итератор исходящих ребер графа для вершины, заданной номером v,
beg( )
- возвращает итератор, установленный на первое исходящее ребро вершины,
end( )
- возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующему исходящему ребру,
operator * - возвращает дескриптор исходящего ребра вершины, на которое указывает
итератор.
АТД «Итератор входящих ребер вершины»
Интерфейс АТД «Итератор входящих ребер вершины» включает операции:
Конструктор (v) - создает
итератор входящих ребер графа для вершины, заданной номером v,
beg( )
- возвращает итератор, установленный на первое входящее ребро вершины,
end( )
- возвращает итератор, соответствующий окончанию переходов итератора,
operator ++ - переход к следующему входящему ребру,
operator * - возвращает дескриптор входящего ребра вершины, на которое указывает
итератор.
2. Основная
часть
2.1 Диаграмма
взаимосвязи объектов
UML-диаграмма
взаимодействия классов.
Рисунок 1. диаграмма для класса «Простой граф».
Рисунок 2. UML-диаграмма для
классов итераторов.
2.2 АТД
«Простой граф»
.2.1 Формат
АТД
АТД “Простой, статический граф”:
Простой статический граф с заданным типом для хранения данных в рёбрах - D, а также типом хранения веса ребра -
W. Граф может быть ориентированным или
неориентированным, для каждого ребра предусмотрен его вес и данные для
хранения. В графе запрещены петли и параллельные рёбра из одной вершины.
Класс абстрактный, создание объекта этого класса не предусмотрено.
ДАННЫЕ:
Параметры:
verticesCount - переменна хранящая количество вершин
edgesCount - переменная хранящая количество ребер
directed - переменная хранящая тип графа ориентированный/неориентированный
ОПЕРАЦИИ:
Конструктор
Вход:нет
Предусловия: нет
Процесс: создание объекта простого графа, граф не ориентированный
Выход: нет
Постусловия: создан пустой неориентированный граф
Конструктор
Вход:cVertex - число вершин, сDirected - признак ориентированности графа
Предусловия: нет
Процесс: создание объекта графа заданной ориентированности и вставка
заданного числа вершин
Выход: нет
Постусловия: создан граф заданной ориентированности, с количеством вершин
cVertex
Конструктор
Вход:cVertex - число вершин, cEdge-число рёбер, сDirected - признак ориентированности графа
Предусловия: нет
Процесс: создание объекта графа заданной ориентированности и вставка
заданного числа вершин и рёбер
Выход: нет
Постусловия: создан граф заданной ориентированности, с количеством вершин
cVertex и количеством ребер cEdge.
Конструктор копирования
Вход: объект типа “Простой, статический граф” graph
Предусловия: нет
Процесс: создание нового графа и копирование в него всех свойств graph, а также вершин и рёбер
Выход: нет
Постусловие: создание графа с такой же структурой и элементами, что у graph
Опрос числа вершин в графе
Вход: нет
Предусловия: нет
Процесс: чтение количества вершин
Выход: количество вершин в графе
Постусловия: нет
Опрос числа рёбер в графе
Вход: нет
Предусловия: нет
Процесс: чтение количества рёбер
Выход: количество рёбер в графе
Постусловия: нет
Опрос типа ориентированности графа
Вход: нет
Предусловия: нет
Процесс: чтение типа графа
Выход: тип графа (ориентированный/неориентированный)
Постусловия: нет
Опрос формы представления графа
Вход: нет
Предусловия: нет
Процесс: чтение значения формы представления графа
Выход: форма представления графа (L-граф/M-граф)
Постусловия: нет
Коэффициент насыщенности графа
Вход: нет
Предусловия: нет
Процесс: расчёт коэффициента насыщенности графа
Для ориентированного: Е/(V*(V-1))
Для неориентированного: 2*Е/(V*(V-1)), где E-количество ребер, V-количество врешин
Выход: значение коэффициента насыщенности графа
Постусловия: нет
Преобразования графа к L-графу
Вход: нет
Предусловия: нет
Процесс: преобразование текущего представления графа к L-графу
Выход: нет
Постусловия: граф преобразован к L-графу
Преобразования графа к M-графу
Вход: нет
Предусловия: нет
Процесс: преобразование текущего представления графа к М-графу
Выход: нет
Постусловия: граф преобразован к М-графу
Добавление ребра
Вход: номер исходящей вершины vertex1 и входящий vertex2
Предусловия:
· vertex1 не равно vertex2
· вершины vertex1
и vertex2 существуют
· ребро vertex1- vertex2 не
существует
Процесс: вставка ребра соединяющего вершины vertex1и vertex2
Выход: false при не выполнении предусловия, true при выполнении.
Постусловия: ребро вставлено при выполнении предусловия.
Удаление ребра
Вход: номер исходящей вершины vertex1 и входящий vertex2
Предусловия:
· vertex1 не равно vertex2
· вершины vertex1
и vertex2 существуют
· ребро vertex1- vertex2 существует
Процесс: удаление ребра соединяющего вершины vertex1и vertex2
Выход: false при не выполнении предусловия, true при выполнении.
Постусловия: ребро удалено при выполнении предусловия.
Добавление вершины
Вход: номер вершины vertexNumber
Предусловия: вершина vertexNumber не существует
Процесс: вставка вершины vertexNumber
Выход: false при не выполнении предусловия, true при выполнении.
Постусловия: вершина вставлена при выполнении предусловия.
Удаление вершины
Вход: номер вершины vertexNumber
Предусловия: вершина vertexNumber существует
Процесс: удаление вершины vertexNumber и всех связанных с ней ребер
Выход: false при не выполнении предусловия, true при выполнении.
Постусловия: вершина удалена при выполнении предусловия.+
Признак существования ребра
Вход: номер исходящей вершины vertex1 и входящий vertex2
Предусловия: вершины vertex1
и vertex2 существуют
Процесс: проверки есть ли ребро соединяющие вершины vertex1- vertex2
Выход: true - если ребро есть, иначе false
Постусловия: нет
Опрос веса ребра
Вход: номер исходящей вершины vertex1 и входящий vertex2
Предусловия:
· вершины vertex1
и vertex2 существуют
· ребро vertex1- vertex2 существует
Процесс: получение веса ребра vertex1- vertex2
Выход: вес ребра шаблонного типа W
Постусловия: генерация исключения при невыполнении предусловия
Задание веса ребра
Вход: номер исходящей вершины vertex1 и входящий vertex2, вес weight
Предусловия:
· вершины vertex1
и vertex2 существуют
· ребро vertex1- vertex2 существует
Процесс: задание веса ребра vertex1- vertex2
Выход: true при выполнении предусловия, иначе false
Постусловия: задан вес ребра шаблонного типа W
Опрос данных ребра
Вход: номер исходящей вершины vertex1 и входящий vertex2
Предусловия:
· вершины vertex1
и vertex2 существуют
· ребро vertex1- vertex2 существует
Процесс: получение данных ребра vertex1- vertex2
Выход: данные ребра шаблонного типа D
Постусловия: генерация исключения при невыполнении предусловия
Задание данных ребра
Вход: номер исходящей вершины vertex1 и входящий vertex2, данные data
Предусловия:
· вершины vertex1
и vertex2 существуют
· ребро vertex1- vertex2 существует
Процесс: задание данных ребра vertex1- vertex2
Выход: true при выполнении предусловия, иначе false
Постусловия: заданы данные ребра шаблонного типа D
КОНЕЦ АТД
.2.2
Клиентское определение класса
public abstract class Graph<W, D>
{
// конструктор без параметров
public Graph();
// конструктор с параметрамиGraph(int cVertex, bool cDirected);
// конструктор с параметрамиGraph(int cVertex, int cEdge, bool
cDirected);
//опрос типа ориентированности
public bool isDirected();
//опрос формы представления графа
abstract public bool getType();
//опрос коэффициента насыщенности
public double denseCoef();
//конвертирование в L-графpublic Graph<W, D> toListGraph();
//конвертирование к М-графpublic Graph<W, D>
toMatrixGraph();
//вставка вершиныpublic bool addVertex(int vertexNumber);
//удаление вершиныpublic bool removeVertex(int vertexNumber);
//вставка ребраpublic bool addEdge(int vertex1, int vertex2);
//удаление ребраpublic bool removeEdge(int vertex1, int vertex2);
//проверка наличия ребраpublic bool hasEdge(int vertex1, int
vertex2);
//получение веса ребраpublic W getEdgeWeight(int vertex1,
int vertex2);
//установка веса ребраpublic bool setEdgeWeight(int
vertex1, int vertex2, W weight);
//получение данных ребраpublic D getEdgeData(int vertex1, int
vertex2);
//установка данных ребраpublic bool setEdgeData(int vertex1,
int vertex2, D data);
}
2.3 АТД «L-граф»
2.3.1 Формат
АТДАТД “L - граф”:
Класс наследник класса «Простой, статический граф». Наследует все
операции родительского класса. Представляет граф в виде списка смежности его
вершин.
ДАННЫЕ:
Параметры:
adjacencyList - список смежности
ОПЕРАЦИИ:
Конструктор
Вход:нет
Предусловия: нет
Процесс: создание объекта L-
графа, граф неориентированный
Выход: нет
Постусловия: создан пустой неориентированный L- граф
Конструктор
Вход:cVertex - число вершин, сDirected - признак ориентированности графа
Предусловия: нет
Процесс: создание объекта L-графа
заданной ориентированности и вставка заданного числа вершин
Выход: нет
Постусловия: создан L-граф
заданной ориентированности, с количеством вершин cVertex
Конструктор
Вход:cVertex - число вершин, cEdge-число рёбер, сDirected - признак ориентированности графа
Предусловия: нет
Процесс: создание объекта L-графа
заданной ориентированности и вставка заданного числа вершин и рёбер
Выход: нет
Постусловия: создан L-граф
заданной ориентированности, с количеством вершин cVertex и количеством ребер cEdge.
Конструктор копирования
Вход: объект типа L-граф
graph
Предусловия: нет
Процесс: создание нового L-графа
и копирование в него всех свойств graph, а также вершин и рёбер
Выход: нет
Постусловие: создание L-графа
с такой же структурой и элементами, что у graph
КОНЕЦ АТД
2.3.2
Клиентское определение класса
class LGraph<W, D> : Graph<W, D>, ICloneable
{
// конструктор без параметров
public LGraph() : base();
// конструктор с параметрамиLGraph(int cVertex, bool cDirected) : base(cVertex,
cDirected);
// конструктор с параметрамиLGraph(int cVertex, int cEdge, bool
cDirected) : base(cVertex, cDirected);
//опрос типа ориентированности
public bool hasDirected();
//опрос формы представления графа
public override
bool getType()
//вставка вершиныoverride bool addVertex(int vertexNumber)
//удаление вершиныoverride bool removeVertex(int vertexNumber)
//вставка ребраoverride bool addEdge(int vertex1, int vertex2)
//удаление ребраoverride bool addEdge(int vertex1, int vertex2)
//проверка наличия ребраoverride bool hasEdge(int vertex1,
int vertex2)
//получение веса ребраoverride W getEdgeWeight(int vertex1,
int vertex2)
//установка веса ребра override bool setEdgeWeight(int
vertex1, int vertex2, W weight)
//получение данных ребраoverride D getEdgeData(int vertex1,
int vertex2)
//установка данных ребраoverride bool setEdgeData(int
vertex1, int vertex2, D data)
//конвертирование в L-граф
public override
Graph<W, D> toListGraph()
//конвертирование в М-граф
public override Graph<W, D> toMatrixGraph()
}
2.4 АТД «M-граф»
.4.1 Формат
АТД
АТД “M- граф”:
Класс наследник класса «Простой, статический граф». Наследует все операции
родительского класса. Представляет граф в виде матрицы смежности.
ДАННЫЕ:
Параметры:
adjacencyMatrix - матрица смежности
ОПЕРАЦИИ:
Конструктор
Вход:cVertex - число вершин, сDirected - признак ориентированности графа
Предусловия: нет
Процесс: создание объекта М-графа заданной ориентированности и вставка
заданного числа вершин
Выход: нет
Постусловия: создан М-граф заданной ориентированности, с количеством
вершин cVertex
Конструктор
Вход:cVertex - число вершин, cEdge-число рёбер, сDirected - признак ориентированности графа
Предусловия: нет
Процесс: создание объекта М-графа заданной ориентированности и вставка
заданного числа вершин и рёбер
Выход: нет
Постусловия: создан М-граф заданной ориентированности, с количеством
вершин cVertex и количеством ребер cEdge.
Конструктор копирования
Вход: объект типа М-граф graph
Предусловия: нет
Процесс: создание нового М-графа и копирование в него всех свойств graph, а также вершин и рёбер
Выход: нет
Постусловие: создание М-графа с такой же структурой и элементами, что у graph
КОНЕЦ АТД
.4.2
Клиентское определение класса
class MGraph<W, D> :Graph<W, D>, ICloneable
{
// конструктор без параметров
public
МGraph() : base();
// конструктор с параметрами МGraph(int cVertex, bool cDirected) : base(cVertex, cDirected);
// конструктор с параметрамиМGraph(int cVertex, int cEdge, bool cDirected) : base(cVertex,
cDirected);
//опрос типа ориентированности
public bool isDirected();
//опрос формы представления графа
public override
bool getType()
//вставка вершиныoverride bool addVertex(int vertexNumber)
//удаление вершиныoverride bool removeVertex(int vertexNumber)
//вставка ребраoverride bool addEdge(int vertex1, int vertex2)
//удаление ребраoverride bool removeEdge(int vertex1, int vertex2)
//проверка наличия ребраoverride bool hasEdge(int vertex1,
int vertex2)
//получение веса ребраoverride W getEdgeWeight(int vertex1,
int vertex2)
//установка веса ребра override bool setEdgeWeight(int
vertex1, int vertex2, W weight)
//получение данных ребраoverride D getEdgeData(int vertex1,
int vertex2)
//установка данных ребраoverride bool setEdgeData(int
vertex1, int vertex2, D data)
//конвертирование в L-граф
public override
Graph<W, D> toListGraph()
//конвертирование в М-граф
public override Graph<W, D> toMatrixGraph()
}
2.5 АТД
«Дескриптор ребра»
.5.1 Формат
АТД
АТД “Дескриптор ребра”:
Дескриптор ребра служит для описания ребер графа. Он хранит в себе номера
вершин ребра, а также данные и вес.
ДАННЫЕ:
Параметры:
Vertex1
- Номер вершины из которой выходит ребро
Vertex2
- Номер вершины в которую входит ребро
Data -
Данные связанные с ребром
Weight
- Вес ребра
ОПЕРАЦИИ:
Конструктор
Вход:номер исходящей вершины vertex1 и входящий vertex2
Предусловия: нет
Процесс: создание ребра из исходящей вершины во входящую
Выход: нет
Конструктор
Вход:номер исходящей вершины vertex1 и входящий vertex2, вес weight
Предусловия: нет
Процесс: создание ребра из исходящей вершины во входящую, весом weight
Выход: нет
Постусловия: создано ребро из исходящей вершины во входящую, весом weight
Конструктор
Вход:номер исходящей вершины vertex1 и входящий vertex2, вес weight, данные data
Предусловия: нет
Процесс: создание ребра из исходящей вершины во входящую, весом weight, с данными data
Выход: нет
Постусловия: создано ребро из исходящей вершины во входящую, весом weight, с данными data
КОНЕЦ АТД
2.5.2
Клиентское определение класса
public class Edge<W, D> : ICloneable
{
//конструктор без параметров
public Edge(int v1, int v2)
//конструктор с параметрами
public Edge(int v1, int v2, W w)
//конструктор с параметрами
public Edge(int v1, int v2, W w, D d)
}
2.6 Итератор
вершин
2.6.1
Описание формата
АТД “Итератор вершин”:
Итератор служит для последовательного доступа к вершинам графа.
ДАННЫЕ:
Параметры:
currentPosition - текущая вершина в графе
graph
- граф
ОПЕРАЦИИ:
Конструктор
Вход:нет
Предусловия: нет
Процесс: создание объекта итератора вершин
Выход: нет
Постусловия: создан объект итератор вершин графа
Установка итератора на первую вершину
Вход:нет
Предусловия: нет
Процесс: установка итератор на первую вершину
Выход: нет
Постусловия: итератор установлен на первую вершину
Установка итератора на последнюю вершину
Вход:нет
Предусловия: нет
Процесс: установка итератор на последнюю вершину
Выход: нет
Постусловия: итератор установлен на последнюю вершину
Установка итератора на следующую вершину
Вход:нет
Предусловия: нет
Процесс: установка итератор на следующую вершину
Выход: нет
Постусловия: итератор установлен на следующую вершину
Получение номера вершины (проверка состояния)
Вход:нет
Предусловия: нет
Процесс: получение номера вершины
Выход: номер вершины графа, на которую указывает итератора или null, если итератор вышел за пределы
графа
Постусловия: нет
КОНЕЦ АТД
2.6.2
Клиентское определение класса
public class VertexIterator<W, D> : Iterator<W,
D>
{
//конструктор с параметрамиVertexIterator(Graph<W, D>
graphC)
: base(graphC)
//установка на началоoverride void benig()
//установка в конец
public override
void end()
//переход к следующей
public override void next() override Edge<W, D> state()
}
2.7 Итератор
ребер
2.7.1
Описание формата
АТД “Итератор рёбер”:
Итератор служит для последовательного доступа к ребрам графа.
ДАННЫЕ:
Параметры:
currentPosition - текущее ребро в графе
graph
- граф
ОПЕРАЦИИ:
Конструктор
Вход:нет
Предусловия: нет
Процесс: создание объекта итератора рёбер
Выход: нет
Постусловия: создан объект итератор рёбер графа
Установка итератора на первое ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на первое ребро графа
Выход: нет
Постусловия: итератор установлен на первое ребро графа
Установка итератора на послднее ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на послднее ребро графа
Выход: нет
Постусловия: итератор установлен на послднее ребро графа
Установка итератора на следующее ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на следующее ребро графа
Выход: нет
Постусловия: итератор установлен на следующее ребро графа
Получение дескриптора текущего ребра (проверка состояния)
Вход:нет
Предусловия: нет
Процесс: получение дескриптора ребра
Выход: дескриптор ребра, на которое указывает итератор, или null если итератор вышел за пределы графа
Постусловия: нет
КОНЕЦ АТД
.7.2
Клиентское определение класса
public class EdgeIterator<W, D> : Iterator<W, D>
{
//конструктор с параметрамиEdgeIterator(Graph<W, D>
graphC)
: base(graphC)
//установка на начало
public override
void benig()
//установка в конец
public override
void end()
//переход к следующей
public override void next() override Edge<W, D> state()
}
2.8 Итератор
исходящих ребер
2.8.1
Описание формата
АТД “Итератор исходящих рёбер”:
Итератор служит для последовательного доступа ко всем исходящим ребрам
заданной вершины графа.
ДАННЫЕ:
Параметры:
vertexNumber - номер вершины
ОПЕРАЦИИ:
Конструктор
Вход:номер вершины vertexNumb
Предусловия: нет
Процесс: создание объекта итератора исходящих рёбер из заданной вершины
Выход: нет
Постусловия: создан объект итератор исходящих рёбер вершины
Установка итератора на первое исходящее ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на первое исходящее ребро вершины
Выход: нет
Постусловия: итератор установлен на первое ребро вершины
Установка итератора на послднее исходящее ребро вершины
Вход:нет
Предусловия: нет
Процесс: установка итератор на послднее исходящее ребро вершины
Выход: нет
Постусловия: итератор установлен на послднее исходящее ребро вершины
Установка итератора на следующее ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на следующее исходящее ребро вершины
Выход: нет
Постусловия: итератор установлен на следующее исходящее ребро вершины
Получение дескриптора текущего ребра (проверка состояния)
Вход:нет
Предусловия: нет
Процесс: получение дескриптора ребра
Выход: дескриптор исходящего ребра, вершины vertexNumber, на которое указывает итератор
Постусловия: нет
КОНЕЦ АТД
.8.2
Клиентское определение класса
public class OutgoingEdgesIterator<W, D> :
Iterator<W, D>
{
//конструктор с параметрамиOutgoingEdgesIterator (Graph<W,
D> graphC)
: base(graphC)
//установка на началоoverride void benig()
//установка в конец
public override
void end()
//переход к следующей
public override void next() override Edge<W, D> state()
}
2.9 Итератор
входящих ребер
2.9.1
Описание формата
АТД “Итератор входящих рёбер”:
Итератор служит для последовательного доступа ко всем входящим ребрам
заданной вершины графа.
ДАННЫЕ:
Параметры:
vertexNumber - номер вершины
ОПЕРАЦИИ:
Конструктор
Вход:номер вершины vertexNumb
Предусловия: нет
Процесс: создание объекта итератора входящих рёбер из заданной вершины
Выход: нет
Постусловия: создан объект итератор входящих рёбер вершины
Установка итератора на первое входящее ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на первое входящее ребро вершины
Выход: нет
Постусловия: итератор установлен на первое входящее ребро вершины
Установка итератора на последнее входящее ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на последнее входящее ребро вершины
Выход: нет
Постусловия: итератор установлен на последнее входящее ребро вершины
Установка итератора на следующее ребро
Вход:нет
Предусловия: нет
Процесс: установка итератор на следующее входящее ребро вершины
Выход: нет
Постусловия: итератор установлен на следующее входящее ребро вершины
Получение дескриптора текущего ребра (проверка состояния)
Вход:нет
Предусловия: нет
Процесс: получение дескриптора ребра
Выход: дескриптор входящего ребра, вершины vertexNumber, на которое указывает итератор
Постусловия: нет
КОНЕЦ АТД
2.9.2
Клиентское определение класса
public class IncomingEdgesIterator<W, D> :
Iterator<W, D>
{
//конструктор с параметрамиIncomingEdgesIterator (Graph<W,
D> graphC)
: base(graphC)
//установка на началоoverride void benig()
//установка в конец
public override
void end()
//переход на следующую
public override void next() override Edge<W, D> state()
}
Заключение
граф программный статический
В ходе работы над расчётно-графической работой, была спроектирована и
реализована универсальная коллекция «Простой статический граф» с графическим
интерфейсом. Были получены знания о работы с разными типами графов, а также
решения различных проблем связанных с их построением. В ходе создания
графического интерфейса были получены навыки визуализации графов.
Список
используемой литературы
1. Р. Сэджвик, «Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах»,
2002 г. - 496 с.
Приложение
Исходные коды
Edge.cs
using System;
using System.Collections.Generic;System.Linq;System.Text;RGR
{class Edge<W, D> : ICloneable
{int vertex1;int vertex2;W weight;D data;Edge()
{= -1;= -1;
}Edge(int v1, int v2)
{= v1;= v2;
}Edge(int v1, int v2, W w)
{= v1;= v2;= w;
}Edge(int v1, int v2, W w, D d)
{= v1;= v2;= w;= d;
}Object Clone()
{new Edge<W, D>(Vertex1, Vertex2, Weight, Data);
}int Vertex1
{
{= value;
}
{vertex1;
}
}int Vertex2
{
{= value;
}
{vertex2;
}
}W Weight
{
{=value;
}
{weight;
}
}D Data
{
{= value;
}
{data;
}
}
}
}
Graph.cs
using
System;System.Collections.Generic;System.Linq;System.Text;RGR
{abstract class Graph<W, D>
{static int MAXVERTICESCOUNT = 10;int verticesCount;int
edgesCount;bool directed;SortedDictionary<int, int> dictionary;Graph()
{= 0;= 0;= false;
}Graph(int cVertex, bool cDirected)
{= cVertex;= 0;= cDirected;
}Graph(int cVertex, int cEdge, bool cDirected)
{= cVertex;= cEdge;= cDirected;
}int getVerticesCount()
{verticesCount;
}void increaseVerticesCount()
{++;
}void decreaseVerticesCount()
{-;
}int getEdgesCount()
{edgesCount;
}void increaseEdgesCount()
{++;
}void decreaseEdgesCount()
{-;
}void decreaseEdgesCount(int decrease)
{-= decrease;
}bool isDirected()
{directed;
}public bool getType();double denseCoef()
{(directed) return (double)edgesCount /
((double)verticesCount * ((double)verticesCount - 1.0));2.0 *
(double)edgesCount / ((double)verticesCount * ((double)verticesCount - 1.0));
}public Graph<W, D> toListGraph();public Graph<W,
D> toMatrixGraph();public bool addVertex(int vertexNumber);public bool
removeVertex(int vertexNumber);public bool addEdge(int vertex1, int
vertex2);public bool addEdge(Edge<W, D> edge);public bool removeEdge(int
vertex1, int vertex2);public bool hasEdge(int vertex1, int vertex2);public W
getEdgeWeight(int vertex1, int vertex2);public bool setEdgeWeight(int vertex1,
int vertex2, W weight);public D getEdgeData(int vertex1, int vertex2);public
bool setEdgeData(int vertex1, int vertex2, D data);public List<int>
getNeighbors(int vertexNumber);
//---PARENT ITERATORS--------------------------------abstract
class Iterator<W, D>
{Graph<W, D> graph;Edge<W, D>
currentPosition;Iterator(Graph<W, D> graphC)
{= graphC;();
}abstract void begin();abstract void end();abstract void
next();abstract Edge<W, D> state();
}
}
}
LGraph.cs
using
System;System.Collections.Generic;System.Linq;System.Text;RGR
{LGraph<W, D> : Graph<W, D>, ICloneable
{List<List<Edge<W, D>>>
adjacencyList;LGraph()
: base()
{= new List<List<Edge<W, D>>>();= new
SortedDictionary<int, int>();
}LGraph(int cVertex, bool cDirected)
: base(cVertex, cDirected)
{= new SortedDictionary<int, int>();= new
List<List<Edge<W, D>>>(cVertex);(int i = 0; i < cVertex;
i++)
{.Add(new List<Edge<W, D>>());.Add(i, i);
}
}LGraph(int cVertex, int cEdge, bool cDirected)
: base(cVertex, cDirected)
{= new List<List<Edge<W, D>>>(cVertex);=
new SortedDictionary<int, int>();(int i = 0; i < cVertex; i++)
{.Add(new List<Edge<W, D>>());.Add(i, i);
}rand = new Random();(int i = 0; i < cEdge; )
{vertex1 = rand.Next(cVertex);vertex2 =
rand.Next(cVertex);edgeInserted = addEdge(vertex1, vertex2);(edgeInserted) i++;
}
}LGraph(int cVertex, int cEdge, List<List<Edge<W,
D>>> list, bool cDirected)
: base(cVertex, cEdge, cDirected)
{= list;
}override bool getType()
{true;
}override bool addVertex(int vertexNumber)
{(vertexNumber < 0) return false;.Add(vertexNumber,
adjacencyList.Count);.Add(new List<Edge<W, D>>());();true;
}override bool removeVertex(int vertexNumber)
{(vertexNumber < 0) return false;
{deleteIndex =
dictionary[vertexNumber];(adjacencyList[deleteIndex].Count);.RemoveAt(deleteIndex);();(List<Edge<W,
D>> list in adjacencyList)
{(int i = 0; i < list.Count; )
{(list[i].Vertex2 == deleteIndex)
{.RemoveAt(i);();
}
{(list[i].Vertex1 > deleteIndex)
list[i].Vertex1--;(list[i].Vertex2 > deleteIndex) list[i].Vertex2--;++;
}
}
}.Remove(vertexNumber);(int key = 0; key <= MAXVERTICESCOUNT;
key++)
{value;(dictionary.TryGetValue(key, out value))
{(value > vertexNumber)
{.Remove(key);.Add(key, value - 1);
}
}
}true;
}
}override bool addEdge(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return false;(hasEdge(vertex1, vertex2))
return false;source = dictionary[vertex1];destanation =
dictionary[vertex2];<W, D> newEdge = new Edge<W, D>(source, destanation);inserted
= false;(source < 0 || destanation < 0 || source == destanation) return
false;(adjacencyList[source].Count == 0)
{[source].Add(newEdge);();= true;
}
{(Edge<W, D> edge in adjacencyList[source])
{(edge.Vertex1 == source && edge.Vertex2 == destanation)false;
}[source].Add(newEdge);();= true;
}(inserted && !isDirected())
{<W, D> reverseEdge = new Edge<W, D>(destanation,
source);[destanation].Add(reverseEdge);
}inserted;
}override bool addEdge(Edge<W, D> edge)
{(edge == null) return false;[edge.Vertex1].Add(edge);();(!isDirected())
{<W, D> reverseEdge = new Edge<W,
D>(edge.Vertex2, edge.Vertex1, edge.Weight,
edge.Data);[edge.Vertex2].Add(reverseEdge);
}true;
}override bool removeEdge(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return false;(!hasEdge(vertex1, vertex2))
return false;source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0) return
false;(int i = 0; i < adjacencyList[source].Count;
i++)(adjacencyList[source][i].Vertex2 == destanation)
{[source].RemoveAt(i);();(!isDirected())
{(adjacencyList[destanation][j].Vertex2 ==
source)[destanation].RemoveAt(j);
}
}true;
}false;
}override bool hasEdge(int vertex1, int vertex2)
{source;destanation;(dictionary.TryGetValue(vertex1, out
source) && dictionary.TryGetValue(vertex2, out destanation))
{(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0 || source ==
destanation) return false;(int i = 0; i < adjacencyList[source].Count;
i++)(adjacencyList[source][i].Vertex2 == destanation) return true;
}false;
}override W getEdgeWeight(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) throw new
ArgumentException();(!hasEdge(vertex1, vertex2)) throw new
ArgumentException();source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0) throw new
ArgumentOutOfRangeException("this edge does not exist");(int i = 0; i
< adjacencyList[source].Count; i++)(adjacencyList[source][i].Vertex2 ==
destanation) return adjacencyList[source][i].Weight;new
ArgumentOutOfRangeException("Ребро не существует");
}override bool setEdgeWeight(int vertex1, int vertex2, W
weight)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return false;(!hasEdge(vertex1, vertex2))
return false;source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0) return
false;(int i = 0; i < adjacencyList[source].Count;
i++)(adjacencyList[source][i].Vertex2 == destanation)
{[source][i].Weight = weight;true;
}false;
}override D getEdgeData(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) throw new
ArgumentException();(!hasEdge(vertex1, vertex2)) throw new
ArgumentException();source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0) throw new
ArgumentOutOfRangeException("this edge does not exist");(int i = 0; i
< adjacencyList[source].Count; i++)(adjacencyList[source][i].Vertex2 ==
destanation) return adjacencyList[source][i].Data;new
ArgumentOutOfRangeException("Ребро не существует");
}override bool setEdgeData(int vertex1, int vertex2, D data)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return false;(!hasEdge(vertex1, vertex2))
return false;source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0) return false;(int
i = 0; i < adjacencyList[source].Count;
i++)(adjacencyList[source][i].Vertex2 == destanation)
{[source][i].Data = data;true;
}false;
}Object Clone()
{new LGraph<W, D>(getVerticesCount(), getEdgesCount(),
adjacencyList, isDirected());
}override Graph<W, D> toListGraph()
{this;
}override Graph<W, D> toMatrixGraph()
{<W, D> mGraph = new MGraph<W,
D>(getVerticesCount(), isDirected());(List<Edge<W, D>>
listOfEdges in adjacencyList)(Edge<W, D> edge in listOfEdges)
{.addEdge(edge);
}.dictionary = dictionary;mGraph;
}override List<int> getNeighbors(int vertexNumber)
{currentVertexNeighbor = 0;<int> result = new
List<int>();min = 100;(adjacencyList[vertexNumber].Count != 0)
{(Edge<W, D> edge in adjacencyList[vertexNumber])
{(edge.Vertex2 < min && edge.Vertex2 >=
currentVertexNeighbor)
{= edge.Vertex2;
}
}.Add(min);= min;
}(true)
{old = currentVertexNeighbor;= 100;(Edge<W, D> edge in
adjacencyList[vertexNumber])
{(edge.Vertex2 < min && edge.Vertex2 > old)
{= edge.Vertex2;
}
}
(min == 100)
{= 0;result;
}= min;.Add(currentVertexNeighbor);
}
}class VertexIterator<W, D> : Iterator<W, D>
{VertexIterator(Graph<W, D> graphC)
: base(graphC)
{
}override void begin()
{(graph.getVerticesCount() == 0)
{= null;;
}min = 100;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Key < min) min = entry.Key;
}= new Edge<W, D>(min, 100);
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}max = 0;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Key > max) max = entry.Key;
}= new Edge<W, D>(max, 100);
}
override void next()
{(currentPosition == null)
{;
}min = 100;old =
currentPosition.Vertex1;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Key < min && entry.Key > old) min =
entry.Key;
}(min != 100)
{= new Edge<W, D>(min, 100);
}
{= null;
}
}override Edge<W, D> state()
{currentPosition;
}
}class EdgeIterator<W, D> : Iterator<W, D>
{lastI = 0;lastJ = 0;edgesCount = 0;EdgeIterator(Graph<W,
D> graphC)
: base(graphC)
{
}override void begin()
{(graph.getVerticesCount() == 0)
{= null;;
}(graph.isDirected())
{i = 0;j = 0;isExist = false;(!isExist)
{(i == ((LGraph<W, D>)graph).adjacencyList.Count)
{= null;;
}(((LGraph<W, D>)graph).adjacencyList[i].Count == 0)
i++;
{= true;
}
}source = ((LGraph<W,
D>)graph).adjacencyList[i][j].Vertex1;destanation = ((LGraph<W,
D>)graph).adjacencyList[i][j].Vertex2;sourceVertex = 0;destanationVertex =
0;(KeyValuePair<int, int> entry in graph.dictionary)
{(entry.Value == source) sourceVertex =
entry.Key;(entry.Value == destanation) destanationVertex = entry.Key;
}= new Edge<W, D>(sourceVertex, destanationVertex,
graph.getEdgeWeight(sourceVertex, destanationVertex),
graph.getEdgeData(sourceVertex, destanationVertex));= i;= j;= 1;
}
{(int i = 0; i <= MAXVERTICESCOUNT; i++)
{(int j = 0; j <= MAXVERTICESCOUNT; j++)
{(!graph.dictionary.ContainsKey(i) ||
!graph.dictionary.ContainsKey(j)) continue;(graph.hasEdge(graph.dictionary[i],
graph.dictionary[j]))
{sourceVertex = 0;destanationVertex = 0;(KeyValuePair<int,
int> entry in graph.dictionary)
{(entry.Value == i) sourceVertex = entry.Key;(entry.Value ==
j) destanationVertex = entry.Key;
}= new Edge<W, D>(sourceVertex, destanationVertex,
graph.getEdgeWeight(sourceVertex, destanationVertex),
graph.getEdgeData(sourceVertex, destanationVertex));= i;= j;= 1;;
}
}= i;
}
}
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}(graph.isDirected())
{i = ((LGraph<W, D>)graph).adjacencyList.Count -
1;isExist = false;(!isExist)
{(i == -1)
{= null;;
}(((LGraph<W, D>)graph).adjacencyList[i].Count == 0)
i--;
{= true;
}
}j = ((LGraph<W, D>)graph).adjacencyList[i].Count -
1;source = ((LGraph<W, D>)graph).adjacencyList[i][j].Vertex1;destanation
= ((LGraph<W, D>)graph).adjacencyList[i][j].Vertex2;sourceVertex =
i;destanationVertex = j;(KeyValuePair<int, int> entry in graph.dictionary)
{(entry.Value == source) sourceVertex =
entry.Key;(entry.Value == destanation) destanationVertex = entry.Key;
}= new Edge<W, D>(sourceVertex, destanationVertex,
graph.getEdgeWeight(sourceVertex, destanationVertex),
graph.getEdgeData(sourceVertex, destanationVertex));= graph.getEdgesCount();
}
{(int i = MAXVERTICESCOUNT; i >= 0; i--)(int j =
MAXVERTICESCOUNT; j >= i; j--)
{(i == j || !graph.dictionary.ContainsKey(i) ||
!graph.dictionary.ContainsKey(j)) continue;(graph.hasEdge(i, j))
{sourceVertex = 0;destanationVertex = 0;(KeyValuePair<int,
int> entry in graph.dictionary)
{(entry.Value == i) sourceVertex = entry.Key;(entry.Value ==
j) destanationVertex = entry.Key;
}= new Edge<W, D>(sourceVertex, destanationVertex,
graph.getEdgeWeight(sourceVertex, destanationVertex),
graph.getEdgeData(sourceVertex, destanationVertex));= i;= j;=
graph.getEdgesCount();;
}
}
}
}override void next()
{(currentPosition == null)
{;
}(edgesCount == graph.getEdgesCount())
{= null;;
}(graph.isDirected())
{i = lastI;j = lastJ + 1;(j == ((LGraph<W,
D>)graph).adjacencyList[i].Count)
{= 0;++;
}isExist = false;(!isExist)
{(i == ((LGraph<W, D>)graph).adjacencyList.Count)
{= null;;
}(((LGraph<W, D>)graph).adjacencyList[i].Count == 0)
i++;
{= true;
}
}(i == ((LGraph<W, D>)graph).adjacencyList.Count)
{= null;;
}source = ((LGraph<W,
D>)graph).adjacencyList[i][j].Vertex1;destanation = ((LGraph<W,
D>)graph).adjacencyList[i][j].Vertex2;sourceVertex = 0;destanationVertex =
0;(KeyValuePair<int, int> entry in graph.dictionary)
{(entry.Value == source) sourceVertex =
entry.Key;(entry.Value == destanation) destanationVertex = entry.Key;
}= new Edge<W, D>(sourceVertex, destanationVertex,
graph.getEdgeWeight(sourceVertex, destanationVertex),
graph.getEdgeData(sourceVertex, destanationVertex));++;= i;= j;;
}
{(int i = lastI; i <= MAXVERTICESCOUNT; i++)
{(int j = lastJ + 1; j <= MAXVERTICESCOUNT; j++)
{(i == j || !graph.dictionary.ContainsKey(i) ||
!graph.dictionary.ContainsKey(j)) continue;(graph.hasEdge(i, j))
{sourceVertex = i;destanationVertex = j;= new Edge<W,
D>(sourceVertex, destanationVertex, graph.getEdgeWeight(sourceVertex,
destanationVertex), graph.getEdgeData(sourceVertex, destanationVertex));= i;=
j;++;;
}
}= i;
}
}
}override Edge<W, D> state()
{currentPosition;
}
}class IncomingEdgesIterator<W, D> : Iterator<W,
D>
{lastI = 0;vertexNumb = -2;IncomingEdgesIterator(Graph<W,
D> graphC, int vertexNumbC)
: base(graphC)
{= graph.dictionary[vertexNumbC];();
}override void begin()
{(vertexNumb == -2) return;(graph.getVerticesCount() == 0)
{= null;;
}(int i = 0; i < graph.getVerticesCount(); i++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value ==
vertexNumb) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}(i == graph.getVerticesCount() - 1)
{= null;
}
}
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}(int i = graph.getVerticesCount() - 1; i >= 0; i--)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value ==
vertexNumb) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}(i == 0)
{= null;
}
}
}override void next()
{(currentPosition == null)
{;
}i;(i = lastI + 1; i < graph.getVerticesCount(); i++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value ==
vertexNumb) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}
}(i == graph.getVerticesCount())
{= null;
}
}override Edge<W, D> state()
{currentPosition;
}
}class OutGoingEdgesIterator<W, D> : Iterator<W,
D>
{lastI = 0;vertexNumb = -2;OutGoingEdgesIterator(Graph<W,
D> graphC, int vertexNumbC)
: base(graphC)
{= graph.dictionary[vertexNumbC];();
}override void begin()
{(vertexNumb == -2) return;(graph.getVerticesCount() == 0)
{= null;;
}(((LGraph<W, D>)graph).adjacencyList[vertexNumb].Count
== 0)
{= null;;
}i = 0;source = ((LGraph<W,
D>)graph).adjacencyList[vertexNumb][i].Vertex1;destanation = ((LGraph<W,
D>)graph).adjacencyList[vertexNumb][i].Vertex2;sourceOK =
false;destanationOK = false;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Value == source && !sourceOK)
{= entry.Key;= true;
}(entry.Value == destanation && !destanationOK)
{= entry.Key;= true;
}
}= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}(((LGraph<W, D>)graph).adjacencyList[vertexNumb].Count
== 0)
{= null;;
}i = ((LGraph<W, D>)graph).adjacencyList[vertexNumb].Count
- 1;source = ((LGraph<W,
D>)graph).adjacencyList[vertexNumb][i].Vertex1;destanation = ((LGraph<W,
D>)graph).adjacencyList[vertexNumb][i].Vertex2;sourceOK =
false;destanationOK = false;(KeyValuePair<int, int> entry in graph.dictionary)
{(entry.Value == source && !sourceOK)
{= entry.Key;= true;
}(entry.Value == destanation && !destanationOK)
{= entry.Key;= true;
}
}= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));=
i;
}override void next()
{(currentPosition == null)
{;
}i = lastI + 1;(i == ((LGraph<W,
D>)graph).adjacencyList[vertexNumb].Count)
{= null;;
}source = ((LGraph<W,
D>)graph).adjacencyList[vertexNumb][i].Vertex1;destanation = ((LGraph<W,
D>)graph).adjacencyList[vertexNumb][i].Vertex2;sourceOK =
false;destanationOK = false;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Value == source && !sourceOK)
{= entry.Key;= true;
}(entry.Value == destanation && !destanationOK)
{= entry.Key;= true;
}
}= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;
}override Edge<W, D> state()
{currentPosition;
}
}
}
}
MGraph.cs
using
System;System.Collections.Generic;System.Linq;System.Text;RGR
{MGraph<W, D> : Graph<W, D>, ICloneable
{<W, D>[,] adjacencyMatrix;MGraph(int cVertex, bool
cDirected)
: base(cVertex, cDirected)
{= new Edge<W, D>[cVertex * 2, cVertex * 2];= new
SortedDictionary<int, int>();(int i = 0; i < cVertex; i++)
{.Add(i, i);
}
}MGraph(int cVertex, int cEdge, bool cDirected)
: base(cVertex, cDirected)
{= new Edge<W, D>[cVertex * 2, cVertex * 2];= new
SortedDictionary<int, int>();(int i = 0; i < cVertex; i++)
{.Add(i, i);
}rand = new Random();(int i = 0; i < cEdge; )
{vertex1 = rand.Next(cVertex);vertex2 =
rand.Next(cVertex);edgeInserted = addEdge(vertex1, vertex2);(edgeInserted) i++;
}
}MGraph(int cVertex, int cEdge, Edge<W, D>[,]
cAdjacencyMatrix, bool cDirected)
: base(cVertex, cEdge, cDirected)
{= cAdjacencyMatrix;
}override bool getType()
{false;
}override bool addVertex(int vertexNumber)
{(vertexNumber < 0) return false;.Add(vertexNumber,
getVerticesCount());length = adjacencyMatrix.GetLength(0);(getVerticesCount()
== length) growArray();();true;
}void growArray()
{newLength;oldLength =
adjacencyMatrix.GetLength(0);(oldLength == 0) newLength = 2;newLength =
oldLength * 2;<W, D>[,] newAdjacencyMatrix = new Edge<W,
D>[newLength, newLength];(int i = 0; i < oldLength; i++)
{(int j = 0; j < oldLength; j++)[i, j] = adjacencyMatrix[i,
j];
}= newAdjacencyMatrix;
}override bool removeVertex(int vertexNumber)
{(vertexNumber < 0) return false;deleteIndex =
dictionary[vertexNumber];deleteEdgesCount = 0;(int i = 0; i <
getVerticesCount(); i++)
{(adjacencyMatrix[deleteIndex, i] != null)
deleteEdgesCount++;(adjacencyMatrix[i, deleteIndex] != null)
deleteEdgesCount++;
}(deleteEdgesCount);();(int i = deleteIndex; i <
getVerticesCount(); i++)(int j = 0; j < getVerticesCount() + 1; j++)
{[i, j] = adjacencyMatrix[i + 1, j];(adjacencyMatrix[i, j] !=
null)
{[i, j].Vertex1 = i;[i, j].Vertex2 = j;
}
}(int i = 0; i < getVerticesCount() + 1; i++)(int j =
deleteIndex; j < getVerticesCount(); j++)
{[i, j] = adjacencyMatrix[i, j + 1];(adjacencyMatrix[i, j] !=
null)
{[i, j].Vertex1 = i;[i, j].Vertex2 = j;
}
}clearIndex = getVerticesCount();(int i = 0; i <
getVerticesCount() ; i++)
{[clearIndex, i] = null;[i, clearIndex] = null;
}.Remove(vertexNumber);(int key = 0; key <=
MAXVERTICESCOUNT; key++)
{value;(dictionary.TryGetValue(key, out value))
{(value > vertexNumber)
{.Remove(key);.Add(key, value - 1);
}
}
}true;
}override bool addEdge(int vertex1, int vertex2)
{(hasEdge(vertex1, vertex2)) return false;(vertex1 == vertex2
|| !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) return
false;source = dictionary[vertex1];destanation = dictionary[vertex2];(source
< 0 || destanation < 0 || source == destanation) return false;(adjacencyMatrix[source,
destanation] != null) return false;[source, destanation] = new Edge<W,
D>(source, destanation);();(!isDirected())
{[destanation, source] = new Edge<W, D>(destanation,
source);
}true;
}override bool addEdge(Edge<W, D> edge)
{(edge == null) return false;[edge.Vertex1, edge.Vertex2] =
edge;();(!isDirected())
{<W, D> reverseEdge = new Edge<W,
D>(edge.Vertex2, edge.Vertex1, edge.Weight, edge.Data);[edge.Vertex2,
edge.Vertex1] = reverseEdge;
}true;
}override bool removeEdge(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return false;(!hasEdge(vertex1, vertex2))
return false;source = dictionary[vertex1];destanation =
dictionary[vertex2];(source < 0 || destanation < 0 || source == destanation)
return false;(adjacencyMatrix[source, destanation] == null) return
false;[source, destanation] = null;();(!isDirected())
{[destanation, source] = null;
}true;
}override bool hasEdge(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return
false;source;destanation;(dictionary.TryGetValue(vertex1, out source)
&& dictionary.TryGetValue(vertex2, out destanation))
{(source < 0 || destanation < 0 || source ==
destanation) return false;(adjacencyMatrix[source, destanation] != null) return
true;
}false;
}override W getEdgeWeight(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) throw new ArgumentException();(!hasEdge(vertex1,
vertex2)) throw new ArgumentException();source =
dictionary[vertex1];destanation = dictionary[vertex2];(source < 0 ||
destanation < 0 || source == destanation) new
ArgumentOutOfRangeException("Ребро не существует");(adjacencyMatrix[source,
destanation] != null)adjacencyMatrix[source, destanation].Weight;new
ArgumentOutOfRangeException("Ребро не существует");
}override bool setEdgeWeight(int vertex1, int vertex2, W
weight)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return false;(!hasEdge(vertex1, vertex2))
return false;source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0) return false;(adjacencyMatrix[source,
destanation] != null)
{[source, destanation].Weight = weight;(!isDirected())
adjacencyMatrix[destanation, source].Weight = weight;true;
}false;
}override D getEdgeData(int vertex1, int vertex2)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) throw new
ArgumentException();(!hasEdge(vertex1, vertex2)) throw new
ArgumentException();source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation > getVerticesCount()
- 1 || source < 0 || destanation < 0) throw new
ArgumentOutOfRangeException("this edge does not
exist");(adjacencyMatrix[source, destanation] !=
null)adjacencyMatrix[source, destanation].Data;new ArgumentOutOfRangeException("Ребро не существует");
}override bool setEdgeData(int vertex1, int vertex2, D data)
{(vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) ||
!dictionary.ContainsKey(vertex2)) return false;(!hasEdge(vertex1, vertex2))
return false;source = dictionary[vertex1];destanation =
dictionary[vertex2];(source > getVerticesCount() - 1 || destanation >
getVerticesCount() - 1 || source < 0 || destanation < 0) return
false;(adjacencyMatrix[source, destanation] != null)
{[source, destanation].Data = data;(!isDirected()) adjacencyMatrix[destanation,
source].Data = data;true;
}false;
}Object Clone()
{new MGraph<W, D>(getVerticesCount(), getEdgesCount(),
adjacencyMatrix, isDirected());
}override Graph<W, D> toMatrixGraph()
{this;
}override Graph<W, D> toListGraph()
{<W, D> lGraph = new LGraph<W,
D>(getVerticesCount(), isDirected());(isDirected())
{(int i = 0; i < getVerticesCount(); i++)(int j = 0; j
< getVerticesCount(); j++)
{(adjacencyMatrix[i, j] != null)
{.addEdge(adjacencyMatrix[i, j]);
}
}
}
{(int i = 0; i < getVerticesCount(); i++)(int j = i + 1; j
< getVerticesCount(); j++)
{(adjacencyMatrix[i, j] != null)
{.addEdge(adjacencyMatrix[i, j]);
}
}
}.dictionary = dictionary;lGraph;
}override List<int> getNeighbors(int vertexNumber)
{currentVertexNeighbor = 0;<int> result = new
List<int>();(true)
{(adjacencyMatrix[vertexNumber, currentVertexNeighbor] ==
null)
{(currentVertexNeighbor == getVerticesCount())
{result;
}++;
}.Add(adjacencyMatrix[vertexNumber,
currentVertexNeighbor++].Vertex2);
}
}class VertexIterator<W, D> : Iterator<W, D>
{VertexIterator(Graph<W, D> graphC)
: base(graphC)
{
}override void begin()
{(graph.getVerticesCount() == 0)
}min = 100;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Key < min) min = entry.Key;
}= new Edge<W, D>(min, 100);
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}max = 0;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Key > max) max = entry.Key;
}= new Edge<W, D>(max, 100);
}override void next()
{(currentPosition == null)
{;
}min = 100;old =
currentPosition.Vertex1;(KeyValuePair<int, int> entry in
graph.dictionary)
{(entry.Key < min && entry.Key > old) min =
entry.Key;
}(min != 100)
{= new Edge<W, D>(min, 100);
}
{= null;
}
}override Edge<W, D> state()
{currentPosition;
}
}class EdgeIterator<W, D> : Iterator<W, D>
{lastI = 0;lastJ = 0;edgesCount = 0;EdgeIterator(Graph<W,
D> graphC)
: base(graphC)
{
}override void begin()
{(graph.getVerticesCount() == 0)
{= null;;
}(graph.isDirected())
{(int i = 0; i < graph.getVerticesCount(); i++)(int j = 0;
j < graph.getVerticesCount(); j++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value == j)
destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;= j;= 1;;
}
}
}
{(int i = 0; i < graph.getVerticesCount(); i++)(int j = i;
j < graph.getVerticesCount(); j++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value == j)
destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;= j;= 1;;
}
}
}
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}
(graph.isDirected())
{(int i = graph.getVerticesCount() - 1; i >= 0; i--)(int j
= graph.getVerticesCount() - 1; j >= 0; j--)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value == j)
destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;= j;= 1;;
}
}
}
{(int i = graph.getVerticesCount() - 1; i >= 0; i--)(int j
= graph.getVerticesCount() - 1; j >= i; j--)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value == j)
destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;= j;= 1;;
}
}
}
}override void next()
{(currentPosition == null)
{;
}(edgesCount == graph.getEdgesCount())
{= null;;
}(graph.isDirected())
{(int i = lastI; i < graph.getVerticesCount(); i++)
{(int j = lastJ + 1; j < graph.getVerticesCount(); j++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value == j)
destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;= j;++;;
}
}= -1;
}
}
{(int i = lastI; i < graph.getVerticesCount(); i++)
{(int j = lastJ + 1; j < graph.getVerticesCount(); j++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value == j)
destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;= j;= 1;;
}
}= i;
}
}
}override Edge<W, D> state()
{currentPosition;
}
}class IncomingEdgesIterator<W, D> : Iterator<W,
D>
{lastI = 0;vertexNumb = -2;IncomingEdgesIterator(Graph<W,
D> graphC, int vertexNumbC)
: base(graphC)
{= graph.dictionary[vertexNumbC];();
}override void begin()
{(vertexNumb == -2) return;(graph.getVerticesCount() == 0)
{= null;;
}i;(i = 0; i < graph.getVerticesCount(); i++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value ==
vertexNumb) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}
}(i == graph.getVerticesCount())
{= null;
}
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}i;(i = graph.getVerticesCount() - 1; i >= 0; i--)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value ==
vertexNumb) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}
}(i == 0)
{= null;
}
}override void next()
{(currentPosition == null)
{;
}i;(i = lastI + 1; i < graph.getVerticesCount(); i++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == i) source = entry.Key;(entry.Value ==
vertexNumb) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}
}(i == graph.getVerticesCount())
{= null;
}
}override Edge<W, D> state()
{currentPosition;
}
}class OutGoingEdgesIterator<W, D> : Iterator<W,
D>
{lastI = 0;vertexNumb;OutGoingEdgesIterator(Graph<W, D>
graphC, int vertexNumbC)
: base(graphC)
{= graph.dictionary[vertexNumbC];();
}override void begin()
{(graph.getVerticesCount() == 0)
{= null;;
}i;(i = 0; i < graph.getVerticesCount(); i++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == vertexNumb) source = entry.Key;(entry.Value
== i) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}
}(i == graph.getVerticesCount())
{= null;
}
}override void end()
{(graph.getVerticesCount() == 0)
{= null;;
}i;(i = graph.getVerticesCount() - 1; i >= 0; i--)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == vertexNumb) source = entry.Key;(entry.Value
== i) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}(i == 0)
{= null;
}
}
}override void next()
{(currentPosition == null)
{;
}i;(i = lastI + 1; i < graph.getVerticesCount(); i++)
{source = 0;destanation = 0;(KeyValuePair<int, int>
entry in graph.dictionary)
{(entry.Value == vertexNumb) source = entry.Key;(entry.Value
== i) destanation = entry.Key;
}(graph.hasEdge(source, destanation))
{= new Edge<W, D>(source, destanation,
graph.getEdgeWeight(source, destanation), graph.getEdgeData(source,
destanation));= i;;
}
}(i == graph.getVerticesCount())
{= null;
}
}override Edge<W, D> state()
{currentPosition;
}
}
}
}