Алгоритм объединения частей ориентированного графа
Ключевые слова:
графы, программное обеспечение, алгоритмы, объединение графов, разрез графа, разрезающее множествоАннотация
Рассматривается задача объединения графов с общей частью, которые были получены в результате серии моделирований сети Петри с использованием программного пакета Colored Petri Nets Tools, в котором адресное пространство процесса ограничено 232 байтами, начиная с различных вершин и при различных начальных условиях. Для ее решения необходимо определить общую часть графов, выполнить разрез таким образом, чтобы их общая часть осталась только в одном из начальных графов, и составить таблицу соответствия (переходов) между вершинами графов для возможности осуществления переходов между ними. Изначально предполагается, что графы представлены в виде списков смежности, но в процессе работы алгоритма они преобразовываются в хеш-таблицы для быстрого определения общей части графов, которое реализуется при помощи обхода одного из графов и проверки наличия вершин во втором. Составление таблицы переходов между графами осуществляется при помощи обхода графа по парам «родительская-дочерняя» вершины, в ходе которого проверяются условия добавления узлов в таблицу переходов. Предлагается алгоритм решения задачи объединения частей ориентированного графа и приведен пример его использования.Литература
1. Орлов С.А. Технология разработки программного обеспечения // Питер. 2012. 609 с.
2. Islam S., Krinke J., Binkley D., Harman M. Coherent clusters in source code // The Journal of Systems and Software. 2014. vol. 88. pp. 1–24.
3. Burgstaller B., Scholz B., Blieberger J. A symbolic analysis framework for static analysis of imperative programming languages // The Journal of Systems and Software. 2012. vol. 85. pp. 1418–1439.
4. Аветисян А. И. Современные методы статического и динамического анализа программ для автоматизации процессов повышения качества программного обеспечения: дисс. доктора физ. мат. наук // Москва: 2012. 271 с.
5. Clarke E.M., O. Grumberg, D. Peled. Model Checking // The MIT Press. 1999. 330 p.
6. Шудрак М.О., Золотарев В.В. Модель, алгоритмы и программный комплекс автоматизированного поиска уязвимостей в исполняемом коде // Труды СПИИРАН. 2015. Вып. 42. C. 212–231.
7. Романников Д.О. Разработка программного обеспечения с применением UML диаграмм и сетей Петри для систем управления локальным оборудованием дисс. канд. техн. наук // Новосибирск: 2012. 195 с.
8. Коротиков С.В. Применение сетей Петри в разработке программного обеспечения центров дистанционного контроля и управления: дисс. канд. техн. наук // Новосибирск: 2007. 216 с.
9. Марков А.В. Aвтоматизация проектированияи анализа программного обеспечения с использованием языка UML и сетей Петри: дисс. канд. техн. наук // Новосибирск: 2015. 176 с.
10. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms: 3rd Edition // The MIT Press. 2009. 1328 p.
11. Even S. Graph Algorithms: 2nd Edition // Cambridge University Press. 2011. 187 p.
12. Tarjan R. Data Structures and Network Algorithms // Society for Industrial and Applied Mathematics. 1983.
13. Sedgewick R. Algorithms in C++: 3rd Edition // Addison-Wesley Professional. 1998. 752 p.
14. Goldberg A., Tardos E., Tarjan R. Network flow algorithms // Springer. 1990. pp. 101–164.
15. Schhrijver A. Paths and flows – A historical survey // CWI Quarterly. 1993. pp. 169–183.
16. Марков, А.В., Воевода А.А. Анализ сетей Петри при помощи деревьев достижимости // Сб. науч. тр. НГТУ. 2013. №. 71. C. 78–95.
2. Islam S., Krinke J., Binkley D., Harman M. Coherent clusters in source code // The Journal of Systems and Software. 2014. vol. 88. pp. 1–24.
3. Burgstaller B., Scholz B., Blieberger J. A symbolic analysis framework for static analysis of imperative programming languages // The Journal of Systems and Software. 2012. vol. 85. pp. 1418–1439.
4. Аветисян А. И. Современные методы статического и динамического анализа программ для автоматизации процессов повышения качества программного обеспечения: дисс. доктора физ. мат. наук // Москва: 2012. 271 с.
5. Clarke E.M., O. Grumberg, D. Peled. Model Checking // The MIT Press. 1999. 330 p.
6. Шудрак М.О., Золотарев В.В. Модель, алгоритмы и программный комплекс автоматизированного поиска уязвимостей в исполняемом коде // Труды СПИИРАН. 2015. Вып. 42. C. 212–231.
7. Романников Д.О. Разработка программного обеспечения с применением UML диаграмм и сетей Петри для систем управления локальным оборудованием дисс. канд. техн. наук // Новосибирск: 2012. 195 с.
8. Коротиков С.В. Применение сетей Петри в разработке программного обеспечения центров дистанционного контроля и управления: дисс. канд. техн. наук // Новосибирск: 2007. 216 с.
9. Марков А.В. Aвтоматизация проектированияи анализа программного обеспечения с использованием языка UML и сетей Петри: дисс. канд. техн. наук // Новосибирск: 2015. 176 с.
10. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms: 3rd Edition // The MIT Press. 2009. 1328 p.
11. Even S. Graph Algorithms: 2nd Edition // Cambridge University Press. 2011. 187 p.
12. Tarjan R. Data Structures and Network Algorithms // Society for Industrial and Applied Mathematics. 1983.
13. Sedgewick R. Algorithms in C++: 3rd Edition // Addison-Wesley Professional. 1998. 752 p.
14. Goldberg A., Tardos E., Tarjan R. Network flow algorithms // Springer. 1990. pp. 101–164.
15. Schhrijver A. Paths and flows – A historical survey // CWI Quarterly. 1993. pp. 169–183.
16. Марков, А.В., Воевода А.А. Анализ сетей Петри при помощи деревьев достижимости // Сб. науч. тр. НГТУ. 2013. №. 71. C. 78–95.
Algorithm for Union of Oriented Graph Parts
Abstract
In the paper, we consider a task of uniting graphs with a common part. The graphs were received as the result of series of simulations of a Petri net using a program package Colored Petri Nets Tools, where a process address space is restricted by 232 bytes starting from different vertices and with different initial conditions. To solve this task, it is necessary to determine the graphs common part, to perform graphs cutting in such a way that their common part remains in only one of the initial graphs, and compose a table of accordance (transitions) between the graphs vertices for making transitions between them. Firstly, we assume that the graphs are represented in the form of adjacency lists. During algorithm’s work they are converted into hash tables for fast determination of the common part of the graphs that is implemented with the help of traversing one of the graphs and testing for the presence of nodes in the second graph. A transition table is created with the help of graph traversal by “parents-child” vertex pairs, during which it is checked whether one of the nodes of a pair can be added to the table. The algorithm for solving the problem of uniting the parts of a di-rected graph is offered, and an example of its use is given.
Опубликован
2015-11-25
Как цитировать
Романников, Д. О., & Воевода, А. А. (2015). Алгоритм объединения частей ориентированного графа. Труды СПИИРАН, 6(43), 83-93. https://doi.org/10.15622/sp.43.5
Раздел
Теоретическая и прикладная математика
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
