# Presentation: 640679

## eCGE (Enhanced PetriNet Graphical Editor) : A Multi-Platform Petri Net Editor

- eCGE (Enhanced PetriNet Graphical Editor) : A Multi-Platform Petri Net Editor

- 15 April 2005
- David Dugan

## Overview

- Role of Petri Nets in software development and testing
- How CGE implements Stochastic Petri Nets
- History of CGE and how eCGE enhances capability
- Design of eCGE
- Test Cases
- Future plans and conclusion

## Verification of design requirements

- Through formal testing or simulation of the environment
- Very costly and time consuming
- Difficult to go thru all possible execution paths
- Difficult to simulate timing problems
- Does not catch problems until well into coding phase
- Performance modeling though a special graphical language formalism
- Temporal specifications for time-critical systems
- Probabilistic specifications to describe selection among different possible events
- Performance modeling through graphics

## Petri Nets - Graphical Modeling of Critical Timing Applications

- Flow charts, block diagrams, state diagrams do not show timing or probability of events
- Firing time in Petri Nets is the delay time before a transition can take place
- Immediate (Deterministic) – Fixed delay time
- Timed (Stochastic) – Random or asynchronous time

## eCGE Benefits

- eCGE provides a graphical means to specify a Stochastic Petri Net Model to model the dynamic as well as static aspects
- Output of eCGE can be input into the Stochastic Petri Net Package to obtain numerical results for the model using Markov analysis

## eCGE Goals

- Model a system quickly and inexpensively
- Produce a tool that does not require extensive training
- Be able to use the model to communicate to customers

## CGE Background

- Original work by Norb Gravelle proof of concept that CSPL coding language can be generated from a graphical interface instead of a text editor
- Work by Wen Wei extended this tool to include graphical layout algorithms
- Spring Algorithm
- Tree Algorithm

## eCGE Components

| Component | Language | GUI Framework | Design Methodology | OS Supported |
| --- | --- | --- | --- | --- |
| Original CGE | C++ | MS Visual Studios | procedural | MS Windows |
| CSPL parser | C++ | N/A – command line application | object-oriented | any |
| Spring and Tree Algorithms | C++ | N/A – selected by a menu item | procedural | any |
| Enhanced CGE | Java | AWT / Swing | object-oriented | any supporting Java 1.4 |

## My Contribution

- Combined work by Gravelle, Wei, and CSPL parser into a single application
- Added parser to import CSPL files
- Designed the application using object-oriented analysis and design techniques for future enhancements
- Designed an interface for future development of graph layout algorithms
- Added a Random graph layout algorithm

## CSPL (C Based Stochastic Petri-net language)

- Specification language for Stochastic Petri Net package - CSPL - can be used to specify complex system behaviors with Petri nets
- CSPL Conversion Process
- Reads in CSPL file to determine elements and attributes of model
- CGE Language adds graphical information for each model element

## Enhancements to CGE I

- Ability to read in a CSPL file and display it graphically
- Edit and display an imported CSPL file
- Parameters for a model are input through dialog boxes
- Specify the properties of a place, transition, or arc
- Interface for defining guard function
- Read and save a model in CGE format

## Enhancements to CGE II

- Consistency checking of parameters insures a syntactically correct model
- Improved maintainability of design through complete redesign of code based on object oriented design
- Rewrote all code in JAVA to enhance portability to other platforms
- Added a Random Graph Layout Algorithm

## CGE Evolution

**First Iteration**

**Second Iteration**

## CGE Evolution

**Third Iteration**

**Fourth Iteration**

## eCGE Design

- Redesign  and integration of legacy CGE components into eCGE
- Gravelle’s Original CGE
- Wen Wei Graphical Layout algorithms
- CSPL parser
- Used Object Oriented Design to integrate these components into a single application

## Legacy Design Approach

## eCGE Classes

- High-Level Class Chart for eCGE
- An appendix in the thesis describes the design and implementation details
- Class charts
- Design and implementation details of key components

## Case Studies

- Case # 1 - Connected Cyclic Reliability (CCR) model for the anti-lock braking system
- Analyzed the mean time to failure for the braking system of a vehicle
- Case # 2 - How the layout affects understanding and finding problems in a Petri net model (race condition).

## Case Study # 1 – CCR Model

- Model input from CSPL language and translated into CGL language
- Layout (Spring and Tree) algorithms proved inadequate to handle the reformatting of graphical layout of a complex model
- eCGE requires further enhancements to resolve the layout of complex models, as shown in the following figures.

## Layout using Random Algorithm Method

- Applying the Random Algorithm results in this arrangement.

## Layout using Manual Methods

- Manually laying out the elements provides a more readable layout.

## Case Study 2

- The use of layout is important in understanding the structure of a model and detecting potential problems
- Types of possible problems:
- Conflict
- Confusion (analogous to a race condition)

## Example of how a race condition “conflict” can be in Petri Net 

- p = places, t = transitions, 1 = tokens
- Figures 3a and 3b represent confusion as to which path program will take based on which token fires first

## CSPL Code for prior example of conflict (race condition)

- The following segment shows the equivalent CSPL code for the previous example
- The textual version shows the elements, but not the graphical structure, of the model

## Future Enhancements of eCGE

- Enhance graph layout algorithms to handle more complex structures
- Be able to import and translate other Petri Net modeling tools file formats
- Add a scroll bar to document window to increase work space
- Be able to group elements to move them
- Incorporate an algorithm to minimize arc crossings (such as the various *graphviz* layout algorithms, see http://www.graphviz.org/ )

## Conclusions I

- eCGE has integrated a number of separate programs which represent a foundation for using Stochastic Petri Nets in industry
- Mechanizing and simplifying the development of a model by using a graphical, rather than textual, interface
- Being able to visualize time critical events via the Petri net diagrammatic language using eCGE facilities and layout algorithms
- Including visualization of a large library of legacy (textually based) CSPL models

## Conclusions II

- Increased maintainability of the code using object-oriented design makes it easier to further enhance the application
- Made programs/components of CGE platform independent through use of JAVA to encourage usage on a variety of platforms

## Questions & Answer Session

- Mr. Dugan has a severe speaking disability (WSU has certified) and for the purposes of the defense we asked him to write the answers to the committee’s questions.

## Ordinary Petri Net

- A biparte graph that consists of
- A set of Places
- A set of Transitions
- A set of directed Arcs
- Arcs connect Places to Transitions
- Input Arc - Directed Arc from Place to Transition
- Output Arc - Directed Arc from Transition to Place

## Ordinary Petri Net Formal Definition

- PN = (P,T,A)
- P= {p1, p2,....p(n)}
- T= {t1,t2,....t(m)}
- A = {a1, a2, ..., a(o)} - arcs

## Generalized Stochastic Petri Net (GSPN)

- Time is associated with Transition
- Transitions are immediate and timed
- Immediate - Fire immediately when enabled and the logical structure is modeled, but not the timing
- Timed -Fire after a random,exponentially distributed enabling time
- Example of timed - A finite time delay until a hardware device is ready to accept the command before issuing it
- Timed - Used with devices that cannot respond at the program execution rate
- Example of Immediate - Usual case in programming where transitions are made at the same rate as program execution

## Markings

- Tangible - Only timed transitions are enabled in a marking
- Vanishing - At least one immediate transition is enabled in a marking. May be removed in the analysis to reduce time and space complexity
- Absorbing
- Applies to a place which has no output Arcs
- Transition firing adds a token to this place
- However, the token can no longer be used to enable a transition

## Consistency Checking

- Drawing Window
- Shows an error message for an illegal operation
- For example, conecting a place to a place
- Dialogue Boxes
- Grays out boxes or input fields(allows operator no input) if operation is illegal or undefined
- Example - Transition Dialogue Box cannot have a Guard Function if no functions have been defined

## Spring Algorithm

- Places and transitions are like weights on springs
- Starts from the first arc
- Simulates a mechanical system consisting of springs (arcs) and nodes (places and transitions).  From the initial configuration or ring positions, the system oscillates until it stabilizes at a minimum-energy configuration.  It has been noted that in such a configuration, all the edges typically have relatively uniform length and nodes not connected tend to be far apart.

## Tree Algorithm

- The goal of this algorithm is to produce a graph that is planar, straight-lined, and upward (that is, a ‘parent’ node is above its ‘children’).  Vertices at the same level are horizontally aligned.  The first place in the place list is chosen to be the root of the tree.
- 	The space (vertical distance) between each level is uniform.
- 	The separation distance between two consecutive vertices on the same level is kept to a minimum.
- 	The overall width of the graph is as small as possible and still be readable.

## Other ways of laying out graphs

- Reference Article: Empirical Layout of Aesthetics-based Graph Layout by Purchase, Carrington, and Allder
- Planar Grid Drawing Algorithm
- Force Directed Algorithm
- Goals of Graph layout program
- Minimize edge crossings
- Orthogonality
- Information Flow (connected nodes should be close together)
- Minimize edge bends

## Weaknesses of Graphical Approaches

- Reference Article: Empirical Layout of Aesthetics-based Graph Layout by Purchase, Carrington, and Allder
- No one type of layout works for every graph
- Graph layout requires a significant computational power
- History of the flow chart
- How to show a large graph in a drawing window:
- Add scroll bars
- Re-size the model (zoom in and out)

## Understanding

- A graphical representation of a Petri Net tends to be at a higher level of abstraction than a textual representation
- affects response time
- Easier to see errors
- Shows the structure of the model

## Extensibility

- Interface for graph layout algorihm described in section A.3 of thesis
- Adding a graph layout algorithms requires the following steps:
- Create a new subroutine containing the implementation (class document_class)
- Add a new menu item in the Algorithms menu bar (class algorithms_menu)
- Add code so that when the menu item is selected, the correct subroutine is called (affects classes document_manager, document_internal_frame, and document_panel)

## Ease of Use

- Goal is to minimize the amount of effort required to use the tool such as
- Minimizing keystrokes
- Logically organizing the layout of dialog boxes

## OO Design Maintainability

- The system architecture uses fine grained, self contained components that can readily be changed
- Avoids shared data structures and global variables (minimizes data coupling)
- Each class is self-contained - all relevant operations and data are contained within the class