Проектирование программной коллекции «Простой, статический граф»
Конструктор Вход: нет Предусловия: нет Процесс: создание объекта простого графа, граф не ориентированный Выход: нет Постусловия: создан пустой неориентированный граф Конструктор Вход: cVertex — число вершин, сDirected — признак ориентированности графа Предусловия: нет Процесс: создание объекта графа заданной ориентированности и вставка заданного числа вершин Выход: нет Постусловия: создан граф… Читать ещё >
Проектирование программной коллекции «Простой, статический граф» (реферат, курсовая, диплом, контрольная)
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,
GetEdgeWeight (v1,v2)возвращает вес ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2,
SetEdgeWeight (v1,v2, w) задает вес ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2, равным w.
GetEdgeData (v1,v2)возвращает данные ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2,
SetEdgeData (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.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.2 Клиентское определение класса
public abstract class Graph
{
// конструктор без параметров
public Graph ();
// конструктор с параметрами
public Graph (int cVertex, bool cDirected);
// конструктор с параметрами
public Graph (int cVertex, int cEdge, bool cDirected);
//опрос типа ориентированности
public bool isDirected ();
//опрос формы представления графа
abstract public bool getType ();
//опрос коэффициента насыщенности
public double denseCoef ();
//конвертирование в L-граф
abstract public Graph toListGraph ();
//конвертирование к М-граф
abstract public Graph toMatrixGraph ();
//вставка вершины
abstract public bool addVertex (int vertexNumber);
//удаление вершины
abstract public bool removeVertex (int vertexNumber);
//вставка ребра
abstract public bool addEdge (int vertex1, int vertex2);
//удаление ребра
abstract public bool removeEdge (int vertex1, int vertex2);
//проверка наличия ребра
abstract public bool hasEdge (int vertex1, int vertex2);
//получение веса ребра
abstract public W getEdgeWeight (int vertex1, int vertex2);
//установка веса ребра
abstract public bool setEdgeWeight (int vertex1, int vertex2, W weight);
//получение данных ребра
abstract public D getEdgeData (int vertex1, int vertex2);
//установка данных ребра
abstract 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 : Graph, ICloneable
{
// конструктор без параметров
public LGraph (): base ();
// конструктор с параметрами
public LGraph (int cVertex, bool cDirected): base (cVertex, cDirected);
// конструктор с параметрами
public LGraph (int cVertex, int cEdge, bool cDirected): base (cVertex, cDirected);
//опрос типа ориентированности
public bool hasDirected ();
//опрос формы представления графа
public override bool getType ()
//вставка вершины
public override bool addVertex (int vertexNumber)
//удаление вершины
public override bool removeVertex (int vertexNumber)
//вставка ребра
public override bool addEdge (int vertex1, int vertex2)
//удаление ребра
public override bool addEdge (int vertex1, int vertex2)
//проверка наличия ребра
public override bool hasEdge (int vertex1, int vertex2)
//получение веса ребра
public override W getEdgeWeight (int vertex1, int vertex2)
//установка веса ребра
public override bool setEdgeWeight (int vertex1, int vertex2, W weight)
//получение данных ребра
public override D getEdgeData (int vertex1, int vertex2)
//установка данных ребра
public override bool setEdgeData (int vertex1, int vertex2, D data)
//конвертирование в L-граф
public override Graph toListGraph ()
//конвертирование в М-граф
public override Graph toMatrixGraph ()
}
2.4 АТД «M-граф»
2.4.1 Формат АТД
АТД «Mграф»:
Класс наследник класса «Простой, статический граф». Наследует все операции родительского класса. Представляет граф в виде матрицы смежности.
ДАННЫЕ:
Параметры:
adjacencyMatrix — матрица смежности ОПЕРАЦИИ:
Конструктор Вход: cVertex — число вершин, сDirected — признак ориентированности графа Предусловия: нет Процесс: создание объекта М-графа заданной ориентированности и вставка заданного числа вершин Выход: нет Постусловия: создан М-граф заданной ориентированности, с количеством вершин cVertex
Конструктор Вход: cVertex — число вершин, cEdge-число рёбер, сDirected — признак ориентированности графа Предусловия: нет Процесс: создание объекта М-графа заданной ориентированности и вставка заданного числа вершин и рёбер Выход: нет Постусловия: создан М-граф заданной ориентированности, с количеством вершин cVertex и количеством ребер cEdge.
Конструктор копирования Вход: объект типа М-граф graph
Предусловия: нет Процесс: создание нового М-графа и копирование в него всех свойств graph, а также вершин и рёбер Выход: нет Постусловие: создание М-графа с такой же структурой и элементами, что у graph
КОНЕЦ АТД
2.4.2 Клиентское определение класса
class MGraph: Graph, ICloneable
{
// конструктор без параметров
public МGraph (): base ();
// конструктор с параметрами
public МGraph (int cVertex, bool cDirected): base (cVertex, cDirected);
// конструктор с параметрами
public МGraph (int cVertex, int cEdge, bool cDirected): base (cVertex, cDirected);
//опрос типа ориентированности
public bool isDirected ();
//опрос формы представления графа
public override bool getType ()
//вставка вершины
public override bool addVertex (int vertexNumber)
//удаление вершины
public override bool removeVertex (int vertexNumber)
//вставка ребра
public override bool addEdge (int vertex1, int vertex2)
//удаление ребра
public override bool removeEdge (int vertex1, int vertex2)
//проверка наличия ребра
public override bool hasEdge (int vertex1, int vertex2)
//получение веса ребра
public override W getEdgeWeight (int vertex1, int vertex2)
//установка веса ребра
public override bool setEdgeWeight (int vertex1, int vertex2, W weight)
//получение данных ребра
public override D getEdgeData (int vertex1, int vertex2)
//установка данных ребра
public override bool setEdgeData (int vertex1, int vertex2, D data)
//конвертирование в L-граф
public override Graph toListGraph ()
//конвертирование в М-граф
public override Graph toMatrixGraph ()
}
2.5 АТД «Дескриптор ребра»
2.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: 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: Iterator
{
//конструктор с параметрами
public VertexIterator (Graph graphC)
: base (graphC)
//установка на начало
public override void benig ()
//установка в конец
public override void end ()
//переход к следующей
public override void next ()
public override Edge state ()
}
2.7 Итератор ребер
2.7.1 Описание формата
АТД «Итератор рёбер»:
Итератор служит для последовательного доступа к ребрам графа.
ДАННЫЕ:
Параметры:
currentPosition — текущее ребро в графе
graph — граф ОПЕРАЦИИ:
Конструктор Вход: нет Предусловия: нет Процесс: создание объекта итератора рёбер Выход: нет Постусловия: создан объект итератор рёбер графа Установка итератора на первое ребро Вход: нет Предусловия: нет Процесс: установка итератор на первое ребро графа Выход: нет Постусловия: итератор установлен на первое ребро графа Установка итератора на послднее ребро Вход: нет Предусловия: нет Процесс: установка итератор на послднее ребро графа Выход: нет Постусловия: итератор установлен на послднее ребро графа Установка итератора на следующее ребро Вход: нет Предусловия: нет Процесс: установка итератор на следующее ребро графа Выход: нет Постусловия: итератор установлен на следующее ребро графа Получение дескриптора текущего ребра (проверка состояния) Вход: нет Предусловия: нет Процесс: получение дескриптора ребра Выход: дескриптор ребра, на которое указывает итератор, или null если итератор вышел за пределы графа Постусловия: нет КОНЕЦ АТД
2.7.2 Клиентское определение класса
public class EdgeIterator: Iterator
{
//конструктор с параметрами
public EdgeIterator (Graph graphC)
: base (graphC)
//установка на начало
public override void benig ()
//установка в конец
public override void end ()
//переход к следующей
public override void next ()
public override Edge state ()
}
2.8 Итератор исходящих ребер
2.8.1 Описание формата
АТД «Итератор исходящих рёбер»:
Итератор служит для последовательного доступа ко всем исходящим ребрам заданной вершины графа.
ДАННЫЕ:
Параметры:
vertexNumber — номер вершины ОПЕРАЦИИ:
Конструктор Вход: номер вершины vertexNumb
Предусловия: нет Процесс: создание объекта итератора исходящих рёбер из заданной вершины
Выход: нет Постусловия: создан объект итератор исходящих рёбер вершины Установка итератора на первое исходящее ребро Вход: нет Предусловия: нет Процесс: установка итератор на первое исходящее ребро вершины Выход: нет Постусловия: итератор установлен на первое ребро вершины Установка итератора на послднее исходящее ребро вершины Вход: нет Предусловия: нет Процесс: установка итератор на послднее исходящее ребро вершины Выход: нет Постусловия: итератор установлен на послднее исходящее ребро вершины Установка итератора на следующее ребро Вход: нет Предусловия: нет Процесс: установка итератор на следующее исходящее ребро вершины Выход: нет Постусловия: итератор установлен на следующее исходящее ребро вершины Получение дескриптора текущего ребра (проверка состояния) Вход: нет Предусловия: нет Процесс: получение дескриптора ребра Выход: дескриптор исходящего ребра, вершины vertexNumber, на которое указывает итератор Постусловия: нет КОНЕЦ АТД
2.8.2 Клиентское определение класса
public class OutgoingEdgesIterator: Iterator
{
//конструктор с параметрами
public OutgoingEdgesIterator (Graph graphC)
: base (graphC)
//установка на начало
public override void benig ()
//установка в конец
public override void end ()
//переход к следующей
public override void next ()
public override Edge state ()
}
2.9 Итератор входящих ребер
2.9.1 Описание формата
АТД «Итератор входящих рёбер»:
Итератор служит для последовательного доступа ко всем входящим ребрам заданной вершины графа.
ДАННЫЕ:
Параметры:
vertexNumber — номер вершины ОПЕРАЦИИ:
Конструктор Вход: номер вершины vertexNumb
Предусловия: нет Процесс: создание объекта итератора входящих рёбер из заданной вершины
Выход: нет Постусловия: создан объект итератор входящих рёбер вершины Установка итератора на первое входящее ребро Вход: нет Предусловия: нет Процесс: установка итератор на первое входящее ребро вершины Выход: нет Постусловия: итератор установлен на первое входящее ребро вершины Установка итератора на последнее входящее ребро Вход: нет Предусловия: нет Процесс: установка итератор на последнее входящее ребро вершины Выход: нет Постусловия: итератор установлен на последнее входящее ребро вершины Установка итератора на следующее ребро Вход: нет Предусловия: нет Процесс: установка итератор на следующее входящее ребро вершины Выход: нет Постусловия: итератор установлен на следующее входящее ребро вершины Получение дескриптора текущего ребра (проверка состояния) Вход: нет Предусловия: нет Процесс: получение дескриптора ребра Выход: дескриптор входящего ребра, вершины vertexNumber, на которое указывает итератор Постусловия: нет КОНЕЦ АТД
2.9.2 Клиентское определение класса
public class IncomingEdgesIterator: Iterator
{
//конструктор с параметрами
public IncomingEdgesIterator (Graph graphC)
: base (graphC)
//установка на начало
public override void benig ()
//установка в конец
public override void end ()
//переход на следующую
public override void next ()
public override Edge state ()
}
Заключение
граф программный статический
В ходе работы над расчётно-графической работой, была спроектирована и реализована универсальная коллекция «Простой статический граф» с графическим интерфейсом. Были получены знания о работы с разными типами графов, а также решения различных проблем связанных с их построением. В ходе создания графического интерфейса были получены навыки визуализации графов.
Список используемой литературы
1. Р. Сэджвик, «Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах», 2002 г. — 496 с.
Приложение
Исходные коды
Edge.cs
using System;
using System.Collections.Generic;
using System. Linq;
using System. Text;
namespace RGR
{
public class Edge: ICloneable
{
private int vertex1;
private int vertex2;
private W weight;
private D data;
public Edge ()
{
vertex1 = -1;
vertex2 = -1;
}
public Edge (int v1, int v2)
{
vertex1 = v1;
vertex2 = v2;
}
public Edge (int v1, int v2, W w)
{
vertex1 = v1;
vertex2 = v2;
weight = w;
}
public Edge (int v1, int v2, W w, D d)
{
vertex1 = v1;
vertex2 = v2;
weight = w;
data = d;
}
public Object Clone ()
{
return new Edge (Vertex1, Vertex2, Weight, Data);
}
public int Vertex1
{
set
{
vertex1 = value;
}
get
{
return vertex1;
}
}
public int Vertex2
{
set
{
vertex2 = value;
}
get
{
return vertex2;
}
}
public W Weight
{
set
{
weight =value;
}
get
{
return weight;
}
}
public D Data
{
set
{
data = value;
}
get
{
return data;
}
}
}
}
Graph.cs
using System;
using System.Collections.Generic;
using System. Linq;
using System. Text;
namespace RGR
{
public abstract class Graph
{
public static int MAXVERTICESCOUNT = 10;
private int verticesCount;
private int edgesCount;
private bool directed;
public SortedDictionary dictionary;
public Graph ()
{
verticesCount = 0;
edgesCount = 0;
directed = false;
}
public Graph (int cVertex, bool cDirected)
{
verticesCount = cVertex;
edgesCount = 0;
directed = cDirected;
}
public Graph (int cVertex, int cEdge, bool cDirected)
{
verticesCount = cVertex;
edgesCount = cEdge;
directed = cDirected;
}
public int getVerticesCount ()
{
return verticesCount;
}
public void increaseVerticesCount ()
{
verticesCount++;
}
public void decreaseVerticesCount ()
{
verticesCount—;
}
public int getEdgesCount ()
{
return edgesCount;
}
public void increaseEdgesCount ()
{
edgesCount++;
}
public void decreaseEdgesCount ()
{
edgesCount—;
}
public void decreaseEdgesCount (int decrease)
{
edgesCount -= decrease;
}
public bool isDirected ()
{
return directed;
}
abstract public bool getType ();
public double denseCoef ()
{
if (directed) return (double)edgesCount / ((double)verticesCount * ((double)verticesCount — 1.0));
return 2.0 * (double)edgesCount / ((double)verticesCount * ((double)verticesCount — 1.0));
}
abstract public Graph toListGraph ();
abstract public Graph toMatrixGraph ();
abstract public bool addVertex (int vertexNumber);
abstract public bool removeVertex (int vertexNumber);
abstract public bool addEdge (int vertex1, int vertex2);
abstract public bool addEdge (Edge edge);
abstract public bool removeEdge (int vertex1, int vertex2);
abstract public bool hasEdge (int vertex1, int vertex2);
abstract public W getEdgeWeight (int vertex1, int vertex2);
abstract public bool setEdgeWeight (int vertex1, int vertex2, W weight);
abstract public D getEdgeData (int vertex1, int vertex2);
abstract public bool setEdgeData (int vertex1, int vertex2, D data);
abstract public List getNeighbors (int vertexNumber);
//—-PARENT ITERATORS————————————————
public abstract class Iterator
{
public Graph graph;
public Edge currentPosition;
public Iterator (Graph graphC)
{
graph = graphC;
begin ();
}
public abstract void begin ();
public abstract void end ();
public abstract void next ();
public abstract Edge state ();
}
}
}
LGraph.cs
using System;
using System.Collections.Generic;
using System. Linq;
using System. Text;
namespace RGR
{
class LGraph: Graph, ICloneable
{
private List>> adjacencyList;
public LGraph ()
: base ()
{
adjacencyList = new List>>();
dictionary = new SortedDictionary ();
}
public LGraph (int cVertex, bool cDirected)
: base (cVertex, cDirected)
{
dictionary = new SortedDictionary ();
adjacencyList = new List>>(cVertex);
for (int i = 0; i < cVertex; i++)
{
adjacencyList.Add (new List>());
dictionary.Add (i, i);
}
}
public LGraph (int cVertex, int cEdge, bool cDirected)
: base (cVertex, cDirected)
{
adjacencyList = new List>>(cVertex);
dictionary = new SortedDictionary ();
for (int i = 0; i < cVertex; i++)
{
adjacencyList.Add (new List>());
dictionary.Add (i, i);
}
Random rand = new Random ();
for (int i = 0; i < cEdge;)
{
int vertex1 = rand. Next (cVertex);
int vertex2 = rand. Next (cVertex);
bool edgeInserted = addEdge (vertex1, vertex2);
if (edgeInserted) i++;
}
}
public LGraph (int cVertex, int cEdge, List>> list, bool cDirected)
: base (cVertex, cEdge, cDirected)
{
adjacencyList = list;
}
public override bool getType ()
{
return true;
}
public override bool addVertex (int vertexNumber)
{
if (vertexNumber < 0) return false;
dictionary.Add (vertexNumber, adjacencyList. Count);
adjacencyList.Add (new List>());
increaseVerticesCount ();
return true;
}
public override bool removeVertex (int vertexNumber)
{
if (vertexNumber < 0) return false;
else
{
int deleteIndex = dictionary[vertexNumber];
decreaseEdgesCount (adjacencyList[deleteIndex].Count);
adjacencyList.RemoveAt (deleteIndex);
decreaseVerticesCount ();
foreach (List> list in adjacencyList)
{
for (int i = 0; i < list. Count;)
{
if (list[i]. Vertex2 == deleteIndex)
{
list.RemoveAt (i);
decreaseEdgesCount ();
}
else
{
if (list[i]. Vertex1 > deleteIndex) list[i]. Vertex1—;
if (list[i]. Vertex2 > deleteIndex) list[i]. Vertex2—;
i++;
}
}
}
dictionary.Remove (vertexNumber);
for (int key = 0; key <= MAXVERTICESCOUNT; key++)
{
int value;
if (dictionary.TryGetValue (key, out value))
{
if (value > vertexNumber)
{
dictionary.Remove (key);
dictionary.Add (key, value — 1);
}
}
}
return true;
}
}
public override bool addEdge (int vertex1, int vertex2)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey (vertex1) || !dictionary.ContainsKey (vertex2)) return false;
if (hasEdge (vertex1, vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
Edge newEdge = new Edge (source, destanation);
bool inserted = false;
if (source < 0 || destanation < 0 || source == destanation) return false;
if (adjacencyList[source]. Count == 0)
{
adjacencyList[source]. Add (newEdge);
increaseEdgesCount ();
inserted = true;
}
else
{
foreach (Edge edge in adjacencyList[source])
{
if (edge.Vertex1 == source && edge. Vertex2 == destanation)
return false;
}
adjacencyList[source]. Add (newEdge);
increaseEdgesCount ();
inserted = true;
}
if (inserted && !isDirected ())
{
Edge reverseEdge = new Edge (destanation, source);
adjacencyList[destanation]. Add (reverseEdge);
}
return inserted;
}
public override bool addEdge (Edge edge)
{
if (edge == null) return false;
adjacencyList[edge.Vertex1]. Add (edge);
increaseEdgesCount ();
if (!isDirected ())
{
Edge reverseEdge = new Edge (edge.Vertex2, edge. Vertex1, edge. Weight, edge. Data);
adjacencyList[edge.Vertex2]. Add (reverseEdge);
}
return true;
}
public override bool removeEdge (int vertex1, int vertex2)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey (vertex1) || !dictionary.ContainsKey (vertex2)) return false;
if (!hasEdge (vertex1, vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source > getVerticesCount () — 1 || destanation > getVerticesCount () — 1 || source < 0 || destanation < 0) return false;
for (int i = 0; i < adjacencyList[source]. Count; i++)
if (adjacencyList[source][i]. Vertex2 == destanation)
{
adjacencyList[source]. RemoveAt (i);
decreaseEdgesCount ();
if (!isDirected ())
{
for (int j = 0; j < adjacencyList[destanation]. Count; j++)
{
if (adjacencyList[destanation][j]. Vertex2 == source)
adjacencyList[destanation]. RemoveAt (j);
}
}
return true;
}
return false;
}
public override bool hasEdge (int vertex1, int vertex2)
{
int source;
int destanation;
if (dictionary.TryGetValue (vertex1, out source) && dictionary. TryGetValue (vertex2, out destanation))
return false;
}
public override W getEdgeWeight (int vertex1, int vertex2)
!dictionary.ContainsKey (vertex2)) throw new ArgumentException ();
if (!hasEdge (vertex1, vertex2)) throw new ArgumentException ();
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source > getVerticesCount () — 1
public override bool setEdgeWeight (int vertex1, int vertex2, W weight)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey (vertex1) || !dictionary.ContainsKey (vertex2)) return false;
if (!hasEdge (vertex1, vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source > getVerticesCount () — 1 || destanation > getVerticesCount () — 1 || source < 0 || destanation < 0) return false;
for (int i = 0; i < adjacencyList[source]. Count; i++)
if (adjacencyList[source][i]. Vertex2 == destanation)
{
adjacencyList[source][i]. Weight = weight;
return true;
}
return false;
}
public override D getEdgeData (int vertex1, int vertex2)
public override bool setEdgeData (int vertex1, int vertex2, D data)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey (vertex1) || !dictionary.ContainsKey (vertex2)) return false;
if (!hasEdge (vertex1, vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source > getVerticesCount () — 1 || destanation > getVerticesCount () — 1 || source < 0 || destanation < 0) return false;
for (int i = 0; i < adjacencyList[source]. Count; i++)
if (adjacencyList[source][i]. Vertex2 == destanation)
{
adjacencyList[source][i]. Data = data;
return true;
}
return false;
}
public Object Clone ()
{
return new LGraph (getVerticesCount (), getEdgesCount (), adjacencyList, isDirected ());
}
public override Graph toListGraph ()
{
return this;
}
public override Graph toMatrixGraph ()
{
MGraph mGraph = new MGraph (getVerticesCount (), isDirected ());
foreach (List> listOfEdges in adjacencyList)
foreach (Edge edge in listOfEdges)
{
mGraph.addEdge (edge);
}
mGraph.dictionary = dictionary;
return mGraph;
}
public override List getNeighbors (int vertexNumber)
{
int currentVertexNeighbor = 0;
List result = new List ();
int min = 100;
if (adjacencyList[vertexNumber]. Count ≠ 0)
{
foreach (Edge edge in adjacencyList[vertexNumber])
{
if (edge.Vertex2 < min && edge. Vertex2 >= currentVertexNeighbor)
{
min = edge. Vertex2;
}
}
result.Add (min);
currentVertexNeighbor = min;
}
while (true)
{
int old = currentVertexNeighbor;
min = 100;
foreach (Edge edge in adjacencyList[vertexNumber])
{
if (edge.Vertex2 < min && edge. Vertex2 > old)
{
min = edge. Vertex2;
}
}
if (min == 100)
{
currentVertexNeighbor = 0;
return result;
}
currentVertexNeighbor = min;
result.Add (currentVertexNeighbor);
}
}
public class VertexIterator: Iterator
{
public VertexIterator (Graph graphC)
: base (graphC)
{
}
public override void begin ()
{
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
int min = 100;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Key < min) min = entry. Key;
}
currentPosition = new Edge (min, 100);
}
public override void end ()
{
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
int max = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Key > max) max = entry. Key;
}
currentPosition = new Edge (max, 100);
}
public override void next ()
{
if (currentPosition == null)
{
return;
}
int min = 100;
int old = currentPosition. Vertex1;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Key < min && entry. Key > old) min = entry. Key;
}
if (min ≠ 100)
{
currentPosition = new Edge (min, 100);
}
else
{
currentPosition = null;
}
}
public override Edge state ()
{
return currentPosition;
}
}
public class EdgeIterator: Iterator
{
int lastI = 0;
int lastJ = 0;
int edgesCount = 0;
public EdgeIterator (Graph graphC)
: base (graphC)
{
}
public override void begin ()
{
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
if (graph.isDirected ())
{
int i = 0;
int j = 0;
bool isExist = false;
while (!isExist)
{
if (i == ((LGraph)graph).adjacencyList.Count)
{
currentPosition = null;
return;
}
if (((LGraph)graph).adjacencyList[i]. Count == 0) i++;
else
{
isExist = true;
}
}
int source = ((LGraph)graph).adjacencyList[i][j]. Vertex1;
int destanation = ((LGraph)graph).adjacencyList[i][j]. Vertex2;
int sourceVertex = 0;
int destanationVertex = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == source) sourceVertex = entry. Key;
if (entry.Value == destanation) destanationVertex = entry. Key;
}
currentPosition = new Edge (sourceVertex, destanationVertex, graph. getEdgeWeight (sourceVertex, destanationVertex), graph. getEdgeData (sourceVertex, destanationVertex));
lastI = i;
lastJ = j;
edgesCount = 1;
}
else
{
for (int i = 0; i <= MAXVERTICESCOUNT; i++)
{
for (int j = 0; j <= MAXVERTICESCOUNT; j++)
{
if (!graph.dictionary.ContainsKey (i) || !graph.dictionary.ContainsKey (j)) continue;
if (graph.hasEdge (graph.dictionary[i], graph. dictionary[j]))
{
int sourceVertex = 0;
int destanationVertex = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == i) sourceVertex = entry. Key;
if (entry.Value == j) destanationVertex = entry. Key;
}
currentPosition = new Edge (sourceVertex, destanationVertex, graph. getEdgeWeight (sourceVertex, destanationVertex), graph. getEdgeData (sourceVertex, destanationVertex));
lastI = i;
lastJ = j;
edgesCount = 1;
return;
}
}
lastJ = i;
}
}
}
public override void end ()
{
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
if (graph.isDirected ())
{
int i = ((LGraph)graph).adjacencyList.Count — 1;
bool isExist = false;
while (!isExist)
{
if (i == -1)
{
currentPosition = null;
return;
}
if (((LGraph)graph).adjacencyList[i]. Count == 0) i—;
else
{
isExist = true;
}
}
int j = ((LGraph)graph).adjacencyList[i]. Count — 1;
int source = ((LGraph)graph).adjacencyList[i][j]. Vertex1;
int destanation = ((LGraph)graph).adjacencyList[i][j]. Vertex2;
int sourceVertex = i;
int destanationVertex = j;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == source) sourceVertex = entry. Key;
if (entry.Value == destanation) destanationVertex = entry. Key;
}
currentPosition = new Edge (sourceVertex, destanationVertex, graph. getEdgeWeight (sourceVertex, destanationVertex), graph. getEdgeData (sourceVertex, destanationVertex));
edgesCount = graph. getEdgesCount ();
}
else
{
for (int i = MAXVERTICESCOUNT; i >= 0; i—)
for (int j = MAXVERTICESCOUNT; j >= i; j—)
{
if (i == j || !graph.dictionary.ContainsKey (i) || !graph.dictionary.ContainsKey (j)) continue;
if (graph.hasEdge (i, j))
{
int sourceVertex = 0;
int destanationVertex = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == i) sourceVertex = entry. Key;
if (entry.Value == j) destanationVertex = entry. Key;
}
currentPosition = new Edge (sourceVertex, destanationVertex, graph. getEdgeWeight (sourceVertex, destanationVertex), graph. getEdgeData (sourceVertex, destanationVertex));
lastI = i;
lastJ = j;
edgesCount = graph. getEdgesCount ();
return;
}
}
}
}
public override void next ()
{
if (currentPosition == null)
{
return;
}
if (edgesCount == graph. getEdgesCount ())
{
currentPosition = null;
return;
}
if (graph.isDirected ())
{
int i = lastI;
int j = lastJ + 1;
if (j == ((LGraph)graph).adjacencyList[i]. Count)
{
j = 0;
i++;
}
bool isExist = false;
while (!isExist)
{
if (i == ((LGraph)graph).adjacencyList.Count)
{
currentPosition = null;
return;
}
if (((LGraph)graph).adjacencyList[i]. Count == 0) i++;
else
{
isExist = true;
}
}
if (i == ((LGraph)graph).adjacencyList.Count)
{
currentPosition = null;
return;
}
int source = ((LGraph)graph).adjacencyList[i][j]. Vertex1;
int destanation = ((LGraph)graph).adjacencyList[i][j]. Vertex2;
int sourceVertex = 0;
int destanationVertex = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == source) sourceVertex = entry. Key;
if (entry.Value == destanation) destanationVertex = entry. Key;
}
currentPosition = new Edge (sourceVertex, destanationVertex, graph. getEdgeWeight (sourceVertex, destanationVertex), graph. getEdgeData (sourceVertex, destanationVertex));
edgesCount++;
lastI = i;
lastJ = j;
return;
}
else
{
for (int i = lastI; i <= MAXVERTICESCOUNT; i++)
{
for (int j = lastJ + 1; j <= MAXVERTICESCOUNT; j++)
{
if (i == j || !graph.dictionary.ContainsKey (i) || !graph.dictionary.ContainsKey (j)) continue;
if (graph.hasEdge (i, j))
{
int sourceVertex = i;
int destanationVertex = j;
currentPosition = new Edge (sourceVertex, destanationVertex, graph. getEdgeWeight (sourceVertex, destanationVertex), graph. getEdgeData (sourceVertex, destanationVertex));
lastI = i;
lastJ = j;
edgesCount++;
return;
}
}
lastJ = i;
}
}
}
public override Edge state ()
{
return currentPosition;
}
}
public class IncomingEdgesIterator: Iterator
{
int lastI = 0;
int vertexNumb = -2;
public IncomingEdgesIterator (Graph graphC, int vertexNumbC)
: base (graphC)
{
vertexNumb = graph. dictionary[vertexNumbC];
begin ();
}
public override void begin ()
{
if (vertexNumb == -2) return;
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
for (int i = 0; i < graph. getVerticesCount (); i++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == i) source = entry. Key;
if (entry.Value == vertexNumb) destanation = entry. Key;
}
if (graph.hasEdge (source, destanation))
{
currentPosition = new Edge (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));
lastI = i;
return;
}
if (i == graph. getVerticesCount () — 1)
{
currentPosition = null;
}
}
}
public override void end ()
{
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
for (int i = graph. getVerticesCount () — 1; i >= 0; i—)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == i) source = entry. Key;
if (entry.Value == vertexNumb) destanation = entry. Key;
}
if (graph.hasEdge (source, destanation))
{
currentPosition = new Edge (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));
lastI = i;
return;
}
if (i == 0)
{
currentPosition = null;
}
}
}
public override void next ()
{
if (currentPosition == null)
{
return;
}
int i;
for (i = lastI + 1; i < graph. getVerticesCount (); i++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == i) source = entry. Key;
if (entry.Value == vertexNumb) destanation = entry. Key;
}
if (graph.hasEdge (source, destanation))
{
currentPosition = new Edge (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));
lastI = i;
return;
}
}
if (i == graph. getVerticesCount ())
{
currentPosition = null;
}
}
public override Edge state ()
{
return currentPosition;
}
}
public class OutGoingEdgesIterator: Iterator
{
int lastI = 0;
int vertexNumb = -2;
public OutGoingEdgesIterator (Graph graphC, int vertexNumbC)
: base (graphC)
{
vertexNumb = graph. dictionary[vertexNumbC];
begin ();
}
public override void begin ()
{
if (vertexNumb == -2) return;
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
if (((LGraph)graph).adjacencyList[vertexNumb]. Count == 0)
{
currentPosition = null;
return;
}
int i = 0;
int source = ((LGraph)graph).adjacencyList[vertexNumb][i]. Vertex1;
int destanation = ((LGraph)graph).adjacencyList[vertexNumb][i]. Vertex2;
bool sourceOK = false;
bool destanationOK = false;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == source && !sourceOK)
{
source = entry. Key;
sourceOK = true;
}
if (entry.Value == destanation && !destanationOK)
{
destanation = entry. Key;
destanationOK = true;
}
}
currentPosition = new Edge (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));
lastI = i;
}
public override void end ()
{
if (graph.getVerticesCount () == 0)
{
currentPosition = null;
return;
}
if (((LGraph)graph).adjacencyList[vertexNumb]. Count == 0)
{
currentPosition = null;
return;
}
int i = ((LGraph)graph).adjacencyList[vertexNumb]. Count — 1;
int source = ((LGraph)graph).adjacencyList[vertexNumb][i]. Vertex1;
int destanation = ((LGraph)graph).adjacencyList[vertexNumb][i]. Vertex2;
bool sourceOK = false;
bool destanationOK = false;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == source && !sourceOK)
{
source = entry. Key;
sourceOK = true;
}
if (entry.Value == destanation && !destanationOK)
{
destanation = entry. Key;
destanationOK = true;
}
}
currentPosition = new Edge (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));
lastI = i;
}
public override void next ()
{
if (currentPosition == null)
{
return;
}
int i = lastI + 1;
if (i == ((LGraph)graph).adjacencyList[vertexNumb]. Count)
{
currentPosition = null;
return;
}
int source = ((LGraph)graph).adjacencyList[vertexNumb][i]. Vertex1;
int destanation = ((LGraph)graph).adjacencyList[vertexNumb][i]. Vertex2;
bool sourceOK = false;
bool destanationOK = false;
foreach (KeyValuePair entry in graph. dictionary)
{
if (entry.Value == source && !sourceOK)
{
source = entry. Key;
sourceOK = true;
}
if (entry.Value == destanation && !destanationOK)
{
destanation = entry. Key;
destanationOK = true;
}
}
currentPosition = new Edge (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));
lastI = i;
}
public override Edge state ()
{
return currentPosition;
}
}
}
}
MGraph.cs
using System;
using System.Collections.Generic;
using System. Linq;
using System. Text;
namespace RGR
{
class MGraph: Graph, ICloneable
{
Edge[,] adjacencyMatrix;
public MGraph (int cVertex, bool cDirected)
: base (cVertex, cDirected)
{
adjacencyMatrix = new Edge[cVertex * 2, cVertex * 2];
dictionary = new SortedDictionary ();
for (int i = 0; i < cVertex; i++)
{
dictionary.Add (i, i);