ргр по алгоритмам и структурам данных. АиСД РГР, ключников. Разработка атд Простой граф

• Название: Разработка атд Простой граф
• Анкор: ргр по алгоритмам и структурам данных
• Дата: 20.12.2022
• Размер: 135.4 Kb.
• Имя файла: АиСД РГР, ключников.docx
• Тип: Документы; #854773
• страница: 8 из 12

9.2. Клиентское определение класса «итератор входящих ребер»

internal abstract class IteratorInputEdge
public IteratorInputEdge(Vertex v, AbstractGraph g)

public static IteratorInputEdge MakeIt(Vertex v, AbstractGraph g)


public abstract bool Beg();

public abstract bool End();

public abstract void Next();

public abstract Edge Input();

11. 10. АТД «Задача 2»

    1. 10.1. Формат АТД «задача 2»

Задача 2 – формирование двусвязного неориентированного графа.

АТД «Задача 2» является клиентом для АТД «Простой граф». Объект может работать с графом, структура которого изменяется, а также перенастраиваться на другой граф.



ОПЕРАЦИИ:

Конструктор

Вход: ссылка на объект типа «Простой граф» , s – дескриптор начальной вершины

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

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

Выход: нет

Постусловия: создан объект задачи 1, и найдено её решение

Конструктор копирования

Вход: task - ссылка на объект типа «Задача 1»

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

Процесс: создание объекта задачи 1 и копирование всей информации из task

Выход: нет

Постусловия: создан объект задачи 1, как копия task

Связывание объекта графа с задачей

Вход: ссылка на объект типа «Простой граф» , s – дескриптор начальной вершины

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

Процесс: связывание объекта графа с задачей 1 и решение задачи

Выход: нет

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

Повторное решение задачи

Вход: нет

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

Процесс: повторное выполнение решения задачи 1 для связанного с ней графа

Выход: нет

Постусловия: получено новое решение

Возврат результата
Вход: нет

Предусловия: задача выполнена

Процесс: возвращение Result

Выход: Result

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

3. 10.2. Клиентское определение класса «Задача 2»

internal class Task1

{

public Graph FBgraph;

public List BadVertexes;

public List Sons;

public int[] Parents;

public bool[] used;

public int[] dd, low;

public int counter = 0;
public Task1(Graph g)

public void FindBV(Vertex v1, int parent = -1)

12. Заключение

В ходе работы, была спроектирована и реализована универсальная программная коллекция «Простой граф» и программные компоненты, являющиеся клиентскими классами для данной коллекции. Также разработана программа представления структуры графа. Просмотр результатов работы всех операций АТД «Простой граф» и итераторов, операций и результатов задач 1. Было произведено тестирование данного программного комплекса на графе с количеством вершин, не превышающим 30. Результаты всех операций правильны. Были сформированы представления и знания об основных классах алгоритмов на графах, используемых в них структурах данных и общих схемах решения задач на их основе.

13. Список литературы

1. 
   С/С++. Программирование на языке высокого уровня: учебник для вузов. Т.А. Павловская. – Санкт-Петербург: Изд-во Питер, 2006.
   
2. 
   Абстракция данных и решение задач на С++. Стены и зеркала. Ф. Каррано, Д. Причард. – Москва: издательский дом «Вильямс», 2003.
   
3. 
   Структуры данных и алгоритмы: учебное пособие. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. – Москва: Издательский дом «Вильямс», 2000.
   
4. 
   Сэджвик Р. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах - М: DiaSoft, 2002 г. – 496 с.
   

1. 
   
   

14. Приложение

1. Program.cs

using System;

using TTWeight = System.Int32;

using TTData = System.Int32;

using TTEdge = System.Int32;

namespace АиСД_РГР

{

class Program

{

static void PrintMenu()

{

Console.WriteLine("-------------------------------------------");

Console.WriteLine("Выберите действие:");

Console.WriteLine("1 - Пустой граф");

Console.WriteLine("2 - Граф с вершинами");

Console.WriteLine("3 - Случайный граф с вершинами и ребрами");

Console.WriteLine("4 - Добавить вершину");

Console.WriteLine("5 - Добавить ребро");

Console.WriteLine("6 - Удалить вершину");

Console.WriteLine("7 - Удалить ребро");

Console.WriteLine("8 - Преобразовать граф");

Console.WriteLine("9 - Печать графа");

Console.WriteLine("10 - Удалить граф");

Console.WriteLine("11 - Итератор вершин");

Console.WriteLine("12 - Итератор всех ребер");

Console.WriteLine("13 - Итератор исходящих ребер");

Console.WriteLine("14 - Итератор входящих ребер");

Console.WriteLine("15 - Коэффициент насыщенности");

Console.WriteLine("16 - Количество ребер");

Console.WriteLine("17 - Количество вершин");

Console.WriteLine("18 - Форма представления графа");

Console.WriteLine("19 - Тип графа");

Console.WriteLine("21 - Сформировать двусвязный");

// Console.WriteLine("22 - Операции над ребром");

Console.WriteLine("24 - Прочитать вершину");

Console.WriteLine("25 - Изменить вершину");

Console.WriteLine("26 - Запросить число вершин");

Console.WriteLine("27 - Запросить число ребер");

Console.WriteLine("28 - Изменить вес ребра");

Console.WriteLine("29 - Изменить данные ребра");

Console.WriteLine("30 - Прочитать ребро");

Console.WriteLine("0 - Выход");

}

public static void Menu(Graph e)

{

while (true)

{

PrintMenu();

Console.WriteLine("Ваш выбор:");

int m = int.Parse(Console.ReadLine());

switch (m)

{

case 0:

return;

case 1:

e = new Graph();

break;

case 2:

Console.WriteLine("Введите количество вершин (int):");

int v = int.Parse(Console.ReadLine());

Console.WriteLine("Введите тип (bool):");

bool d2 = bool.Parse(Console.ReadLine());

Console.WriteLine("Введите форму (bool):");

bool f2 = bool.Parse(Console.ReadLine());

e = new Graph(v, d2, f2);

break;

case 3:

Console.WriteLine("Введите количество вершин (int):");

int v1 = int.Parse(Console.ReadLine());

Console.WriteLine("Введите количество ребер (int):");

int e1 = int.Parse(Console.ReadLine());

Console.WriteLine("Введите тип (bool):");

bool d1 = bool.Parse(Console.ReadLine());

Console.WriteLine("Введите форму (bool):");

bool f1 = bool.Parse(Console.ReadLine());

e = new Graph(v1, e1, d1, f1);

var it = AbstractGraph.IteratorAllEdges.MakeIt(e.G);

it.Beg();

int y1 = 9;

Random r = new Random();

for (; it.Input() != null; it.Next())

{

it.Input().Weight = r.Next(y1);

}

break;

case 4:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

var t = e.G.AddVertex();

Console.WriteLine("Добавлена вершина " + t.Index.ToString());

break;

}

case 5:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Введите номера вершин и вес (для ор)");

Console.WriteLine("Введите номер вершины 1 (int):");

int V1 = int.Parse(Console.ReadLine());

Console.WriteLine("Введите номер вершины 2 (int):");

int V2 = int.Parse(Console.ReadLine());

Console.WriteLine("Введите вес (int):");

int V3 = int.Parse(Console.ReadLine());

if (V1 >= e.G.Vertexes.Count || V2 >= e.G.Vertexes.Count || V1 == V2)

{

if (V1 >= e.G.Vertexes.Count)

Console.WriteLine("Ошибка: вершина 1 больше либо равна количеству вершин");

if (V2 >= e.G.Vertexes.Count)

Console.WriteLine("Ошибка: вершина 2 больше либо равна количеству вершин");

if (V1 == V2)

Console.WriteLine("Ошибка: номер вершины 1 равен номеру вершины 2");

break;

}

else

{

var t = e.G.AddEdge(e.G.Vertexes[V1], e.G.Vertexes[V2]);

if (t == null)

{

Console.WriteLine("Ошибка: между вершинами уже есть ребро");

break;

}

t.Weight = V3;

Console.WriteLine("Добавлено ребро");

break;

}

}

case 6:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Введите номер вершины (int):");

int V1 = int.Parse(Console.ReadLine());

if (V1 >= e.G.Vertexes.Count)

{

Console.WriteLine("Ошибка: номер вершины больше либо равен количеству вершин");

break;

}

e.G.DeleteVertex(e.G.Vertexes[V1]);

break;

}

case 7:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Введите номер вершины 1 (int):");

int V1 = int.Parse(Console.ReadLine());

Console.WriteLine("Введите номер вершины 2 (int):");

int V2 = int.Parse(Console.ReadLine());

if (V1 >= e.G.Vertexes.Count || V2 >= e.G.Vertexes.Count || V1 == V2)

{

if (V1 >= e.G.Vertexes.Count)

Console.WriteLine("Ошибка: вершина 1 больше либо равна количеству вершин");

if (V2 >= e.G.Vertexes.Count)

Console.WriteLine("Ошибка: вершина 2 больше либо равна количеству вершин");

if (V1 == V2)

Console.WriteLine("Ошибка: номер вершины 1 равен номеру вершины 2");

break;

}

e.G.DeleteEdge(e.G.Vertexes[V1], e.G.Vertexes[V2]);

break;

}

case 8:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

if (e.G == null)

{

Console.WriteLine("null");

break;

}

e.Reverse();

Console.WriteLine("Граф преобразован к типу " + e.G.Type.ToString());

break;

}

case 9:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

if (e.G == null)

{

Console.WriteLine("null");

break;

}

e.Print();

break;

}

case 10:

{

e = null;

break;

}

case 11:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Итератор вершин:");

ItAllVer(e);

break;

}

case 12:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Итератор всех ребер:");

ItAllEdges(e);

break;

}

case 13:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Итератор исходящих ребер:");

ItOutEdge(e);

break;

}

case 14:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Итератор входящих ребер:");

ItInEdge(e);

break;

}

case 15:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine(e.G.Saturation().ToString());

break;

}

case 16:

{

Console.WriteLine(e.G.EdgesCount.ToString());

break;

}

case 17:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine(e.G.Vertexes.Count.ToString());

break;

}

case 18:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("M-граф — " + e.G.Type.ToString());

break;

}

case 19:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Ориентированный — " + e.G.Oriented);

break;

}

case 20:

{

break;

}

case 21:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

if (e.G == null)

{

Console.WriteLine("null");

break;

}

else

{

Console.WriteLine("Двусвязный граф:");

var dv = new Task1(e);

dv.FindBV(dv.FBgraph.G.Vertexes[0]);

e.Print();

break;

}

}

//case 22:

// {

// if (e == null)

// {

// Console.WriteLine("Ошибка: e == null");

// break;

// }

// Console.WriteLine("Введите номер вершины 1 (int):");

// int vv1 = int.Parse(Console.ReadLine());

// Console.WriteLine("Введите номер вершины 2 (int):");

// int vv2 = int.Parse(Console.ReadLine());

// if (vv1 >= e.G.Vertexes.Count || vv2 >= e.G.Vertexes.Count)

// {

// if (vv1 >= e.G.Vertexes.Count)

// Console.WriteLine("Ошибка: вершина 1 больше либо равна количеству вершин");

// if (vv2 >= e.G.Vertexes.Count)

// Console.WriteLine("Ошибка: вершина 2 больше либо равна количеству вершин");

// break;

// }

// var t = e.GetEdge(e.G.Vertexes[vv1], e.G.Vertexes[vv2]);

// if (t == null)

// {

// Console.WriteLine("null");

// break;

// }

// break;

// }

case 24:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Введите номер вершины (int):");

int y111 = int.Parse(Console.ReadLine());

var a = e.G.GetVertex(y111);

if (a == null)

{

Console.WriteLine("Ошибка: a == null");

break;

}

Console.WriteLine("Индекс — " + a.Index + ", данные — " + a.Data + ", имя — " + a.Name);

break;

}

case 25:

{

if (e == null)

{

Console.WriteLine("Ошибка: e == null");

break;

}

Console.WriteLine("Введите номер вершины (int):");

int y111 = int.Parse(Console.ReadLine());

Console.WriteLine("Введите данные (string):");

string h1 = (Console.ReadLine());

Console.WriteLine("Введите имя (string):");

string h2 = (Console.ReadLine());

var a = e.G.GetVertex(y111);

if (a == null)

{

Console.WriteLine("Ошибка: a == null");

break;

}

a.Name = h2;

a.Data = h1;

Console.WriteLine("Данные изменены.");

break;

}

case 26:

{

int vertexesCount = e.G.V();

Console.WriteLine("Число вершин в графе: " + vertexesCount);

break;

}

case 27:

{

int edgesCount = e.G.E();

Console.WriteLine("Число ребер в графе: " + edgesCount);

break;

}

case 28:

{

Console.WriteLine("Введите номер вершины 1 (int):");

int x = int.Parse(Console.ReadLine());

Console.WriteLine("Введите номер вершины 2 (int):");

int y = int.Parse(Console.ReadLine());

var t = e.GetEdge(e.G.Vertexes[x], e.G.Vertexes[y]);

if (t == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Введите новый вес (int):");

int w = int.Parse(Console.ReadLine());

t.SetW(w);

break;

}

case 29:

{

Console.WriteLine("Введите номер вершины 1 (int):");

int x = int.Parse(Console.ReadLine());

Console.WriteLine("Введите номер вершины 2 (int):");

int y = int.Parse(Console.ReadLine());

var t = e.GetEdge(e.G.Vertexes[x], e.G.Vertexes[y]);

if (t == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Введите новые данные (string):");

string d = Console.ReadLine();

t.SetD(d);

break;

}

case 30:

{

Console.WriteLine("Введите номер вершины 1 (int):");

int x = int.Parse(Console.ReadLine());

Console.WriteLine("Введите номер вершины 2 (int):");

int y = int.Parse(Console.ReadLine());

var t = e.GetEdge(e.G.Vertexes[x], e.G.Vertexes[y]);

if (t == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Вес — " + t.Weight + ", данные — " + t.Data);

break;

}

}

}

}

public static void ItAllEdges(Graph e)

{

var it = AbstractGraph.IteratorAllEdges.MakeIt(e.G); //создали итератор

while (true)

{

bool flagExit = false;

Console.WriteLine("1 - установить на начало");

Console.WriteLine("2 - установить на конец");

Console.WriteLine("3 - следующий");

Console.WriteLine("4 - чтение");

Console.WriteLine("5 - запись");

Console.WriteLine("6 - выход");

int k = int.Parse(Console.ReadLine());

switch (k)

{

case 1:

{

it.Beg();

Console.WriteLine("it.begin()");

break;

}

case 2:

{

it.End();

Console.WriteLine("it.end()");

break;

}

case 3:

{

it.Next();

Console.WriteLine("it.next()");

break;

}

case 4:

{

var a = it.Input();

if (a != null)

{

Console.WriteLine("Исходящая — " + a.Vertex1.Index.ToString() + ", входящая — " +

a.Vertex2.Index.ToString() + ", с весом — " + a.Weight);

}

else

{

Console.WriteLine("null");

}

break;

}

case 5:

{

if (it.Input() == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Введите вес (float):");

float k1 = float.Parse(Console.ReadLine());

Console.WriteLine("Введите данные (string):");

string k2 = Console.ReadLine();

it.Input().Data = k2;

it.Input().Weight = k1;

Console.WriteLine("Данные изменены.");

break;

}

case 6:

{

flagExit = true;

break;

}

default:

break;

}

if (flagExit) break;

}

}

public static void ItInEdge(Graph e)

{

bool flagExit = false;

Console.WriteLine("Введите номер вершины (int):");

int k5 = int.Parse(Console.ReadLine());

var it = AbstractGraph.IteratorInputEdge.MakeIt(e.G.Vertexes[k5], e.G); //создали итератор

while (true)

{

Console.WriteLine("1 - установить на начало");

Console.WriteLine("2 - установить на конец");

Console.WriteLine("3 - следующий");

Console.WriteLine("4 - чтение");

Console.WriteLine("5 - запись");

Console.WriteLine("6 - выход");

int k = int.Parse(Console.ReadLine());

switch (k)

{

case 1:

{

it.Beg();

Console.WriteLine("it.begin()");

break;

}

case 2:

{

it.End();

Console.WriteLine("it.end()");

break;

}

case 3:

{

it.Next();

Console.WriteLine("it.next()");

break;

}

case 4:

{

if (it.Input() == null)

{

Console.WriteLine("Ошибка");

break;

}

var a = it.Input();

Console.WriteLine("Исходящая — " + a.Vertex1.Index.ToString() + ", входящая — " +

a.Vertex2.Index.ToString() + ", с весом — " + a.Weight +

", с данными — " + a.Data);

break;

}

case 5:

{

if (it.Input() == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Введите вес (float):");

float k1 = float.Parse(Console.ReadLine());

Console.WriteLine("Введите данные (string):");

string k2 = Console.ReadLine();

it.Input().Data = k2;

it.Input().Weight = k1;

Console.WriteLine("Данные изменены.");

break;

}

case 6:

{

flagExit = true;

break;

}

default:

break;

}

if (flagExit) break;

}

}

public static void GoEdge(Edge edge, Graph e)

{

if (edge == null)

{

Console.WriteLine("Ошибка: edge == null");

return;

}

while (true)

{

bool flagExit = false;

Console.WriteLine("1 - чтение ребра");

Console.WriteLine("2 - изменение ребра");

Console.WriteLine("3 - признак исхода из вершины");

Console.WriteLine("4 - прочитать другую вершину");

Console.WriteLine("5 - исходящая вершина");

Console.WriteLine("6 - входящая вершина");

Console.WriteLine("7 - выход");

int c = int.Parse(Console.ReadLine());

switch (c)

{

case 1:

{

Console.WriteLine("Из вершины — " + edge.Vertex1.Index + ", в вершину — " + edge.Vertex2.Index +

", с весом — " + edge.Weight + ", с данными — " + edge.Data);

break;

}

case 2:

{

Console.WriteLine("Введите вес (float):");

float f1 = float.Parse(Console.ReadLine());

Console.WriteLine("Введите данные (string):");

string f2 = Console.ReadLine();

edge.Weight = f1;

edge.Data = f2;

break;

}

case 3:

{

Console.WriteLine("Введите номер вершины (int):");

int i1 = int.Parse(Console.ReadLine());

if (i1 >= e.G.Vertexes.Count)

{

Console.WriteLine("Ошибка: номер вершины больше либо равен количеству вершин");

break;

}

Console.WriteLine(edge.from(e.G.Vertexes[i1]));

break;

}

case 4:

{

Console.WriteLine("Введите номер вершины (int):");

int i1 = int.Parse(Console.ReadLine());

if (i1 >= e.G.Vertexes.Count)

{

Console.WriteLine("Ошибка: номер вершины больше либо равен количеству вершин");

break;

}

Console.WriteLine(edge.other(e.G.Vertexes[i1]).Index.ToString());

break;

}

case 5:

{

Console.WriteLine("Введите номер вершины (int):");

Console.WriteLine(edge.Vertex1.Index);

break;

}

case 6:

{

Console.WriteLine("Введите номер вершины (int):");

Console.WriteLine(edge.Vertex2.Index);

break;

}

case 7:

{

flagExit = true;

break;

}

default:

break;

}

if (flagExit) break;

}

}

public static void ItOutEdge(Graph e)

{

Console.WriteLine("Введите номер вершины (int):");

int k5 = int.Parse(Console.ReadLine());

var it = AbstractGraph.IteratorOutEdge.MakeIt(e.G.Vertexes[k5], e.G); //создали итератор 4 16

while (true)

{

bool flagExit = false;

Console.WriteLine("1 - установить на начало");

Console.WriteLine("2 - установить на конец");

Console.WriteLine("3 - следующий");

Console.WriteLine("4 - чтение");

Console.WriteLine("5 - запись");

Console.WriteLine("6 - выход");

int k = int.Parse(Console.ReadLine());

switch (k)

{

case 1:

{

it.Beg();

Console.WriteLine("it.begin()");

break;

}

case 2:

{

it.End();

Console.WriteLine("it.end()");

break;

}

case 3:

{

it.Next();

Console.WriteLine("it.next()");

break;

}

case 4:

{

if (it.Input() == null)

{

Console.WriteLine("null");

break;

}

var a = it.Input();

Console.WriteLine("Исходящая — " + a.Vertex1.Index.ToString() + ", входящая — " +

a.Vertex2.Index.ToString() + ", с весом — " + a.Weight +

", и данными — " + a.Data);

break;

}

case 5:

{

if (it.Input() == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Введите вес (float):");

float k1 = float.Parse(Console.ReadLine());

Console.WriteLine("Введите данные (string):");

string k2 = Console.ReadLine();

it.Input().Data = k2;

it.Input().Weight = k1;

Console.WriteLine("Данные изменены");

break;

}

case 6:

{

flagExit = true;

break;

}

default:

break;

}

if (flagExit) break;

}

}

public static void ItAllVer(Graph e)

{

var it = new AbstractGraph.IteratorVertexes

(e.G);

while (true)

{

bool flagExit = false;

Console.WriteLine("1 - установить на начало");

Console.WriteLine("2 - установить на конец");

Console.WriteLine("3 - следующий");

Console.WriteLine("4 - чтение");

Console.WriteLine("5 - запись");

Console.WriteLine("6 - выход");

int k = int.Parse(Console.ReadLine());

switch (k)

{

case 1:

{

it.Beg();

Console.WriteLine("it.begin()");

break;

}

case 2:

{

it.End();

Console.WriteLine("it.end()");

break;

}

case 3:

{

it.Next();

Console.WriteLine("it.next()");

break;

}

case 4:

{

var a = it.Input();

if (a == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Индекс — " + a.Index.ToString());

break;

}

case 5:

{

if (it.Input() == null)

{

Console.WriteLine("null");

break;

}

Console.WriteLine("Введите данные (string):");

string k2 = Console.ReadLine();

Console.WriteLine("Введите имя (string):");

string k3 = Console.ReadLine();

it.Input().Name = k3;

it.Input().Data = k2;

Console.WriteLine("Данные изменены");

break;

}

case 6:

{

flagExit = true;

break;

}

default:

break;

}

if (flagExit) break;

}

}

private static void Main(string[] args)

{

Graph MainGraph = new Graph();

Menu(MainGraph);

}

}

}