Разработка и реализация графического редактора сетей Петри
Аннотация
В данной курсовой работе был разработан и реализован графический редактор
сетей Петри. Программа позволяет создавать новые сети путем добавления позиций
и переходов, соединяя их определенным образом. Вершины и ребра графа сети Петри
можно перемещать по области построения, а также удалять, редактировать и
копировать. Была разработана xml схема, описывающая структуру xml файла,
получающегося в результате сохранения построенной сети Петри. Данная схема
позволяет феривицировать xml файл при загрузке уже построенной сети, что
исключает ошибки, если входной файл имеет неправильную структуру. Программа
написана на языке Java, поэтому ее можно запускать как в ОС Windows, так и в Linux и др. платформах, на которых
установлена JVM.
Содержание
Введение
Постановка
задачи
Архитектура
программы, основные алгоритмы и структуры данных- диаграммы
Инструкция
пользователя
Заключение
Список
литературы
Введение
Среди большого числа понятий, которые возникли и исследуются в
кибернетике и информатике, одним из наиболее общих является понятие дискретной
динамической системы. Примерами дискретных систем могут служить ЭВМ, их
элементы и устройства, сети ЭВМ, системы сбора и автоматической обработки
цифровой информации и т.п. Изучение свойств дискретных систем и развитие
методов их конструирования проводится с помощью различных математических
моделей и методов в зависимости от класса систем, степени детализации их
структуры и свойств, а также от характера исследуемых проблем.
По мере усложнения дискретных систем все большее внимание привлекают
«неалгоритмические» параллельные системы с недетерминированным поведением, в
котором отдельные компоненты функционируют, в основном, независимо,
взаимодействуя друг с другом время от времени. Системы с параллельно
функционирующими и асинхронно взаимодействующими компонентами не описываются в
терминах классической теории автоматов. Такие фундаментальные понятия, как
состояния автомата и глобальная функция перехода, не удобны для наглядной и
экономной характеризации недетерминированной динамики поведения систем с
локальными связями между независимыми параллельными процессами.
Среди многих существующих методов описания и анализа дискретных
параллельных систем выделился подход, который основан на использовании сетевых
моделей, предложенных Карлом Петри для моделирования асинхронных информационных
потоков в системах преобразования данных.
В настоящее время сети Петри становятся все более актуальными, так как
применяются при решении многих задач, таких как:
§ моделирование множества взаимосвязанных и параллельных процессов;
§ моделирование работы телефонной системы и исследования ее свойств, при
этом исходными данными являются протоколы взаимодействия абонентов в
телекоммуникационной сети;
§ разработка параллельных графических объектно-ориентированных средств
программирования;
§ разработка ПО центров дистанционного управления и контроля.
То есть, сети Петри применяются для описания и исследования динамических
систем.
На практике такие системы очень сложны, часто велики, включают множество
взаимодействующих компонент. Каждая компонента также может быть очень сложной,
поскольку взаимодействует с другими компонентами системы.
Таким образом, чтобы снизить трудоемкость проектных работ, уменьшить
вероятность ошибок, повысить техническую эффективность проектируемых устройств
и систем за счет оперативного анализа вариантов проектных решений
проектировщику желательно иметь удобный инструмент. В качестве такого
инструмента может выступать графический редактор сетей Петри, разработка и
реализация которого является целью данной курсовой работы.
Структура сети Петри
Сеть Петри определяется как четверка <Р, Т, I, О>, где Р и Т -
конечные множества позиций и переходов, I и О - множества входных и выходных
функций. Другими словами, сеть Петри представляет собой двудольный
ориентированный граф, в котором позициям соответствуют вершины, изображаемые
кружками, а переходам - вершины, изображаемые утолщенными черточками; функциям
I соответствуют дуги, направленные от позиций к переходам, а функциям О - от
переходов к позициям.
|
|
|
Рис. 1. Пример
сети Петри
|
В сетях Петри вводятся объекты двух типов: динамические - изображаются
метками (маркерами) внутри позиций и статические - им соответствуют вершины
сети Петри. Распределение маркеров по позициям называют маркировкой. Маркеры
могут перемещаться в сети. Каждое изменение маркировки называют событием,
причем каждое событие связано с определенным переходом. Считается, что события
происходят мгновенно и разновременно при выполнении некоторых условий. Каждому
условию в сети Петри соответствует определенная позиция. Совершению события
соответствует срабатывание (возбуждение или запуск) перехода, при котором
маркеры из входных позиций этого перехода перемещаются в выходные позиции.
|
 
|
|
Рис. 2. Распределение
маркеров по позициям перед срабатыванием (слева) и после (справа)
|
Последовательность событий образует моделируемый процесс. Правила
срабатывания переходов (рис. 2) конкретизируют следующим образом: переход
срабатывает, если для каждой из его входных позиций выполняется условие N, >
Kt , где N, - число маркеров в i-й
входной позиции, К, - число дуг, идущих от i-и позиции к переходу; при срабатывании перехода число маркеров
в i-й входной позиции уменьшается на К„
а в j-и выходной позиции увеличивается на
Мj , где Мj - число дуг, связывающих переход j-й позицией. На рис. 2 показан пример распределения маркеров
по позициям перед срабатыванием, эту маркировку записывают в виде (2, 2,3, 1).
После срабатывания перехода маркировка становится иной: (1,0,1,4).
Постановка
задачи
Наименование задачи
Разработка и реализация графического редактор сетей Петри
Назначение и цель
1. Программа должна иметь набор средств, позволяющих пользователю
нарисовать сеть Петри:
1.1. Добавление, редактирование и удаление вершин графа;
1.2. Добавление, редактирование и удаление ребер графа;
.3. Перемещение вершин и ребер.
2. Программа должна иметь возможность сохранять и загружать
построенные сети Петри в xml файл;
3. Программа должна обеспечивать функционирование сети, т.е.
выполнять разрешенные переходы;
. Программа должна осуществлять проверку вводимых пользователем
данных. Например, количества фишек вершины.
. Программа должна иметь интуитивный и понятный пользовательский
интерфейс.
Технические средства
Данная программа разработана в среде NetBeans 6.9.1 на языке
программирования java.
Минимально рекомендуемые требования для работы с программой приведены в
таблице:
Таблица
|
Процессор
|
Частота не ниже 400
МГц
|
|
Оперативная память
|
128 Мб
|
|
Операционная система
|
Любая, на которой
установлена jvm
|
Входная и выходная информация
Входной информацией для программы являются данные полученные доступными
программно-техническими средствами, а также xml файлы полученные ранее в ходе работы с
программой.схема, описывающая структуру входного и выходного файлов:
Архитектура
программы, основные алгоритмы и структуры данных
Архитектура программы
Программа включает следующие классы:.java - класс, реализующий
пользовательский интерфейс программы..java - класс, описывающий уникальные
свойства вершины, как узла сети Петри..java - класс, содержащий размеры
перехода, а также метод отображающий переход в области построения сети..java -
класс, содержащий размеры позиции, а также метод отображающий переход в области
построения сети..java - класс, содержащий информацию о ребре графа сети Петри
(к каким вершинам ребро прилегает, координаты ребра и дополнительные
точки)..java - класс, содержащий методы для сохранения и загрузки сети
Петри.java - класс, содержащий информацию о названии вершины..java - класс,
отображающий дополнительные точки ребер графа..java - класс, реализующий
основные функции по созданию и редактированию сети Петри. Он отображает сеть
Петри в области построения и содержит данные обо всех вершинах и ребрах графа.
Основные структуры данных
Организация основных данных отображена на следующей диаграмме классов:
В программе все вершины являются объектами класса Vertex, а ребра - Edge. Вершины и ребра
хранятся в классе PanelPetri в виде хеш таблицы, для повышения быстродействия
программы. Ключами хеш таблицы являются уникальные идентификаторы вершин и
ребер, а значениями - объекты соответствующих классов. Названия вершин являются
объекты класса JLabel, которые также хранятся в классе PanelPetri, где ключами
являются идентификаторы вершин, а значениями - сами названия.
Основные алгоритмы
Основными алгоритмами являются:
§ добавление ребра между вершинами графа сети Петри;
|
|
|
Рис. 3. Алгоритм добавления
пользователем ребра между двумя вершинами
|
§ удаление выбранной пользователем вершины;
|
|
|
Рис. 4. Алгоритм удаление
выбранной вершины
|
|
§ удаление выбранного пользователем ребра;
|
|
|
Рис. 5. Удаление ребра
графа сети Петри
|
|
|
Рис. 6. Вставка элементов
графа, выделенной пользователем области
|
UML -
диаграммы
Диаграмма вариантов использования:
|
|
|
Рис. 7. Диаграмма вариантов
использования
|
Диаграмма деятельности:
|
|
|
Рис. 8. Диаграмма
деятельности
|
Краткое описание основных классов
Класс Vertex, описывающий общие для всех вершин
сети Петри свойства. Классы Position и
Transition наследуются от данного класса.class
Vertex extends JComponent {Integer vertexId; // id вершиныint marker; // Кол-во маркеров
/**
* Количество ребер исходящих из вершины( ключ- в какую вершину направлено
ребро, значение -сколько ребер)
*/HashMap<Integer, Integer> outVertex;ArrayList<Integer>
edgeIdLst; // id ребер, прилегающих к вершинеString label; // Название вершиныfloat scale = 1.0f; // масштаб float lnTkns; // Толщина
линии при отрисовки элемента
private Integer copyVertexId = null;
//Создать новую вершинуVertex(Integer vertexId, int marker,
String label, float scale) {….}void addMarker(int num) { this.marker += num;
}void subMarker(int num) { this.marker -= num; }
//Добавление прилегающего к вершине
ребраvoid addEdge(Integer
vertexId, int type, Integer edgeId) {
//ребро направлено из вершиныcount = outVertex.get(vertexId);(count == null)
{.put(vertexId, 1);
} else {++;.put(vertexId, count);
}.add(edgeId);
}
геттеры и сеттеры ….
Класс Edge, описывающий свойства ребра графа
сети Петри
public class Edge {Integer edgeId;// id ребра
private Integer inVertex; // id вершины
начала ребра
private Integer outVertex; // id вершины в которую направлено ребро
private LinkedList<Point2D.Double> point; // Координаты ребра
// создать новое реброEdge(Integer edgeId, Integer
inVertex, Integer outVertex, int type) {…}
геттеры и сеттеры ….
Класс PanelPetri, содержащий логику работы сети Петри и отображающий
элементы графа:
public class PanelPetri extends JPanel {
private SortedMap<Integer, Vertex> vertexMap; // Вершины графа
private HashMap<Integer, Edge> edgeMap; // Ребра графаHashMap<Integer,
JLabel> labelMap; // Надписи вершинInteger selEdgeId = null; // id выбранного ребраint nextVertexId = 1; // Id следующей вершиныint nextPositionInd = 1;
// индекс следующей позицииint nextTransitionInd = 1;
// индекс следующего переходаint nextEdgeId = 1; // Id следующего ребраJComponent current = null; // текущий выбранный элемент
//Последовательность точек панели на которые нажимал пользователь
private LinkedList<Point> curPLst = new
LinkedList<Point>();
/**
* Последовательность из двух точек.
* Первая откуда, вторая куда пользователь переместил элемент
*/LinkedList<Point> moveP = new
LinkedList<Point>();
/**
* точки, которые отмечает пользоваль, чтобы провести ребро
*/Point _p1;Point _p2;
/**
* Точки прямоугольника, который выбрал пользователь
*/
private Point rectUser1;Point rectUser2;
/**
* Создать новую сеть Петри
*/void newPetriNet(){…}
/**
* Установить кол-во фишек и надпись для выбранной позиции или
* установить надпись для выбранного перехода
*/
public void setFieldsV() {…}
/**
* Удалить выбранный элемент
*/void deleteSelected() {…}
/**
* Осуществить переход
*/
public void step() {…}
/**
* Занести id выделенных вершин в буфер для последующей вставки
*/
public void copyVertex() {…}
/**
* Вставить выделенные вершины
*/void pasteVertex() {…}
/**
* Пользователь выбрал вершину
* @return левая нижняя точка выбранной вершины
*/Point2D.Double changeCurrent(Object selectedValue) {…}
/**
* Загрузить из xml
файл
* @param in
*/void loadFromXml(File in) {…}
/**
* Сохранить в xml файл
* @param out
*/void saveToXml(File out) {…}
дополнительные private методы для работы программы …
}
Инструкция
пользователя
Для работы в программе необходимо запустить файл PetriNet.java
|
|
|
Рис. 9. Интерфейс программы
|
Как видно из рисунка выше, интерфейс программы состоит из следующих
элементов:
§ главное меню;
§ панель инструментов;
§ панель редактирования свойств вершины;
§ список вершин;
§ область построения сети Петри.
Главное меню содержит пункты, показанные на следующих рисунке:
|
  
|
|
Рис. 10. Пункты главного
меню
|
При открытии файла или сохранение созданной сети открывается диалоговое
окно выбора xml файла:
|
 
|
|
Рис. 11. Диалоговые окна
открытия и сохранения сети Петри
|
Назначение кнопок панели инструментов:
|
|
Переключиться в режим
выбора элементов сети Петри
|
|
|
Переключиться в режим
добавления позиции
|
|
|
Переключиться в режим
добавления перехода
|
|
|
Переключиться в режим
добавления ребра
|
Горячие клавиши программы:
§ Ctrl+O - открыть созданную ранее сеть Петри;
§ Ctrl+S - сохранить созданную сеть Петри;
§ Ctrl+N - создать новую сеть Петри;
§ Ctrl+D - удалить выбранный(ые) элемент(ы) сети Петри;
§ S - выполнить разрешенные переходы.
При создании сети Петри необходимо переключиться в нужный режим,
переместить курсор мыши в область построения и нажать левую кнопку мыши. В
результате чего, будет добавлена вершина. Для соединения двух вершин нужно
переключиться в режим добавления ребра, щелкнуть по первой вершине и удерживая
левую кнопку мыши указать вторую. Если проведенное ребро «допустимо», то будет
добавлено новое ребро, прилегающее к указанным вершинам. При добавлении позиции
курсор, автоматически перемещается в поле ввода кол-ва фишек, а при добавлении
перехода - в поле ввода надписи. После изменения параметров вершины, достаточно
нажать клавишу Enter, чтобы изменения вступили в силу.
|
|
|
Рис. 12. Создание сети
Петри.
|
Вершины и ребра графа можно перемещать мышью по области построения. Ребра
графа могут принимать форму ломаной прямой, для этого необходимо в нужном месте
ребра 2 раза щелкнуть мышью, чтобы добавить дополнительную точку ребра.
|
|
|
.
|
Для копирования необходимо выделить отметить прямоугольную область и
нажать сочетание клавиш Ctrl+C, для вставки из буфера обмена - Ctrl+V.
|
 
|
|
Рис. 13. Копирование и
вставка элементов сети Петри.
|
При выборе из списка вершин названия вершины в области построения
автоматически отмечается выбранная вершина.
Заключение
В ходе выполнения курсовой работы, мной были рассмотрены и изучены основы
построения сетей Петри. В соответствии с поставленной задачей была создана
программа - графический редактор. Были изучены основы построения систем
автоматизационного проектирования. Разработка данной программы показала, что
при увеличении типов данных, которые хранятся не как поля соответствующих
классов, а как отдельные структуры сложность алгоритмов программы, вероятность
допустить ошибку по невнимательности программиста, и объем используемой
программой памяти повышается. Но данным методом можно увеличить скорость работы
программы. Поэтому необходимо находить компромисс между этими двумя
параметрами.
Таблица. Количество строк кода:
|
Имя класса
|
Назначение
|
Кол-во строк
|
|
Edge.java
|
Ребро графа
|
55
|
|
Position.java
|
Позиция
|
167
|
|
Transition.java
|
Переход
|
44
|
|
Vertex.java
|
Вершина графа
|
119
|
|
LabelVertex.java
|
19
|
|
PanelPetri.java
|
Область построения сети
Петри
|
1162
|
|
PanelPointEdge.java
|
Дополнительная точка ребра
|
39
|
|
XmlIO.java
|
Методы для загрузки и
сохранения в xml файл
|
62
|
|
PetriNetAboutBox.java
|
Окно дополнительной
информации
|
139
|
|
PetriNetApp.java
|
Основной класс программы
|
16
|
|
PetriNetView.java
|
Интерфейс программы
|
690
|
|
Итого:
|
|
2512
|
графический
редактор сеть петри
Список
литературы
1. Норенков
И.П. Основы автоматизированного проектирования: Учеб. для вузов. 2-е изд.,
перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 336 с. ил. - (Сер.
Информатика в техническом университете).
2. Котов
В.Е. Сети Петри - М.: Наука. Главная редакция физико-математической литературы.
1984. -160 с.
. Питерсон
Дж. Теория сетей Петри и моделирование систем - М.: Мир, 1984. - 264 с., ил.
. А.А.
ВОЕВОДА, Д.В. ПРЫТКОВ. О применении сетей Петри в процессе
объектно-ориентированного анализа и проектирования. Сборник научных трудов
НГТУ. - 2009. - № 4(58). - 131-138.
. Д.О.
Саркенов. Применение сетей Петри при разработке протоколов. Ползуновский
альманах №3, 2007г., ст 82,83.
. Кей
С. Хорстманн, Гари Корнел. Java 2.
Библиотека профессионала. Том 1. Основы, 8-е издание.: Пер. с англ. - М.: ООО
«И.Д. Вильямс», 2009. - 816 с. : ил. - Парал. тит. англ.
. Кей
С. Хорстманн, Гари Корнел. Java 2.
Библиотека профессионала. Том 2. Тонкости программирования, 7-е издание.: Пер.
с англ. - М.: ООО «И.Д. Вильямс», 2007. - 1168 с. : ил. - Парал. тит. англ.
Похожие работы на - Разработка и реализация графического редактора сетей Петри
|