Алгоритм объединения частей ориентированного графа
Ключевые слова:
графы, программное обеспечение, алгоритмы, объединение графов, разрез графа, разрезающее множествоАннотация
Рассматривается задача объединения графов с общей частью, которые были получены в результате серии моделирований сети Петри с использованием программного пакета 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.
Опубликован
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).
