Practical Realization of Algorithm of Oriented Graph Paths Decomposition



This study aims to clarify the methodological status program realization of oriented graph paths decomposition. Algorithms of matrix formulation of decomposition table M from multitude of paths, table sorting by NΣ and balance computing explored. On the basis of those algorithms and original algorithm of oriented graph paths decomposition realized Python 3 program. Results for random-generated graph size of 100 vertices computed and time measured. The results obtained can be used to solve the problem of organizing freight rail transportation at the stage of assignment and movement of locomotives. The scientifi c and practical novelty of the work lies in a signifi cant reduction in the dimension of the original problem, which is especially important in the conditions of transport networks of complex topology.

General Information

Keywords: optimization theory, graph optimization, algorithm of directed graph paths decomposition, strongly connected graph, subgraphs

Journal rubric: Optimization Methods

Article type: scientific article


For citation: Zolotarev I.A., Rasskazova V.A. Practical Realization of Algorithm of Oriented Graph Paths Decomposition. Modelirovanie i analiz dannikh = Modelling and Data Analysis, 2020. Vol. 10, no. 3, pp. 60–68. DOI: 10.17759/mda.2020100305. (In Russ., аbstr. in Engl.)


  1. Gainanov D.N., Konygin A.V., Rasskazova V.A. Modelling railway freight traffi c using the methods of graph theory and combinatorial optimization. Automation and Remote Control, 2016 vol. 77, no. 11, pp. 1928–1943.
  2. Gainanov D.N., Kibzun A.I., Rasskazova V.A. Theoretical-graph algorithm in the problem on the assignments and transportations of locomotives. Herald of computer and information technologies, 2017, no. 5, pp. 51–56.
  3. Gainanov D.N., Kibzun A.I., Rasskazova V.A. The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application. Automation and Remote Control, 2018, vol. 79, no. 12, pp. 2217–2236.

Information About the Authors

Igor A. Zolotarev, Master's Student, Moscow Aviation Institute (NRU MAI), Moscow, Russia, ORCID:, e-mail:

Varvara A. Rasskazova, PhD in Physics and Matematics, Associate Professor of Department 804 "Probability Theory and Computer Modeling", Moscow Aviation Institute, (NRU MAI), Moscow, Russia, ORCID:, e-mail:



Total: 214
Previous month: 8
Current month: 6


Total: 78
Previous month: 4
Current month: 2