ПРОГРАММНОЕ СРЕДСТВО РЕАЛИЗАЦИИ АЛГОРИТМА «ФЛОЙ-ДА–УОРШЕЛА». Итог курсового проекта. Программное средство реализации алгоритма флойдауоршела
Скачать 1.65 Mb.
|
ЗаключениеОсновной задачей данной курсового проектирования являлась применение полученных знаний и создание посредством полученных знаний визуализатор алгоритма «Флойда-Уоршелла», которое необходимо для демонстрации пользователя работы алгоритма, а так же возможность применять его в поставленных задачах. Данный алгоритм имеет огромное использование у компаний как по разработке программного обеспечения, так и у организаций, занимающихся сопровождением и программной разработкой различных веб-ресурсов. В ходе курсового проектирования: была определена и изучена предметная область задачи; рассмотрены аналоги разрабатываемого приложения, определены их недостатки и преимущества, которые будут учтены при разработке программного средства; определены функциональные требования и требования к пользовательскому интерфейсу; описаны алгоритмы решения задачи; разработаны диаграммы вариантов использования и деятельности для описания разрабатываемого программного средства. описаны разработанные модуля программного средства, разработанные классы и их методы. произведено написание тест-кейсов разработанного приложения, благодаря которым было выявлено некорректное поведение программного средства. После тестирования было проведено исправление некорректного поведения программного средства; описан процесс установки и руководство пользователя; создана и оформлена пояснительная записка. В процессе реализации, тестирования и документирования программного средства были получены знания и опыт в сфере алгоритмизации. Был получен опыт работы с Windows Forms, языками программирования C#, также была освоена дополнительная литература, что повышает уровень знаний и понимания данного языка программирования. Были изучены множество объектов формы и их свойства, инструменты, предоставляемые платформам и логика их работы. Были получены навыки разработки программного обеспечения с использованием шаблонов проектирования и различных паттернов. Использованные технологии пользуются популярностью в сфере разработки программного обеспечения и часто используются при разработке программных средств в больших компаниях, специализирующихся на разработке программного обеспечения. Список использованных источниковЛитература Кнут Д.Э. – Искусство программирования. Том 1.Основные алгоритмы, 3-е издание, 2019 – Москва: издательство «Вильямс» – 720 с. Куликов С.С. – Тестирование программного обеспечения. Базовый курс. 2-е издание, 2017 – Минск: издательство «Четыре четверти» – 314 с. Интернет-ресурсы Веб-визуализатор – [Электронный ресурс]. – Режим доступа: Floyd-Warshall All-Pairs Shortest Path. Дата доступа: 25.03.2022. Описание алгоритма Флойда-Уоршелла – [Электронный ресурс]. – Режим доступа: https://studfile.net/preview/1673132/page:2/. Дата доступа: 25.03.2022. Аналог – [Электронный ресурс]. – Режим доступа: https://поискслов.рф. Дата доступа: 25.03.2022. Справочник по построению диаграмм – [Электронный ресурс]. – Режим доступа: https://ami.nstu.ru. Дата доступа: 29.03.2022. Справочник по построению диаграмм – [Электронный ресурс]. – Режим доступа: https://itteach.ru. Дата доступа: 19.04.2022. Справочник по построению диаграмм – [Электронный ресурс]. – Режим доступа: https://anylogic.ru. Дата доступа: 19.04.2022. Операторный язык – [Электронный ресурс]. – Режим доступа: https:/otus.ru. Дата доступа: 19.04.2022. Интерфейс – [Электронный ресурс]. – Режим доступа: https://kartaslov.ru. Дата доступа: 25.03.2022. Пользовательский интерфейс – [Электронный ресурс]. – Режим доступа: https://internet-technologies.ru. Дата доступа: 19.04.2022. Исследование рынка операционных систем – [Электронный ресурс]. – Режим доступа: https://www.comss.ru. Дата доступа: 19.04.2022. Язык программирования C# – [Электронный ресурс]. – Режим доступа: https://forum.itvdn.com. Дата доступа: 19.04.2022. Веб-сайт «The Floyd-Warshall Algorithm» – [Электронный сайт.] – Режим доступа:https://algorithms.discrete.ma.tum.de/graph-algorithms/spp-floyd-warshall/index_en.html. Дата: 17.06.2022 Приложение А(обязательное) Текст программы Файл AccountController.cs: using System; using System.Drawing; using System.Windows.Forms; namespace Y2VisualGraph { public partial class Form1 : Form { private const string FILENAME = "data.bin"; public Form1() { InitializeComponent(); this.Text = Application.ProductName + " " + Application.ProductVersion; foreach (ToolStripItem item in toolStrip1.Items) { item.Click += new EventHandler(toolStripButton_Click); } toolStripButton_Click(toolStripButton2, null); } protected override void OnLoad(EventArgs e) { GraphData data= graphUI1.LoadGraph(FILENAME); cboFrom.SelectedIndex=data.FormNode; cboTo.SelectedIndex=data.ToNode; chkUndirectedGrapth.Checked=data.IsUndirectedGraph; base.OnShown(e); } protected override void OnClosing(System.ComponentModel.CancelEventArgs e) { graphUI1.SaveGraph(FILENAME,cboFrom.SelectedIndex,cboTo.SelectedIndex); base.OnClosing(e); } protected override bool ProcessDialogKey(Keys keyData) { switch(keyData) { case Keys.Delete: graphUI1.DeleteSelectedNode(); break; case Keys.D1: toolStripButton_Click(toolStripButton1,null); break; case Keys.D2: toolStripButton_Click(toolStripButton2,null); break; case Keys.D3: toolStripButton_Click(toolStripButton3,null); break; case Keys.D4: toolStripButton_Click(toolStripButton4,null); break; default: break; } return base.ProcessDialogKey(keyData); } private void button1_Click(object sender, EventArgs e) { if (!String.IsNullOrEmpty(cboFrom.Text) && !String.IsNullOrEmpty(cboTo.Text)) graphUI1.FindShortestPath(cboFrom.Text[0] - 'A', cboTo.Text[0] - 'A'); } private void button2_Click(object sender, EventArgs e) { graphUI1.Reset(); } void chkUndirectedGrapth_CheckedChanged(object sender, EventArgs e) { graphUI1.IsUndirectedGraph = chkUndirectedGrapth.Checked; } private void graphUI1_SelectedNodeChanged(object sender, EventArgs e) { groupBox1.Enabled = sender != null; } private void btnDeleteNode_Click(object sender, EventArgs e) { graphUI1.DeleteSelectedNode(); } private void btnChangeNodeColor_Click(object sender, EventArgs e) { Node node = graphUI1.SelectedNode; if (node == null) return; ColorDialog dlg = new ColorDialog(); dlg.Color = node.BackColor; if (dlg.ShowDialog() == DialogResult.OK) { Color c = dlg.Color; //MessageBox.Show(Color.Black.GetBrightness().ToString()+" " + Color.White.GetBrightness().ToString()); node.BackColor = c; node.ForeColor = Color.FromArgb(255 - c.R, 255 - c.G, 255 - c.B); if (Math.Abs(c.ToArgb() - node.ForeColor.ToArgb()) < 100000) { node.ForeColor = Color.Black; } } } private void btnDeleteLastestEdge_Click(object sender, EventArgs e) { graphUI1.DeleteLastestEdge(); } private void btnClearEdge_Click(object sender, EventArgs e) { graphUI1.ClearEdges(); } private void toolStripButton_Click(object sender, EventArgs e) { ToolStripButton btn = (ToolStripButton)sender; DrawingTools tool = (DrawingTools)(int.Parse(btn.Tag.ToString())); graphUI1.Tool = tool; foreach (ToolStripButton item in toolStrip1.Items) { item.Checked = false; } btn.Checked = true; } private void graphUI1_ContentChanged(object sender, EventArgs e) { int f = cboFrom.SelectedIndex; int t = cboTo.SelectedIndex; cboFrom.DataSource = graphUI1.NodeNames; cboTo.DataSource = graphUI1.NodeNames; if (cboFrom.Items.Count > f) cboFrom.SelectedIndex = f; if (cboTo.Items.Count > t) cboTo.SelectedIndex = t; } } } Файл Edge.cs: using System; using System.Collections.Generic; using System.Drawing; using System.Text; namespace Y2VisualGraph { [Serializable] class EdgeCollection : IEnumerable { List public int SelectedIndex { get; set; } public Edge SelectedItem { get { return _list[this.SelectedIndex]; } } public EdgeCollection() { _list = new List } public bool Add(Edge edge) { if (!_list.Contains(edge)) { Edge newEdge = new Edge(edge.End, edge.Start); if (_list.Contains(newEdge)) { edge = _list[_list.IndexOf(newEdge)]; edge.IsUndirected = true; } else { _list.Add(edge); } return true; } return false; } public void Clear() { _list.Clear(); } public bool Contains(Edge edge) { return _list.Contains(edge); } public Edge this[int index] { get { return _list[index]; } } public bool Contains(Edge edge, bool checkInverted) { if (_list.Contains(edge)) return true; if (checkInverted) return _list.Contains(new Edge(edge.End, edge.Start)); return false; } public void RemoveAt(int index) { System.Threading.Thread.Sleep(100); _list.RemoveAt(index); } public int Count { get { return _list.Count; } } public IEnumerator { return _list.GetEnumerator(); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return _list.GetEnumerator(); } } [Serializable] class Edge { private const float EPSILON = 2f; public int Start; public int End; public bool IsUndirected; public bool IsRemoving; public Edge(int start, int end) { this.Start = start; this.End = end; this.IsUndirected = false; } public static bool Contains(PointF start, PointF end, PointF p) { if (p.X < Math.Min(start.X, end.X) || p.X > Math.Max(start.X, end.X) || p.Y < Math.Min(start.Y, end.Y) || p.Y > Math.Max(start.Y, end.Y)) return false; var dx = end.X - start.X; var dy = end.Y - start.Y; var v1 = new Vector2D(dx, dy).Length; float cx = p.X - start.X; float cy = p.Y - start.Y; var v2 = new Vector2D(cx, cy).Length; var v3 = new Vector2D(p.X - end.X, p.Y - end.Y).Length; var pp = (v1 + v2 + v3) / 2; var s = Math.Sqrt(pp * (pp - v1) * (pp - v2) * (pp - v3)); var h = s * 2 / v1; Console.WriteLine(h); return h < EPSILON; } public override bool Equals(Object obj) { if (!(obj is Edge)) return false; Edge con = (Edge)obj; if (this.Start == con.Start && this.End == con.End) return true; if (this.IsUndirected && this.Start == con.End && this.End == con.Start) return true; return false; } public override int GetHashCode() { return Start ^ End; } } } |