close

Вход

Забыли?

вход по аккаунту

?

kursovoy

код для вставкиСкачать
Оглавление
Теоретическое введение3
Постановка задачи5
Входные данные6
Входные формы7
Выходные формы7
Входной формат текстового файла8
Аномалии8
Функциональные тесты10
Метод12
Нисходящее проектирование13
Тестирование20
Приложение А23
Приложение В29
Теоретическое введение
Графы применяются для алгоритмического исследования структур дискретных систем. Рассмотрим основные определения.
Граф - совокупность множества V вершин и множества Е связей между ними, которая обозначается G=(V,Е).
Связь, имеющая направление, называется дугой, в противном случае - ребром.
Граф с дугами называется ориентированным (или орграфом). На рис. 1,а показан ориентированный граф с множеством вершин V={1,2,3,4,5,6} и множеством ребер
E={(1,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3),(6,6)}.
Если в графе G есть дуга (ребро) (V,Е), считают, что вершина V смежная с вершиной Е. Для неорграфов отношение смежности является симметричным, а для орграфов это необязательно. На рис. 1.1, вершина 1 является смежной с вершиной 2. Две вершины графа смежные, если они соединены ребром (дугой) (например, смежными являются вершины 4 и 5 на рис. 1.1, и 2 и 4 на рис.1.1).
Рис.1.1 - Ориентированный граф
Способы представления графов в памяти ЭВМ
Для представления графов можно использовать различные структуры данных. Выбор структуры данных зависит от операторов, которые будут применяться к вершинам и ребрам (дугам) графа.
Одним из наиболее общих представлений орграфа G = (V, Е) является матрица смежности. Предположим, что множество вершин V= {1, 2, ..., n}. Матрица смежности для орграфа G - это матрица размера n х n со значениями булевого типа, где A[i,j] = true тогда и только тогда, когда существует дуга из вершины i в вершину j. Часто в матрицах смежности значение true заменяется на 1, а значение false - на 0. Представление орграфа в виде матрицы смежности удобно применять в тех алгоритмах, в которых надо часто проверять существование данной дуги. На рис. 1.2 показана матрица смежностей: для орграфа, представленного на рис. 1.1
Рис.1.2 - Матрица смежности
Модифицированное FI-представление графа
(MFI-представление)
В MFI-представлении указывается в массиве P верхние границы окончания списков вершин, смежных с заданной вершиной по входящим в нее дугам. Например, для орграфа на рис. 1.1 MFI-представление графа имеет вид: , .
Вариант 18
Ориентированный граф представлен на рис.1.3.
Рисунок 1.3 - Граф
n=10 - количество вершин
m=14 - количество ребер
Построенная матрица смежности представлена в Табл.1.1
Табл.1.1 - Матрица смежности
123456789101112113141511617118191101
Вектор G и P представлены в таблице 1.2
Табл. 1.2 - Вектор G и P
G2||12|35||457|9|67|810|1№1234567891011121314P1135589111314 Постановка задачи
Используя технологию нисходящего проектирования, сравнить два ориентированных графа, представленных массивом последователей (MFI представление), на эквивалентность по числу вершин и ребер в графе окрестности каждой пары вершин. Вершин графа не более 20, число рёбер не более 50. Предусмотреть ввод данных с клавиатуры и из текстового файла.
Входные данные
Входные данные представлены в таблице 2.1
Табл.2.1 - Входные данные
№НаименованиеТипДиапазонНазначение1n1Целый1<=n1<=20Кол-во вершин 1-го графа2m1Целый0<m1<=50Кол-во ребер 1-го графа3G1Массив целых чисел1<=G1[i]<=n1
0<=i<=m1Список номеров вершин, которые входят в соответствующую вершину4P1Массив целых чиселP1[i]<=P1[i+1]
0<=P1[i]<=m1
1<=i<=n1Вектор индексов разделителей5n2Целый1<=n2<=20Кол-во вершин 1-го графа6m2Целый0<m2<=50Кол-во ребер 1-го графа7G2Массив целых чисел1<=G2[i]<=n1
0<=i<=m2Список номеров вершин, которые входят в соответствующую вершину8P2Массив целых чиселP2[i]<=P2[i+1]
0<=P2[i]<=m2
1<=i<=n2Вектор индексов разделителей Входные формы
Входная форма программы представлена на рис.2.1
Рис. 2.1 - Входная форма
Выходные формы
Результат в виде строки "графы эквивалентны!" "графы не эквивалентны" выводится в элемент label (см. Рис.2.2, 2.3)
Рис. 2.2 Рис.2.3 Входной формат текстового файла Каждый граф находится в отдельном файле Рис.2.4 - Входной формат текстового файла
Аномалии
В нашей программе аномалии в основном связаны с контролем входных данных. Все возможные аномалии указаны в табл.3.
Таблица 3 - Аномалии
Номер п/пНаименованиеУсловия возникновенияРеакция1Некорректный ввод количества вершин
1-го графа (при вводе с файла)(n1>20)
n=0Вывод сообщения: "Ошибка ввода количества вершин
1-го графа! "2Некорректный ввод количества ребер 1-го графа (при вводе с файла)(m1>50)Вывод сообщения: "Ошибка ввода количества ребер
1-го графа!"3Элемент вектора G
1-го графа недопустим1>G1[i]>n1
Вывод сообщения: "Элемент вектора G 1-го графа недопустим!"4количество элементов вектора G
1-го графа неверноi!=m1Вывод сообщения: " Количество элементов вектора G 1-го графа неверно!"
5Элемент вектора P
1-го графа недопустимP1[i]>P1[i+1]
P1[i]>m1Вывод сообщения: "Элемент вектора P 1-го графа недопустим!"6количество элементов вектора P
1-го графа недопустим
i!=n1Вывод сообщения: "Количество Элементов вектора P 1-го графа недопустим!"7Некорректный ввод количества вершин
2-го графа (при вводе с файла)(n2>20)
n=0Вывод сообщения: "Ошибка ввода количества вершин
2-го графа! "8Некорректный ввод количества ребер
2-го графа (при вводе с файла)(m2>50)
Вывод сообщения: "Ошибка ввода количества ребер
2-го графа!"9Элемент вектора G
2-го графа недопустим1>G2[i]>n2
Вывод сообщения: "Элемент вектора G 2-го графа недопустим!"10количество элементов вектора G
2-го графа неверноi!=m2
Вывод сообщения: " Количество элементов вектора G 2-го графа неверно!"
11Элемент вектора P
2-го графа недопустимP2[i]>P2[i+1]
P2[i]>m1Вывод сообщения: "Элемент вектора P 2-го графа недопустим!"12количество элементов вектора P
2-го графа недопустимоi!=n2
Вывод сообщения: "количество Элементов вектора P 2-го графа недопустим!"
13недопустимый символсимвол !е {'1,2......9',
' ', новая строка }Вывод сообщения: "Недопустимый элемент"
Функциональные тесты
Функциональные тесты приведены в табл.4.
Таблица 4 - Функциональные тесты
Но-мер п/пНазначение тестаВходные данныеРезультат1
Проверка аномалии 1,721
3
......Вывод сообщения: "Ошибка ввода количества вершин графа! "2
Проверка аномалии 2,84
51
.......Вывод сообщения: "Ошибка ввода количества ребер графа!"3Проверка аномалии 3,94
3
1 1 5Вывод сообщения: "Элемент вектора G графа недопустим!"4Проверка аномалии 4,104
3
1 2 2 3Вывод сообщения: " Количество элементов вектора G графа неверно!"5
Проверка аномалии 5,114
3
1 1 2
5 4 3 2Вывод сообщения: "Элемент вектора P графа недопустим!"6
Проверка аномалии 6,124
3
1 1 2
1 1 2 2 3
Вывод сообщения: "Количество Элементов вектора P графа недопустимо!"7Проверка аномалии 13а
и
а ап апВывод сообщения: "Недопустимый элемент"8Пример нормальной работы - 1
граф 1
граф 24
4
2 2 3 2
1 2 2 3Вывод сообщения: "графы эквивалентны"4
4
2 4 4 1
1 2 3 3
9Пример нормальной работы - 2
граф 1
граф 2
4
4
2 3 3 2
2 3 3 3Вывод сообщения "графы не эквиваленты"4
5
2 4 1 4 1
1 2 4 4
Метод
1. Вводим графы, осуществляем контроль ввода и строим матрицы смежности MS.
2. Сравниваем суммы вершин и ребер окрестности каждой пары вершин:
2.1. Для каждого графа вычисляем вспомогательный вектор В:
2.2. Количество элементов в векторе В будет равняться числу комбинаций пар вершин (size=n*(n-1)/2).
2.3. Устанавливаем счетчики:
3.2.2. Поэлементного перехода в векторе В (int s=0);
3.2.3. Вершин графа;
3.2.4. Ребер графа;
2.4. Проверяем равны ли элементы одной строки единице (ЕСЛИ (MS[i, j] == 1 ТО ver++, i++). Если равны, тогда увеличиваем счетчики вершин и ребер на единицу;
2.5. Проверяем, равны ли элементы другой строки единице (ЕСЛИ (MS[k, j] == 1 ТО ver++, i++). Если равны, тогда увеличиваем счетчики вершин и ребер на единицу;
2.6. Уменьшаем счетчик вершин на единицу если в обоих рассматриваемых строках элементы одинаковой позиции будут равны (т.е. в окрестностях обоих вершин находится одна и та же точка) -( ЕСЛИ ((MS[i, j] == 1) И (MS[k, j] == 1) ТО ver--);
2.7. Убираем из расчета вершины, которые мы рассматриваем (т.е. если имеется связь между рассматриваемыми точками, то мы должны уменьшить счетчик вершин на единицу):
2.7.1. ЕСЛИ (MS[i, k] == 1) ТО ver--;
2.7.2. ЕСЛИ (MS[k, i] == 1) ТО ver--;
2.8. Записываем в вектор В сумму вершин и ребер (B[s] = ver + rebr)
2.9. Обнуляем счетчики вершин и ребер (ver=0; rebr=0)
2.10. увеличиваем счетчик s на единицу и переходим к рассмотрению следующих двух строк (т.е. к шагу 3.3)
2.11. Сравниваем векторы В1 и В2:
2.11.1. Изменяем в векторах В1 и В2 порядок элементов (делаем его по возрастанию) - Array.Sort(B1) и Array.Sort(B2);
2.11.2. Сравниваем вектор В1 и В2 на эквивалентность - (ЕСЛИ (B1[i] != B2[i]) ТО " графы не эквивалентны" ИНАЧЕ "графы эквивалентны"). Нисходящее проектирование
Нисходящее проектирование разобьем на несколько этапов, на каждом из которых будем при необходимости уточнять описываемый алгоритм.
АЛГОРИТМ Сравнение графов
НАЧАЛО
ЕСЛИ (ввод_с_файла) ТО
Ввод данных из файла и перенос на экранные формы // 1.1
ЕСЛИ (ошибка) ТО
Вывод(Ошибка при чтении данных из файла)
КЕСЛИ ИНАЧЕ(ввод с экрана) //1.2
ЕСЛИ (ошибка)ТО
Вывод(Ошибка ввода графа)
Построение матрицы смежности//1.3
Расчет вектора суммы вершин и ребер окрестности каждой пары вершин // 1.4
Сравнение векторов двух графов//1.5
ЕСЛИ (сравнение векторов)ТО // Вывод(Графы эквивалентны)
ИНАЧЕ
Вывод(Графы не эквивалентны)
КОНЕЦ
Рисунок 3.1 - Диаграмма нисходящего проектирования после первого этапа
На рисунке 3 представлена диаграмма нисходящего проектирования алгоритма сравнения двух графов. На диаграмме отображены пять методов, которые требуют детализации. Детализируем эти методы:
МЕТОД 1.1 // Ввод данных из файла на экранные формы с контролем ошибок
НАЧАЛО
Ввод 1-го графа из файла // 1.1.1
ЕСЛИ (ошибка) ТО
Выход
КЕСЛИ
Ввод 2-го графа из файла // 1.1.1
КОНЕЦ
МЕТОД 1.2 // Ввод графов с экрана с контролем ошибок
чтение m,n //1.2.1
чтение c формы вектора G,P // 1.2.2
МЕТОД 1.3 //Построение матрицы смежности
НАЧАЛО
Строим матрицу смежности 1-го графа // 1.3.1
ЕСЛИ (ошибка) ТО
Выход
Строим матрицу смежности 2-го графа // 1.3.1
КОНЕЦ
МЕТОД 1.4 // Расчет вектора суммы вершин и ребер окрестности каждой пары вершин
НАЧАЛО
Рассчитываем вектор для 1-го графа // 1.4.1
Рассчитываем вектор для 2-го графа // 1.4.1
КОНЕЦ
МЕТОД 1.5 // сравнение векторов графов
НАЧАЛО
Для первого графа строим вектор, который содержит суммы вершин и ребер окрестности каждой пары вершин // 1.5.1
Для второго графа строим вектор, который содержит суммы вершин и ребер окрестности каждой пары вершин // 1.5.1
Рисунок 3.2 - Диаграмма нисходящего проектирования после второго этапа
На рисунке 4 представлена диаграмма нисходящего программирования после второго этапа детализации. В четырех из пяти детализированных методах остались фрагменты, так же требующие детализации. Детализируем их:
МЕТОД 1.1.1 // Ввод графа из файла
НАЧАЛО
n ← ЧИСЛО_ВЕРШИН_ИЗ_ФАЙЛА
ЕСЛИ (n <= 0 ИЛИ n > 20) ТО
Вывод(Количество вершин неверно)
КЕСЛИ
ЕСЛИ
m ← ЧИСЛО_РЕБЕР_ИЗ_ФАЙЛА
КЕСЛИ
ЕСЛИ (m < 0 ИЛИ m > 50) ТО
Вывод(Количество ребер неверно)
КЕСЛИ
G ← вектор G из файла
ЕСЛИ (G[i] < 1 || G[i] > n) ТО
Вывод(Количество элементов неверно)
КЕСЛИ
P ← вектор P из файла
ЕСЛИ (P[i] < 0 || P[i] > m) ТО
Вывод(Количество элементов неверно)
КЕСЛИ
ЕСЛИ (P[i] > P[i + 1]) ТО
Вывод(Элементы должны быть в порядке возрастания)
КОНЕЦ
МЕТОД 1.2.1
//чтение m,n public void ReaDFromFormNM(ref int n, ref int m, NumericUpDown n1, NumericUpDown m1, int nomer)
ЕСЛИ (n < 1 || n > 20) ТО ошибка ("количество вершин неверно")
КЕСЛИ
ЕСЛИ (m < 0 || m > 50) ТО ошибка ("количество ребер неверно")
КЕСЛИ МЕТОД 1.2.2 //чтение c формы вектора G,P public void ReadFromForm(ref int n, ref int m, ref int[] G, ref int[] P, TextBox G1, TextBox P1, int nomer)
{
Array.Resize(ref G, m);
Array.Resize(ref P, n);
string s1 = G1.Text;
string s2 = P1.Text;
s1 = s1.TrimEnd();
s2 = s2.TrimEnd();
//s = f.ReadLine();
string[] temps1 = s1.Split(new Char[] { ' ' });
ЕСЛИ (temps1.Length != m) ТО ошибка ("неверно количество элементов")
ИНАЧЕ ОТ i = 0 ДО i < m ЦИКЛ
G[i] = int.Parse(temps1[i])
КЕСЛИ
ЕСЛИ (G[i] < 1 || G[i] > n) ТО ошибка ("неверно количество элементов")
КЕСЛИ
КОНЕЦ цикла
string[] temps2 = s2.Split(new Char[] { ' ' });
ЕСЛИ (temps2.Length != n) ТО ошибка ("неверное количество элементов")
ИНАЧЕ
ОТ i = 0 ДО i < n ЦИКЛ
P[i] = int.Parse(temps2[i])
ЕСЛИ (P[i] < 0 || P[i] > m) ТО ошибка ("Элемент недопустим")
КОНЕЦ ЦИКЛА
КЕСЛИ
ДЛЯ i = 0 ДО i < n - 1 ЦИКЛ
ЕСЛИ (P[i] > P[i + 1]) ТО ошибка ("недопустимый элемент")
КОНЕЦ ЦИКЛА
КЕСЛИ
МЕТОД 1.3.1 // Построение матрицы смежности
НАЧАЛО
j=0;
ОТ i=0 ДО i<количества вершин ЦИКЛ
ПОКА (j < элемента вектора Р - P[i]) ТО
Элемент матрицы смежности = 1 (MS[G[j] - 1, i] = 1)
j++
КОНЕЦ цикла
КОНЕЦ
МЕТОД 1.4.1 // Расчет вектора суммы ребер и вершин каждой окрестности двух вершин
НАЧАЛО
Количество вершин ver = 0;
Количество ребер rebr = 0;
счетчик s = 0;
Размер size = ((n * (n - 1)) / 2);
Вектор B создается размером size
ОТ i = 0 ДО длины матрицы смежности ЦИКЛ
ОТ k = 0 ДО n ЦИКЛ ОТ j = 0 ДО n ЦИКЛ ЕСЛИ (элемент матрицы смежности MS[i, j-1] == 1) ТО ver++; rebr++;
КЕСЛИ
ЕСЛИ (элемент матрицы смежности MS[k-1, j-1] == 1) ТО ver++; rebr++;
КЕСЛИ
ЕСЛИ (элемент матрицы смежности ((MS[i, j-1] == 1) && (MS[k, j-1] == 1)) ТО Ver--;
КЕСЛИ
ЕСЛИ (элемент матрицы смежности (MS[k, i] == 1) ТО Ver--;
КЕСЛИ
Элемент вектора В с номером s равен сумме вершин и ребер - B[s] = ver + rebr;
Обнуляем количество вершин и ребер КОНЕЦ ЦИКЛА
увеличиваем счетчик s на единицу
КОНЕЦ ЦИКЛА
КОНЕЦ
МЕТОД 1.5.1.
Сортируем элементы 1-го графа ОТ меньшего к БОЛЬШЕМУ (метод SORT)
Сортируем элементы 2-го графа ОТ меньшего к БОЛЬШЕМУ (метод SORT)
ОТ i=0 ДО длины вектора (В1.Length) ЦИКЛ
ЕСЛИ (B1[i] != B2[i]) ТО
Вывод ("Графы не эквивалентны")
BREAK
ИНАЧЕ i++ и проверка заново
КЕСЛИ
КОНЕЦ ЦИКЛА
Вывод ("Графы эквивалентны")
КОНЕЦ
Рисунок 3.3 - Диаграмма нисходящего проектирования после третьего этапа
На рисунке 5 представлен окончательный вид диаграммы нисходящего проектирования. На данном этапе не осталось методов, требующих уточнения, поэтому можно произвести их подстановку в методы более высокого уровня, используя имена применимые в последствии при кодировании программы. Подставляем методы описанные на третьем уровне в методы второго уровня нисходящего программирования:
МЕТОД 1.1 // Ввод данных из файла на экранные формы
НАЧАЛО
// Ввод 1-го графа из файла // 1.1.1
ReadFromFile(ref n1, ref m1, ref G1, ref P1, FileName1, 1);
WriteFromFileToForm(n1, m1, G1, P1, textBoxG1, textBoxP1, numericUpDownn1, numericUpDownm1, 1);
// Ввод 2-го графа из файла // 1.1.1
ReadFromFile(ref n2, ref m2, ref G2, ref P2, FileName2, 2);
WriteFromFileToForm(n2, m2, G2, P2, textBoxG2, textBoxP2, numericUpDownn2, numericUpDownm2, 2);
КОНЕЦ
В качестве завершающего этапа нисходящего проектирования подставляем описанные выше методы в главный метод сравнения графов:
АЛГОРИТМ Сравнение графов
<опис. переменных> (n1,m1,G1,P1,MS1,n2,m2,G2,P2,MS2)
НАЧАЛО
ЕСЛИ (ввод_с_файла) ТО
// Ввод данных из файла на экранные формы // 1.1
ReadFromFile(fileName);
ЕСЛИ (ошибка) ТО
Вывод(Ошибка при чтении данных из файла)
КЕСЛИ
КЕСЛИ
// построение матрицы смежности // 1.3
MS()
// Расчет вектора суммы ребер и ввершин находящихся в окресности каждой пары вершин // 1.4
Found()
// Сравнение векторов первого и второго графа // 1.5
comparison ()
КОНЕЦ
Процесс нисходящего проектирования завершен. Используя приведенный псевдокод, преступаем к кодированию программы. Листинг программы приведен в приложении А.
Тестирование
Завершающий этап разработки программы - тестирования. Выполняем тестирование приложения, используя разработанные функциональные тесты. На рисунках 4.1 -4.12 приведены примеры выполнения программой функциональных тестов. На рисунках 4.13 -4.14 примеры выполнения программой корректно введенных данных.
Рисунок 4.1 - Результат выполнения функционального теста 1
Рисунок 4.2 - Результат выполнения функционального теста 2
Рисунок 4.3 - Результат выполнения функционального теста 3
Рисунок 4.4 - Результат выполнения функционального теста 4
Рисунок 4.5 - Результат выполнения функционального теста 5
Рисунок 4.6 - Результат выполнения функционального теста 6
Рисунок 4.7 - Результат выполнения функционального теста 7
Рисунок 4.8 - Результат выполнения функционального теста 8
Рисунок 4.9 - Результат выполнения функционального теста 9
Рисунок 4.10 - Результат выполнения функционального теста 10
Рисунок 4.11 - Результат выполнения функционального теста 11
Рисунок 4.12 - Результат выполнения функционального теста 12
Рисунок 4.13 - Результат выполнения теста 13
Рисунок 4.14 - Пример нормальной работы - 1
Рисунок 4.15 - Пример нормальной работы - 2
Приложение А
Машинный листинг
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
namespace kursovoy
{
public partial class Form1 : Form
{
public string
ERROR = ".............Граф ",
endl = "...............\n";
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
int n1 = 0, m1 = 0, n2 = 0, m2 = 0;
string FileName1 = "graph1.txt";
string FileName2 = "graph2.txt";
int[] G1 = new int[0];
int[] G2 = new int[0];
int[] P1 = new int[0];
int[] P2 = new int[0];
try
{
if (radioButton1.Checked)
{
ReadFromFile(ref n1, ref m1, ref G1, ref P1, FileName1, 1);
FileToForm(n1, m1, G1, P1, textBoxG1, textBoxP1, numericUpDownn1, numericUpDownm1, 1);
}
else
{
ReaDFromFormNM1(ref n1, ref m1, numericUpDownn1, numericUpDownm1, 1);
ReadFromFormGP1(ref n1, ref m1, ref G1, ref P1, textBoxG1, textBoxP1, 1);
}
if (radioButton3.Checked)
{
ReadFromFile(ref n2, ref m2, ref G2, ref P2, FileName2, 2);
FileToForm(n2, m2, G2, P2, textBoxG2, textBoxP2, numericUpDownn2, numericUpDownm2, 2);
}
else
{
ReaDFromFormNM2(ref n2, ref m2, numericUpDownn2, numericUpDownm2, 2);
ReadFromFormGP2(ref n2, ref m2, ref G2, ref P2, textBoxG2, textBoxP2, 2);
}
int[,] MS1 = new int[n1, n1];
int[,] MS2 = new int[n2, n2];
int[] B1 = new int[0];
int[] B2 = new int[0];
MS(ref n1, ref m1, ref G1, ref P1, MS1);
MS(ref n2, ref m2, ref G2, ref P2, MS2);
found(n1, m1, MS1, B1);
found(n2, m2, MS2, B2);
comparison (B1, B2, m1, m2);
}
catch (Exception v)
{
MessageBox.Show(v.Message);
}
}
/////////////////////////////////////МЕТОД////////////////////////////////////////////
//находим сумму ребер и вершин окрестности каждой пары вершин
void found(int n, int m, int[,]MS, int []B)
{
int ver = 0;
int rebr = 0;
int s = 0;
int size = ((n * (n - 1)) / 2);
B = new int[size];
for (int i = 0; i < MS.Length; i++)
for (int k = i + 1; k < n; k++)
{
for (int j = 1; j < n; j++)
{
if (MS[i, j-1] == 1)
{
ver++;
rebr++;
}
if (MS[k-1, j-1] == 1)
{
ver++;
rebr++;
}
if ((MS[i, j-1] == 1) && (MS[k, j-1] == 1))
{
ver--;
}
}
if (MS[i, k] == 1)
{
ver--;
}
if (MS[k, i] == 1)
{
ver--;
}
B[s] = ver + rebr;
ver = 0;
rebr = 0;
}
s++;
}
//сравниваем вектора суммы ребер и вершин окрестности каждой пары вершин
void comparison(int [] B1, int []B2, int m1, int m2)
{
Array.Sort(B1);
Array.Sort(B2);
if (m1 != m2)
{
answer2.Visible = true;
}
else
{
for (int i = 0; i < B1.Length; )
{
if (B1[i] != B2[i])
{
answer2.Visible = true;
break;
}
else i++;
}
answer1.Visible = true;
}
}
/////////////////////МАТРИЦА СМЕЖНОСТИ////////////////////////////////////
//построение матрицы смежности
public void MS(ref int n, ref int m, ref int[] G, ref int[] P, int[,] MS)
{
int j = 0;
for (int i = 0; i < n; i++)
{
while (j < P[i])
{
MS[G[j] - 1, i] = 1;
j++;
}
}
}
///ЧТЕНИЕ С ФОРМЫ//////////////////////////////////////////////////////////
//чтение с формы n,m
public void ReaDFromFormNM1(ref int n, ref int m, NumericUpDown n1, NumericUpDown m1, int nomer)
{
n = (int)n1.Value; if (n < 1 || n > 20) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество вершин графа!");
m = (int)m1.Value; if (m < 0 || m > 50) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество ребер графа!");
}
//чтение с формы n,m
public void ReaDFromFormNM2(ref int n, ref int m, NumericUpDown n2, NumericUpDown m2, int nomer)
{
n = (int)n2.Value; if (n < 1 || n > 20) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество вершин графа!");
m = (int)m2.Value; if (m < 0 || m > 50) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество ребер графа!");
}
// чтение c формы вектора G,P public void ReadFromFormGP1(ref int n, ref int m, ref int[] G, ref int[] P, TextBox G1, TextBox P1, int nomer)
{
try
{
Array.Resize(ref G, m);
Array.Resize(ref P, n);
string s1 = G1.Text;
string s2 = P1.Text;
s1 = s1.TrimEnd();
s2 = s2.TrimEnd();
//s = f.ReadLine();
string[] temps1 = s1.Split(new Char[] { ' ' });
if (temps1.Length != m) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество элементов вектора G!");
else
for (int i = 0; i < m; i++)
{
G[i] = int.Parse(temps1[i]); if (G[i] < 1 || G[i] > n) throw new Exception(ERROR + nomer.ToString() + endl + " Элемент недопустим для вектора G!");
}
string[] temps2 = s2.Split(new Char[] { ' ' });
if (temps2.Length != n) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество элементов вектора Р!");
else
for (int i = 0; i < n; i++)
{
P[i] = int.Parse(temps2[i]); if (P[i] < 0 || P[i] > m) throw new Exception(ERROR + nomer.ToString() + endl + "Элемент недопустим для вектора Р!");
}
for (int i = 0; i < n - 1; i++)
{
if (P[i] > P[i + 1]) throw new Exception(ERROR + nomer.ToString() + endl + "Элементы массива графа расположены не в порядке возрастания!");
}
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
}
//
// чтение c формы вектора G,P public void ReadFromFormGP2(ref int n, ref int m, ref int[] G, ref int[] P, TextBox G2, TextBox P2, int nomer)
{
try
{
Array.Resize(ref G, m);
Array.Resize(ref P, n);
string s1 = G2.Text;
string s2 = P2.Text;
s1 = s1.TrimEnd();
s2 = s2.TrimEnd();
//s = f.ReadLine();
string[] temps1 = s1.Split(new Char[] { ' ' });
if (temps1.Length != m) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество элементов вектора G!");
else
for (int i = 0; i < m; i++)
{
G[i] = int.Parse(temps1[i]); if (G[i] < 1 || G[i] > n) throw new Exception(ERROR + nomer.ToString() + endl + " Элемент недопустим для вектора G!");
}
string[] temps2 = s2.Split(new Char[] { ' ' });
if (temps2.Length != n) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество элементов вектора Р!");
else
for (int i = 0; i < n; i++)
{
P[i] = int.Parse(temps2[i]); if (P[i] < 0 || P[i] > m) throw new Exception(ERROR + nomer.ToString() + endl + "Элемент недопустим для вектора Р!");
}
for (int i = 0; i < n - 1; i++)
{
if (P[i] > P[i + 1]) throw new Exception(ERROR + nomer.ToString() + endl + "Элементы массива графа расположены не в порядке возрастания!");
}
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
}
////////////////////////ЧТЕНИЕ С ФАЙЛА И ЗАНЕСЕНИЕ ДАННЫХ НА ФОРМУ/////////// //чтение с файла
public void ReadFromFile(ref int n, ref int m, ref int[] G, ref int[] P, string FileName, int nomer)
{
try
{
string str;
StreamReader f = new StreamReader(FileName);
str = f.ReadLine();
str = str.TrimEnd(); //удаляем пробелы в конце строки
string[] A = str.Split(new Char[] { ' ' });//разделили элементы
//for (int i = 0; i < A.Length; i++)
// MessageBox.Show(A[i]);
n = int.Parse(A[0]);// на первоой позиции количество вершин if (n < 1 || n > 20) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество вершин графа!");
m = int.Parse(A[1]);
if (m < 0 || m > 50) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество ребер графа!");
Array.Resize(ref G, m);
Array.Resize(ref P, n);
str = f.ReadLine();
string[] B = str.Split(new Char[] { ' ' });//разделили
if (B.Length != m) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество элементов вектора G!");
else
for (int i = 0; i < m; i++)
{
G[i] = int.Parse(B[i]);
if (G[i] < 1 || G[i] > n) throw new Exception(ERROR + nomer.ToString() + endl + " Элемент недопустим для вектора G!");
}
str = f.ReadLine();
string[] temps3 = str.Split(new Char[] { ' ' });
if (temps3.Length != n) throw new Exception(ERROR + nomer.ToString() + endl + "Вы неправильно ввели количество элементов вектора Р!");
else
for (int i = 0; i < n; i++)
{
P[i] = int.Parse(temps3[i]);
if (P[i] < 0 || P[i] > m) throw new Exception(ERROR + nomer.ToString() + endl + "Элемент недопустим для вектора Р!");
}
for (int i = 0; i < n - 1; i++)
{
if (P[i] > P[i + 1]) throw new Exception(ERROR + nomer.ToString() + endl + "Элементы массива графа расположены не в порядке возрастания!");
}
}
catch (Exception ex) { MessageBox.Show(ex.Message);
this.Close();
}
}
//перенос данных на форму
public void FileToForm(int n, int m, int[] G, int[] P, TextBox G1, TextBox P1, NumericUpDown n1, NumericUpDown m1, int nomer)
{
string g = "", p = "";
for (int i = 0; i < m; i++)
g += G[i].ToString() + " ";
for (int i = 0; i < n; i++)
p += P[i].ToString() + " ";
G1.Text = g;//записываем в текстбокс то что в векторе g
P1.Text = p;
n1.Value = n;
m1.Value = m;
}
private void button2_Click(object sender, EventArgs e)
{
this.Close();
}
}
}
Приложение В
Презентация
2
Документ
Категория
Рефераты
Просмотров
217
Размер файла
3 595 Кб
Теги
kursovoy
1/--страниц
Пожаловаться на содержимое документа