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

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

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

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

Матрица состоит из 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;}

Наши рекомендации