Нисхідна проектування
Алгоритм порівняння графів на эквівалентність (Kursovoi_Proect):
Вхідні дані
Вихідні дані
НАЧАЛО
НАЧАЛО слежения за исключениями
ЕСЛИ ChBx_first.Checked ТО
Ввод первого графа с файла с частичным контролем (1.1)
КЕСЛИ
Ввод первого графа с экрана с полным контролем
ЕСЛИ ChBx_ second.Checked ТО
Ввод второго графа с файла с частичным контролем(1.1)
КЕСЛИ
Ввод второго графа с экрана с полным контролем
Построение матрицы смежности (MS1) для первого графа удалением весящих вершин (1.2)
Находждения найдольшего пути графа (диаметр графа)
(k) (1.3)
Построение матрицы смежности (MS1) для втрого графа удаление висящих вершин(1.2)
Нахождения найдольшего пути пути второго графа (диаметр графа)
(k2) (1.4)
ЕСЛИ (k) == (k2) ТО
Вывод сообщения "Данные графы эквивалентны!";
ИНАЧЕ
Вывод сообщения "Данные графы не эквивалентны!"
КЕСЛИ
НАЧАЛО обработки исключений
Обработка исключений
КОНЕЦ обработки исключений
КОНЕЦ слежения за исключениями
КОНЕЦ
Из текста алгоритма видно, что в нём 4 подзадач:
Сравнивание графов на эквивалентность
1.3
1.2
1.4
1.1
Подальше проектування можливо двома способами:
Аналогічно продовжуем проектувать указані підзадачі (розкриваєм їх зміст при допомогі операторів і підзада). Підзадачі другого рівня тоже розкриваєм і т.д.
2) Підзадачі основного алгоритму реалізуємо у вигляді "заглушок" (це або процедура, або функція з правильним заголовком з порожнім (спрощеним) тілом підзадачі). Т.к. вони спрощені, їх можна відразу написати на мові програмування і підставити в основний алгоритм. Після підстановки в основний алгоритм, його так само можна написати на мові програмування, тому що в ньому не буде не розкритих подзадач. Основний алгоритм разом з подзадачами транслюємо і налагоджувати.
Алгоритм ввода графа с файла с контролем:
static void Input_graf_screen(OpenFileDialog OpFlDl, CheckBox ChBx, StreamReader SR, ref string FI, ref int N, ref int M)
{
Вывод сообщения "Ввод графа с файла";
Генерирование ошибок;
}
Подставим данні “заглушки” в основной алгоритм:
Алгоритм сравнения графов на эквивалентность (Kursovoi_Proect):
НАЧАЛО
НАЧАЛО слежения за исключениями
ЕСЛИ ChBx_first.Checked ТО
//Ввод первого графа с файла с частичным контролем (1.1)
Input_graf_screen(OpenFlDl, ChBx_first, SRead, ref FI1, ref N1, ref M1);
ИНАЧЕ
Ввод первого графа с экрана с полным контролем
КЕСЛИ
ЕСЛИ ChBx_ second.Checked ТО
//Ввод второго графа с файла с частичным контролем (1.1)
Input_graf_screen(OpenFlDl,ChBx_second,SRead,ref FI2,ref N2,ref M2);
ИНАЧЕ
Ввод второго графа с экрана с полным контролем
КЕСЛИ
//Удаление висящих вершин для первого графа (1.2)
form_graf(FI1, ref MI1, N1, M1, num_graf);
//Нахождение диаметра для первого графа (k) (1.3)
Max_strong_subset(N1, MI1, ref k) ;
//Удаление висящих вершин для второго графа (1.2)
form_graf(FI2, ref MI2, N2, M2, num_graf);
//Нахождение диаметра для второго графа (k2) (1.3)
Max_strong_subset(N2, MI2, ref k2) ;
ЕСЛИ k == k2 ТО
Вывод сообщения "Данные графы эквивалентны!";
ИНАЧЕ
Вывод сообщения "Данные графы не эквивалентны!"
КЕСЛИ
НАЧАЛО обработки исключений
Обработка исключений
КОНЕЦ обработки исключений
КОНЕЦ слежения за исключениями
КОНЕЦ
Алгоритм зрівняння графів разобран, теперь напишем його на язикі С#
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace Kursovoi_Proect
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
StreamReader SRead = null;
int[][] MI1 = new int[0][];
int[][] MI2 = new int[0][];
string FI1, FI2;
int k, k2, N1, M1, N2, M2, num_graf;
private void BtnStart_Click(object sender, EventArgs e)
{
MI1 = new int[0][];
MI2 = new int[0][];
FI1 = "";
FI2 = "";
N1 = M1 = N2 = M2 = num_graf = 0;
int k = 1;
int k2 = 1;
try
{
//чтение первого графа
if (ChBx_first.Checked == true)
{
num_graf = 1;
MessageBox.Show("Введите файл, в котором задан первый граф");
Input_graf_screen(OpenFlDl, ChBx_first, SRead, ref FI1, ref N1, ref M1, num_graf);
}
else
{
FI1 = TB_FI_first.Text;
N1 = int.Parse(num_top_first.Value.ToString());
M1 = int.Parse(num_edge_first.Value.ToString());
}
//чтение второго графа
if (ChBx_second.Checked == true)
{
num_graf = 2;
MessageBox.Show("Введите файл, в котором задан второй граф");
Input_graf_screen(OpenFlDl, ChBx_second, SRead, ref FI2, ref N2, ref M2, num_graf);
}
else
{
FI2 = TB_FI_second.Text;
N2 = int.Parse(num_top_second.Value.ToString());
M2 = int.Parse(num_edge_second.Value.ToString());
}
//обрабатываем первый граф
num_graf = 1;
form_graf(FI1, ref MI1, N1, M1, num_graf);
if (MI1.Length < 2)
throw new
DivideByZeroException("Собираем точки первого графа");
else
Max_strong_subset(N1, MI1, ref k);
LBL_Res1_1.Text = "Диаметр графа равен:";
LBL_Res1_2.Text = "первого графа: " + k;
//обрабатываем второй граф
num_graf = 2;
form_graf(FI2, ref MI2, N2, M2, num_graf);
if (MI2.Length < 2)
throw new
DivideByZeroException("Собираем точки второго графа ");
else
Max_strong_subset2(N2, MI2, ref k2);
LBL_Res2_1.Text = "Диаметр графа равен:";
LBL_Res2_2.Text = "второго графа: " + k2;
//сравнивание диаметра вершин первого и второго графов
if (k == k2)
MessageBox.Show("Данные графы эквивалентны!", "Результат");
else
MessageBox.Show("Данные графы не эквивалентны!", "Результат");
}
catch (FormatException)
{
MessageBox.Show("Введены недопустимые символы!", "Ошибка!!!");
}
catch (DivideByZeroException x)
{
MessageBox.Show(x.Message, "Ошибка!");
}
}
Детальне проектування подзадачі 1.1
static void Input_graf_screen(OpenFileDialog OpFlDl, CheckBox ChBx, StreamReader SR, ref string FI, ref int N, ref int M)
НАЧАЛО
ЕСЛИ OpFlDl.ShowDialog() == DialogResult.OK ТО
Считуем первую строку с файла;
Заносим в переменные N и M колиество вершин и количество ребер;
ЕСЛИ ((N < 1) || (N > 20)) ТО
Ошибка! Недопустимое количество вершин первого графа;
КЕСЛИ
ЕСЛИ ((M < 1) || (M > 20)) ТО
Ошибка! Недопустимое количество ребер первого графа;
КЕСЛИ
ПОКА ((s = SR.ReadLine()) != null) ЦИКЛ
Строка help_str = help_str + s;
КЦИКЛА
В строку FI записываем строку help_str;
КЕСЛИ
КОНЕЦ
Алгоритм вводу графа с экрана разобран, теперь напишем його на язику С#
static void Input_graf_screen(OpenFileDialog OpFlDl, CheckBox ChBx, StreamReader SR, ref string FI, ref int N, ref int M)
{
if (OpFlDl.ShowDialog() == DialogResult.OK)
{
string fullname = OpFlDl.FileName;
int pos = fullname.LastIndexOf("\\");
string shortname = fullname.Substring(pos + 1);
MessageBox.Show("Открыт файл с именем \n" + shortname);
SR = new StreamReader(fullname);
string help_str;
help_str = SR.ReadLine();
string[] N_M = help_str.Split(' ');
N = int.Parse(N_M[0]);
if ((N < 1) || (N > 20))
throw new
Exception("Недопустимое количество вершин первого графа");
M = int.Parse(N_M[1]);
if ((M < 0) || (M > 50))
throw new
Exception("Недопустимое количество рёбер первого графа");
string s;
help_str = SR.ReadLine();
while ((s = SR.ReadLine()) != null)
help_str += " " + s;
SR.Close();
FI = help_str;
}
}
Детальне проектування підзадачі 1.2
static void form_graf(string k, ref int[][] A, int n, int m, int n_gr)
НАЧАЛО
Переменная zero = 1 типа int;
Преобразовываем элементы, разделенные пробелами, в строке FI1 в тип int и заносим их в вектор chisla;
ДЛЯ int i = 0 ПОКА i < chisla.Length ЦИКЛ
ЕСЛИ (chislo[i] < 0) || (chislo[i] > n) ТО
Ошибка! "Элемент вектора FI вне диапазона";
КЕСЛИ
i = i +1;
КЦИКЛА
ЕСЛИ chislo.Length > (2 * m + n - 1) ТО
Ошибка! "Количество элементов вектора FI должно быть меньше";
КЕСЛИ
ЕСЛИ chislo.Length < (2 * m + n - 1) ТО
Ошибка! "Количество элементов вектора FI должно быть больше";
КЕСЛИ
ДЛЯ int i = 0 ПОКА i < chislo.Length ЦИКЛ
ЕСЛИ chislo[i] == 0 ТО
zero = zero + 1;
КЕСЛИ
i = i +1;
КЦИКЛА
Количество строк в матрице А переопределяем на zero;
ДЛЯ int i = 0 ПОКА i < zero ЦИКЛ
Количество строк в матрице А переопределяем на zero;
i = i +1;
КЦИКЛА
Удаляем весящую вершину chislo графа A; (1.2.1)
ДЛЯ int i = 0 ПОКА i < А.Length ЦИКЛ
ДЛЯ int j = 0 ПОКА j < А.Length ЦИКЛ
ЕСЛИ A[i][j] != A[j][i] ТО
КЕСЛИ
j = j +1;
КЦИКЛА
i = i +1;
КЦИКЛА
КОНЕЦ
Детальне проектування підзадачі 1.2.1
static void from_vec_to_matrix(int[] vec, ref int[][] mat)
НАЧАЛО
Переменные S = 0 и p0 = 0 типа int;
ДЛЯ int i = 0 ПОКА i < vec.Length ЦИКЛ
ЕСЛИ vec[i] == 0 ТО
p0 = p0 + S;
S = 0;
ИНАЧЕ
mat[i - S - p0][vec[i] - 1] = 1;
S = S + 1;
i = i +1;
КЦИКЛ
КОНЕЦ
Алгоритм видалення висящої вершини на язикі С#
static void from_vec_to_matrix(int[] vec, ref int[][] mat)
{
int S = 0;
int p0 = 0;
for (int i = 0; i < vec.Length; i++)
{
if (vec[i] == 0)
{
p0 += S;
S = 0;
}
else
{
mat[i - S - p0][vec[i] - 1] = 1;
S++;
}
}
}
Підставим підзадачу 1.2.1 в підзадачу 1.2
static void form_graf(string k, ref int[][] A, int n, int m, int n_gr)
НАЧАЛО
Переменная zero = 1 типа int;
Преобразовываем элементы, разделенные пробелами, в строке FI1 в тип int и заносим их в вектор chisla;
ДЛЯ int i = 0 ПОКА i < chisla.Length ЦИКЛ
ЕСЛИ (chislo[i] < 0) || (chislo[i] > n) ТО
Ошибка! "Элемент вектора FI вне диапазона";
КЕСЛИ
i = i +1;
КЦИКЛА
ЕСЛИ chislo.Length > (2 * m + n - 1) ТО
Ошибка! "Количество элементов вектора FI должно быть меньше";
КЕСЛИ
ЕСЛИ chislo.Length < (2 * m + n - 1) ТО
Ошибка! "Количество элементов вектора FI должно быть больше";
КЕСЛИ
ДЛЯ int i = 0 ПОКА i < chislo.Length ЦИКЛ
ЕСЛИ chislo[i] == 0 ТО
zero = zero + 1;
КЕСЛИ
i = i +1;
КЦИКЛА
Количество строк в матрице А переопределяем на zero;
ДЛЯ int i = 0 ПОКА i < zeroЦИКЛ
Количество столбцов в матрице А переопределяем на zero;
i = i +1;
КЦИКЛА
//Преобразовываем вектор chislo в матрицу инцидентности A; (1.2.1)
from_vec_to_matrix(chislo, ref A);
ДЛЯ int i = 0 ПОКА i < А.Length ЦИКЛ
ДЛЯ int j = 0 ПОКА j < А.Length ЦИКЛ
ЕСЛИ A[i][j] != A[j][i] ТО
Ошибка! "Матрица инцидентности графа не симметричная";
КЕСЛИ
j = j +1;
КЦИКЛА
i = i +1;
КЦИКЛА
КОНЕЦ
Алгоритм построення матриці інцидентності графа розібран, теперь напишем його на язику С#
static void form_graf(string k, ref int[][] A, int n, int m, int n_gr)
{
int zero = 1;
string[] chisla = k.Split(' ');
int[] chislo = new int[chisla.Length];
for (int i = 0; i < chisla.Length; i++)
{
chislo[i] = int.Parse(chisla[i]);
if ((chislo[i] < 0) || (chislo[i] > n))
throw new
Exception("Элемент вектора FI" + n_gr.ToString() + " вне диапазона");
}
if (chislo.Length > (2 * m + n - 1))
throw new
Exception("Количество элементов вектора FI" + n_gr.ToString() + " должно быть меньше");
if (chislo.Length < (2 * m + n - 1))
throw new
Exception("Количество элементов вектора FI" + n_gr.ToString() + " должно быть больше");
for (int i = 0; i < chislo.Length; i++)
if (chislo[i] == 0)
zero++;
Array.Resize(ref A, zero);
for (int i = 0; i < zero; i++)
Array.Resize(ref A[i], zero);
from_vec_to_matrix(chislo, ref A);
for (int i = 0; i < A.Length; i++)
for (int j = 0; j < A.Length; j++)
if (A[i][j] != A[j][i])
throw new
Exception("Матрица инцидентности графа №" + n_gr.ToString() + " не симметричная. Неориентированный граф задан неверно");
}
Проектування підзадачі 1.3
Нахождення діаметра графа напишем на C#.
public void Max_strong_subset(int sizer, int[][]MI1, ref int k)
{
int[] vrem = new int[sizer];
int[] G = new int[sizer];
int[] G_ = new int[sizer];
int[] temp = new int[sizer];
try
{
int start_top = 1;
for (int i = 0; i < sizer; i++)
{
vrem[i] = 1;
}
vrem[start_top] = 0;
General_function(start_top, sizer, ref G, ref G_, ref temp, ref MI1, k, ref vrem);
for (int i = 0; i < sizer; i++)
{
if (vrem[i] == 1)
{
General_function(i, sizer, ref G, ref G_, ref temp, ref MI1, k, ref vrem);
k++;
}
}
}
catch (Exception)
{
MessageBox.Show("Введите номер cуществующей вершины!", "Error!");
}
}
Проектування підзадачі 1.3.1
public void General_function(int ver, int sizer, ref int[] G, ref int[] G_, ref int[] temp, ref int[][] MI1, int k, ref int[] vrem)
{
int v = ver;
for (int i = 0; i < sizer; i++)
{
G[i] = 0;
G_[i] = 0;
temp[i] = -1;
}
bool tr = true;
G[v] = 1;
temp[v] = 1;
for (int j = 0; j < sizer; j++)
{
if (MI1[v][j] == 1)
{
G[j] = 1;
if (temp[j] == -1)
{
temp[j] = 1;
}
}
if (!(j + 1 < sizer))
{
for (int i = 0; i < sizer && tr; i++)
{
if (temp[i] == 1)
{
temp[i] = 0;
j = -1;
v = i;
tr = false;
}
}
tr = true;
}
}
for (int i = 0; i < sizer; i++)
{
temp[i] = -1;
}
v = ver;
G_[v] = 1;
temp[v] = 1;
for (int j = 0; j < sizer; j++)
{
if (MI1[j][v] == 1)
{
G_[j] = 1;
if (temp[j] == -1)
{
temp[j] = 1;
}
}
if (!(j + 1 < sizer))
{
for (int i = 0; i < sizer && tr; i++)
{
if (temp[i] == 1)
{
temp[i] = 0;
j = -1;
v = i;
tr = false;
}
}
tr = true;
}
}
for (int i = 0; i < sizer; i++)
{
if (G_[i] == G[i] && G[i] == 1)
{
vrem[i] = 0;
}
}
}
Проектування підзадачі 1.4
Нахождення діаметра для другого графа напишем на C#.
public void Max_strong_subset2(int sizer, int[][] MI2, ref int k2)
{
int[] vrem = new int[sizer];
int[] G = new int[sizer];
int[] G_ = new int[sizer];
int[] temp = new int[sizer];
try
{
int start_top = 1;
for (int i = 0; i < sizer; i++)
{
vrem[i] = 1;
}
vrem[start_top] = 0;
General_function2(start_top, sizer, ref G, ref G_, ref temp, ref MI2, k2, ref vrem);
for (int i = 0; i < sizer; i++)
{
if (vrem[i] == 1)
{
General_function2(i, sizer, ref G, ref G_, ref temp, ref MI2, k2, ref vrem);
k2++;
}
}
}
catch (Exception)
{
MessageBox.Show("Введите номер cуществующей вершины!", "Error!");
}
}
Проектування підзадачі 1.4.1
public void General_function2(int ver, int sizer, ref int[] G, ref int[] G_, ref int[] temp, ref int[][] MI2, int k2, ref int[] vrem)
{
int v = ver;
for (int i = 0; i < sizer; i++)
{
G[i] = 0;
G_[i] = 0;
temp[i] = -1;
}
bool tr = true;
G[v] = 1;
temp[v] = 1;
for (int j = 0; j < sizer; j++)
{
if (MI2[v][j] == 1)
{
G[j] = 1;
if (temp[j] == -1)
{
temp[j] = 1;
}
}
if (!(j + 1 < sizer))
{
for (int i = 0; i < sizer && tr; i++)
{
if (temp[i] == 1)
{
temp[i] = 0;
j = -1;
v = i;
tr = false;
}
}
tr = true;
}
}
for (int i = 0; i < sizer; i++)
{
temp[i] = -1;
}
v = ver;
G_[v] = 1;
temp[v] = 1;
for (int j = 0; j < sizer; j++)
{
if (MI2[j][v] == 1)
{
G_[j] = 1;
if (temp[j] == -1)
{
temp[j] = 1;
}
}
if (!(j + 1 < sizer))
{
for (int i = 0; i < sizer && tr; i++)
{
if (temp[i] == 1)
{
temp[i] = 0;
j = -1;
v = i;
tr = false;
}
}
tr = true;
}
}
for (int i = 0; i < sizer; i++)
{
if (G_[i] == G[i] && G[i] == 1)
{
vrem[i] = 0;
}
}
}
Структура програми: