3. Petri Nets
Petri nets are useful tools for modeling systems with control flow. In particular they aid in modeling systems with concurrency, and parallelism. A set of routines have been developed at UWO to serve as the basis for a manufacturing simulation. The routines will support a number of various Petri net functions. The basic operation of the Petri net may be simulated. As well the EOR transitions will also be modeled. An attempt has been made to add ‘colors’ to the tokens, but at the present there is insufficient information (i.e., no references) to verify the implementation.
The routines have been written in a user friendly way to allow simple application interface. Places and Transitions are specified with textual names. A brief theory of petri nets follows.
3.1 A Brief Outline of Petri Nets
There are four basic elements in a petri net; places, transitions, arcs, and tokens. If we are to think in terms of a factory, tokens are equivalent to work parts. Arcs are the paths the work will follow through the factory. Places are buffers where parts are stored temporarily, and transitions are equivalent to machines where the parts are used to make new parts.
The basic operation is that tokens are introduced to the network, and then transitions are fired in different orders, and thus tokens are created and destroyed at the transitions. The example below follows the petri net for a few cycles. The first figure shows the Petri Net with the initial markings.
The reader should note that there are a few interesting properties found in Petri nets.
Transitions are fired when all of their inputs are satisfied, and the user specifies that transition.
Most analysis of petri nets uses random firings of the transitions to obtain statistical performance.
Other basic references to the petri net theory are available in Peterson [1981] and Reisig [1985].
3.2 Using the Subroutines
3.2.1 Basic Petri Net Simulation
The subroutines are applied in a methodical manner. Before the user can integrate the subroutines into their program, they must draw out the petri net, and label all places and transitions. The example given above is illustrated below.
After these labels are determined, they are defined using the petri net subroutines. The arcs in the petri net are also defined in the program. There are defined with respect to the transitions. That is to say that an arc is an input to, or output from a transition. After the petri net structure has been defined, tokens may be placed in the places of the net. The tokens are as given in the previous example.
The transitions are then selectively fired in the net, by function calls in the program. This program also has calls to functions which print the petri net structure after each transition. The code is show below for the example above.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “global.h”
#include “petri.h”
int test1()
/*
* BASIC TEST NET (Peterson book, 1981, pg. 19)
*/
{
static int error;
static struct petri_net net;
static int p1, p2, p3, p4, p5;
static int t1, t2, t3, t4;
error = petri_init(&net);
p1 = petri_place(&net, “p1”);
p2 = petri_place(&net, “p2”);
p3 = petri_place(&net, “p3”);
p4 = petri_place(&net, “p4”);
p5 = petri_place(&net, “p5”);
t1 = petri_transition(&net, “t1”);
t2 = petri_transition(&net, “t2”);
t3 = petri_transition(&net, “t3”);
t4 = petri_transition(&net, “t4”);
petri_input(&net, p1, t1, 1);
petri_input(&net, p2, t2, 1);
petri_input(&net, p3, t2, 1);
petri_input(&net, p4, t2, 1);
petri_input(&net, p4, t3, 1);
petri_input(&net, p4, t3, 1);
petri_input(&net, p5, t4, 1);
petri_output(&net, p2, t1, 1);
petri_output(&net, p3, t1, 1);
petri_output(&net, p4, t1, 1);
petri_output(&net, p4, t1, 1);
petri_output(&net, p2, t2, 1);
petri_output(&net, p5, t3, 1);
petri_output(&net, p3, t4, 1);
petri_output(&net, p4, t4, 1);
petri_add_tokens(&net, p1, 1);
petri_add_tokens(&net, p4, 2);
petri_add_tokens(&net, p5, 1);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
petri_event(&net, t1);
petri_print(&net);
petri_event(&net, t3);
petri_print(&net);
return error;
}
As can be seen this method of implementation is very simple. The user is able to define a number of nets, and refer to transitions and places by name.
3.2.2 Transitions With Inhibiting Inputs
In some cases we want to prevent a transition from firing. To do this, the idea of inhibiting inputs has been proposed. If a transition has an inhibiting input from a place, that has any tokens in it, then the transition cannot fire. Otherwise the transition may fire normally. A sample net has been devised for this case, it is seen below.
The program below shows that the inhibiting input is simply defined when the arc is defined.
int test2()
/*
* INHIBITED TEST NET (Peterson book, 1981, pg. 196)
*/
{
static int error;
static struct petri_net net;
static int p1, p2, p3, p4, p5, p6;
static int t1, t2, t3, t4;
error = petri_init(&net);
p1 = petri_place(&net, “p1”);
p2 = petri_place(&net, “p2”);
p3 = petri_place(&net, “p3”);
p4 = petri_place(&net, “p4”);
p5 = petri_place(&net, “p5”);
p6 = petri_place(&net, “p6”);
t1 = petri_transition(&net, “t1”);
t2 = petri_transition(&net, “t2”);
t3 = petri_transition(&net, “t3”);
t4 = petri_transition(&net, “t4”);
petri_input(&net, p1, t1, 1);
petri_input(&net, p2, t2, 1);
petri_input(&net, p3, t2, 1);
petri_input(&net, p5, t3, 1);
petri_input(&net, p3, t4, INHIBIT);
petri_input(&net, p4, t4, 1);
petri_input(&net, p6, t4, 1);
petri_output(&net, p1, t1, 1);
petri_output(&net, p3, t1, 1);
petri_output(&net, p2, t2, 1);
petri_output(&net, p4, t3, 1);
petri_output(&net, p5, t3, 1);
petri_output(&net, p6, t4, 1);
petri_add_tokens(&net, p1, 1);
petri_add_tokens(&net, p2, 1);
petri_add_tokens(&net, p5, 1);
petri_add_tokens(&net, p6, 1);
petri_print(&net);
petri_event(&net, t1);
petri_print(&net);
petri_event(&net, t3);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
petri_event(&net, t2);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
return error;
}
3.2.3 An Exclusive OR Transition:
The inhibitory inputs are complimentary to the exclusive or function. Thus another research proposed an Exclusive or transition which will fire when one (and only one) input is from a place with tokens. An example of a problem using this, a ring shift register was modeled. This net is modeled as shown below.
In this example the EOR transition is marked with a plus in a circle (at ‘t7’). When run, a token will appear in p1, p3, and p5 in a repeating cycle. The program to set this up is seen below.
int test3()
/*
* EOR TEST NET (Peterson book, 1981, discussed pg. 190)
* This is for a single bit shifter
*/
{
static int error;
static struct petri_net net;
static int p1, p2, p3, p4, p5, p6, p7, p8, p9, p10;
static int t1, t2, t3, t4, t5, t6, t7;
error = petri_init(&net);
p1 = petri_place(&net, “p1”);
p2 = petri_place(&net, “p2”);
p3 = petri_place(&net, “p3”);
p4 = petri_place(&net, “p4”);
p5 = petri_place(&net, “p5”);
p6 = petri_place(&net, “p6”);
p7 = petri_place(&net, “p7”);
p8 = petri_place(&net, “p8”);
p9 = petri_place(&net, “p9”);
p10 = petri_place(&net, “p10”);
t1 = petri_transition(&net, “t1”);
t2 = petri_transition(&net, “t2”);
t3 = petri_transition(&net, “t3”);
t4 = petri_transition(&net, “t4”);
t5 = petri_transition(&net, “t5”);
t6 = petri_transition(&net, “t6”);
t7 = petri_transition(&net, “t7”);
petri_input(&net, p6, t1, 1);
petri_input(&net, p7, t1, 1);
petri_input(&net, p2, t2, 1);
petri_input(&net, p7, t2, 1);
petri_input(&net, p4, t3, 1);
petri_input(&net, p7, t3, 1);
petri_input(&net, p1, t4, 1);
petri_input(&net, p3, t5, 1);
petri_input(&net, p5, t6, 1);
petri_input(&net, p8, t7, 1);
petri_input(&net, p9, t7, 1);
petri_input(&net, p10, t7, 1);
petri_output(&net, p1, t1, 1);
petri_output(&net, p3, t2, 1);
petri_output(&net, p5, t3, 1);
petri_output(&net, p2, t4, 1);
petri_output(&net, p8, t4, 1);
petri_output(&net, p4, t5, 1);
petri_output(&net, p9, t5, 1);
petri_output(&net, p6, t6, 1);
petri_output(&net, p10, t6, 1);
petri_output(&net, p7, t7, 1);
petri_type_transition(&net, t7, EOR);
petri_add_tokens(&net, p1, 1);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
petri_event(&net, t7);
petri_print(&net);
petri_event(&net, t2);
petri_print(&net);
petri_event(&net, t5);
petri_print(&net);
petri_event(&net, t7);
petri_print(&net);
petri_event(&net, t3);
petri_print(&net);
petri_event(&net, t6);
petri_print(&net);
petri_event(&net, t7);
petri_print(&net);
return error;
}
3.2.4 Colored Tokens
This section should be considered incorrect. The theory has not been found, although the approach should adhere to the concept. The concept is that each token may now have a color, and a second bit of private information. If a transition is specified to be colored, it will only fire if tokens of the specified color are available at the inputs. The subroutines will then require that the user supply a new set of instance information so that new tokens may be issued.
The net used has tokens of mixed colors in it, an is seen below.
The code is shown below. The reader should note that a second subroutine is used. This is done because there is a bit of code which would be repeated for each update of tokens at the transition.
int test4()
/*
* COLOR TEST NET (Assumed for now)
* Two consumers of different colors and one input. The instances of tokens
* are kept track of.
*/
{
static int error, i;
static struct petri_net net;
static int p1, p2, p3;
static int t1, t2;
static int color1 = 1, color2 = 2;
static int instance[20], instance_pnt;
error = petri_init(&net);
p1 = petri_place(&net, “p1”);
p2 = petri_place(&net, “p2”);
p3 = petri_place(&net, “p3”);
t1 = petri_transition(&net, “t1”);
t2 = petri_transition(&net, “t2”);
petri_input(&net, p1, t1, 1);
petri_input(&net, p3, t1, 1);
petri_input(&net, p2, t2, 1);
petri_input(&net, p3, t2, 1);
petri_output(&net, p1, t1, 1);
petri_output(&net, p2, t2, 1);
petri_type_transition(&net, t1, COLORED);
petri_type_transition(&net, t2, COLORED);
for(i = 0; i < 20; i++) instance[i] = i;
instance_pnt = 0;
petri_add_color_token(&net, p1, color1, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p2, color2, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p3, color1, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p3, color2, instance[instance_pnt]);
instance_pnt++;
petri_print(&net);
sub4(&net, t2, color1, instance, &instance_pnt);
petri_print(&net);
sub4(&net, t1, color1, instance, &instance_pnt);
petri_print(&net);
sub4(&net, t1, color1, instance, &instance_pnt);
petri_print(&net);
sub4(&net, t2, color2, instance, &instance_pnt);
petri_print(&net);
return error;
}
int sub4(net, transition, color, instance, instance_pnt)
struct petri_net *net;
int transition, color, *instance, *instance_pnt;
{
static int error, i, list[20], n, outputs;
error = ERROR;
if(petri_in_event(net, transition, color) == NO_ERROR){
if(petri_get_consumed(net, transition, &color, list, &n, &outputs) == NO_ERROR){
for(i = 0; i <= n; i++) instance[list[i]] = -1000;
if(petri_set_produced(net, transition, &(instance[*instance_pnt]),outputs) == NO_ERROR){
*instance_pnt += outputs;
error = petri_out_event(net, transition);
}
}
}
return error;
}
3.3 Relational Nets
Relational nets will use various firing rules for each transition. This is by far the most useful for varied manufacturing conditions. An example is seen below.
This may be seen in the fifth test subroutine in the program.
3.4 Software
At present there is one data structure used which holds structures for Places and for Transitions. Arc information is stored (redundantly) in both. These are defined when a Place or Transition number is requested for one that does not exist. Each place and transition have reference numbers, which are used by all other net functions.
The software is still undergoing development, and testing, thus a list of functions would be premature.
3.5 References
3.1 Peterson, J.L., “Petri Net Theory and the Modelling of Systems”, Prentice-Hall, Inc., N.J., U.S.A., 1981.
3.2 Reisig, W., “Petri Nets; An Introduction”, Springer-Verlag, 1985.
3.6 Programs
3.6.1 Test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "petri.h"
main(argc, argv)
int argc;
char **argv;
{
if(argc == 2){
if(argv[1][0] == '1') test1();
if(argv[1][0] == '2') test2();
if(argv[1][0] == '3') test3();
if(argv[1][0] == '4') test4();
if(argv[1][0] == '5') test5();
}
exit(0);
}
int test1()
/*
* BASIC TEST NET (Peterson book, 1981, pg. 21)
*/
{
static int error;
static struct petri_net net;
static int p1, p2, p3, p4, p5;
static int t1, t2, t3, t4;
error = petri_init(&net);
p1 = petri_place(&net, "p1");
p2 = petri_place(&net, "p2");
p3 = petri_place(&net, "p3");
p4 = petri_place(&net, "p4");
p5 = petri_place(&net, "p5");
t1 = petri_transition(&net, "t1");
t2 = petri_transition(&net, "t2");
t3 = petri_transition(&net, "t3");
t4 = petri_transition(&net, "t4");
petri_input(&net, p1, t1, 1, NO_COLOR, NO_RULE);
petri_input(&net, p2, t2, 1, NO_COLOR, NO_RULE);
petri_input(&net, p3, t2, 1, NO_COLOR, NO_RULE);
petri_input(&net, p4, t2, 1, NO_COLOR, NO_RULE);
petri_input(&net, p4, t3, 2, NO_COLOR, NO_RULE);
petri_input(&net, p5, t4, 1, NO_COLOR, NO_RULE);
petri_output(&net, t1, p2, 1, NO_COLOR, NO_RULE);
petri_output(&net, t1, p3, 1, NO_COLOR, NO_RULE);
petri_output(&net, t1, p4, 2, NO_COLOR, NO_RULE);
petri_output(&net, t2, p2, 1, NO_COLOR, NO_RULE);
petri_output(&net, t3, p5, 1, NO_COLOR, NO_RULE);
petri_output(&net, t4, p3, 1, NO_COLOR, NO_RULE);
petri_output(&net, t4, p4, 1, NO_COLOR, NO_RULE);
petri_add_tokens(&net, p1, 1);
petri_add_tokens(&net, p4, 2);
petri_add_tokens(&net, p5, 1);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
petri_event(&net, t1);
petri_print(&net);
petri_event(&net, t3);
petri_print(&net);
return error;
}
int test2()
/*
* INHIBITED TEST NET (Peterson book, 1981, pg. 196)
*/
{
static int error;
static struct petri_net net;
static int p1, p2, p3, p4, p5, p6;
static int t1, t2, t3, t4;
error = petri_init(&net);
p1 = petri_place(&net, "p1");
p2 = petri_place(&net, "p2");
p3 = petri_place(&net, "p3");
p4 = petri_place(&net, "p4");
p5 = petri_place(&net, "p5");
p6 = petri_place(&net, "p6");
t1 = petri_transition(&net, "t1");
t2 = petri_transition(&net, "t2");
t3 = petri_transition(&net, "t3");
t4 = petri_transition(&net, "t4");
petri_input(&net, p1, t1, 1, NO_COLOR, NO_RULE);
petri_input(&net, p2, t2, 1, NO_COLOR, NO_RULE);
petri_input(&net, p3, t2, 1, NO_COLOR, NO_RULE);
petri_input(&net, p5, t3, 1, NO_COLOR, NO_RULE);
petri_input(&net, p3, t4, INHIBIT, NO_COLOR, NO_RULE);
petri_input(&net, p4, t4, 1, NO_COLOR, NO_RULE);
petri_input(&net, p6, t4, 1, NO_COLOR, NO_RULE);
petri_output(&net, t1, p1, 1, NO_COLOR, NO_RULE);
petri_output(&net, t1, p3, 1, NO_COLOR, NO_RULE);
petri_output(&net, t2, p2, 1, NO_COLOR, NO_RULE);
petri_output(&net, t3, p4, 1, NO_COLOR, NO_RULE);
petri_output(&net, t3, p5, 1, NO_COLOR, NO_RULE);
petri_output(&net, t4, p6, 1, NO_COLOR, NO_RULE);
petri_add_tokens(&net, p1, 1);
petri_add_tokens(&net, p2, 1);
petri_add_tokens(&net, p5, 1);
petri_add_tokens(&net, p6, 1);
petri_print(&net);
petri_event(&net, t1);
petri_print(&net);
petri_event(&net, t3);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
petri_event(&net, t2);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
return error;
}
int test3()
/*
* EOR TEST NET (Peterson book, 1981, discussed pg. 190)
* This is for a single bit shifter
*/
{
static int error;
static struct petri_net net;
static int p1, p2, p3, p4, p5, p6, p7, p8, p9, p10;
static int t1, t2, t3, t4, t5, t6, t7;
error = petri_init(&net);
p1 = petri_place(&net, "p1");
p2 = petri_place(&net, "p2");
p3 = petri_place(&net, "p3");
p4 = petri_place(&net, "p4");
p5 = petri_place(&net, "p5");
p6 = petri_place(&net, "p6");
p7 = petri_place(&net, "p7");
p8 = petri_place(&net, "p8");
p9 = petri_place(&net, "p9");
p10 = petri_place(&net, "p10");
t1 = petri_transition(&net, "t1");
t2 = petri_transition(&net, "t2");
t3 = petri_transition(&net, "t3");
t4 = petri_transition(&net, "t4");
t5 = petri_transition(&net, "t5");
t6 = petri_transition(&net, "t6");
t7 = petri_transition(&net, "t7");
petri_input(&net, p6, t1, 1, NO_COLOR, NO_RULE);
petri_input(&net, p7, t1, 1, NO_COLOR, NO_RULE);
petri_input(&net, p2, t2, 1, NO_COLOR, NO_RULE);
petri_input(&net, p7, t2, 1, NO_COLOR, NO_RULE);
petri_input(&net, p4, t3, 1, NO_COLOR, NO_RULE);
petri_input(&net, p7, t3, 1, NO_COLOR, NO_RULE);
petri_input(&net, p1, t4, 1, NO_COLOR, NO_RULE);
petri_input(&net, p3, t5, 1, NO_COLOR, NO_RULE);
petri_input(&net, p5, t6, 1, NO_COLOR, NO_RULE);
petri_input(&net, p8, t7, 1, NO_COLOR, NO_RULE);
petri_input(&net, p9, t7, 1, NO_COLOR, NO_RULE);
petri_input(&net, p10, t7, 1, NO_COLOR, NO_RULE);
petri_output(&net, t1, p1, 1, NO_COLOR, NO_RULE);
petri_output(&net, t2, p3, 1, NO_COLOR, NO_RULE);
petri_output(&net, t3, p5, 1, NO_COLOR, NO_RULE);
petri_output(&net, t4, p2, 1, NO_COLOR, NO_RULE);
petri_output(&net, t4, p8, 1, NO_COLOR, NO_RULE);
petri_output(&net, t5, p4, 1, NO_COLOR, NO_RULE);
petri_output(&net, t5, p9, 1, NO_COLOR, NO_RULE);
petri_output(&net, t6, p6, 1, NO_COLOR, NO_RULE);
petri_output(&net, t6, p10, 1, NO_COLOR, NO_RULE);
petri_output(&net, t7, p7, 1, NO_COLOR, NO_RULE);
petri_type_transition(&net, t7, EOR);
petri_add_tokens(&net, p1, 1);
petri_print(&net);
petri_event(&net, t4);
petri_print(&net);
petri_event(&net, t7);
petri_print(&net);
petri_event(&net, t2);
petri_print(&net);
petri_event(&net, t5);
petri_print(&net);
petri_event(&net, t7);
petri_print(&net);
petri_event(&net, t3);
petri_print(&net);
petri_event(&net, t6);
petri_print(&net);
petri_event(&net, t7);
petri_print(&net);
return error;
}
int test4()
/*
* COLOR TEST NET (Assumed for now)
* Two consumers of different colors and one input. The instances of tokens
* are kept track of.
*/
{
static int error, i;
static struct petri_net net;
static int p1, p2, p3;
static int t1, t2;
static int color1 = 1, color2 = 2;
static int instance[20], instance_pnt;
error = petri_init(&net);
p1 = petri_place(&net, "p1");
p2 = petri_place(&net, "p2");
p3 = petri_place(&net, "p3");
t1 = petri_transition(&net, "t1");
t2 = petri_transition(&net, "t2");
petri_input(&net, p1, t1, 1, color1, NO_RULE);
petri_input(&net, p3, t1, 1, color1, NO_RULE);
petri_input(&net, p2, t2, 1, color2, NO_RULE);
petri_input(&net, p3, t2, 1, color2, NO_RULE);
petri_output(&net, p1, t1, 1, color1, NO_RULE);
petri_output(&net, p2, t2, 1, color2, NO_RULE);
for(i = 0; i < 20; i++) instance[i] = i;
instance_pnt = 0;
petri_add_color_token(&net, p1, color1, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p2, color2, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p3, color1, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p3, color2, instance[instance_pnt]);
instance_pnt++;
petri_print(&net);
sub4(&net, t2, color1, instance, &instance_pnt);
petri_print(&net);
sub4(&net, t1, color1, instance, &instance_pnt);
petri_print(&net);
sub4(&net, t1, color1, instance, &instance_pnt);
petri_print(&net);
sub4(&net, t2, color2, instance, &instance_pnt);
petri_print(&net);
return error;
}
int sub4(net, transition, color, instance, instance_pnt)
struct petri_net *net;
int transition, color, *instance, *instance_pnt;
{
static int error, i, list[20], n, outs[20], places[20], outputs;
error = ERROR;
if(petri_in_event(net, transition, NO_RULE) == NO_ERROR){
if(petri_get_consumed(net, transition, &color, list, &n, outs, places, &outputs) == NO_ERROR){
for(i = 0; i <= n; i++) instance[list[i]] = -1000;
if(petri_set_produced(net, transition, &(instance[*instance_pnt]), outputs) == NO_ERROR){
*instance_pnt += outputs;
error = petri_out_event(net, transition);
}
}
}
return error;
}
int test5()
/*
* RELATIONAL TEST NET
* This is based on an example on pg. 125 of Reisig [1985]
*/
{
static int error, i;
static struct petri_net net;
static int p1, p2, p3, p4;
static int t1;
static int color_a = 1, color_b = 2;
static int rule_a = 1, rule_b = 2;
static int instance[20], instance_pnt;
error = petri_init(&net);
p1 = petri_place(&net, "p1");
p2 = petri_place(&net, "p2");
p3 = petri_place(&net, "p3");
p4 = petri_place(&net, "p4");
t1 = petri_transition(&net, "t1");
/*
* For the rule 'a' firing
*/
petri_input(&net, p1, t1, 2, color_a, rule_a);
petri_input(&net, p1, t1, 1, color_b, rule_a);
petri_input(&net, p2, t1, 1, color_a, rule_a);
petri_input(&net, p2, t1, 1, color_b, rule_a);
petri_output(&net, t1, p3, 1, color_b, rule_a);
petri_output(&net, t1, p4, 2, color_a, rule_a);
petri_output(&net, t1, p4, 2, color_b, rule_a);
/*
* For the rule 'b' firing
*/
petri_input(&net, p1, t1, 1, color_a, rule_b);
petri_input(&net, p1, t1, 2, color_b, rule_b);
petri_input(&net, p2, t1, 2, color_a, rule_b);
petri_input(&net, p2, t1, 2, color_b, rule_b);
petri_output(&net, t1, p3, 2, color_a, rule_b);
petri_output(&net, t1, p3, 3, color_b, rule_b);
petri_output(&net, t1, p4, 2, color_a, rule_b);
petri_output(&net, t1, p4, 2, color_b, rule_b);
for(i = 0; i < 20; i++) instance[i] = i;
instance_pnt = 0;
petri_add_color_token(&net, p1, color_a, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p1, color_a, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p1, color_b, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p1, color_b, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p2, color_a, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p2, color_a, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p2, color_b, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p2, color_b, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p2, color_b, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p3, color_a, instance[instance_pnt]);
instance_pnt++;
petri_add_color_token(&net, p4, color_b, instance[instance_pnt]);
instance_pnt++;
/**/
petri_print(&net);
sub5(&net, t1, rule_a, instance, &instance_pnt);
/**/
/*
petri_print(&net);
sub5(&net, t1, rule_b, instance, &instance_pnt);
*/
petri_print(&net);
return error;
}
int sub5(net, transition, rule, instance, instance_pnt)
struct petri_net *net;
int transition, rule, *instance, *instance_pnt;
{
static int error, i, list[20], n, outs[20], places[20], outputs;
error = ERROR;
if(petri_in_event(net, transition, rule) == NO_ERROR){
if(petri_get_consumed(net, transition, &rule, list, &n, outs, places, &outputs) == NO_ERROR){
for(i = 0; i <= n; i++) instance[list[i]] = -1000;
if(petri_set_produced(net, transition, &(instance[*instance_pnt]), outputs) == NO_ERROR){
*instance_pnt += outputs;
error = petri_out_event(net, transition);
}
}
}
return error;
}
3.6.2 petri.h
/*
*
*/
#ifndef PETRI_HEADER
#define PETRI_HEADER
#define MAX_STRING_LENGTH 100
#define ERROR -1
#define NO_ERROR 0
#define EMPTY 0
#define USED 1
#define FALSE -1
#define TRUE 0
#define NO_COLOR -1
#define NO_RULE -1
#define MAX_NUMBER_PLACES 20
#define MAX_NUMBER_TRANSITIONS 20
#define MAX_NUMBER_INPUTS 10
#define MAX_NUMBER_OUTPUTS 10
#define MAX_NUMBER_COLORS 20
#define MAX_NUMBER_RULES 60
#define INHIBIT -1
#define EOR 1
#define COLORED 2
struct arc {
int color;
int number;
int place;
int next_point;
};
struct petri_net {
struct places {
int status;
char name[MAX_STRING_LENGTH];
int color[MAX_NUMBER_COLORS];
int color_instance[MAX_NUMBER_COLORS];
int color_pnt;
int tokens;
} place[MAX_NUMBER_PLACES];
struct transitions {
int status;
char name[MAX_STRING_LENGTH];
int type;
double fire_time;
int fire_color;
int ready_to_fire;
int input[MAX_NUMBER_COLORS];
int output[MAX_NUMBER_COLORS];
int color[MAX_NUMBER_COLORS];
int color_pnt;
int instance[MAX_NUMBER_INPUTS];
int instance_pnt;
int to_color[MAX_NUMBER_OUTPUTS];
int to_place[MAX_NUMBER_OUTPUTS];
int to_instance[MAX_NUMBER_OUTPUTS];
int to_pnt;
} transition[MAX_NUMBER_TRANSITIONS];
/*
* Rules for transition firing
*/
struct arc precondition[MAX_NUMBER_RULES];
int precondition_pnt;
struct arc event[MAX_NUMBER_RULES];
int event_pnt;
};
#endif
3.6.3 petri.c
/*
*
* NOTE: In this software the view is that arcs are inputs and outputs from
* transitions (not places as in some textbooks). Therefore an INPUT is going
* into a transition. An OUTPUT is coming out of a transition.
*
*
* This petri net simulator allows the transitions to be set in various ways.
* BASIC allows the transactions to fire when all of the inputs have tokens.
* EOR allows the transaction to fire when only one input is set.
* COLORED transactions will only fire when tokens of the same color are
* present on all inputs
* When an input to a transition is set to INHIBIT, the transition cannot fire
* while a token is present in the input place.
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "petri.h"
int petri_init(net)
struct petri_net *net;
{
static int error, i;
error = NO_ERROR;
for(i = 0; i < MAX_NUMBER_PLACES; i++){
net->place[i].status = EMPTY;
}
for(i = 0; i < MAX_NUMBER_TRANSITIONS; i++){
net->transition[i].status = EMPTY;
}
net->precondition_pnt = -1;
net->event_pnt = -1;
return error;
}
int petri_transition(net, name)
struct petri_net *net;
char *name;
{
static int number, i;
number = ERROR;
for(i = 0; (i < MAX_NUMBER_TRANSITIONS)
&& (strcmp(name, net->transition[i].name) != 0); i++);
if(i < MAX_NUMBER_TRANSITIONS){
number = i;
} else {
for(i = 0; (i < MAX_NUMBER_TRANSITIONS)
&& (net->transition[i].status != EMPTY); i++);
if(i < MAX_NUMBER_TRANSITIONS){
number = i;
net->transition[number].status = USED;
strcpy(net->transition[number].name, name);
net->transition[number].color_pnt = -1;
net->transition[number].ready_to_fire = FALSE;
net->transition[number].fire_time = 0.0;
net->transition[number].type = COLORED;
}
}
return number;
}
int petri_type_transition(net, transition, type)
struct petri_net *net;
int transition, type;
{
static int error;
error = ERROR;
if(net->transition[transition].status == USED){
if((type == EOR) || (type == COLORED)){
error = NO_ERROR;
net->transition[transition].type = type;
}
}
return error;
}
int petri_place(net, name)
struct petri_net *net;
char *name;
{
static int number, i;
number = ERROR;
for(i = 0; (i < MAX_NUMBER_PLACES)
&& (strcmp(name, net->place[i].name) != 0); i++);
if(i < MAX_NUMBER_PLACES){
number = i;
} else {
for(i = 0; (i < MAX_NUMBER_PLACES)
&& (net->place[i].status != EMPTY); i++);
if(i < MAX_NUMBER_PLACES){
number = i;
net->place[number].status = USED;
strcpy(net->place[number].name, name);
net->place[number].tokens = 0;
net->place[number].color_pnt = -1;
}
}
return number;
}
int petri_color_find(net, transition, color)
struct petri_net *net;
int transition, color;
{
static int number, i, end_pnt;
number = ERROR;
end_pnt = net->transition[transition].color_pnt;
for(i = 0; (i <= end_pnt) &&(net->transition[transition].color[i] != color);i++);
if(i <= end_pnt){
number = i;
} else {
if(i < MAX_NUMBER_COLORS){
net->transition[transition].color_pnt = i;
number = i;
net->transition[transition].color[i] = color;
net->transition[transition].input[i] = -1;
net->transition[transition].output[i] = -1;
}
}
return number;
}
int petri_add_relation(list, point, end_point, place, number, color)
struct arc *list;
int *point, *end_point, place, number, color;
/*
* Add a relationship to the list of preconditions or events
*/
{
static int error, list_pnt, current_pnt;
error = NO_ERROR;
current_pnt = -1;
if((*point >= 0) && (*point < MAX_NUMBER_RULES)){
list_pnt = *point;
while((current_pnt == -1) && (error == NO_ERROR)){
if((list[list_pnt].place == place)
&& (list[list_pnt].color == color)){
current_pnt = list_pnt;
} else if(list[list_pnt].next_point < 0){
if(*end_point < (MAX_NUMBER_RULES - 1)){
*end_point += 1;
current_pnt = *end_point;
list[current_pnt].color = color;
list[current_pnt].number = 0;
list[current_pnt].place = place;
list[current_pnt].next_point = -1;
list[list_pnt].next_point = *end_point;
} else {
error = ERROR;
}
} else {
list_pnt = list[list_pnt].next_point;
}
}
} else {
if(*end_point < (MAX_NUMBER_RULES - 1)){
*end_point += 1;
*point = *end_point;
current_pnt = *end_point;
list[*point].color = color;
list[*point].number = 0;
list[*point].place = place;
list[*point].next_point = -1;
} else {
error = ERROR;
}
}
if((current_pnt >= 0) && (error == NO_ERROR)){
list[current_pnt].number += number;
}
return error;
}
int petri_get_list(list, point, place, number, color, n)
struct arc *list;
int point, *place, *number, *color, *n;
/*
* Get a list of preconditions or events
*/
{
static int error, i, list_pnt;
error = ERROR;
*n = -1;
if((point >= 0) && (point < MAX_NUMBER_RULES)){
error = NO_ERROR;
list_pnt = point;
while((list_pnt != -1) && (error == NO_ERROR)){
(*n)++;
place[*n] = list[list_pnt].place;
number[*n] = list[list_pnt].number;
color[*n] = list[list_pnt].color;
list_pnt = list[list_pnt].next_point;
}
}
return error;
}
int petri_input(net, from_place, to_transition, number, color, rule)
int from_place, to_transition;
int number, color, rule;
struct petri_net *net;
/*
* Set a relational input to a transition
*/
{
static int error, i, color_pnt;
error = ERROR;
if((net->place[from_place].status != EMPTY)
&& (net->transition[to_transition].status != EMPTY)){
color_pnt = petri_color_find(net, to_transition, rule);
if(color_pnt != ERROR){
error = petri_add_relation(net->precondition,
&(net->transition[to_transition].input[color_pnt]),
&(net->precondition_pnt),
from_place, number, color);
}
}
return error;
}
int petri_output(net, from_transition, to_place, number, color, rule)
int to_place, from_transition;
int number, color, rule;
struct petri_net *net;
/*
* Set relational output from transition
*/
{
static int error, i, color_pnt;
error = ERROR;
if((net->place[to_place].status != EMPTY)
&& (net->transition[from_transition].status != EMPTY)){
color_pnt = petri_color_find(net, from_transition, rule);
if(color_pnt != ERROR){
error = petri_add_relation(net->event,
&(net->transition[from_transition].output[color_pnt]),
&(net->event_pnt),
to_place, number, color);
}
}
return error;
}
int petri_add_tokens(net, place, number)
struct petri_net *net;
int place, number;
/*
* Add or subtract tokens from a place
*/
{
static int error;
error = ERROR;
if(net->place[place].status == USED){
error = NO_ERROR;
net->place[place].tokens += number;
if(net->place[place].tokens < 0){
error = ERROR;
net->place[place].tokens -= number;
}
}
return error;
}
int petri_add_color_token(net, place, color, instance)
struct petri_net *net;
int place, color, instance;
/*
* Add an instance of a colored token to a place
*/
{
static int error, list_pnt;
error = ERROR;
if((net->place[place].status == USED)
&& (net->place[place].color_pnt < (MAX_NUMBER_COLORS - 1))){
error = NO_ERROR;
net->place[place].tokens += 1;
net->place[place].color_pnt += 1;
list_pnt = net->place[place].color_pnt;
net->place[place].color[list_pnt] = color;
net->place[place].color_instance[list_pnt] = instance;
}
return error;
}
int petri_tokens(net, place)
struct petri_net *net;
int place;
/*
* Get a count of tokens in a place
*/
{
static int number;
number = ERROR;
if(net->place[place].status == USED){
number = net->place[place].tokens;
}
return number;
}
int petri_color_tokens(net, place, list_color, list_instance)
struct petri_net *net;
int place, *list_color, *list_instance;
/*
* get a list of colored tokens in a place
*/
{
static int number, i;
number = ERROR;
if(net->place[place].status == USED){
number = net->place[place].color_pnt;
for(i = 0; i <= number; i++){
list_color[i] = net->place[place].color[i];
list_instance[i] = net->place[place].color_instance[i];
}
}
return number;
}
int petri_number_tokens(net, place, color)
struct petri_net *net;
int place, color;
/*
* Get the number of tokens of one color
*/
{
static int number, i;
number = ERROR;
if(net->place[place].status == USED){
number = 0;
if(color == NO_COLOR){
number = net->place[place].tokens;
} else {
for(i = 0; i <= net->place[place].color_pnt; i++){
if(color == net->place[place].color[i])
number++;
}
}
}
return number;
}
int petri_remove_tokens(net, place, color, number, instance)
struct petri_net *net;
int place, color, number, *instance;
/*
* Remove a number of tokens from a place
*/
{
static int error, i, j, temp_cnt, temp_pnt;
error = ERROR;
if((net->place[place].status == USED) && (color >= 0)){
temp_cnt = 0;
temp_pnt = net->place[place].color_pnt;
for(j = temp_pnt; j >= 0; j--){
error = NO_ERROR;
if((net->place[place].color[j] == color)
&& (temp_cnt < number)){
instance[temp_cnt] =
net->place[place].color_instance[j];
net->place[place].color[j] =
net->place[place].color[temp_pnt];
net->place[place].color_instance[j] =
net->place[place].color_instance[temp_pnt];
net->place[place].tokens--;
temp_pnt--;
temp_cnt++;
}
}
net->place[place].color_pnt = temp_pnt;
} else if((net->place[place].status == USED) && (color == NO_COLOR)){
error = NO_ERROR;
net->place[place].tokens -= number;
for(i = 0; i < number; i++)
instance[i] = -1;
}
return error;
}
int petri_in_event(net, transition, rule)
struct petri_net *net;
int transition, rule;
{
static int error, i, color_pnt, type, count, eor_pnt, tokens, inhibit,
i_start, i_end;
static int place[MAX_NUMBER_INPUTS],
number[MAX_NUMBER_INPUTS],
col[MAX_NUMBER_INPUTS],
n;
error = ERROR;
if((net->transition[transition].status == USED)
&& (net->transition[transition].ready_to_fire != TRUE)){
type = net->transition[transition].type;
color_pnt = petri_color_find(net, transition, rule);
if(color_pnt != ERROR){
petri_get_list(net->precondition, net->transition[transition].input[color_pnt],
place, number, col,&n);
inhibit = FALSE;
count = -1;
for(i = 0; i <= n; i++){
tokens = petri_number_tokens(
net, place[i], col[i]);
if((tokens > 0) && (number[i] < 0)){
inhibit = TRUE;
} else if(tokens >= number[i]){
count++;
eor_pnt = i;
}
}
if(inhibit == FALSE){
i_start = 0;
i_end = -1;
if((type == EOR) && (count == 0)){
i_start = eor_pnt;
i_end = eor_pnt;
} else if((type != EOR) && (count == n)){
i_end = n;
}
if(i_start <= i_end){
count = 0;
error = NO_ERROR;
net->transition[transition].fire_color
= rule;
net->transition[transition].ready_to_fire
= TRUE;
for(i = i_start; i <= i_end; i++){
if(number[i] > 0){
petri_remove_tokens(net,
place[i],
col[i],
number[i],
&(net->transition[transition].instance[count]));
count
+= number[i];
}
}
net->transition[transition].instance_pnt
= count - 1;
}
}
}
}
return error;
}
int petri_output_prepare(net, transition, rule)
struct petri_net *net;
int transition, rule;
/*
* Create an output list for a transition
*/
{
static int error, i, j, count, list_pnt, color_pnt;
static int plc[MAX_NUMBER_OUTPUTS],
num[MAX_NUMBER_OUTPUTS],
col[MAX_NUMBER_OUTPUTS],
pnt;
error = ERROR;
color_pnt = petri_color_find(net, transition, rule);
if(color_pnt != ERROR){
error = NO_ERROR;
petri_get_list(net->event, net->transition[transition].output[color_pnt], plc, num, col, &pnt);
count = 0;
for(i = 0; i <= pnt; i++){
for(j = 0; j < num[i]; j++){
net->transition[transition].to_place[j+count]
= plc[i];
net->transition[transition].to_color[j+count]
= col[i];
}
count += num[i];
}
net->transition[transition].to_pnt = count - 1;
}
return error;
}
int petri_get_consumed(net, transition, rule, list, n, color_out, place, n_produced)
struct petri_net *net;
int transition, *rule, *list, *n, *color_out, *place, *n_produced;
{
static int error, i, j, count;
static int plc[MAX_NUMBER_OUTPUTS],
num[MAX_NUMBER_OUTPUTS],
col[MAX_NUMBER_OUTPUTS],
pnt;
error = ERROR;
if(net->transition[transition].ready_to_fire == TRUE){
error = NO_ERROR;
*rule = net->transition[transition].fire_color;
*n = net->transition[transition].instance_pnt;
for(i = 0; i <= *n; i++){
list[i] = net->transition[transition].instance[i];
}
if(petri_output_prepare(net, transition, *rule) != ERROR){
*n_produced = net->transition[transition].to_pnt;
for(i = 0; i <= *n_produced; i++){
color_out[i] = col[i];
place[i] = plc[i];
}
}
}
return error;
}
int petri_set_produced(net, transition, list, n)
struct petri_net *net;
int transition, *list, n;
/*
* Add a new list of instances to the transition before firing
*/
{
static int error, i;
error = ERROR;
if(net->transition[transition].ready_to_fire == TRUE){
error = NO_ERROR;
for(i = 0; i <= n; i++){
net->transition[transition].to_instance[i] = list[i];
}
}
return error;
}
int petri_out_event(net, transition)
struct petri_net *net;
int transition;
{
static int error, place, number, i, j, color, instance, point;
error = ERROR;
if((net->transition[transition].status == USED)
&& (net->transition[transition].ready_to_fire == TRUE)){
error = NO_ERROR;
for(i = 0; i <= net->transition[transition].to_pnt; i++){
color = net->transition[transition].to_color[i];
if(color == NO_COLOR){
petri_add_tokens(net,
net->transition[transition].to_place[i], 1);
} else {
petri_add_color_token(net,
net->transition[transition].to_place[i],
net->transition[transition].to_color[i],
net->transition[transition].to_instance[i]);
}
}
net->transition[transition].ready_to_fire = FALSE;
}
return error;
}
int petri_event(net, transition)
struct petri_net *net;
int transition;
{
static int error;
error = petri_in_event(net, transition, NO_COLOR, NO_RULE);
if(error == NO_ERROR) error = petri_output_prepare(net, transition, NO_RULE);
if(error == NO_ERROR) error = petri_out_event(net, transition);
return error;
}
int petri_print(net)
struct petri_net *net;
{
static int error, i, j, k, place[MAX_NUMBER_RULES],
color[MAX_NUMBER_RULES], number[MAX_NUMBER_RULES], end_pnt;
error = NO_ERROR;
/*
* Print the list of places
*/
printf("\n\nPLACES -------------------------- \n");
for(i = 0; i < MAX_NUMBER_PLACES; i++){
if(net->place[i].status == USED){
printf("# %d -- %30s -- %d tokens\n", i,
net->place[i].name,
net->place[i].tokens);
for(j = 0; j <= net->place[i].color_pnt; j++){
printf(" color token %d -- instance %d\n",
net->place[i].color[j],
net->place[i].color_instance[j]);
}
}
}
/*
* Print the list of transitions
*/
printf("\n\nTRANSITIONS ---------------------\n");
for(i = 0; i < MAX_NUMBER_TRANSITIONS; i++){
if(net->transition[i].status == USED){
printf("# %d -- %30s -- %d fire(?) -- %d color -- %f time -- %d type\n", i,
net->transition[i].name,
net->transition[i].ready_to_fire,
net->transition[i].fire_color,
net->transition[i].fire_time,
net->transition[i].type);
for(j = 0; j <= net->transition[i].color_pnt; j++){
printf(" Rule %d -> color %d \n", j,
net->transition[i].color[j]);
petri_get_list(net->precondition,
net->transition[i].input[j],
place, number, color, &end_pnt);
for(k = 0; k <= end_pnt; k++){
printf(" Input %d -- place %d -- color %d -- number %d\n", k,
place[k], color[k], number[k]);
}
petri_get_list(net->event,
net->transition[i].output[j],
place, number, color, &end_pnt);
for(k = 0; k <= end_pnt; k++){
printf(" Output %d -- place %d -- color %d -- number %d\n", k,
place[k], color[k], number[k]);
}
}
for(k = 0; k <= net->transition[i].instance_pnt; k++){
printf(" instance consumed %d is %d\n",
k, net->transition[i].instance[k]);
}
for(k = 0; k <= net->transition[i].to_pnt; k++){
printf(" token out %d is %d, %d, %d\n",
k, net->transition[i].to_color[k],
net->transition[i].to_place[k],
net->transition[i].to_instance[k]);
}
}
}
printf("\n\n PRECONDITIONS \n");
for(i = 0; i <= net->precondition_pnt; i++){
printf(" %d --> color %d -> number %d -> place %d -> point %d\n", i,
net->precondition[i].color,
net->precondition[i].number,
net->precondition[i].place,
net->precondition[i].next_point);
}
printf("\n\n EVENTS \n");
for(i = 0; i <= net->event_pnt; i++){
printf(" %d --> color %d -> number %d -> place %d -> point %d\n", i,
net->event[i].color,
net->event[i].number,
net->event[i].place,
net->event[i].next_point);
}
return error;
}
