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

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

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

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

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

к курсовой работе

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

на тему "Алгоритм Форда - Фалкерсона для нахождения максимального потока"

Выполнил: студент Ягудин М.Р.

Приняли: Малютина Г.И., Пащенко Д.В.

Пенза 2017



Оглавление

• Введение
• 1. Постановка задачи
• 2. Теоретическая часть задания
• 2.1 Общие теоретические сведения
• 2.2 Описание алгоритма программы
• 3. Ручной расчёт задачи
• 4. Описание программы
• 5. Тестирование
• Заключение
• Список литературы
• Приложение А. Листинг программы


Введение

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

В качестве среды разработки мною была выбрана среда Microsoft Visual Studio 2017, язык программирования - С++.

В ходе выполнения данной курсовой работы были приобретены навыки работы с формами и их элементами в среде Microsoft Visual Studio 2017, навыки работы с проектами и многомодульными программами.



1. Постановка задачи

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

Исходный граф в программе должен задаваться матрицей смежности, причём при вводе данных должны быть предусмотрены граничные условия, должна выполняться проверка корректности введенных данных. Устройства ввода данных - клавиатура и мышь. Программа должна быть разработана для работы в операционной системе Microsoft Windows. Для удобства использования программы должен быть разработан графический интерфейс оформленный при помощи Windows Form Application с возможностью ввода и вывода информации.

Задания выполняются в соответствии с вариантом №20.



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

2.1 Общие теоретические сведения

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

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

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

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

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

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

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

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

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

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

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

2.2 Описание алгоритма программы

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

Результат: полный поток в сети.

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

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

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

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

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

На рисунке 1 показана схема работы программы.



Рисунок 1 - Схема программы



3. Ручной расчёт задачи

Дана транспортная сеть D(V,X) (рис. 5.3). Построить максимальный поток.

Рисунок 2- Транспортная сеть

Полагаем =D,, т.е. начинаем с нулевого потока (см. рис. 5.4).

Рисунок 3 - Орграф ,,, 1=v1v2v4v6.

Насыщенные дуги отсутствуют. Выделим в простой путь ₁=v₁v₂v₄v₆ и увеличим потоки по дугам на а ₁= 3 до насыщения дуги (v₂,v₄) (рис. 5.5)



Рисунок 4 - Поток ,.

В результате получим ,, содержащий одну насыщенную дугу. Пометим её знаком "~" и удалим из орграфа. Оставшийся граф снова обозначим через(рис. 5.6)

Рисунок 5 - Орграф ,2=v1v2v3v4v6.

Рисунок 6 - Поток ,.



Рисунок 7 - Орграф ,3=v1v3v5v6.

Рисунок 8 - Поток ,.

Рисунок 9 - Орграф ,4=v1v2v5v6.

Рисунок 10 - Поток ,.



Рисунок 11 - Орграф , 5.

В полученном графе не существует пути из v₁ в v₆, следовательно, потокявляется максимальным (см. рис. 5.11).



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

алгоритм граф матрица интерфейс

Программа разбита на несколько модулей. Логика.cpp - главный файл проекта. В нем осуществляется запуск главного окна Form1().

Файл Form1.h отвечает за внешний вид главного окна, а именно: заголовок, пункты меню. Также в этом файле осуществляются сам алгоритм поиска максимального потока.

На рисунке 12 изображено стартовое окно программы:

Рисунок 12 - стартовое окно программы

Далее мы указываем количество вершин и рёбер в графе, после этого мы можем задать вес рёбер вручную или же заполнить их случайным образом, из диапазона случайных значений, который мы указываем в программе. После заполнения матрицы нажимаем появившиеся кнопки "Вывести граф" и "Рассчитать максимальный поток" и получаем графическое изображение сети и значение максимального потока. На рисунке 13. Показан результат работы программы.



Рисунок 13 - результат работы программы



5. Тестирование

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

Если пользователь неправильно вводит исходную матрицу смежности (вводит текстовые), то выдаётся окно с ошибкой "Ошибка ввода матрицы смежности".

Рисунок 14 - неправильный ввод исходной матрицы



Заключение

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

При выполнении данной работы использовались функции Windows.form, описанные в заголовочном файле Windows.h для визуализации результатов работы.

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

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



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

1. Брайан Керниган, Деннис Ритчи - Язык программирования Си, 2-е издание, 2016.

2. Стивен Прата - Язык программирования C++. Лекции и упражнения, 6-е издание, 2017.

3. Брюс Эккель - Философия C++. Введение в стандартный C++, 2-е издание, 2004.



Приложение А. Листинг программы

#pragma once

#include <memory.h>

#include <string.h>

#include <stdlib.h>

#include <ctime>

#include <math.h>

#define M_PI 3.14159265358979323846

const int MAX_VERTICES = 100;

int NUM_VERTICES;

int f[MAX_VERTICES][MAX_VERTICES];

int c[MAX_VERTICES][MAX_VERTICES];

int Flow[MAX_VERTICES];

int Link[MAX_VERTICES];

int Queue[MAX_VERTICES];

int QP, QC;

int source, target;

int FindPath(int source, int target)

{

QP = 0; QC = 1; Queue[0] = source;

Link[target] = -1;

int i;

int CurVertex;

memset(Flow, 0, sizeof(int)*NUM_VERTICES);

Flow[source] = 10000;

while (Link[target] == -1 && QP < QC)

{

CurVertex = Queue[QP];

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

if ((c[CurVertex][i] - f[CurVertex][i])>0 && Flow[i] == 0)

{

Queue[QC] = i; QC++;

Link[i] = CurVertex;

if (c[CurVertex][i]-f[CurVertex][i] < Flow[CurVertex])

Flow[i] = c[CurVertex][i];

else

Flow[i] = Flow[CurVertex];

}

QP++;

}

if (Link[target] == -1) return 0;

CurVertex = target;

while (CurVertex != source) {

f[Link[CurVertex]][CurVertex] +=Flow[target];

CurVertex = Link[CurVertex];

}

return Flow[target];

}

int MaxFlow(int source, int target) {

memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTICES);

int MaxFlow = 0;

int AddFlow;

do {

AddFlow = FindPath(source, target);

MaxFlow += AddFlow;

} while (AddFlow >0);

return MaxFlow;

}

namespace Логика {

using namespace System;

using namespace System::ComponentModel;

using namespace System::Collections;

using namespace System::Windows::Forms;

using namespace System::Data;

using namespace System::Drawing;

/// <summary>

/// Summary for Form1

/// </summary>

public ref class Form1 : public System::Windows::Forms::Form

{

public:

Form1(void)

{

InitializeComponent();

//

//TODO: Add the constructor code here

//

}

protected:

/// <summary>

/// Clean up any resources being used.

/// </summary>

~Form1()

{

if (components)

{

delete components;

}

}

private: System::Windows::Forms::Button^ button1;

protected:

private: System::Windows::Forms::Button^ button2;

private: System::Windows::Forms::MenuStrip^ menuStrip1;

private: System::Windows::Forms::DataGridView^ dataGridView1;

private: System::Windows::Forms::PictureBox^ pictureBox1;

private: System::Windows::Forms::Button^ button3;

private: System::Windows::Forms::Button^ button4;

private: System::Windows::Forms::Label^ label1;

private: System::Windows::Forms::TextBox^ textBox1;

private: System::Windows::Forms::NumericUpDown^ numericUpDown1;

private: System::Windows::Forms::Label^ label2;

private: System::Windows::Forms::Label^ label3;

private: System::Windows::Forms::NumericUpDown^ numericUpDown2;

private: System::Windows::Forms::Label^ label4;

private: System::Windows::Forms::NumericUpDown^ numericUpDown3;

private:

/// <summary>

/// Required designer variable.

/// </summary>

System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code

/// <summary>

/// Required method for Designer support - do not modify

/// the contents of this method with the code editor.

/// </summary>

void InitializeComponent(void)

{

this->button1 = (gcnew System::Windows::Forms::Button());

this->button2 = (gcnew System::Windows::Forms::Button());

this->menuStrip1 = (gcnew System::Windows::Forms::MenuStrip());

this->dataGridView1 = (gcnew System::Windows::Forms::DataGridView());

this->pictureBox1 = (gcnew System::Windows::Forms::PictureBox());

this->button3 = (gcnew System::Windows::Forms::Button());

this->button4 = (gcnew System::Windows::Forms::Button());

this->label1 = (gcnew System::Windows::Forms::Label());

this->textBox1 = (gcnew System::Windows::Forms::TextBox());

this->numericUpDown1 = (gcnew System::Windows::Forms::NumericUpDown());

this->label2 = (gcnew System::Windows::Forms::Label());

this->label3 = (gcnew System::Windows::Forms::Label());

this->numericUpDown2 = (gcnew System::Windows::Forms::NumericUpDown());

this->label4 = (gcnew System::Windows::Forms::Label());

this->numericUpDown3 = (gcnew System::Windows::Forms::NumericUpDown());

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown2))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown3))->BeginInit();

this->SuspendLayout();

//

// button1

//

this->button1->Location = System::Drawing::Point(11, 90);

this->button1->Name = L"button1";

this->button1->Size = System::Drawing::Size(124, 23);

this->button1->TabIndex = 0;

this->button1->Text = L"Случайные значения";

this->button1->UseVisualStyleBackColor = true;

this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);

//

// button2

//

this->button2->Location = System::Drawing::Point(142, 90);

this->button2->Name = L"button2";

this->button2->Size = System::Drawing::Size(115, 23);

this->button2->TabIndex = 1;

this->button2->Text = L"Заполнить вручную";

this->button2->UseVisualStyleBackColor = true;

this->button2->Click += gcnew System::EventHandler(this, &Form1::button2_Click);

//

// menuStrip1

//

this->menuStrip1->Location = System::Drawing::Point(0, 0);

this->menuStrip1->Name = L"menuStrip1";

this->menuStrip1->Size = System::Drawing::Size(1018, 24);

this->menuStrip1->TabIndex = 2;

this->menuStrip1->Text = L"menuStrip1";

//

// dataGridView1

//

this->dataGridView1->AllowUserToAddRows = false;

this->dataGridView1->AllowUserToDeleteRows = false;

this->dataGridView1->AllowUserToResizeColumns = false;

this->dataGridView1->AllowUserToResizeRows = false;

this->dataGridView1->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;

this->dataGridView1->Location = System::Drawing::Point(12, 119);

this->dataGridView1->Name = L"dataGridView1";

this->dataGridView1->ReadOnly = true;

this->dataGridView1->Size = System::Drawing::Size(245, 167);

this->dataGridView1->TabIndex = 3;

this->dataGridView1->CellEndEdit += gcnew System::Windows::Forms::DataGridViewCellEventHandler(this, &Form1::dataGridView1_CellEndEdit);

//

// pictureBox1

//

this->pictureBox1->BackColor = System::Drawing::SystemColors::HighlightText;

this->pictureBox1->Location = System::Drawing::Point(262, 20);

this->pictureBox1->Name = L"pictureBox1";

this->pictureBox1->Size = System::Drawing::Size(742, 402);

this->pictureBox1->TabIndex = 4;

this->pictureBox1->TabStop = false;

//

// button3

//

this->button3->Location = System::Drawing::Point(11, 292);

this->button3->Name = L"button3";

this->button3->Size = System::Drawing::Size(245, 23);

this->button3->TabIndex = 5;

this->button3->Text = L"Вывести граф";

this->button3->UseVisualStyleBackColor = true;

this->button3->Click += gcnew System::EventHandler(this, &Form1::button3_Click);

//

// button4

//

this->button4->Location = System::Drawing::Point(11, 321);

this->button4->Name = L"button4";

this->button4->Size = System::Drawing::Size(245, 23);

this->button4->TabIndex = 6;

this->button4->Text = L"Рассчитать полный поток";

this->button4->UseVisualStyleBackColor = true;

this->button4->Click += gcnew System::EventHandler(this, &Form1::button4_Click);

//

// label1

//

this->label1->AutoSize = true;

this->label1->Location = System::Drawing::Point(9, 353);

this->label1->Name = L"label1";

this->label1->Size = System::Drawing::Size(82, 13);

this->label1->TabIndex = 7;

this->label1->Text = L"Полный поток:";

this->label1->Click += gcnew System::EventHandler(this, &Form1::label1_Click);

//

// textBox1

//

this->textBox1->Location = System::Drawing::Point(97, 350);

this->textBox1->Name = L"textBox1";

this->textBox1->ReadOnly = true;

this->textBox1->Size = System::Drawing::Size(159, 20);

this->textBox1->TabIndex = 8;

this->textBox1->TextChanged += gcnew System::EventHandler(this, &Form1::textBox1_TextChanged);

//

// numericUpDown1

//

this->numericUpDown1->Location = System::Drawing::Point(141, 20);

this->numericUpDown1->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

this->numericUpDown1->Name = L"numericUpDown1";

this->numericUpDown1->Size = System::Drawing::Size(65, 20);

this->numericUpDown1->TabIndex = 9;

this->numericUpDown1->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

//

// label2

//

this->label2->AutoSize = true;

this->label2->Location = System::Drawing::Point(9, 22);

this->label2->Name = L"label2";

this->label2->Size = System::Drawing::Size(126, 13);

this->label2->TabIndex = 10;

this->label2->Text = L"Размерность матрицы:";

//

// label3

//

this->label3->AutoSize = true;

this->label3->Location = System::Drawing::Point(8, 48);

this->label3->Name = L"label3";

this->label3->Size = System::Drawing::Size(167, 13);

this->label3->TabIndex = 11;

this->label3->Text = L"Диапазон случайных значений:";

//

// numericUpDown2

//

this->numericUpDown2->Location = System::Drawing::Point(12, 64);

this->numericUpDown2->Name = L"numericUpDown2";

this->numericUpDown2->Size = System::Drawing::Size(58, 20);

this->numericUpDown2->TabIndex = 12;

this->numericUpDown2->ValueChanged += gcnew System::EventHandler(this, &Form1::numericUpDown2_ValueChanged);

//

// label4

//

this->label4->AutoSize = true;

this->label4->Location = System::Drawing::Point(85, 66);

this->label4->Name = L"label4";

this->label4->Size = System::Drawing::Size(10, 13);

this->label4->TabIndex = 13;

this->label4->Text = L"-";

//

// numericUpDown3

//

this->numericUpDown3->Location = System::Drawing::Point(116, 64);

this->numericUpDown3->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

this->numericUpDown3->Name = L"numericUpDown3";

this->numericUpDown3->Size = System::Drawing::Size(61, 20);

this->numericUpDown3->TabIndex = 14;

this->numericUpDown3->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

this->numericUpDown3->ValueChanged += gcnew System::EventHandler(this, &Form1::numericUpDown3_ValueChanged);

//

// Form1

//

this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);

this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;

this->ClientSize = System::Drawing::Size(1018, 430);

this->Controls->Add(this->numericUpDown3);

this->Controls->Add(this->label4);

this->Controls->Add(this->numericUpDown2);

this->Controls->Add(this->label3);

this->Controls->Add(this->label2);

this->Controls->Add(this->numericUpDown1);

this->Controls->Add(this->textBox1);

this->Controls->Add(this->label1);

this->Controls->Add(this->button4);

this->Controls->Add(this->button3);

this->Controls->Add(this->pictureBox1);

this->Controls->Add(this->dataGridView1);

this->Controls->Add(this->button2);

this->Controls->Add(this->button1);

this->Controls->Add(this->menuStrip1);

this->FormBorderStyle = System::Windows::Forms::FormBorderStyle::Fixed3D;

this->MainMenuStrip = this->menuStrip1;

this->MaximizeBox = false;

this->MinimizeBox = false;

this->Name = L"Form1";

this->Text = L"Полный поток";

this->Load += gcnew System::EventHandler(this, &Form1::Form1_Load);

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown2))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown3))->EndInit();

this->ResumeLayout(false);

this->PerformLayout();

}

#pragma endregion

private: void GenRand(int **Mass, int SizeMass) {

srand(time(NULL));

for (int i=0; i < SizeMass; i++) {

for (int j=0; j < SizeMass; j++) {

if((i==j)||(j<i)) continue;

Mass[i][j] = Convert::ToInt32(numericUpDown2->Value)+rand()%(Convert::ToInt32(numericUpDown3->Value)-Convert::ToInt32(numericUpDown2->Value)+1);;

Mass[j][i] = 0;

}

}

}

private: void ShowMass(int **Mass, int SizeMass) {

for (int i=0; i < SizeMass; i++) {

for (int j=0; j < SizeMass; j++) {

if (j==0)

{

dataGridView1->Columns[j]->HeaderCell->Value = "I";

}

else

{

if (j==SizeMass-1)

{

dataGridView1->Columns[j]->HeaderCell->Value = "S";

}

else

{

dataGridView1->Columns[j]->HeaderCell->Value = Convert::ToString(j+1);

}

}

if (i==0)

{

dataGridView1->Rows[i]->HeaderCell->Value = "I";

}

else

{

if (i==SizeMass-1)

{

dataGridView1->Rows[i]->HeaderCell->Value = "S";

}

else

{

dataGridView1->Rows[i]->HeaderCell->Value = Convert::ToString(i+1);

}

}

dataGridView1->Rows[i]->Cells[j]->Value = Mass[i][j];

}

}

}

private: void ShowGraph(int SizeMass) {

Graphics^ g = this->pictureBox1->CreateGraphics();

g->TextRenderingHint = System::Drawing::Text::TextRenderingHint::AntiAlias;

g->Clear(Color::White);

Brush^ Кисть = gcnew SolidBrush(Color::Red);

float Xc=371, Yc=201, A=311, B=141, e=sqrt(1-(pow(B,2)/pow(A,2))), Grad=180, Angle=Grad*M_PI/180, R=0, X=0, Y=0, Offset=0;

int **Coord = new int*[SizeMass];

for (int i=0; i<SizeMass; i++) {

Coord[i] = new int[2];

}

Offset=360/SizeMass;

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

{

if(i==0)

{

R=B/(sqrt(1-pow(e,2)*pow(cos(180*M_PI/180),2)));

X=R*cos(180*M_PI/180)+Xc;

Y=R*sin(180*M_PI/180)+Yc;

Coord[i][0]=X;

Coord[i][1]=Y;

Grad+=Offset;

Angle=Grad*M_PI/180;

g->DrawEllipse(gcnew Pen(Color::Red),Coord[i][0],Coord[i][1],3,1);

g->DrawString("I", Font, Кисть, Coord[i][0]-15,Coord[i][1]);

continue;

}

if(i==SizeMass-1)

{

R=B/(sqrt(1-pow(e,2)*pow(cos(0*M_PI/180),2)));

X=R*cos(0*M_PI/180)+Xc;

Y=R*sin(0*M_PI/180)+Yc;

Coord[i][0]=X;

Coord[i][1]=Y;

Grad+=Offset;

Angle=Grad*M_PI/180;

g->DrawEllipse(gcnew Pen(Color::Red),Coord[i][0],Coord[i][1],3,1);

g->DrawString("S", Font, Кисть, Coord[i][0]+15,Coord[i][1]);

continue;

}

if((i+1)%2==0)

{

R=B/(sqrt(1-pow(e,2)*pow(cos(Angle),2)));

X=R*cos(Angle)+Xc;

Y=R*sin(Angle)+Yc;

Coord[i][0]=X;

Coord[i][1]=Y;

g->DrawEllipse(gcnew Pen(Color::Red),Coord[i][0],Coord[i][1],3,1);

g->DrawString(System::Convert::ToString(i+1), Font, Кисть, Coord[i][0],Coord[i][1]-15);

}

else

{

Grad*=-1;

Angle=Grad*M_PI/180;

R=B/(sqrt(1-pow(e,2)*pow(cos(Angle),2)));

X=R*cos(Angle)+Xc;

Y=R*sin(Angle)+Yc;

Coord[i][0]=X;

Coord[i][1]=Y;

Grad*=-1;

Grad+=Offset;

Angle=Grad*M_PI/180;

g->DrawEllipse(gcnew Pen(Color::Red),Coord[i][0],Coord[i][1],3,1);

g->DrawString(System::Convert::ToString(i+1), Font, Кисть, Coord[i][0],Coord[i][1]+15);

}

}

Кисть = gcnew SolidBrush(Color::Green);

for (int i = 0; i<SizeMass; i++) {

for (int j = 0; j<SizeMass; j++) {

if (Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)> 0) {

g->DrawLine(gcnew Pen(Color::Black), Coord[i][0], Coord[i][1], Coord[j][0], Coord[j][1]);

Angle=atan2((float)(Coord[i][1]-Coord[j][1]),(float)(Coord[i][0]-Coord[j][0]));

if (Angle*180/M_PI<185&&Angle*180/M_PI>175) {

Xc=((Coord[j][0]-Coord[i][0])/2)-55+Coord[i][0];

Yc=((Coord[j][1]-Coord[i][1])/2)-20+Coord[i][1];

}

else {

if (-Angle*180/M_PI<95&&-Angle*180/M_PI>85) {

Xc=((Coord[j][0]-Coord[i][0])/2)-20+Coord[i][0];

Yc=((Coord[j][1]-Coord[i][1])/2)+55+Coord[i][1];

}

else {

Xc=((Coord[j][0]-Coord[i][0])/2)-20+Coord[i][0];

Yc=((Coord[j][1]-Coord[i][1])/2)-20+Coord[i][1];

}

}

g->DrawLine(gcnew Pen(Color::Black), Coord[j][0], Coord[j][1], Coord[j][0]+20*cos(Angle-(15*M_PI/180)), Coord[j][1]+20*sin(Angle-(15*M_PI/180)));

g->DrawLine(gcnew Pen(Color::Black), Coord[j][0], Coord[j][1], Coord[j][0]+20*cos(Angle+(15*M_PI/180)), Coord[j][1]+20*sin(Angle+(15*M_PI/180)));

g->DrawString(System::Convert::ToString(dataGridView1->Rows[i]->Cells[j]->Value)+"/"+System::Convert::ToString(dataGridView1->Rows[j]->Cells[i]->Value), Font, Кисть, Xc,Yc);

}

}

}

for (int i=0; i < SizeMass; i++) {

delete [] Coord[i];

}

delete [] Coord;

}

private: System::Void Form1_Load(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void сгенерироватьМатрицуToolStripMenuItem_Click(System::Object^ sender, System::EventArgs^ e) {

button1->PerformClick();

}

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {

dataGridView1->ReadOnly=true;

int SizeMass = Convert::ToInt32(numericUpDown1->Value);

int **Mass=new int *[SizeMass];

for(int i=0; i<SizeMass; i++) {

Mass[i]=new int[SizeMass];

}

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

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

Mass[i][j]=0;

dataGridView1->ColumnCount = SizeMass;

dataGridView1->RowCount = SizeMass;

dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView1->AutoResizeColumns();

GenRand(Mass,SizeMass);

ShowMass(Mass,SizeMass);

for (int i=0; i < SizeMass; i++) {

delete [] Mass[i];

}

delete [] Mass;

}

private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) {

dataGridView1->ReadOnly=false;

int SizeMass = Convert::ToInt32(numericUpDown1->Value);

int **Mass=new int *[SizeMass];

for(int i=0; i<SizeMass; i++) {

Mass[i]=new int[SizeMass];

}

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

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

Mass[i][j]=0;

dataGridView1->ColumnCount = SizeMass;

dataGridView1->RowCount = SizeMass;

dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView1->AutoResizeColumns();

ShowMass(Mass,SizeMass);

for (int i=0; i < SizeMass; i++) {

delete [] Mass[i];

}

delete [] Mass;

}

private: System::Void label1_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e) {

int SizeMass = dataGridView1->Rows->Count;

if (SizeMass==0) {

MessageBox::Show("Отсутствует граф для вывода!","Ошибка");

return;

}

ShowGraph(SizeMass);

}

private: System::Void button4_Click(System::Object^ sender, System::EventArgs^ e) {

int SizeMass = dataGridView1->Rows->Count;

for (int i = 0; i<SizeMass; i++) {

for (int j = 0; j<SizeMass; j++) {

c[i][j] = 0;

c[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

NUM_VERTICES = SizeMass;

source = 0;

target = (dataGridView1->Rows->Count)-1;

textBox1->Text = System::Convert::ToString(MaxFlow(source, target));

}

private: System::Void dataGridView1_CellEndEdit(System::Object^ sender, System::Windows::Forms::DataGridViewCellEventArgs^ e) {

int q,n;

if(!Int32::TryParse(Convert::ToString(dataGridView1->CurrentCell->Value),q)) {

MessageBox::Show("Матрица может состоять только из цифр!","Ошибка");

dataGridView1->CurrentCell->Value="0";

}

if((dataGridView1->CurrentRow->Index == dataGridView1->CurrentCell->ColumnIndex)&&(dataGridView1->CurrentCell->Value != "0")){

MessageBox::Show("Данная программа не предназначена для работы с петлями!","Ошибка");

dataGridView1->CurrentCell->Value="0";

}

}

private: System::Void numericUpDown2_ValueChanged(System::Object^ sender, System::EventArgs^ e) {

if ((Convert::ToInt32(numericUpDown2->Value)>(Convert::ToInt32(numericUpDown3->Value)))) {

MessageBox::Show("Превышение максимального значения!","Ошибка");

numericUpDown2->Value--;

}

}

private: System::Void numericUpDown3_ValueChanged(System::Object^ sender, System::EventArgs^ e) {

if ((Convert::ToInt32(numericUpDown2->Value)>(Convert::ToInt32(numericUpDown3->Value)))) {

numericUpDown2->Value=numericUpDown3->Value;

}

}

private: System::Void textBox1_TextChanged(System::Object^ sender, System::EventArgs^ e) {

}

};

}

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

...