Полный поток в транспортной сети

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

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

Пензенский государственный университет

Кафедра «Вычислительная техника»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

курсовому проектированию

по курсу «Логика и основы алгоритмизации в инженерных задачах»

на тему «ПОЛНЫЙ ПОТОК В ТРАНСПОРТНОЙ СЕТИ»

Выполнил:

студент группы 16ВВ3 Страхов А.В.

Приняли:

Малютина Г. И.

д.т.н., профессор Пащенко Д. В.



Содержание

Введение

Описание разработки программы

Определение структуры файла базы данных

Теоретическая часть задания

Описание алгоритма для решения поставленной задачи

Результат работы программы

Ручной расчет

Описание самой программы

Заключение

Список литературы

Приложение



Введение

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



Описание разработки программы

Для написания данной программы будет использован язык программирования Си. Язык Си является одним из наиболее важных и популярных языков программирования. Его использование все более расширяется, поскольку часто программисты предпочитают язык Си всем другим языкам после первого знакомства с ним. Он включает в себя те управляющие конструкции, которые рекомендуются теоретическим и практическим программированием. Его структура побуждает программиста использовать в своей работе нисходящее проектирование, структурное программирование и пошаговую разработку модулей. Результатом такого подхода является надежная и читаемая программа. Структура языка Си позволяет наилучшим образом использовать возможности современных ЭВМ. На языке Си программы обычно отличаются компактностью и быстротой исполнения. Программа, написанная на Си для одной вычислительной системы, может быть перенесена с небольшими изменениями (или вообще без них) на другую.

Основной интерфейс информационной системы будет выполнен в виде стандартного окна Windows, основанный на WinApi.

Windows API спроектирован для использования в языке Си для написания прикладных программ, предназначенных для работы под управлением операционной системы MS Windows. Работа через Windows API -- это наиболее близкий к операционной системе способ взаимодействия с ней из прикладных программ. Более низкий уровень доступа, необходимый только для драйверов устройств.

Windows API представляет собой множество функций, структур данных и числовых констант, следующих соглашениям языка Си. Все языки программирования, способные вызывать такие функции и оперировать такими типами данных в программах, исполняемых в среде Windows, могут пользоваться этим API. В частности, это языки C++, Pascal, Visual Basic и многие другие.

С помощью данных инструментов необходимо создать программу, в которой пользователь мог бы иметь возможность:

Загружать матрицу из файла.

Увидеть отображение сети по загруженной матрице.

Найти максимальный поток в сети и увидеть распределение этого самого потока.

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

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

Определение структуры файла базы данных

программа транспортный сеть алгоритм

Для работы данной программы используется следующие основные массивы:

int M[6][6], //сюда считывается матрица,

на основе которой строится граф

MaxFlow[6][6]; //матрица с макс. насыщением

В данные матрицы заносятся данные из файлов с расширением “.txt” путем посимвольного считывания.

Пример матрицы:

0,5,6,0,0,0,

0,0,4,3,0,0,

0,0,0,5,5,0,

0,0,0,0,2,6,

0,0,0,0,0,4,

0,0,0,0,0,0

Особенностью считывания является то, что в файл заносятся значения с учетом смены ориентации у матрицы:

столбцы (у исх. матрицы ) =строки (у полученной матр.);

строки (у исх. матрицы ) =столбцы (у полученной матр.).

Это важно учитывать, так как граф ориентированный - дуги имеют направление.

Теоретическая часть задания

Введем основные понятия в транспортной сети.

Транспортной сетью называется орграф D = (V, X) с множеством вершин V = {v1,…,vn}, для которого выполняются условия:

существует одна и только одна вершина v1, называемая источником, такая, что Г-1 (v1) = (т.е. ни одна дуга не заходит в v1),

существует одна и только одна вершина vn, называемая стоком, такая, что Г(vn) = (т.е. из vn не исходит ни одной дуги),

каждой дуге xX поставлено в соответствие целое число c (x) 0, называемое пропускной способностью дуги.

Функция (x), определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если

для любой дуги xX величина (x), называемая потоком по дуге x, удовлетворяет условию 0 (x) c(x),

для любой промежуточной вершины v сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.

Величиной потока в транспортной сети D называется величина, равная сумме потоков по всем дугам, заходящим в сток, или, что то же самое сумме потоков по всем дугам, исходящим из источника.

Дуга xX называется насыщенной, если поток по ней равен ее пропускной способности. Поток называется полным, если любой путь в сети из источника в сток содержит, по крайней мере, одну насыщенную дугу.

Описание алгоритма для решения поставленной задачи

Пусть нам дана транспортная сеть D, заданная матрицей пропускных способностей дуг. Необходимо найти полный поток в сети.

Полагаем для любой дуги xХ (x) = 0 ( начинаем с нулевого потока ).

Полагаем D* = D.

Удаляем из орграфа D* все дуги, являющиеся насыщенными при потоке в транспортной сети D. Полученный орграф снова обозначим через D*.

Ищем в D* простую цепь из v1 в vn . Если такой цепи нет, то - искомый полный поток в транспортной сети D. В противном случае переходим к шагу 5.

Увеличиваем поток (x) по каждой дуге x из на одинаковую величину a>0 такую, что, по крайней мере, одна дуга из окажется насыщенной, а потоки по всем остальным дугам из не превышают их пропускных способностей. При этом величина потока также увеличится на a, а сам поток в транспортной сети D остается допустимым. После этого перейдем к шагу 3.

Результат работы программы

Найдем максимальный поток в сети, заданной орграфом по матрице:

0,5,6,0,0,0,

0,0,4,3,0,0,

0,0,0,5,5,0,

0,0,0,0,2,6,

0,0,0,0,0,4,

0,0,0,0,0,0,

Загрузим данную сеть для нахождения результата.

Рисунок 1-Начальное окно

Рисунок 2-Сообщение о загрузке



Рисунок 3-Вывод исходного графа

Рисунок 4 ?? Максимальный поток

Рисунок 5-Насыщенная сеть



Ручной расчет

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

0,0,0,0,0,0,

5,0,0,0,0,0,

5,4,0,0,0,0,

0,1,5,0,0,0,

0,0,4,2,0,4,

0,0,0,4,5,0,

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

Значения этой матрицы соответствуют значениям, выведенными программой, из чего можем сделать вывод о том, что программа работает исправно.

Описание самой программы

Порядок работы программы:

Загружается матрица орграфа.

Строится каркас, состоящих из стрелочек, поверх которого накладываются вершины.

Затем по загруженной матрице подписываются веса дуг.

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



Рисунок 6-Модули проекта

Полное и подробное описание функций, на основе которых функционирует программа, находится в «Приложении А».

Программа состоит из нескольких модулей, см. рис. 6.

В модуле «L_CW. cpp» находится основной код программы. Там содержится «родительская» функция WinMain и находятся все функции для загрузки обработки и вывода графа. Модуль «Resource.h» содержит в себе дополнительные параметры и объявления для работы окна.

Модуль «stadfx.h» содержит прекомпилируемую часть программы, а в нашем случае библиотеки.

Модуль «L_CW.rc» хранит все дополнительную информацию для создания меню и привязки иконки

Тесты

При загрузке некорректной матрицы выводится ошибка, см рис. 7.



Рисунок 7-Сообщение об ошибке

Если матрица подходит для работы, то при загрузке выводится сообщение об успешной загрузке матрицы, см. рис. 2.



Заключение

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

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



Список литературы

1. Зыков А.А. Основы теории графов. - М.: Наука, 1984.

2. Электронный ресурс: htpp://CyberForum.ru.

3. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные понятия и приложения. - М.: Наука, 1987.



Приложение

Листинг

«L_CW. cpp»

#include "stdafx.h"

#include "Resource.h"

BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)//ф-ия. окна

{

int XWndSize=500, YWndSize=400; //разрешание экрана

HWND hWnd;

hInst = hInstance;

hWnd = CreateWindow(

szWindowClass,

L"CW-17V. 16vv3-Strakhov A.V.",

WS_OVERLAPPEDWINDOW,

GetSystemMetrics(SM_CXSCREEN)/2-XWndSize/2, //задаем позицию угла окна по Х

GetSystemMetrics(SM_CYSCREEN)/2-YWndSize/2, //задаем позицию угла окна по У

XWndSize, YWndSize,

NULL, NULL,

hInstance, NULL);

if (!hWnd) return FALSE;

ShowWindow(hWnd, nCmdShow);

UpdateWindow(hWnd);

return TRUE;

}

int M[6][6], //сюда считывается матрица, на основе которой строится граф

MaxFlow[6][6]; //матрица с макс. насыщением

//ф. вывод ошибки, если что-то пошло не так

void end (HWND hWnd)

{

MessageBoxA(hWnd, "Try again!", "File error", MB_OK | MB_ICONHAND);

PostQuitMessage(0);

}

//ф.загрузки матрицы из файла

void upload (HWND hWnd)

{

//обнуляем матрицы

for (int i=0; i<6; i++)

{

for (int j=0; j<6; j++)

{

M[i][j]=0;

MaxFlow[i][j]=0;

}

}

//считываем матрицу из файла

FILE *oMatr;

if (fopen_s(&oMatr, "graph1.txt", "r")==1) end(hWnd);

for (int i=0; i<6; i++)

{

for (int j=0; j<6; j++)

{

fscanf_s(oMatr, "%d,", &M[i][j]);

}

}

fclose(oMatr);

for (int i=0; i<6; i++)

{

for (int j=0; j<6; j++)

{

//проверка на то, что граф ненаправленный

if (M[i][j]>0 && M[j][i]>0) end(hWnd);

}

//проверка на отсутсвие петлей

if (M[i][i]>0) end(hWnd);

}

}

//ф. для отрисовки графа

void DrawGR (HDC hdc)

{

//подписываем исток и сток

SetTextColor(hdc,RGB(105,00,255));

TextOut(hdc, 40, 140, _T("Исток"), 5);

TextOut(hdc, 410, 140, _T("Сток"), 4);

//координаты вершин

int V[6][2]={{60,170},{180,80},{180,260},{300,260},{300,80},{420,170}};

//создаем кисти

HPEN

pen=CreatePen(PS_SOLID,1,RGB(0,0,0)),

hpen=CreatePen(PS_SOLID,4,RGB(0,0,0));

//рисуем граф

SetTextColor(hdc,RGB(255,0,0));

for (int i=0; i<6; i++)

{

for (int j=0; j<6; j++)

{

if (M[i][j]>0)

{

//отрисовываем дугу

MoveToEx(hdc,V[i][0], V[i][1],0);

LineTo(hdc, V[j][0], V[j][1]);

//меняем кисть для подсветки направления

SelectObject(hdc,hpen);

//стартовые координаты для стрелочки

int x=(V[j][0]-V[i][0]);

int y=(V[j][1]-V[i][1]);

//уменьшаем длину стрелочки до прим. 25 пикс.

while (sqrt(pow(x,2.0)+pow(y,2.0))>25)

{ x*=0.89; y*=0.89; }

//отрисовываем стрелочку

MoveToEx(hdc,V[j][0]-x, V[j][1]-y,0);

LineTo(hdc, V[j][0], V[j][1]);

//применяем стандартную кисть

SelectObject(hdc,pen);

}

}

}

for (int i=0; i<6; i++)

{

//отрисовываем круг для вершины

Ellipse(hdc, V[i][0]-13,V[i][1]-13,V[i][0]+13,V[i][1]+13);

//выводим текстом

char v[2];

TextOut(hdc, V[i][0]-5, V[i][1]-7, (LPCTSTR) itoa(i+1, v, 10), 1);

}

//удаляем кисти и устанавливаем цвет текста на черный

SetTextColor(hdc,RGB(0,0,0));

DeleteObject(pen);

DeleteObject(hpen);

}

//ф. для нанесения значения дуг

void AcrValues(HDC hdc, int Mtrx[6][6])

{

//координаты полей для вывода веса дуг

int Cap[10][4]={{110,105,1,2},{110,220,1,3},{160,170,2,3},

{215,110,2,4},{240,60,2,5},{240,270,3,4},

{215,215,3,5},{310,170,4,5},{369,210,4,6},{365,105,5,6}};

SetTextColor(hdc,RGB(0,0,255));

//перебираем соединения графа

for (int x=1; x<7; x++)

{

for (int y=1; y<7; y++)

{

//при нахождении связи запускаем цикл по

//выбору соответствующих координат поля веса дуги

if (Mtrx[x-1][y-1]>0)

{

for (int i=0; i<10; i++)

{

if ((Cap[i][2]==x && Cap[i][3]==y) || (Cap[i][2]==y && Cap[i][3]==x))

{

//переводим вес дуги из матрицы int в char

char buf[2];

itoa(Mtrx[x-1][y-1], buf, 10);

//выводим значение дуги

TextOut(hdc, Cap[i][0], Cap[i][1], (LPCTSTR) buf, strlen(buf));

}

}

}

}

}

SetTextColor(hdc,RGB(0,0,0));

}

//ф. для насыщения дуг и вывода ChainLength

void Solution (HDC hdc, HWND hWnd)

{

int Sum=0,

IniFlow=0,

Buf[6][6],

Min=1000;

char Result[120];

//копируем M в Buf

for (int i=0; i<6; i++)

{

for (int j=0; j<6; j++)

{

Buf[i][j]=M[i][j];

}

//заодно подсчитываем начальный поток в сети

IniFlow+=Buf[0][i];

}

//запускаем цикл по насыщению сети

while(1)

{

int ChainLength=0, //длина цепи

Input=0, //исток

Output=0; //сток

for (int i=0; i<6; i++)

{

for (int j=0; j<6; j++)

{

if (Buf[i][j]>0)

{

//определяем минимальный элемент в цепи

if (Buf[i][j]<Min) Min=Buf[i][j];

i=j;

ChainLength++;

}

}

}

//если цепь слишком короткая- остановка

if (ChainLength<3) break;

for (int i=0; i<6; i++)

{

for (int j=0; j<6; j++)

{

if (Buf[i][j]>0)

{

//насыщяем сеть и вычитаем из исх. добавленный поток

Buf[i][j]-=Min;

MaxFlow[i][j]+=Min;

i=j;

}

}

}

//считаем ввод и вывод в сеть

for (int i=0; i<6; i++)

{

Input+=MaxFlow[0][i];

Output+=MaxFlow[i][5];

}

//в случае достижения максимума остановить поиск

if ( Input>=IniFlow || Output>=IniFlow) break;

}

//подсчитываем суммарный поток

for (int i=0; i<6; i++)

{

Sum+=MaxFlow[i][5];

}

//вывод максимальной пропускной способности

MessageBoxA(hWnd, itoa(Sum, Result,10), "Max flow", MB_OK);

}

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)

{

int wmId, wmEvent;

PAINTSTRUCT ps;

HDC hdc;

switch (message)

{

case WM_COMMAND:

wmId = LOWORD(wParam);

wmEvent = HIWORD(wParam);

switch (wmId)

{

case IDM_N_2:

DrawN2=!DrawN2;

InvalidateRect(hWnd,NULL, true);

UpdateWindow(hWnd);

break;

case IDM_N_3:

DrawN3=!DrawN3;

InvalidateRect(hWnd,NULL, true);

UpdateWindow(hWnd);

break;

case IDM_EXIT:

DestroyWindow(hWnd);

break;

default:

return DefWindowProc(hWnd, message, wParam, lParam);

}

break;

case WM_PAINT:

hdc = BeginPaint(hWnd, &ps);

if (DrawN2) //вывод графа с весом дуг

{

upload(hWnd);

MessageBoxA(hWnd, "File was successfuly uploaded!", "Notification", MB_OK);

TextOut(hdc, 2, 2, _T("Presentation of initial graph"), 30);

DrawGR(hdc);

AcrValues(hdc, M);

DrawN2=false;

}

if (DrawN3) //подсчет пропускной способности сети + вывод графа со значениями дуг и конечным результатом

{

TextOut(hdc, 2, 2, _T("Presentation of solution with maximum possiable flow."), 54);

DrawGR(hdc);

Solution(hdc, hWnd);

AcrValues(hdc, MaxFlow);

DrawN3=false;

}

EndPaint(hWnd, &ps);

break;

case WM_DESTROY:

PostQuitMessage(0);

break;

default:

return DefWindowProc(hWnd, message, wParam, lParam);

}return 0;}

«Resource.h»

#define IDS_APP_TITLE 103

#define IDM_EXIT 105

#define IDI_L_CW 107

#define IDI_SMALL 108

#define IDC_L_CW 109

#define IDC_MYICON 2

#define IDM_N_2 112

#define IDM_N_3 113

//переменные для меню

bool DrawN1 = false;

bool DrawN2 = false;

bool DrawN3 = false;

#define MAX_LOADSTRING 100

HINSTANCE hInst; // текущий экземпляр

TCHAR szTitle[MAX_LOADSTRING]; // Текст строки заголовка

TCHAR szWindowClass[MAX_LOADSTRING]; // имя класса главного окна

BOOL InitInstance(HINSTANCE, int);

LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);

ATOM MyRegisterClass(HINSTANCE hInstance)

{

WNDCLASSEX wcex;

wcex.cbSize = sizeof(WNDCLASSEX);

wcex.style = CS_HREDRAW | CS_VREDRAW;

wcex.lpfnWndProc = WndProc;

wcex.cbClsExtra = 0;

wcex.cbWndExtra = 0;

wcex.hInstance = hInstance;

wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_L_CW));

wcex.hCursor = LoadCursor(NULL, IDC_ARROW);

wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);

wcex.lpszMenuName = MAKEINTRESOURCE(IDC_L_CW);

wcex.lpszClassName = szWindowClass;

wcex.hIconSm = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

return RegisterClassEx(&wcex);

}

int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)

{

UNREFERENCED_PARAMETER(hPrevInstance);

UNREFERENCED_PARAMETER(lpCmdLine);

MSG msg;

HACCEL hAccelTable;

LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);

LoadString(hInstance, IDC_L_CW, szWindowClass, MAX_LOADSTRING);

MyRegisterClass(hInstance);

if (!InitInstance (hInstance, nCmdShow)) return FALSE;

hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_L_CW));

while (GetMessage(&msg, NULL, 0, 0))

{

if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))

{

TranslateMessage(&msg);

DispatchMessage(&msg);

}

}

return (int) msg.wParam;

}

«L_CW.rc»

#include "resource.h"

// Значок

IDI_L_CW ICON "IC.ico"

IDI_SMALL ICON "IC.ico"

// Меню

IDC_L_CW MENU

BEGIN

MENUITEM "Initial graph", IDM_N_2

MENUITEM "Solution", IDM_N_3

MENUITEM "Exit", IDM_EXIT

END

// Таблица строк

STRINGTABLE

BEGIN

IDC_L_CW "L_CW"

IDS_APP_TITLE "L_CW"

END

«stdfx.h»

#pragma once

// Файлы заголовков Windows:

#include <windows.h>

// Файлы заголовков C RunTime

#include <stdlib.h>

#include <malloc.h>

#include <memory.h>

#include <tchar.h>

// TODO: Установите здесь ссылки на дополнительные заголовки, требующиеся для программы

#include <math.h>

#include <winbase.h>

#include <string.h>

#include <stdio.h>

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

...