Разработка и описание графа

Представление входного файла выглядит следующим образом:

<Количество вершин>

 

<Матрица смежности с весами ребер >

 

Матрица состоит из n-го количества строк и в каждой строке находятся n-ое количество весов, разделенных «пробелом».

 

Пример входного файла:

 

0 2 3 9 3 1

2 0 7 2 4 2

3 7 0 3 5 3

9 1 3 0 8 4

3 4 5 8 0 5

6 7 8 9 1 0

 

Рассмотрим описание каждого массива в программе и занесем в табл. 4.

Таблица 4. Обозначения и описание массивов.

№	Имя массива	Размерность массива	Описание массива
	a	n*n, n-количество вершин	матрица смежности
	q	k, k-количество вершин в подграфе	массив с вершинами подграфа
	q1	k, k-количество вершин в подграфе	массив с вершинами подграфа, необходимый для подбора вершин
	p1	k+1, k-количество вершин в подграфе	массив для подсчета вероятности
	p2	k, k-количество вершин в подграфе	массив для подсчета вероятности
	b	n*n, n-количество вершин	матрица с феромонами
	x	n, n-количество вершин	массив с вершинами, для выбора не пройденных вершин

В табл. 5 рассмотрены описания всех переменных в программе.

Таблица 5. Обозначения и описание переменных.

№	Имя переменной	Тип переменной	Минимальное и максимальное значения переменной	Описание переменной
	Q	int	0…65535	константа равная 5
	i1	int	0…65535	рабочий индекс
	i2	int	0…65535	рабочий индекс
	f1	int	0…65535	заменяет переменную k при подсчете не пройденных вершин и вероятности
	p	int	0…65535	рабочий индекс
	l	int	0…65535	начальная вершина при разбиении
	m	int	0…65535	количество выбранных вершин
	n	int	0…65535	количество вершин
	k	int	0…65535	количество вершин в подграфе
	f	int	0…65535	рабочий индекс
	c	int	0…65535	конечная вершина при разбиении
	t	int	0…65535	количество не пройденных вершин
	y	int	0…65535	рабочий индекс
	i	int	0…65535	рабочий индекс
	j	int	0…65535	рабочий индекс
	v	double		степень феромона
	sum	float	1.17549e-38… 3.40282e+38	сумма между выбранными и оставшимися вершинами
	min	float	1.17549e-38… 3.40282e+38	минимальная сумма между выбранными и оставшимися вершинами
	sum1	double	2.22507e-308… 1.79769e+308	сумма для подсчета вероятности
	g1	double	2.22507e-308… 1.79769e+308	случайное числа для подсчета вероятности
	g	double	2.22507e-308… 1.79769e+308	случайное числа для подсчета вероятности между 0 и 1
	sum2	double	2.22507e-308… 1.79769e+308	сумма для подсчета вероятности
	min1	float	1.17549e-38… 3.40282e+38	минимальная сумма между выбранными и оставшимися вершинами

Программная реализация алгоритма

Решения задачи и ее описание

В программной реализации алгоритма на Microsoft Visual Studio 2010 требуется включить следующие библиотеки:

 

#include "stdafx.h" – заголовок со стандартным именем

#include <stdio.h> - стандартный заголовочный файл ввода/вывода

#include <conio.h> - заголовочный файл, используемый в старых компиляторах, работающих в операционных системах MS-DOS, для создания текстового интерфейса пользователя

#include <locale> - заголовочный файл для включения кириллицы в программе

#include <iostream> - заголовочный файл с классами, функциями и переменными для организации ввода-вывода

using namespace std - использовать пространство имен std

#include "fun1.h" – файл содержащий функцию, которая используется для считывания данных с файла

#include "fun2.h"" – файл содержащий функцию, которая используется для разбиения графа на подграфы

#include "fun3.h"" – файл содержащий функцию, которая используется для записи данных в файл

 

В реализации программы также потребуются перечисленные ниже функции и методы:

 

fscanf – функция считывания с файла

fprintf – функцию записи в файл

random - функция генерирующая случайные числа

 

Разработка системы тестов и отладка программы

Тесты черного ящика

Для проектирования тестов программы методами черного ящика с помощью эквивалентного разбиения входных/выходных данных на области (классы) эквивалентности составлен список ситуаций, каждая из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в табл. 6, в скобках указаны их номера.

 

Таблица 6. Области входных/выходных данных тестов программы.

Входные и выходные параметры	Допустимые значения	Недопустимые значения
Количество вершин, n	2..NMAX (1)	<2 (2), >NMAX (3)
Количество ребер	1…n*(n-1) (4)	< 1 (5), > n*(n-1) (6)
Наличие петель	Нет (7)	Есть (8)
Вес ребра	>=0 (9)	<0(10)
Входной файл существует	Да(11)	Нет(12)
Выходной файл существует	Да(13)	Нет(14)

Для создания перечисленных тестовых ситуаций разработаны тесты, представленные в табл. 7. Входные и выходные данные тестов по возможности выбирались ближе к границам классов эквивалентности.

 

Таблица 7. Тесты черного ящика для отладки программы.

№ теста	Входные данные	Выходные данные	№ ситуаций
	0 2 3 9 5 2 0 7 1 6 3 7 0 3 7 9 1 3 0 9 5 6 7 9 0	G1 (4,1) G2 (0,2,3)	1, 4, 7, 9, 11, 13
		Сообщение «Количество вершин меньше или равно 0»	2, 1, 7, 9, 11, 13
	0 2 3 9 5 2 0 7 1 6 3 7 0 3 7 9 1 3 0 9 5 6 7 9 5	Сообщение «Присутствуют петли»	1, 4, 8, 10, 11, 13
		Сообщение «Ошибка открытия файла для чтения»	12, 13
	0 2 3 9 5 2 0 7 1 6 3 7 0 3 7 9 1 3 0 9 5 6 7 9 0	Сообщение «Ошибка открытия файла для записи»	1, 4, 7, 9, 11, 14
	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	Сообщение «Матрица смежности состоит из нулей»	1, 5, 7, 9, 11, 13
	0 1 2 3 4 5 1 0 6 7 8 9 2 6 0 8 7 6 3 7 8 0 5 4 4 8 7 5 0 3 5 9 6 4 3 0	G1 (2,3,4) G2 (0,1,5)	1, 4, 7, 9, 11, 13
	1 1 2 3 4 5 1 0 6 7 8 9 2 6 0 8 7 6 3 7 8 0 5 4 4 8 7 5 0 3 5 9 6 4 3 0	Сообщение «Присутствуют петли»	1, 4, 8, 9, 11, 13
	0 1 -2 3 4 5 1 0 6 7 8 9 -2 6 0 8 7 6 3 7 8 0 5 4 4 8 7 5 0 -3 5 9 6 4 -3 0	Сообщение «Вес ребра меньше 0»	1, 4, 7, 10, 11, 13
	0 2 3 9 5 7 3 4 2 0 7 2 6 8 0 7 3 7 0 3 7 3 8 0 9 2 3 0 9 5 9 4 5 6 7 9 0 6 7 8 7 8 3 5 6 0 3 1 3 0 8 9 7 3 0 4 4 7 0 4 8 1 4 0	G1 (3,6,2,4) G2 (0,1,5,7)	1, 4, 7, 9, 11, 13
	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	Сообщение «Матрица смежности состоит из нулей»	1, 5, 7, 9, 11, 13

 

Тесты белого ящика

Разработанные тесты проверены методом белого ящика по критериям охвата основных путей выполнения алгоритма подпрограмм. В программе имеются составные условия. Поэтому использован критерий комбинаторного покрытия условий (см. табл. 8).

 

Таблица 8. Комбинаторное покрытие условий тестами черного ящика.

Модуль	Элементарные условия	Истина	Ложь
main	n>0	1,5,7,10	2,3,4,6,8,9
fun1	inp == NULL	Остальные
fun1	n<=0		Остальные
fun1	a[i][j]<0	3,9	Остальные
fun1	i==j	Остальные
fun1	a[i][j]!=0		Остальные
fun2	m<k	Остальные	6,11
fun2	m>1	Остальные	6,11
fun2	a[i][j]>0	Остальные	6,11
fun2	j!=x[i1]	Остальные	6,11
fun2	f==m	Остальные	6,11
fun2	i1<f1	Остальные	6,11
fun2	i1<=f1	Остальные	6,11
fun2	g1>=p1[i2]	Остальные	6,11
fun2	g1<=p1[i1]	Остальные	6,11
fun2	y!=x[i]	Остальные	6,11
fun2	f==k	Остальные	6,11
fun2	min>sum	Остальные	6,11
fun2	i=0;i<n;i++	Остальные	6,11
fun2	j=0;j<n;j++	Остальные	6,11
fun2	i1=0;i1<m;i1++	Остальные	6,11
fun2	i1=0;i1<f1;i1++	Остальные	6,11
fun2	int e=0;e<k;e++	Остальные	6,11
fun2	y=0;y<n;y++	Остальные	6,11
fun2	i=0;i<k;i++	Остальные	6,11
fun2	y=0;y<k;y++	Остальные	6,11
fun3	q[0]==q[1]	6,11	Остальные
fun3	fp == NULL	Остальные
fun3	y=0;y<k;y++	6,11,5	Остальные
fun3	y=0;y<n;y++	6,11,5	Остальные
fun3	i=0;i<k;i++	6,11,5	Остальные

 

Из табл. 8 видно, что тесты черного ящика обеспечивают полное комбинаторное покрытие все х ситуаций, поэтому нет необходимости в тестах белого ящика.

 

ЗАКЛЮЧЕНИЕ

 

Проблема разбиения графов является актуальной при решении многих научных задач. В наше время существует много разновидностей алгоритмов. В данной работе рассмотрен так называемый муравьиный алгоритм разбиения графов.

 

Ниже следуют пункты, рассмотренные в курсовой работе.

1) Оформлялась содержательная часть задачи разбиения графов.

2) Разрабатывался алгоритм решения задачи.

3) Разрабатывались структуры программы и алгоритмы программных модулей.

4) Решили задачу на контрольном примере.

5) Разрабатывался и описывался граф.

6) Исходя из разработанного алгоритма, реализовывалась программа.

7) Разрабатывались системы тестов в виде черных и белых ящиков.

 

Алгоритм разбиения был реализован на языке высокого уровня С++. Отлаживалась программа в среде разработки MS Visual studio 2010.

 

Курсовая работа выполнена в соответствии с требованиями в полном объеме.

СПИСОК ЛИТЕРАТУРЫ

 

1. Хохлов Д.Г. Основы технологии модульного программирования. Учебное пособие – Казань: КГТУ (КАИ), 2003.

2. Ладыженский Ю.П., Родригес Р.А. Муравьиный алгоритм для разбиения графов. Учебное пособие – Донецк: ДНТУ, 2007.

3. Лебедев О.Б. Гибридный алгоритм разбиения на основе метода муравьиной колонии и коллективной адаптации.М.: Физматлит, 2010.

4. Методы и алгоритмы компоновки, размещения и трассировки печатных плат

5. Родригес Р.А. Методы решения задач разбиения графов с использованием компьютерной кластерной сети. Учебное пособие – Донецк: ДНТУ, 2003.

6. Деньдобренько Б.Н. Автоматизация конструирования РЭА. Москва: Высшая школа, 1980.

7. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва: Радио

и связь, 1990.

8. Хортон А. Visual C++: полный курс. М.:ООО «Дифлектика», 2011.

9. Введение в теорию графов [Электронный ресурс] / Под ред. В.С. Князьков, Т.В. Волченская — Электрон. дан. — М.: Интернет университет информационных технологий, 2005. — Режим доступа: ссылка свободная. — Загл. с экрана.

10. Струструп Б. Дизайн и эволюция С++. М.:ДМК Пресс, 2006.

 

 

ПРИЛОЖЕНИЯ. Листинг программы

//…………Основной модуль main

 

#include "stdafx.h"

#include <stdio.h>

#include <conio.h>

#include <locale>

#include <iostream>

#include "fun1.h"

#include "fun2.h"

#include "fun3.h"

using namespace std;

 

int main ()

{setlocale (LC_ALL, "rus");

int n;

int a[100][100];

int *q;

 

n=fun1(a);

if (n>0)

{q=fun2(n,a);

fun3(n,q);

}

 

getch();

return 0;

 

//……………….Модуль fun1.h

 

#include <iostream>

using namespace std;

 

int fun1 (int a[100][100]) //функция считывания мартицы с файла

{int i,j,n;

FILE *inp=fopen("C:\\2.txt","r");

 

if (inp == NULL)

{cout << "Ошибка открытия файла для чтения"; return -1; }

else

{fscanf(inp,"%d",&n);

if(n<=0) {cout<<"Количество вершин меньше или равно 0"; return -1; }

for (i=0; i<n; i++)

for (j=0; j<n; j++)

{fscanf(inp,"%d",&a[i][j]);

{if (a[i][j]<0)

{cout<<"Вес ребра меньше 0"; return -1;}

if(i==j)

if(a[i][j]!=0)

{cout<<"Присутствуют петли"; return -1;}}

}}

fclose(inp);

 

return n;

}

 

//………………Модуль fun2.h

 

#include <iostream>

using namespace std;

 

int *fun2 (int n,int a[100][100]) //функция обработки графа

{int Q=5,i1,i2,f1,p;

double v,sum1,g1,g,sum2;

int q1[100],q2[100];

double p1[100],p2[100];

int l,m;

double b[100][100];

int x[100];

float min1=65000,min=65000;

float sum;

int f,c,t;

int *q,k=n/2,y;

int i,j,l1,h1;

q=new int[k];

 

for (i=0;i<n;i++) //матрица с феромонами

for (j=0;j<n;j++)

{if (i==j) b[i][j]=0;

else b[i][j]=1;}

 

l=0;

while (l<n)

{l1=0; h1=l;

while (l1<n)

{m=1; i=h1; c=i; t=0; x[t]=h1;

while (m<k)

{y=0; f1=-1;

for (j=0;j<n;j++)

{if (m>1&&(a[i][j]>0)) // выбираем не пройденные вершины

{f=0;

for (i1=0;i1<m;i1++)

{if (j!=x[i1]) f++;}

if (f==m)

{f1++; q1[f1]=j;}

}

else

{if (a[i][j]>0) {f1++; q1[f1]=j;}

}

}

 

sum1=0; //находим сумму для нахождения вероятности

for (i1=0;i1<f1;i1++)

{sum1=a[i][q1[i1]]*b[i][q1[i1]]+sum1;}

 

for (i1=0;i1<f1;i1++) //находим вероятность и делим 1 на эту вероятность

{sum2=a[i][q1[i1]]/sum1; p2[i1]=b[i][q1[i1]]*1/sum2;}

 

sum1=0;

for (i1=0;i1<f1;i1++)

{sum1=p2[i1]+sum1; }

sum1=1/sum1; //находим среднюю вероятность

 

p1[0]=0; i2=0; i1=0;

while (i1<f1) // распологаем вероятности между 0 и 1

{i1++; p1[i1]=p2[i2]*sum1+p1[i2]; i2++;}

 

g=rand () % 100;

g1=g/100; //случайное число между 0 и 1

 

f=0;i2=0;i1=0;

while (i1<=f1) //ищем в какую из областей вероятности она входит и выбираем эту вершину

{i1++;

if (g1>p1[i2]&&g1<=p1[i1])

{f++; i2++; c=q1[i1];}

else i2++;}

 

m++; t++; x[t]=c; i=c;

}

 

for(int e=0;e<k;e++)

t=0;

for (y=0;y<n;y++) //не пройденные вершины

{f=0;

for (i=0;i<k;i++)

{if (y!=x[i]) f++;}

if (f==k) {q1[t]=y; t++;}

}

 

sum=0;

for (y=0;y<k;y++) //суммируем связь между выбранными и не пройденными вершинами

for (p=0;p<t;p++)

{sum=a[x[y]][q1[p]]+sum;}

if (sum<min1) //выбор минимальной суммы и присвоение вершин

{min1=sum;

for (y=0;y<k;y++)

{q2[y]=x[y];}}

l1++; h1=c;

}

 

for(int e=0;e<k;e++)

t=0;

for (y=0;y<n;y++) //не пройденные вершины

{f=0;

for (i=0;i<k;i++)

{if (y!=x[i]) f++;}

if (f==k) {q1[t]=y; t++;}

}

 

sum=0;

for (y=0;y<k;y++) //суммируем связь между выбранными и не пройденными вершинами

for (p=0;p<t;p++)

{sum=a[x[y]][q1[p]]+sum;}

if (sum<min) //выбор минимальной суммы и присвоение вершин

{min=sum;

for (y=0;y<k;y++)

{q[y]=q2[y];}}

 

v=Q/sum; // степень феромона

i2=1;

for (i1=0;i1<k-1;i1++) //увеличиваем степень феромона

{b[x[i1]][x[i2]]=b[x[i1]][x[i2]]+v;

b[x[i2]][x[i1]]=b[x[i2]][x[i1]]+v; i2++;}

l++;

}

 

if (q[0]!=q[1]) cout<<"сумма смежных ребер между выбранными подграфами равна "<<min;

return q;

}

 

//……………….Модуль fun3.h

 

#include <iostream>

using namespace std;

 

int fun3 (int n, int *q) //функция вывода полученных после разбияния графов

{int i,j;

int k=n/2,y,f;

FILE *fp = fopen("C:\\3.txt","w");

 

if (fp == NULL)

{cout << "Ошибка открытия файла для записи";}

else

if (q[0]==q[1])

{cout<<"Матрица смежности состоит из нулей"; return-1; }

{fprintf(fp,"%s","G1 (");

for (y=0;y<k;y++)

{fprintf(fp,"%d",q[y]); fprintf(fp,"%s",",");}

fprintf(fp,"%s",")");

fprintf(fp,"\n");

 

fprintf(fp,"%s","G2 (");

for (y=0;y<n;y++)

{f=0;

for (i=0;i<k;i++)

{if (y!=q[i]) f++;}

if (f==k) {fprintf(fp,"%d",y); fprintf(fp,"%s",",");}}

fprintf(fp,"%s",")");

}

fclose(fp);

 

cout<<"Программа успешно выполнена";

return 0;}