1

Размещено на http://www.allbest.ru/

ПРОГРАММА ДЛЯ ЭВМ «GRAF»

Введение

В данной работе приведена программа реализация проверки телекоммуникационной системы на связность. Цель работы - показать преимущество метода «разбиения» для проверки телекоммуникационной системы на связность.

В работе приведены:

· особенности работы программы и требования для работы с ней;

· описание алгоритма и программы проверки телекоммуникационной системы на связность;

· текст программы.

1. Особенности работы программы и требования для работы с ней

Программа Graph предназначена для оценки времени проверки телекоммуникационной системы на связность методом разбиения графа системы. Проверка производится для системы с различным числом узлов (от 9 до 1600). Программа написана на языке программирования Delphi 4.0.

Программа запускается двойным щелчком левой кнопки мыши на значке программы. После запуска появляется окно программы представленное на рисунке 1.1:

Рисунок 1.1 - Рабочее окно программы

Вычислительная работа программы начинается после того, как будет нажата кнопка «Начать расчет». По окончании расчета программа заканчивает свою роботу и выгружается из оперативной памяти. При этом в рабочей папке программы появляется файл Graf.txt, в котором содержится информация о времени проверки системы при заданном количестве узлов.

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

Для работы программы рекомендуется следующая конфигурация ЭВМ:

· Процессор - Pentium 100MHz и выше;

· Операционная система - Windows 95, 98, ME, NT, 2000.

· Оперативная память 32Мб и выше.

Следует заметить, что при различной конфигурации ЭВМ программа будет выдавать различные результаты времени проверки системы. Это связано с тем, что в программе все операции производятся над матрицами, описывающими систему. Обработка матриц требует высокой скорости работы процессора, поэтому время проверки будет зависеть от тактовой частоты работы процессора.

2. Описание алгоритма работы программы

2.1 Описание метода проверки графа на связность

При анализе систем связи на надежность методом статистического моделирования пользуются их упрощенными математическими моделями - графами систем. Основной частью анализа является проверка графа системы на связность. Поскольку анализ ведется в реальном масштабе времени, то к методу проверки графа на связность предъявляются достаточно жесткие требования. телекоммуникационный граф разбиение статистический

В данной работе для проверки графа используется метод «разбиения» [2]. Суть данного метода заключается в следующем: граф, описывающий телекоммуникационную систему, разбивается на множество подграфов. Количество таких подграфов:

,

где S - количество узлов исходного графа; N - количество подграфов. Очевидно, что количество узлов в каждом из подграфов равно N. Каждый подграф проверяется на связность методом «стягивания» [1] (использование метода «стягивания» позволяет получить наилучший результат при данном способе разбиения исходного графа).

По окончании проверки формируется «суперграф», элементы которого определяются следующим образом:

· Если подграф связен, то он заменяется одним узлом. При этом все связи подграфа сохраняются после замены;

· Если подграф не связен, то он включается в «суперграф» без изменения.

Метод «стягивания»

Суть этого метода заключается в следующем. Выберем произвольный узел графа и будем «стягивать» к нему все соседние узлы, соединенные с ним ребрами. На рисунке это можно изобразить следующим образом:

• Рисунок 2.1 - Процесс стягивания графа
• Стягивание будет происходить до тех пор, не останется множество несвязанных точек (узлов), к которым производилось стягивание. Если это множество содержит единственную точку, то исходный граф является связным, в противном случае исходный граф не связен. Следует сказать, что в результате такой операции должна остаться хотя бы одна точка, т.е. множество оставшихся точек не будет пустым. Таким образом, процесс «стягивания» состоит из двух частей:
• · выбор узла, к которому будет производиться «стягивание»;
• · выполнение «стягивания».

2.2 Алгоритм работы и текст программы

При программировании метода на ЭВМ приходится иметь дело с матричным заданием графа. Обычно граф задается с помощью матрицы инцидентности B:

Элемент матрицы bi,j равен количеству ребер, соединяющих вершину i с вершиной j. Если i = j, то bi,j = 0. Для неориентированного графа данная матрица симметрична относительно главной диагонали. Далее будем полагать, что bij = 1, если существует хотя бы одно ребро, соединяющее вершину i с вершиной j. Стягивание узлов графа в матричной форме сводится к операции дизъюнкции над соответствующими столбцами и строками исходного графа

Данный метод можно свести к следующим операциям, выполняемым машиной при проверке графа на связность:

· Выбирается узел, к которому будут «стягиваться все остальные, т.е. выбирается строка матрицы инцидентности, с которой будет начинаться проверка. Поскольку принципиальной разницы в выборе той или иной строки нет, то выбирается первая строка.

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

· Формируется новая матрица. Данный пункт может выполняться в процессе операции 2.

· Пункты 2, 3 повторяются до тех пор, пока не сформируется матрица размером 2 x 2.

· Проверка побочной диагонали матрицы.

Следует сказать, что данный алгоритм позволяет сделать интегральную проверку неориентированного графа.

Описанные выше действия можно запрограммировать в виде функции, которая приведена ниже.

function choosearr(var arr: matrix; n:word):boolean;

label lab;

var i,j,k,l:word;

key:boolean;

begin

for k:=0 to n-3 do

begin

key:=false;

for i:=k+1 to n-1 do

if (arr[k,i] <> 0) and (arr[i,k] <> 0) then

begin

key:= true;

for j:=k to n-1 do begin

arr[j,i]:=arr[k,j] or arr[j,i];

arr[i,j]:=arr[j,k] or arr[i,j];

arr[j,k]:=0; arr[k,j]:=0;

end;

arr1[i,i]:=0;

break;

end

else if (i=n-1)and(key=false) then

begin choosearr:=false; goto lab;

end;

end;

if (arr[n-1,n-2] = 1) or (arr[n-2,n-1] = 1) then choosearr:=true

else choosearr:=false;

lab:

end;

Данная функция выполняет проверку графа методом «стягивания». Входные данные - матрица инцидентности графа (массив arr); количество узлов графа - n. Переменные i, j, k, l используются в качестве переменных цикла. Логическая переменная key предназначена для выхода из цикла при обнаружении нулевой строки. Функция принимает значение true в случае, если граф - связен, и false - в противном случае.

Функцию можно использовать при анализе исходного графа и при анализе подграфа.

Кроме данной функции, в программе используется так же функция заполнения матрицы инцидентности B. При этом узлы графа привязываются к координатной сетке (рис.2.6):

Рисунок 2.2 - Пример задания графа, привязанного к координатной сетке

На рисунке указана нумерация нескольких узлов графа. Из рисунка видно, что свойства узлов (связи узлов) повторяются для определенных номеров. Поэтому заполнение матрицы инцидентности такого графа можно производить в цикле. Процедура заполнения графа приведена ниже.

procedure fillarr(var arr:matrix; x,y: word);

var n: word;

i,j:word;

begin

n:=(x+1)*(y+1);

for i:=0 to (n-1) do

for j:=0 to (n-1) do

arr[i,j]:=0;

for i:=0 to (n-1) do

for j:=0 to (n-1) do

begin

a:=i mod (x+1);

if ((a-1)>=0)and((i-1)=j) then arr[i,j]:=1;

if ((a+1)<=x) and ((i+1)=j) then arr[i,j]:=1;

if ((i-x-1)>=0) and((i-x-1)=j) then arr[i,j]:=1;

if ((i+x+1)<=n) and ((i+x+1)=j) then arr[i,j]:=1;

end;

end;

Входные данные: массив типа matrix; количество рядов узлов по осям X и Y. После выполнения процедуры массив данных будет заполнен.

3. Текст программы

Программа состоит из двух частей: рабочей и модуля. Текст рабочей части программы приведен ниже.

program Graf;

uses

SysUtils,

Forms,

Main in 'Main.pas' {Form1};

label 1,2,3;

type matrix=array [0..2000,0..2000] of byte;

var

i,j:word;

n,q: word;

x,y: word;

arr1,arr2,arr3:matrix;

m,k:word;

a:word;

b,c,d:word;

key:boolean;

hour,hour1,aa,qq:TDateTime;

f:textfile;

procedure fillarr(var arr:matrix; x,y: word);

var n: word;

i,j:word;

begin

n:=(x+1)*(y+1);

for i:=0 to (n-1) do

for j:=0 to (n-1) do

arr[i,j]:=0;

for i:=0 to (n-1) do

for j:=0 to (n-1) do

begin

a:=i mod (x+1);

if ((a-1)>=0)and((i-1)=j) then arr[i,j]:=1;

if ((a+1)<=x) and ((i+1)=j) then arr[i,j]:=1;

if ((i-x-1)>=0) and((i-x-1)=j) then arr[i,j]:=1;

if ((i+x+1)<=n) and ((i+x+1)=j) then arr[i,j]:=1;

end;

end;

function choosearr(var arr: matrix; n:word):boolean;

label lab;

var i,j,k,l:word;

key:boolean;

begin

for k:=0 to n-3 do

begin

key:=false;

for i:=k+1 to n-1 do

if (arr[k,i] <> 0) and (arr[i,k] <> 0) then

begin

key:= true;

for j:=k to n-1 do begin

arr[j,i]:=arr[k,j] or arr[j,i];

arr[i,j]:=arr[j,k] or arr[i,j];

arr[j,k]:=0; arr[k,j]:=0;

end;

arr1[i,i]:=0;

break;

end

else if (i=n-1)and(key=false) then

begin choosearr:=false; goto lab;

end;

end;

if (arr[n-1,n-2] = 1) or (arr[n-2,n-1] = 1) then choosearr:=true

else choosearr:=false;

lab:

end;

{$R *.RES}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.Run;

aa:=0;

assign(f,'Graf.txt');

rewrite(f);

writeln(f,'Количество узлов':20,'Время расчета(с)':20);

for q:=3 to 40 do

begin

fillarr(arr1,q-1,q-1);

hour:=time;

m:=0;

k:=0;

repeat

for i:=m to (m+q-1) do

for j:=m to (m+q-1) do

arr2[i-m,j-m]:=arr1[i,j];

key:=choosearr(arr2,q);

if key then

begin

arr3[k,k]:=1;

k:=k+1;

end

else

begin

for i:=m to (m+q-1) do

for j:=m to (m+q-1) do

arr3[k+i-m,k+j-m]:=arr1[i,j];

k:=k+q;

end;

m:=m+q;

until (m>q*q-1);

i:=0;

repeat

if arr3[i,i]=1 then

begin

n:=(i mod q)+(i div q);

x:=0;

for b:=i+1 to (k-1) do

if arr3[b,b]=1 then

begin

a:=(b mod q)+(b div q);

for c:=n*q to (n*q+q-1) do

for d:=a*q to (a*q+q-1) do

if arr1[c,d]=1 then

begin

arr3[i,b]:=1;

arr3[b,i]:=arr3[i,b];

break;

end;

end

else

begin

a:=(b mod q)+(b div q);

x:=x+1;

if ((x mod q)<>1) then continue;

for c:=a*q to (a*q+q-1) do

for d:=n*q to (n*q+q-1) do

begin

arr3[i,b+c-a*q]:=arr3[i,b+c-a*q] or arr1[d,c];

arr3[b+c-a*q,i]:=arr3[i,b+c-a*q];

end;

end;

goto 1;

end;

if arr3[i,i]=0 then

begin

x:=0;

n:=(i mod q)+(i div q);

for b:=i+q to (k-1) do

if arr3[b,b]=1 then

begin

a:=(b div q)+(b mod q);

for c:=n*q to (n*q+q-1) do

for d:=a*q to (a*q+q-1) do

begin

arr3[i+c-n*q,b]:=arr3[i+c-n*q,b] or arr1[c,d];

arr3[b,i+c-n*q]:=arr3[i+c-n*q,b];

end;

end

else

begin

x:=x+1;

a:=(b div q)+(b mod q);

if ((x mod q)<>1) then continue;

for c:=n*q to (n*q+q-1) do

for d:=a*q to (a*q+q-1) do

begin

arr3[i+c-n*q,b+d-a*q]:=arr1[c,d];

arr3[b+d-a*q,i+c-n*q]:=arr3[i+c-n*q,b+d-a*q];

end;

end;

goto 2;

end;

1: i:=i+1;

goto 3;

2: i:=i+q;

3: until (i>k-1);

key:=choosearr(arr3,k);

hour1:=time;

qq:=Hour1-hour;

qq:=qq*24*60*60;

aa:=aa+qq;

writeln(f,q*q:15,qq:30:3);

end;

writeln(f,'Общее время(с): ',aa:5:3);

close(f);

end.

В программе используется модули:Forms, Main, SysUtils. Модули Forms и SysUtils являются стандартными, поставляемыми вместе с Delphi. Текст модуля Main приведен ниже.

unit Main;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

StdCtrls;

type

TForm1 = class(TForm)

Button1: TButton;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);

begin

Close;

end;

end.

Заключение

Описанный выше метод проверки системы на связность позволяет производить анализ в реальном масштабе времени. Для сравнения скорости работы приведен график зависимости времени проверки от количества узлов исследуемой системы для двух методов: «стягивания» и «разбиения», которые описаны выше.

Вычисления производились в следующей конфигурации:

· Процессор Cyrix 233MMX Media GX;

· Оперативная память 80Мб;

· Операционная система Windows 98SE.

Из графиков видно преимущество метода «разбиения» над методом «стягивания». Следует сказать, что известные на сегодняшний день методы проверки графа на связность показывают худшие результаты. Таким образом, метод «разбиения» является одним из перспективных методов проверки телекоммуникационной системы на связность.

Литература

1. Новиков С.Н., Гольник А.Н. Анализ живучести сетей связи (рекламно-техническое описание). ФАП РФ номер рег. № 1534 от 2002 г.

2. Новиков С.Н., Куцева Т.В. Расчет структурной надежности сети связи // Труды учебных институтов связи / Л. 1987. С. 99 - 102.

Размещено на Allbest.ru

...