УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

АЛГОРИТМЫ УКЛАДКИ ДИАГРАММ СОСТОЯНИЙ

© 2007, М.А. Коротков

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Полный текст работы
Библиотека укладки диаграмм состояний как часть проекта UniMod

Программный пакет с открытым исходным кодом UniMod обеспечивает разработку и выполнение автоматно-ориентированных программ. Он позволяет создавать и редактировать диаграммы классов и состояний UML, которые соответствуют графу переходов и схеме связей конечного автомата. После создания диаграмм существует возможность выполнить их. При этом содержимое диаграмм преобразуется в XML-описание, которое передается интерпретатору, также входящему в рассматриваемый пакет. Разработанный пакет базируется на парадигме автоматного программирования.

Во многих современных редакторах для текстовых языков программирования существует возможность автоматического форматирования программного кода. В случае если программным кодом является не текст, а набор диаграмм, задача форматирования текста преобразуется в задачу укладки диаграмм. В рамках проекта UniMod основной интерес представляет укладка диаграмм состояний языка UML. Этой задаче посвящена данная работа.

Постановка задачи. При укладке диаграммы необходимо учитывать ряд критериев, которые могут противоречить друг другу, например, такие как минимизация площади, занимаемой диаграммой, и наличие достаточного количества свободного места ("воздуха"). Такие критерии называются эстетиками. Задавшись некоторым набором эстетик, можно построить штрафную функцию (которая тем больше, чем больше расхождения между изображением диаграммы и критериями), и пытаться минимизировать её, перемещая элементы, или разработать алгоритм, последовательно модифицирующий исходную диаграмму так, чтобы результат соответствовал выбранным критериям.

Практические результаты. В работе приведен краткий обзор существующих решений в данной области, Дан обзор двух групп алгоритмов построения укладки: алгоритмов с физическим аналогом и аналитических алгоритмов.

Разработаны и описаны два алгоритма укладки диаграмм состояний UML, принадлежащие к различным семействам алгоритмов укладки. Первый алгоритм - метод отжига с применением ортогонализации, второй - разработанный автором алгоритм QMATH-STATECHART, базирующийся на одном из известных алгоритмов ортогональной укладки и адаптированный для работы с диаграммами состояний.

Моделирование и верификация потоков данных на диаграммах состояний