Article

Article title LOCALIZATION OF THE GRAPH NODES FOR TASKS OF REPRESENTING THE MANAGED OBJECTS
Authors N. E. Sergeev, E. R. Muntyan
Section SECTION III. MODELING OF COMPLEX SYSTEMS
Month, Year 07, 2017 @en
Index UDC 004.421+519.178
DOI
Abstract In case of use of graph models for displaying objects appears the problem of the correct graph representation. Considered is a visual and logical representation of multiple views of the same graph: the initial graph, bipartite graph and graph with vertex position along the contour. The necessity of fixation of the graph nodes location was shown not only when it is displayed, but also when represented. To solve this problem, recommended is the way to represent a graph indi-cating the logical relationship between the nodes, their relative positions and indicated are the points of intersection of the graph edges. Developed are the step-by-step rules representing the graph in the form of lists, providing for the recording of the nodes based on their visual locations. To fix the visual images of the situation nodes proposed is their presentation in the form of ordered lists taking into account the graph"s topology based on the concepts about the rotation of the graph nodes. Moreover, we recommend consideration of the localization areas of each node. Localization area of the node is the area of allowable movement of the node that do not lead to formation of new intersections of the edges. Illustrated is the possibility of transformation the original image of the graph to the desired form by moving the nodes within its areas of localization. To fix the intersections of the edges it is offered to mark the intersection points of the graph edges as the nodes with a special status, for example as the newly formed. It is shown that such nodes can be used in any way of the graph representation, both in the form of matrices and lists.

Download PDF

Keywords Graph; situation; control; list; presentation; location; visualization; topology; cross.
References 1. Kurapov S.V., Chechenya V.S. Topologicheskie metody postroeniya risunka grafa [Topological methods for the construction of the pattern graph], Радіоелектроніка, інформатика, управління [Electronics, Informatics, control], 2013, No. 1, pp. 72-81.
2. Kurapov S.V., Davidovskiy M.V. Proverka planarnosti i postroenie topologicheskogo risunka ploskogo grafa (poiskom v glubinu) [Check planarnot and the construction of topological flat drawing of the graph (depth first search], Prikladnaya diskretnaya matematika [Applied discrete mathematics], 2016, No. 2 (32), pp. 100-114.
3. Baburin D.E. Ierarkhicheskiy podkhod dlya avtomaticheskogo razmeshcheniya atsiklicheskikh grafov [Hierarchical approach to automatic placement directed acyclic graphs], Sovremennye problemy konstruirovaniya program [Modern problems of constructing programs]. Novosi-birsk: ISI SO RAN, 2002, pp. 7-37.
4. Apanovich Z.V. Metody navigatsii pri vizualizatsii grafov [Methods of navigation in visualization of graphs], Vestnik NGU. Seriya Informatsionnye tekhnologii [Novosibirsk State University Journal of Information Technologies], 2008, Vol. 6, No. 3, pp. 35-47.
5. Vasil'ev Yu.M., Fridman G.M. Vizualizatsiya kooperativnykh skhem: gibridnyy evristicheskiy algoritm dlya minimizatsii kolichestva peresecheniy reber pri ukladke grafa [Visualization of cooperative schemes: a hybrid heuristic algorithm to minimize the number of crossings of edges when laying the graph], Izvestiya Sankt-Peterburgskogo gosudarstvennogo ekonomicheskogo universiteta [Izvestiâ Sankt-Peterburgskogo gosudarstvennogo èkonomičeskogo universiteta], 2017, No. 1-2 (103), pp. 87-93.
6. Sergeev N.E., Muntyan E.R., Tselykh A.A., Samoylov A.N. Obobshchenie grafov situatsiy na osnove spiskovogo algoritma svertki dlya zadach situatsionnogo upravleniya [Situation graph generalization for situation awareness using a list-based folding algorithm], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 3 (188), pp. 111-121.
7. Ore O. Teoriya grafov [Graph theory]. Moscow: Nauka, 1968, 352 p.
8. Foster Dzh. Obrabotka spiskov [Processing lists]. Moscow: Mir, 1974, 72 p.
9. Kormen T., Leyzerson Ch., Rivest R. Algoritmy. Postroenie i analiz [Algorithms. The construc-tion and analysis]. Moscow: MTsNMO, 2000, 960 p.
10. Mukha Yu.P., Sekachev V.A. Algoritm dlya opredeleniya vozmozhnosti nalozheniya napravlennykh grafov [Algorithm to determine the possibility of imposition of directed graphs], Izvestiya VolgTGU [Izvestia VSTU], 2014, Vol. 9, No. 10 (137), pp. 87-97.
11. Sergeev N.E., Tselykh A.A. Nechetkie teoretiko-grafovye podkhody k modelirovaniyu i analizu sotsiosemanticheskikh setey znaniy dlya zadach prinyatiya resheniy v nauchnoy i nauchno-tekhnicheskoy ekspertize [Fuzzy-theoretic graph approaches to modeling and analysis socioemotional networks of knowledge for decision-making problems in the scientific and technical expertise], Politematicheskiy setevoy elektronnyy nauchnyy zhurnal Kubanskogo gosudarstvennogo agrarnogo universiteta [Polythematic network electronic scientific journal of the Kuban state agrarian University], 2016, No. 09 (123), pp. 1-21. Available at: http://ej.kubagro.ru/2016/09/pdf/27.pdf.
12. Emelichev V.A. Diskretnaya optimizatsiya. Posledovatel'nye skhemy resheniya. II [Discrete optimization. Sequential schemes of solution. II], Kibernetika [Cybernetics], 1972, No. 2,
pp. 109-121.
13. Himsolt M. GraphEd: a graphical platform for the implementation of graph algorithms, Lect. Notes Comput. Sci., 1994, Vol. 894, pp. 182-193.
14. Sugiyama K., Missue K. A generic compound graph visualizer/manipulator: D-ABSTRUCTOR, Lect. Notes Comput. Sci., 1995, Vol. 1027, pp. 500-503.
15. Gasner E.R., North S.C., Vo K.P. DAG – a program that draws directad graph, Software – Practice and Experience, 1998, Vol. 18, No. 1, pp. 1047-1062.
16. Kristofides N. Teoriya grafov. Algoritmicheskiy podkhod [Graph theory. Algorithmic ap-proach]. Moscow: Mir, 1978, 432 p.
17. Tselykh A.A. Grafogipergrafovaya model' sementicheskoy sotsial'noy seti [Graph-hypergraph model of a semantic social network], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 4 (129), pp. 225-229.
18. Sergeev N.E., Tselykh Yu.A. GH-modeli sotsial'nykh setey [GH-models of social networks] Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009,
No. 1 (90), pp. 90-95.
19. Tselykh A.N., Kotov E.M., Tselykh A.A. Metod informatsionnogo poiska na osnove nechetkogo skhodstva situatsiy [Method of information retrieval based on a fuzzy similarity of situations], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 6 (155), pp. 74-78.
20. Tselykh A.A. Metod raspoznavaniya izomorfnogo vlozheniya nechetkikh grafov na osnove nechetkogo mnozhestva klik [Recognition method investments isomorphic fuzzy graphs, based on fuzzy sets click], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2008, No. 4 (81), pp. 129-132.
21. Sergeev N.E., Tselykh A.A., Tselykh A.N. Generalized approach to modeling user activity graphs for network security and public safety monitoring, SIN 2013 – Proceedings of the 6th International Conference on Security of Information and Networks, 2013, pp. 117-122.

Comments are closed.