Построение потокового графа

Министерство образования и науки РФ

Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Ивановский государственный энергетический университет имени В.И. Ленина»

Кафедра программного обеспечения компьютерных систем

Контрольная работа

по дисциплине «Тестирование ПО»

Выполнил: студент

группы 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.	}