Выделение общей части в версиях исходного кода программ, представленного графовой моделью

Аннотация: Решение задач анализа структурного сходства объектов на основе применения графовых моделей (ГМ) является одним из актуальных направлений исследований в прикладной теории графов. В статье в качестве объектов для анализа сходства рассматриваются версии исходного кода программ. Существующие системы управления версиями (СУВ) при решении данной задачи работают непосредственно с текстами исходных кодов версий программ. Наделение СУВ возможностью работать с ГМ, адекватно представляющими исходный код версий программ, позволяет существенно улучшить качество выполнения традиционных функций СУВ и расширить инструментарий по сопровождению процесса разработки программ. Оценивать сходство версий программ предлагается на основе выделения в них наибольшей общей части, т.е. наибольшего общего подграфа. Цель исследований заключается в разработке метода решения задачи выделения наибольшей общей части в версиях программ, представленных в виде ГМ. Исследования базируются на применении предложенной автором теории дифференциации вершин графа, в которой модель структуры графа представляется в виде сети автоматов. Важным преимуществом метода является его способность легко адаптироваться к особенностям написания исходного кода программы и используемой версии языка программирования. Метод включает три этапа – составление и кодирование списков атрибутов, приписанных вершинам и дугам ГМ; преобразование ГМ в стандартную форму в виде ориентированного графа; выделение общей части в двух ориентированных графах, представляющих сравниваемые версии программы. Алгоритм выделения общей части, работая со стандартными формами представления ГМ, является инвариантным относительно особенностей описания ГМ и набора используемых атрибутов. Приводится пример решения задачи выделения общей части для двух сравниваемых фрагментов ГМ.

Ключевые слова: графовая модель программы, система управления версиями, общая часть двух графов, подстановка сходства графов, дифференциация вершин графов

Библиография статьи: Погребной А. В. Выделение общей части в версиях исходного кода программ, представленного графовой моделью / А. В. Погребной // Доклады ТУСУР. – 2018. – Т. 21, № 3. – С. 49–56. DOI: 10.21293/1818-0442-2018-21-3-49-56