Надіслати статтю
вул. Інститутська 11, м. Хмельницький, 29016
visnyk.khnu@khmnu.edu.ua
(0382) 67-51-08

ПРОГРАМНИЙ КОМПЛЕКС ДЛЯ ВІЗУАЛІЗАЦІЇ АЛГОРИТМІВ НА ГРАФАХ

SOFTWARE COMPLEX FOR GRAPH ALGORITHMS VISUALIZATION

 Сторінки: 81-85. Номер: №6, 2021 (303) 
Автори:
ЛАВРЕНЧУК С. В.
Луцький національний технічний університет
ORCID ID: 0000-0002-5453-3924
lavrsveet@gmail.com
ЗДОЛБІЦЬКА Н. В.
Луцький національний технічний університет
ORCID ID: 0000-0002-1345-3581
ninazdolb@gmail.com
ХАМУЛА Н. М.
Луцький національний технічний університет
nadya.synuyk0907@gmail.com
Svitlana LAVRENCHUK, Nina ZDOLBITSKA, Nadiia KHAMULA
Lutsk National Technical University
DOI: https://www.doi.org/10.31891/2307-5732-2021-303-6-81-85
Рецензія/Peer review : 08.11.2021 р.
Надрукована/Printed : 30.12.2021 р.

Анотація мовою оригіналу

Розглянуто алгоритми на графах, що представлені за допомогою різних структур даних. Програмний комплекс має модульний web-інтерфейс. Реалізовано представлення графа як множини вершин у вигляді пронумерованих кругів та зв’язків між ними (графічне зображення); за допомогою динамічних зв’язаних списків (списки суміжності); у вигляді матриці суміжності. Користувачі даного проекту мають змогу інтерактивно впливати та спостерігати за покроковим виконанням алгоритмів на графах, що дасть змогу набути дослідницьких навичок та компетентностей в області використання дискретних структур.
Ключові слова: граф, дискретні структури, візуалізація, способи подання графа, програмний комплекс, алгоритм Прима, алгоритм Дейкстри, алгоритм Крускала, алгоритм Флойда, пошук вглиб, пошук вшир.

Розширена анотація англійською мовою

Algorithms on graphs represented by graphical structures are offered. The software complex has a modular web interface. A representative graph is implemented as a set of vertices in the form of numbered circles and links between them (graphic image); using dynamically linked lists (adjacency lists); using an adjacency matrix. The project of this project allows the use of interactive algorithms for step-by-step calculations and algorithms on graphical images to obtain the necessary research results and competencies in the use of discrete structures. The project was implemented using HTML, CSS, JavaScript, which allows visualizing the application and interactively working with algorithms on graphs represented by different data structures. Graphics File Algorithm Programming provides web-based and interactive algorithms created by the used DHTML itself, creating a software project in the form of a site. Each page is dedicated to a separate algorithm and structurally consists of a header, container, footer. The website design uses HTML and cascading CSS stylesheets, to create an interactive parsing process and to transform methods in graphic files – based on JavaScript, which allows third-party scripts to be processed and rendered. The user can vibrate the image type (for orientation), the number of nodes, the presentation method, generate this graph, indicate the starting point for starting the search algorithm, observe the operational operation of the algorithm. The user can adjust the animation speed. The development of a set of programs is meant for interactive demonstration and visualization of the operation of algorithms in the study of graph theory.
Keywords: graph, discrete structures, visualization, methods of graph representation, software complex, Prim’s algorithm, Dijkstra’s algorithm, Kruskal’s algorithm, Floyd’s algorithm, depth search, breadth search.

References

  1. Kuzmenko I. M. Teoriia hrafiv : navchalnyi posibnyk dlia zdobuvachiv stupenia bakalavra za spetsialnistiu 122 «Kompiuterni nauky» [Elektronnyi resurs] / Ihor Mykolaiovych Kuzmenko. – KPI im. Ihoria Sikorskoho, 2020. – Rezhym dostupu : https://ela.kpi.ua/handle/123456789/35854.
  2. Shevchenko H. V. Dyskretna matematyka : navchalno-metodychnyi posibnyk. / H. V. Shevchenko, V. V. Shkapa. – Kyiv : DUT, 2018. – 158 s.
  3. Ostapiuk Z. V. Zastosuvannia hrafiv dlia vidobrazhennia zhyttievoho tsyklu sutnostei pid chas rozroblennia systemy opratsiuvannia vidhukiv bezposerednikh korystuvachiv prohramnykh produktiv / Z. V. Ostapiuk, T. O. Korotieieva // Naukovyi visnyk NLTU Ukrainy. – 2019. –29, № 9. – S. 147–152.
  4. Ryshkovets Yu. V. Alhorytmizatsiia ta prohramuvannia. Chastyna 2: navchalnyi posibnyk / Yu. V. Ryshkovets, V. A. Vysotska. – Lviv : Novyi Svit-2000, 2020. – 320 s.
  5. Sholom P. S. Proportsiino-intehralno-dyferentsialne upravlinnia stabilnistiu rukhu mobilnoho ahenta 3pi po zadanii traiektorii / P. Sholom, N. V. Zdolbitska // Kompiuterno-intehrovani tekhnolohii: osvita, nauka, vyrobnytstvo : mizhvuzivskyi zbirnyk. – Lutsk : Vydavnytstvo LNTU, 2012. – № 8. – S. 125–129.
  6. Sholom P. S. Analiz alhorytmiv obkhodu hrafa dlia zadachi trasuvannia marshrutu / P. S. Sholom, N. V. Zdolbitska // Kompiuterno-intehrovani tekhnolohii: osvita, nauka, vyrobnytstvo : mizhvuzivskyi zbirnyk. – Lutsk : Vydavnytstvo LNTU, 2011. – № 3. – S. 204–207.
  7. Lavrenchuk S. V. Doslidzhennia tekhnolohii obrobky pryrodnoi movy ta mashynnoho navchannia pry stvorenni chat-bot zasobamy Python / S. V. Lavrenchuk, R. S. Iliushyk. // Kompiuterno-intehrovani tekhnolohii: osvita, nauka, vyrobnytstvo : mizhvuzivskyi zbirnyk. – Lutsk : Vydavnytstvo LNTU. – 2019. – № 37. – S. 36–42.
  8. Graph Theory Towards New Graphical Passwords In Information Networks [Elektronnyi resurs] / [Y. Bing, S. Hui, W. Hongyu ta in.]. – 2018. – Rezhym dostupu : https://arxiv.org/abs/1806.02929.
  9. Borysenko I. I. Zastosuvannia teorii hrafiv v zadachakh stvorennia stehanohrafichnykh povidomlen / I. I. Borysenko // Suchasna spetsialna tekhnika. – 2015. – № 2. – S. 26–33.
  10. Zhyharevych O. K. Metody ta zasoby proektuvannia ta rozrobky systemy optymizatsii transportnykh marshrutiv / O. K. Zhyharevych // Kompiuterno-intehrovani tekhnolohii: osvita, nauka, vyrobnytstvo : mizhvuzivskyi zbirnyk. – Lutsk : Vydavnytstvo LNTU, 2013. – № 11. – S.16–23.
  11. Optimal Transport for structured data with application on graphs [Elektronnyi resurs] / [T. Vayer, L. Chapel, R. Flamary ta in.]. – 2019. – Rezhym dostupu : https://arxiv.org/abs/1805.09114.
  12. Biziuk A. V. Zastosuvannia teorii hrafiv do analizu strukturno-lohichnoi skhemy navchalnoho planu / A. V. Biziuk, V. P. Tkachenko, V. Biziuk // Tezy dopovidei IV mizhnarodnoi naukovo-tekhnichnoi konferentsii «Polihrafichni, multymediini ta web-tekhnolohii» (PMW-2019), 14–17 travnia 2019 r., Kharkiv. – Kharkiv : Drukarnia Madryd, 2019. – S. 238-239.
  13. Bobrytska H. S. Prykladne zastosuvannia teorii hrafiv u riznykh sferakh zhyttia suspilstva ta okremoi osobystosti / H. S. Bobrytska // Fizyko-matematychna osvita: naukovyi zhurnal. – 2017. – № 3. – S. 26–30.
  14. Novozhylova L. M. Modelyrovanye hrafamy dyskretnыkh system y protses sov : uchebnoe posobye / L. M. Novozhylova. – SPb : SPbHU, 2017. – 16 s.
  15. Graph Builder [Elektronnyi resurs]. – Rezhym dostupu : https://www.softportal.com/software-19403-graph-builder.html
  16. Obzor MaxFlow [Elektronnyi resurs]. – Rezhym dostupu : https://soft.mydiv.net/win/download-MaxFlow.html
  17. Grafoanalizator [Elektronnyi resurs]. – Rezhym dostupu : https://sourceforge.net/projects/grafoanalizator/
  18. Graph Magics [Elektronnyi resurs]. – Rezhym dostupu : http://www.graph-magics.com/

Post Author: Горященко Сергій

Translate