Проектирование программной коллекции "Простой, статический граф"

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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< W, D>

{

// конструктор без параметров

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< W, D> toListGraph ();

//конвертирование к М-граф

abstract public Graph< W, D> 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< W, D>: Graph< W, D>, 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< W, D> toListGraph ()

//конвертирование в М-граф

public override Graph< W, D> 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< W, D>: Graph<W, D>, 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< W, D> toListGraph ()

//конвертирование в М-граф

public override Graph< W, D> 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< 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>

{

//конструктор с параметрами

public VertexIterator (Graph< W, D> graphC)

: base (graphC)

//установка на начало

public override void benig ()

//установка в конец

public override void end ()

//переход к следующей

public override void next ()

public override Edge< W, D> state ()

}

2. 7 Итератор ребер

2.7.1 Описание формата

АТД «Итератор рёбер»:

Итератор служит для последовательного доступа к ребрам графа.

ДАННЫЕ:

Параметры:

currentPosition — текущее ребро в графе

graph — граф

ОПЕРАЦИИ:

Конструктор

Вход: нет

Предусловия: нет

Процесс: создание объекта итератора рёбер

Выход: нет

Постусловия: создан объект итератор рёбер графа

Установка итератора на первое ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на первое ребро графа

Выход: нет

Постусловия: итератор установлен на первое ребро графа

Установка итератора на послднее ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на послднее ребро графа

Выход: нет

Постусловия: итератор установлен на послднее ребро графа

Установка итератора на следующее ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на следующее ребро графа

Выход: нет

Постусловия: итератор установлен на следующее ребро графа

Получение дескриптора текущего ребра (проверка состояния)

Вход: нет

Предусловия: нет

Процесс: получение дескриптора ребра

Выход: дескриптор ребра, на которое указывает итератор, или null если итератор вышел за пределы графа

Постусловия: нет

КОНЕЦ АТД

2. 7.2 Клиентское определение класса

public class EdgeIterator< W, D>: Iterator< W, D>

{

//конструктор с параметрами

public EdgeIterator (Graph< W, D> graphC)

: base (graphC)

//установка на начало

public override void benig ()

//установка в конец

public override void end ()

//переход к следующей

public override void next ()

public override Edge< W, D> state ()

}

2. 8 Итератор исходящих ребер

2.8.1 Описание формата

АТД «Итератор исходящих рёбер»:

Итератор служит для последовательного доступа ко всем исходящим ребрам заданной вершины графа.

ДАННЫЕ:

Параметры:

vertexNumber — номер вершины

ОПЕРАЦИИ:

Конструктор

Вход: номер вершины vertexNumb

Предусловия: нет

Процесс: создание объекта итератора исходящих рёбер из заданной вершины

Выход: нет

Постусловия: создан объект итератор исходящих рёбер вершины

Установка итератора на первое исходящее ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на первое исходящее ребро вершины

Выход: нет

Постусловия: итератор установлен на первое ребро вершины

Установка итератора на послднее исходящее ребро вершины

Вход: нет

Предусловия: нет

Процесс: установка итератор на послднее исходящее ребро вершины

Выход: нет

Постусловия: итератор установлен на послднее исходящее ребро вершины

Установка итератора на следующее ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на следующее исходящее ребро вершины

Выход: нет

Постусловия: итератор установлен на следующее исходящее ребро вершины

Получение дескриптора текущего ребра (проверка состояния)

Вход: нет

Предусловия: нет

Процесс: получение дескриптора ребра

Выход: дескриптор исходящего ребра, вершины vertexNumber, на которое указывает итератор

Постусловия: нет

КОНЕЦ АТД

2. 8.2 Клиентское определение класса

public class OutgoingEdgesIterator< W, D>: Iterator< W, D>

{

//конструктор с параметрами

public OutgoingEdgesIterator (Graph< W, D> graphC)

: base (graphC)

//установка на начало

public override void benig ()

//установка в конец

public override void end ()

//переход к следующей

public override void next ()

public override Edge< W, D> state ()

}

2.9 Итератор входящих ребер

2.9.1 Описание формата

АТД «Итератор входящих рёбер»:

Итератор служит для последовательного доступа ко всем входящим ребрам заданной вершины графа.

ДАННЫЕ:

Параметры:

vertexNumber — номер вершины

ОПЕРАЦИИ:

Конструктор

Вход: номер вершины vertexNumb

Предусловия: нет

Процесс: создание объекта итератора входящих рёбер из заданной вершины

Выход: нет

Постусловия: создан объект итератор входящих рёбер вершины

Установка итератора на первое входящее ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на первое входящее ребро вершины

Выход: нет

Постусловия: итератор установлен на первое входящее ребро вершины

Установка итератора на последнее входящее ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на последнее входящее ребро вершины

Выход: нет

Постусловия: итератор установлен на последнее входящее ребро вершины

Установка итератора на следующее ребро

Вход: нет

Предусловия: нет

Процесс: установка итератор на следующее входящее ребро вершины

Выход: нет

Постусловия: итератор установлен на следующее входящее ребро вершины

Получение дескриптора текущего ребра (проверка состояния)

Вход: нет

Предусловия: нет

Процесс: получение дескриптора ребра

Выход: дескриптор входящего ребра, вершины vertexNumber, на которое указывает итератор

Постусловия: нет

КОНЕЦ АТД

2.9.2 Клиентское определение класса

public class IncomingEdgesIterator< W, D>: Iterator< W, D>

{

//конструктор с параметрами

public IncomingEdgesIterator (Graph< W, D> graphC)

: base (graphC)

//установка на начало

public override void benig ()

//установка в конец

public override void end ()

//переход на следующую

public override void next ()

public override Edge< W, D> 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< W, D>: 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< W, D> (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< W, D>

{

public static int MAXVERTICESCOUNT = 10;

private int verticesCount;

private int edgesCount;

private bool directed;

public SortedDictionary< int, int> 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< W, D> toListGraph ();

abstract public Graph< W, D> 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< W, D> 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< int> getNeighbors (int vertexNumber);

//---PARENT ITERATORS--------------------------------

public abstract class Iterator< W, D>

{

public Graph< W, D> graph;

public Edge< W, D> currentPosition;

public Iterator (Graph< W, D> graphC)

{

graph = graphC;

begin ();

}

public abstract void begin ();

public abstract void end ();

public abstract void next ();

public abstract Edge< W, D> state ();

}

}

}

LGraph. cs

using System;

using System. Collections. Generic;

using System. Linq;

using System. Text;

namespace RGR

{

class LGraph< W, D>: Graph< W, D>, ICloneable

{

private List< List<Edge<W, D> >> adjacencyList;

public LGraph ()

: base ()

{

adjacencyList = new List< List<Edge<W, D> >>();

dictionary = new SortedDictionary< int, int> ();

}

public LGraph (int cVertex, bool cDirected)

: base (cVertex, cDirected)

{

dictionary = new SortedDictionary< int, int> ();

adjacencyList = new List< List<Edge<W, D> >>(cVertex);

for (int i = 0; i < cVertex; i++)

{

adjacencyList. Add (new List< Edge<W, D> >());

dictionary. Add (i, i);

}

}

public LGraph (int cVertex, int cEdge, bool cDirected)

: base (cVertex, cDirected)

{

adjacencyList = new List< List<Edge<W, D> >>(cVertex);

dictionary = new SortedDictionary< int, int> ();

for (int i = 0; i < cVertex; i++)

{

adjacencyList. Add (new List< Edge<W, D> >());

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<Edge<W, D> >> 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< Edge<W, D> >());

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< Edge<W, D> > 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< W, D> newEdge = new Edge< W, D> (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< W, D> edge in adjacencyList[source])

{

if (edge. Vertex1 == source & & edge. Vertex2 == destanation)

return false;

}

adjacencyList[source]. Add (newEdge);

increaseEdgesCount ();

inserted = true;

}

if (inserted & & !isDirected ())

{

Edge< W, D> reverseEdge = new Edge< W, D> (destanation, source);

adjacencyList[destanation]. Add (reverseEdge);

}

return inserted;

}

public override bool addEdge (Edge< W, D> edge)

{

if (edge == null) return false;

adjacencyList[edge. Vertex1]. Add (edge);

increaseEdgesCount ();

if (!isDirected ())

{

Edge< W, D> reverseEdge = new Edge< W, D> (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< W, D> (getVerticesCount (), getEdgesCount (), adjacencyList, isDirected ());

}

public override Graph< W, D> toListGraph ()

{

return this;

}

public override Graph< W, D> toMatrixGraph ()

{

MGraph< W, D> mGraph = new MGraph< W, D> (getVerticesCount (), isDirected ());

foreach (List< Edge<W, D> > listOfEdges in adjacencyList)

foreach (Edge< W, D> edge in listOfEdges)

{

mGraph. addEdge (edge);

}

mGraph. dictionary = dictionary;

return mGraph;

}

public override List< int> getNeighbors (int vertexNumber)

{

int currentVertexNeighbor = 0;

List< int> result = new List< int>();

int min = 100;

if (adjacencyList[vertexNumber]. Count ≠ 0)

{

foreach (Edge< W, D> 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< W, D> 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< W, D>: Iterator< W, D>

{

public VertexIterator (Graph< W, D> graphC)

: base (graphC)

{

}

public override void begin ()

{

if (graph. getVerticesCount () == 0)

{

currentPosition = null;

return;

}

int min = 100;

foreach (KeyValuePair< int, int> entry in graph. dictionary)

{

if (entry. Key < min) min = entry. Key;

}

currentPosition = new Edge< W, D> (min, 100);

}

public override void end ()

{

if (graph. getVerticesCount () == 0)

{

currentPosition = null;

return;

}

int max = 0;

foreach (KeyValuePair< int, int> entry in graph. dictionary)

{

if (entry. Key > max) max = entry. Key;

}

currentPosition = new Edge< W, D> (max, 100);

}

public override void next ()

{

if (currentPosition == null)

{

return;

}

int min = 100;

int old = currentPosition. Vertex1;

foreach (KeyValuePair< int, int> entry in graph. dictionary)

{

if (entry. Key < min & & entry. Key > old) min = entry. Key;

}

if (min ≠ 100)

{

currentPosition = new Edge< W, D> (min, 100);

}

else

{

currentPosition = null;

}

}

public override Edge< W, D> state ()

{

return currentPosition;

}

}

public class EdgeIterator< W, D>: Iterator< W, D>

{

int lastI = 0;

int lastJ = 0;

int edgesCount = 0;

public EdgeIterator (Graph< W, D> 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< W, D>)graph). adjacencyList. Count)

{

currentPosition = null;

return;

}

if (((LGraph< W, D>)graph). adjacencyList[i]. Count == 0) i++;

else

{

isExist = true;

}

}

int source = ((LGraph< W, D>)graph). adjacencyList[i][j]. Vertex1;

int destanation = ((LGraph< W, D>)graph). adjacencyList[i][j]. Vertex2;

int sourceVertex = 0;

int destanationVertex = 0;

foreach (KeyValuePair< int, int> entry in graph. dictionary)

{

if (entry. Value == source) sourceVertex = entry. Key;

if (entry. Value == destanation) destanationVertex = entry. Key;

}

currentPosition = new Edge< W, D> (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< int, int> entry in graph. dictionary)

{

if (entry. Value == i) sourceVertex = entry. Key;

if (entry. Value == j) destanationVertex = entry. Key;

}

currentPosition = new Edge< W, D> (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< W, D>)graph). adjacencyList. Count — 1;

bool isExist = false;

while (!isExist)

{

if (i == -1)

{

currentPosition = null;

return;

}

if (((LGraph< W, D>)graph). adjacencyList[i]. Count == 0) i--;

else

{

isExist = true;

}

}

int j = ((LGraph< W, D>)graph). adjacencyList[i]. Count — 1;

int source = ((LGraph< W, D>)graph). adjacencyList[i][j]. Vertex1;

int destanation = ((LGraph< W, D>)graph). adjacencyList[i][j]. Vertex2;

int sourceVertex = i;

int destanationVertex = j;

foreach (KeyValuePair< int, int> entry in graph. dictionary)

{

if (entry. Value == source) sourceVertex = entry. Key;

if (entry. Value == destanation) destanationVertex = entry. Key;

}

currentPosition = new Edge< W, D> (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< int, int> entry in graph. dictionary)

{

if (entry. Value == i) sourceVertex = entry. Key;

if (entry. Value == j) destanationVertex = entry. Key;

}

currentPosition = new Edge< W, D> (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< W, D>)graph). adjacencyList[i]. Count)

{

j = 0;

i++;

}

bool isExist = false;

while (!isExist)

{

if (i == ((LGraph< W, D>)graph). adjacencyList. Count)

{

currentPosition = null;

return;

}

if (((LGraph< W, D>)graph). adjacencyList[i]. Count == 0) i++;

else

{

isExist = true;

}

}

if (i == ((LGraph< W, D>)graph). adjacencyList. Count)

{

currentPosition = null;

return;

}

int source = ((LGraph< W, D>)graph). adjacencyList[i][j]. Vertex1;

int destanation = ((LGraph< W, D>)graph). adjacencyList[i][j]. Vertex2;

int sourceVertex = 0;

int destanationVertex = 0;

foreach (KeyValuePair< int, int> entry in graph. dictionary)

{

if (entry. Value == source) sourceVertex = entry. Key;

if (entry. Value == destanation) destanationVertex = entry. Key;

}

currentPosition = new Edge< W, D> (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< W, D> (sourceVertex, destanationVertex, graph. getEdgeWeight (sourceVertex, destanationVertex), graph. getEdgeData (sourceVertex, destanationVertex));

lastI = i;

lastJ = j;

edgesCount++;

return;

}

}

lastJ = i;

}

}

}

public override Edge< W, D> state ()

{

return currentPosition;

}

}

public class IncomingEdgesIterator< W, D>: Iterator< W, D>

{

int lastI = 0;

int vertexNumb = -2;

public IncomingEdgesIterator (Graph< W, D> 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< int, int> 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< W, D> (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< int, int> 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< W, D> (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< int, int> 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< W, D> (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));

lastI = i;

return;

}

}

if (i == graph. getVerticesCount ())

{

currentPosition = null;

}

}

public override Edge< W, D> state ()

{

return currentPosition;

}

}

public class OutGoingEdgesIterator< W, D>: Iterator< W, D>

{

int lastI = 0;

int vertexNumb = -2;

public OutGoingEdgesIterator (Graph< W, D> 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< W, D>)graph). adjacencyList[vertexNumb]. Count == 0)

{

currentPosition = null;

return;

}

int i = 0;

int source = ((LGraph< W, D>)graph). adjacencyList[vertexNumb][i]. Vertex1;

int destanation = ((LGraph< W, D>)graph). adjacencyList[vertexNumb][i]. Vertex2;

bool sourceOK = false;

bool destanationOK = false;

foreach (KeyValuePair< int, int> 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< W, D> (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< W, D>)graph). adjacencyList[vertexNumb]. Count == 0)

{

currentPosition = null;

return;

}

int i = ((LGraph< W, D>)graph). adjacencyList[vertexNumb]. Count — 1;

int source = ((LGraph< W, D>)graph). adjacencyList[vertexNumb][i]. Vertex1;

int destanation = ((LGraph< W, D>)graph). adjacencyList[vertexNumb][i]. Vertex2;

bool sourceOK = false;

bool destanationOK = false;

foreach (KeyValuePair< int, int> 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< W, D> (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< W, D>)graph). adjacencyList[vertexNumb]. Count)

{

currentPosition = null;

return;

}

int source = ((LGraph< W, D>)graph). adjacencyList[vertexNumb][i]. Vertex1;

int destanation = ((LGraph< W, D>)graph). adjacencyList[vertexNumb][i]. Vertex2;

bool sourceOK = false;

bool destanationOK = false;

foreach (KeyValuePair< int, int> 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< W, D> (source, destanation, graph. getEdgeWeight (source, destanation), graph. getEdgeData (source, destanation));

lastI = i;

}

public override Edge< W, D> state ()

{

return currentPosition;

}

}

}

}

MGraph. cs

using System;

using System. Collections. Generic;

using System. Linq;

using System. Text;

namespace RGR

{

class MGraph< W, D>: Graph< W, D>, ICloneable

{

Edge< W, D> [,] adjacencyMatrix;

public MGraph (int cVertex, bool cDirected)

: base (cVertex, cDirected)

{

adjacencyMatrix = new Edge< W, D> [cVertex * 2, cVertex * 2];

dictionary = new SortedDictionary< int, int> ();

for (int i = 0; i < cVertex; i++)

{

dictionary. Add (i, i);

ПоказатьСвернуть
Заполнить форму текущей работой