Министерство образования и науки РФ
Федеральное государственное бюджетное
образовательное учреждение высшего профессионального образования «Ивановский государственный энергетический университет имени В.И. Ленина»
Кафедра программного обеспечения компьютерных систем
Контрольная работа
по дисциплине «Тестирование ПО»
Выполнил: студент
группы 5-80к
Сошко О.А.
Проверил: к.т.н., доцент
Зубков В.П.
Иваново, 2017
Часть 1. Разработка приложения
Задание
Разработать программу построения матрицы смежности, инцидентности и списка ребер для произвольного графа.
2. Описание предметной области
В предметной области построения графа, основной сущностью будет сам граф - совокупность непустого множества вершин и наборов пар вершин (связей между вершинами), в свою очередь граф состоит из такой сущности, как вершина и связей – рёбер.
Для вершин существенны следующие признаки (атрибуты):
· Координата по Х;
· Координата по У.
Связь – ребро, можно выделить тоже как сущность с атрибутами:
· Вершина 1;
· Вершина 2;
Исходный код
Класс Form1.cs
using System;
using System.Collections.Generic;
using System.Windows.Forms;
namespace SystAnalys_lr1
{
public partial class Form1: Form
{
DrawGraph G;
List<Vertex> V;
List<Edge> E;
int[,] AMatrix; //матрица смежности
int[,] IMatrix; //матрица инцидентности
int selected1; //выбранные вершины, для соединения линиями
int selected2;
public Form1()
{
InitializeComponent();
V = new List<Vertex>();
G = new DrawGraph(sheet.Width, sheet.Height); //Инициализация рабочей поверхности
E = new List<Edge>();
sheet.Image = G.GetBitmap();
}
//кнопка - рисовать вершину
private void drawVertexButton_Click(object sender, EventArgs e)
{
drawVertexButton.Enabled = false;
drawEdgeButton.Enabled = true;
deleteButton.Enabled = true;
G.clearSheet();
G.drawALLGraph(V, E);
sheet.Image = G.GetBitmap();
}
//кнопка - рисовать ребро
private void drawEdgeButton_Click(object sender, EventArgs e)
{
drawEdgeButton.Enabled = false;
drawVertexButton.Enabled = true;
deleteButton.Enabled = true;
G.clearSheet();
G.drawALLGraph(V, E);
sheet.Image = G.GetBitmap();
selected1 = -1;
selected2 = -1;
}
//кнопка - удалить элемент
private void deleteButton_Click(object sender, EventArgs e)
{
deleteButton.Enabled = false;
drawVertexButton.Enabled = true;
drawEdgeButton.Enabled = true;
G.clearSheet();
G.drawALLGraph(V, E);
sheet.Image = G.GetBitmap();
}
//кнопка - удалить граф
private void deleteALLButton_Click(object sender, EventArgs e)
{
drawVertexButton.Enabled = true;
drawEdgeButton.Enabled = true;
deleteButton.Enabled = true;
const string message = "Вы действительно хотите полностью удалить граф?";
const string caption = "Удаление";
var MBSave = MessageBox.Show(message, caption, MessageBoxButtons.YesNo, MessageBoxIcon.Question);
if (MBSave == DialogResult.Yes)
{
V.Clear();
E.Clear();
G.clearSheet();
sheet.Image = G.GetBitmap();
}
}
//кнопка - матрица смежности
private void buttonAdj_Click(object sender, EventArgs e)
{
createAdjAndOut();
}
//кнопка - матрица инцидентности
private void buttonInc_Click(object sender, EventArgs e)
{
createIncAndOut();
}
private void sheet_MouseClick(object sender, MouseEventArgs e)
{
//нажата кнопка "рисовать вершину"
if (drawVertexButton.Enabled == false)
{
V.Add(new Vertex(e.X, e.Y));
G.drawVertex(e.X, e.Y, V.Count.ToString());
sheet.Image = G.GetBitmap();
}
//нажата кнопка "рисовать ребро"
if (drawEdgeButton.Enabled == false)
{
if (e.Button == MouseButtons.Left)
{
for (int i = 0; i < V.Count; i++)
{
if (Math.Pow((V[i].x - e.X), 2) + Math.Pow((V[i].y - e.Y), 2) <= G.R * G.R)
{
if (selected1 == -1)
{
G.drawSelectedVertex(V[i].x, V[i].y);
selected1 = i;
sheet.Image = G.GetBitmap();
break;
}
if (selected2 == -1)
{
G.drawSelectedVertex(V[i].x, V[i].y);
selected2 = i;
E.Add(new Edge(selected1, selected2));
G.drawEdge(V[selected1], V[selected2], E[E.Count - 1], E.Count - 1);
selected1 = -1;
selected2 = -1;
sheet.Image = G.GetBitmap();
break;
}
}
}
}
if (e.Button == MouseButtons.Right)
{
if ((selected1!= -1) &&
(Math.Pow((V[selected1].x - e.X), 2) + Math.Pow((V[selected1].y - e.Y), 2) <= G.R * G.R))
{
G.drawVertex(V[selected1].x, V[selected1].y, (selected1 + 1).ToString());
selected1 = -1;
sheet.Image = G.GetBitmap();
}
}
}
//нажата кнопка "удалить элемент"
if (deleteButton.Enabled == false)
{
bool flag = false; //удалили ли что-нибудь по ЭТОМУ клику
//ищем, возможно была нажата вершина
for (int i = 0; i < V.Count; i++)
{
if (Math.Pow((V[i].x - e.X), 2) + Math.Pow((V[i].y - e.Y), 2) <= G.R * G.R)
{
for (int j = 0; j < E.Count; j++)
{
if ((E[j].v1 == i) || (E[j].v2 == i))
{
E.RemoveAt(j);
j--;
}
else
{
if (E[j].v1 > i) E[j].v1--;
if (E[j].v2 > i) E[j].v2--;
}
}
V.RemoveAt(i);
flag = true;
break;
}
}
//ищем, возможно было нажато ребро
if (!flag)
{
for (int i = 0; i < E.Count; i++)
{
if (E[i].v1 == E[i].v2) //если это петля
{
if ((Math.Pow((V[E[i].v1].x - G.R - e.X), 2) + Math.Pow((V[E[i].v1].y - G.R - e.Y), 2) <= ((G.R + 2) * (G.R + 2))) &&
(Math.Pow((V[E[i].v1].x - G.R - e.X), 2) + Math.Pow((V[E[i].v1].y - G.R - e.Y), 2) >= ((G.R - 2) * (G.R - 2))))
{
E.RemoveAt(i);
flag = true;
break;
}
}
else //не петля
{
if (((e.X - V[E[i].v1].x) * (V[E[i].v2].y - V[E[i].v1].y) / (V[E[i].v2].x - V[E[i].v1].x) + V[E[i].v1].y) <= (e.Y + 4) &&
((e.X - V[E[i].v1].x) * (V[E[i].v2].y - V[E[i].v1].y) / (V[E[i].v2].x - V[E[i].v1].x) + V[E[i].v1].y) >= (e.Y - 4))
{
if ((V[E[i].v1].x <= V[E[i].v2].x && V[E[i].v1].x <= e.X && e.X <= V[E[i].v2].x) ||
(V[E[i].v1].x >= V[E[i].v2].x && V[E[i].v1].x >= e.X && e.X >= V[E[i].v2].x))
{
E.RemoveAt(i);
flag = true;
break;
}
}
}
}
}
//если что-то было удалено, то обновляем граф на экране
if (flag)
{
G.clearSheet();
G.drawALLGraph(V, E);
sheet.Image = G.GetBitmap();
}
}
}
//создание матрицы смежности и вывод в листбокс
private void createAdjAndOut()
{
AMatrix = new int[V.Count, V.Count];
G.fillAdjacencyMatrix(V.Count, E, AMatrix);
listBoxMatrix.Items.Clear();
string sOut = " ";
for (int i = 0; i < V.Count; i++)
sOut += (i + 1) + " ";
listBoxMatrix.Items.Add(sOut);
for (int i = 0; i < V.Count; i++)
{
sOut = (i + 1) + " | ";
for (int j = 0; j < V.Count; j++)
sOut += AMatrix[i, j] + " ";
listBoxMatrix.Items.Add(sOut);
}
}
//создание матрицы инцидентности и вывод в листбокс
private void createIncAndOut()
{
if (E.Count > 0)
{
IMatrix = new int[V.Count, E.Count];
G.fillIncidenceMatrix(V.Count, E, IMatrix);
listBoxMatrix.Items.Clear();
string sOut = " ";
for (int i = 0; i < E.Count; i++)
sOut += (char)('a' + i) + " ";
listBoxMatrix.Items.Add(sOut);
for (int i = 0; i < V.Count; i++)
{
sOut = (i + 1) + " | ";
for (int j = 0; j < E.Count; j++)
sOut += IMatrix[i, j] + " ";
listBoxMatrix.Items.Add(sOut);
}
}
else
listBoxMatrix.Items.Clear();
}
//вывод списка рёбер
private void chainButton_Click(object sender, EventArgs e)
{
listBoxMatrix.Items.Clear();
for (int i=0; i<E.Count;i++)
{
listBoxMatrix.Items.Add((i+1)+". "+"[" + (E[i].v1+1) + "," + (E[i].v2+1) + "]");
}
}
}
} Класс CodeFile.cs
using System.Collections.Generic;
using System.Drawing;
namespace SystAnalys_lr1
{
class Vertex
{
public int x, y;
public Vertex(int x, int y)
{
this.x = x;
this.y = y;
}
}
class Edge
{
public int v1, v2;
public Edge(int v1, int v2)
{
this.v1 = v1;
this.v2 = v2;
}
}
class DrawGraph
{
Bitmap bitmap;
Pen blackPen;
Pen redPen;
Pen darkGoldPen;
Graphics gr;
Font fo;
Brush br;
PointF point; //точка с координатами х и у
public int R = 20; //радиус окружности вершины
public DrawGraph(int width, int height)
{
bitmap = new Bitmap(width, height);
gr = Graphics.FromImage(bitmap);
clearSheet();
blackPen = new Pen(Color.Black);
blackPen.Width = 2;
redPen = new Pen(Color.Red);
redPen.Width = 2;
darkGoldPen = new Pen(Color.DarkGoldenrod);
darkGoldPen.Width = 2;
fo = new Font("Arial", 15);
br = Brushes.Black;
}
public Bitmap GetBitmap()
{
return bitmap;
}
public void clearSheet()
{
gr.Clear(Color.White);
}
public void drawVertex(int x, int y, string number)
{
gr.FillEllipse(Brushes.White, (x - R), (y - R), 2 * R, 2 * R);
gr.DrawEllipse(blackPen, (x - R), (y - R), 2 * R, 2 * R);
point = new PointF(x - 9, y - 9);
gr.DrawString(number, fo, br, point);
}
public void drawSelectedVertex(int x, int y)
{
gr.DrawEllipse(redPen, (x - R), (y - R), 2 * R, 2 * R);
}
public void drawEdge(Vertex V1, Vertex V2, Edge E, int numberE)
{
if (E.v1 == E.v2)
{
gr.DrawArc(darkGoldPen, (V1.x - 2 * R), (V1.y - 2 * R), 2 * R, 2 * R, 90, 270);
point = new PointF(V1.x - (int)(2.75 * R), V1.y - (int)(2.75 * R));
gr.DrawString(((char)('a' + numberE)).ToString(), fo, br, point);
drawVertex(V1.x, V1.y, (E.v1 + 1).ToString());
}
else
{
gr.DrawLine(darkGoldPen, V1.x, V1.y, V2.x, V2.y);
point = new PointF((V1.x + V2.x) / 2, (V1.y + V2.y) / 2);
gr.DrawString(((char)('a' + numberE)).ToString(), fo, br, point);
drawVertex(V1.x, V1.y, (E.v1 + 1).ToString());
drawVertex(V2.x, V2.y, (E.v2 + 1).ToString());
}
}
public void drawALLGraph(List<Vertex> V, List<Edge> E)
{
//рисуем ребра
for (int i = 0; i < E.Count; i++)
{
if (E[i].v1 == E[i].v2)
{
gr.DrawArc(darkGoldPen, (V[E[i].v1].x - 2 * R), (V[E[i].v1].y - 2 * R), 2 * R, 2 * R, 90, 270);
point = new PointF(V[E[i].v1].x - (int)(2.75 * R), V[E[i].v1].y - (int)(2.75 * R));
gr.DrawString(((char)('a' + i)).ToString(), fo, br, point);
}
else
{
gr.DrawLine(darkGoldPen, V[E[i].v1].x, V[E[i].v1].y, V[E[i].v2].x, V[E[i].v2].y);
point = new PointF((V[E[i].v1].x + V[E[i].v2].x) / 2, (V[E[i].v1].y + V[E[i].v2].y) / 2);
gr.DrawString(((char)('a' + i)).ToString(), fo, br, point);
}
}
//рисуем вершины
for (int i = 0; i < V.Count; i++)
{
drawVertex(V[i].x, V[i].y, (i + 1).ToString());
}
}
//заполняет матрицу смежности
public void fillAdjacencyMatrix(int numberV, List<Edge> E, int[,] matrix)
{
for (int i = 0; i < numberV; i++)
for (int j = 0; j < numberV; j++)
matrix[i, j] = 0;
for (int i = 0; i < E.Count; i++)
{
matrix[E[i].v1, E[i].v2] = 1;
matrix[E[i].v2, E[i].v1] = 1;
}
}
//заполняет матрицу инцидентности
public void fillIncidenceMatrix(int numberV, List<Edge> E, int[,] matrix)
{
for (int i = 0; i < numberV; i++)
for (int j = 0; j < E.Count; j++)
matrix[i, j] = 0;
for (int i = 0; i < E.Count; i++)
{
matrix[E[i].v1, i] = 1;
matrix[E[i].v2, i] = -1;
}
}
}
}
Спецификация
Написать программу построения матрицы смежности, инцидентности и списка рёбер для произвольного графа на языке C#. При написании использовать платформу WindowsForm.
Входные данные вводятся вручную на графическом поле интерфейса с помощью таких встроенных инструментов, как «вершина» и «ребро».
Результат построения графа отображается на графическом поле интерфейса, а матрицы смежности, инцидентности и список рёбер выводится в listBox.
Программа должна выполняться на операционных системах семейства Windows версии Seven и выше. При ошибках пользовательского ввода или внутренних ошибках программа должна осуществлять вывод соответствующего сообщения.
Ограничения
· Максимальное число вершин графа не должно превышать 10. (CountVertex < 11)
· Направление рёбер задаётся от первой вершины ко второй, данную тенденцию можно проследить при выводе списка рёбер.
· Формат вывода матрицы смежности:
| … | |||
| … | |||
· Формат матрицы инцидентности:
| A | … | N | |
| … | |||
| -1 |
· Формат вывода списка рёбер:
1. [1,2]
2. ….
· Название рёбер обозначается латинскими буквами;
· Номера вершин обозначаются натуральными цифрами.
Классы эквивалентности
| № | Входное или выходное событие | Классы эквивалентности | |
| Допустимые | Недопустимые | ||
| Ввод вершин | Вершины имеют вид окружности с номером N | N<1 | |
| N – натуральное число | N>10 | ||
| S<11 | N – не цифра | ||
| Контроль кол-ва вершин | 1<=S<=10 | S<1 | |
| S>10 | |||
| Вывод данных | Матрица инцидентности размером MxN(M-число вершин; N-число рёбер) | Матрица инцидентности размером NxM | |
| Матрица смежности размеро MxM(M-число вершин) | Элементы матрицы отличаются от 1,0,-1. | ||
| Элементы матрицы 1,0,-1 |
Часть 2. Модульное тестирование. Тестирование методом «белого ящика».
Модуль drawALLGraph
Программный код модуля приведен в листинге 1.
| 1. | public void drawALLGraph(List<Vertex> V, List<Edge> E) | |
| 2. | { | |
| 3. | for (int i = 0; i < E.Count; i++) | |
| 4. | { | |
| 5. | if (E[i].v1 == E[i].v2) | |
| 6. | { | |
| 7. | gr.DrawArc(darkGoldPen, (V[E[i].v1].x - 2 * R), (V[E[i].v1].y - 2 * R), 2 * R, 2 * R, 90, 270); | |
| 8. | point = new PointF(V[E[i].v1].x - (int)(2.75 * R), V[E[i].v1].y - (int)(2.75 * R)); | |
| 9. | gr.DrawString(((char)('a' + i)).ToString(), fo, br, point); | |
| 10. | } | |
| 11. | Else | |
| 12. | { | |
| 13. | gr.DrawLine(darkGoldPen, V[E[i].v1].x, V[E[i].v1].y, V[E[i].v2].x, V[E[i].v2].y); | |
| 14. | point = new PointF((V[E[i].v1].x + V[E[i].v2].x) / 2, (V[E[i].v1].y + V[E[i].v2].y) / 2); | |
| 15. | gr.DrawString(((char)('a' + i)).ToString(), fo, br, point); | |
| 16. | } | |
| 17. | } | |
| 18. | for (int i = 0; i < V.Count; i++) | |
| 19. | { | |
| 20. | drawVertex(V[i].x, V[i].y, (i + 1).ToString()); | |
| 21. | } | |
| 22. | } |
Построение потокового графа
Потоковый граф рассматриваемого модуля с указанием регионов и выделенными предикатными узлами приведен ниже.
Управляющий граф не содержит сложных условий, следовательно потоковый граф такойже как и управляющий.
