# The Azimuth Project Blog - Petri net programming (part 1) (Rev #11, changes)

Showing changes from revision #10 to #11: Added | Removed | Changed

# Contents

## Introduction

Petri nets are a simple model of computation with a range of modelling applications that include chemical reaction networks, manufacturing processes, and population biology dynamics. They are graphs through which entities flow and have their types transformed. They also have far-reaching mathematical properties which are the subject of an extensive literature. See the Network Theory series on the Azimuth Blog for a panoramic and well-diagrammed introduction to the the theory and applications of Petri nets.

In this series of articles, we approach the concepts with the aim of writing programs that put make them to work. The readership would include anyone coding interested enthusiasts, in professional using programmers, programming to think about problems and solve them: scientists interested in programming models, coding enthusiasts, professional programmers, software engineers, engineers and computer scientists. The articles will give succinct tutorials, present brief tutorials, give programs to exercise the concepts, and analyze the code. These will illustrative be programs working should “toy” programs, which hopefully will give the reader some “clay” clay to work with.

Here We we now introduce Petri nets and give a small simulator simulation program. It will be applied to a toy “toy” model of a chemical reaction network that for involves the synthesis and dissociation of H2O molecules.

## Definition of Petri nets

A Petri net is a diagram with two kinds of nodes: container nodes, called species (or “places”, “states”), which can hold zero or more tokens, and active transition nodes, which are “wired” to some containers called its inputs and some called its outputs. A transition can have multiple input connections to a single container, and multiple output connections.

When a transition fires, it removes one token from each input container, and adds one token to each output container. If there are multiple inputs or outputs to the same container, then that many tokens get removed or added.

The total state of the Petri net is given by a labelling function that maps each container to the number of tokens that it holds. Given a labelling, a transition is enabled if there are sufficient tokens at its inputs for it to fire. If no transitions are enabled, the it is halted. The sequencing is non-deterministic, because in a given labelling, there may be multiple transitions that are enabled. Dataflow arises when one transition outputs tokens to a container that is input to another transition.

## Using Petri nets to model Entity Conversion Networks

Petri nets can describe reaction networks that consist of entities belonging to different species, with conversion reactions from the input species to the output species. Each entity is symbolized by a token in the net, and all the tokens for a species are grouped into a container. The conversion of entities is symbolized by the transition that operates on their tokens.

One area of application is to modeling population dynamics. Tokens represent organisms, and the species are biological species. A pedagogical example is given on the Network Theory page, where there are two species, Wolf and Rabbit, and three transitions: Birth, which takes one Rabbit in and outputs two Rabbits (think of asexual reproduction), Predation, which converts Rabbit + Wolf to Wolf + Wolf, and Death, which takes one Wolf in and outputs nothing.

The application we will take up is to chemical reaction networks. The entities are chemical units: molecules, isolated atoms, or ions. Each chemical unit is represented by a token, and a container holds all of the tokens for a chemical species. The transitions that transform the tokens symbolize the reactions that transform the chemical units.

We will be using, from the Network Theory page, the following model for water formation and dissociation:

• The species are H, O, and H2O. (Note that the model is only intended to show the idea of chemical reaction Petri nets. The actual reactions involves H2 and O2.)

• Transition combine inputs two H atoms and one O atom, and outputs an H2O molecule.

• Transition split is the reverse process.

## A Petri net simulator

We now give a program that builds a model of a Petri net, given parameters that define the species and transitions. The rule for sequencing the transitions is to choose a random enabled transition. The simulation runs for a specified number of steps, starting from an initial labelling. At each stage of the process, the labelling is printed on the console.

### Running the script

The code is HERE. It is a self-contained Python script. See the APPENDIX for notes on obtaining the interpeter. The parameters for the model are already coded into the script. So let’s give it whirl:

python petri1.py

This produced the output:

H, O, H2O, Transition
5, 3, 4, split
7, 4, 3, split
9, 5, 2, combine
7, 4, 3, combine
5, 3, 4, split
7, 4, 3, split
9, 5, 2, split
11, 6, 1, combine
9, 5, 2, split
11, 6, 1, split
13, 7, 0, ...

In words, we started out in a state with 5 H’s, 3 O’s, and 2 H2O’s, then a split took place, which increased H by 2, increased O by 1, and decreased H2O by one, then…

Running it again gives a different execution sequence. See the APPENDIX for notes on the language runtime environment.

### Top-level structure of the script

The job of the script is to construct a Petri net instance, given parameters that define the species and transitions, and then to execute it.

Here is the statement that builds it:

petriNet = PetriNet(
["H", "O", "H2O"],    # states
["combine", "split"], # transitions
[("combine",2,"H"), ("combine",1,"O"), ("split",1,"H2O")], # inputs
[("combine",1,"H2O"), ("split",2,"H"), ("split",1,"O")],   # outputs
#
# combine has 2 H inputs, 1 O input, and 1 H2O output
# split has 1 H20 input, 2 H outputs, and 1 O output
)

Then we setup the initial condition of the net:

initialLabelling = {"H":5, "O":3, "H2O":4}

And run it for twenty steps:

steps = 20
petriNet.RunSimulation(steps, initialLabelling)

Exercise: Improve the script to accept the model parameters from the command-line. Hints: Use “import sys,” and sys.argv[i]. Then you can pass strings like “[H, O, H20]” from the command line, and use the eval function on them.

### Anatomy of the program

We represent species by their names (strings), and use classes for Transition and Petri net.

The Transition class contains a map that describes the input connections. It maps each species name to the number of times that it is taken as input. The transition class contains a similar map to describe the output connections.

A Petri net object has a member that holds the current labelling, which is a map (dictionary) from stateName to the token count.

The chief data in the Petri net classes are the Transition objects, and the labeling, which describes the current configuration of the net.

The Transition object contains two maps… Transition exposes two key methods, both of which operate on labellings: isEnabled takes a labeling as parameter, and returns a boolean saying whether it is enabled to fire. This is determined by comparing the input map for the transition with the token counts in the labeling, to see if there is sufficient tokens for it to fire.

The constructor for the Petri net class takes the transition specifications, and “digests” them into the initial data structures used in the simulation. This involves constructing Transition objects for each of the transitions.

Each transition object contains a map (dictionary) from input species name to the number of times that the species is input to the transition, and an output map with the same structure.

The PetriNet class contains the list of species names, the list of transition names, the current labelling, which maps species names to integers, and a map from transition names to Transition objects.

The top-level method in PetriNet is RunSimulation, which makes repeated calls to a method called FireOneRule. FireOneRule constructs the list of enabled transitions, chooses one randomly, and fires it. This is facilitated by the methods IsEnabled and Fire on the Transition class.

The fire method takes a labeling in, and performs the action indicated by the transition: it removes tokens from the input, and adds tokens to the output. It modifies the labelling, decreasing the values for the inputs, and increasing the values for the outputs.

Here is the Transition class:

Now that our Petri net is equipped with a labelling and a list of Transitions, each with an isEnabled and fire method, it has everything that it needs to fire a rule: pick a transition, check if it is enabled in the current labelling, and if so, call the Fire method on the transition, to update the labelling to the new state. All that is left for running a simulation is to specify a rule for choosing which enabled transition to fire: For this, our first program, we will just choose a random transition.

The top-level entry point is the method runSimulation, which takes the initial labelling, and a number of states to iterate.

Here is the main Petri net class:

Note that the PetriNet inherits from a base class PetriNetDataStructures. This base class was separated for clarity, and contains the “housekeeping” methods needed to support PetriNet: printHeader, printLabelling, and, not to be forgotten, the constructor, which converts the specifications ‘[combine,2,H etc. into the actual transition objects. Here is the code for it:]

# Author line
#
#!/usr/bin/python
#
# for Windows without cygwin, use this form for the top line:
#!C:\Python27\python.exe

import string
from random import random,randrange

def selectRandom(list):
return list[randrange(len(list))]

# States are represented just by their names, no class is needed

class Transition:
# Fields used in this class:
#
# name -- transitionName
# inputs: stateName -> inputCount
# outputs: stateName -> outputCount

def __init__(this, transitionName):
this.transitionName = transitionName
this.inputs = {}
this.outputs = {}

def isEnabled(this, labelling):
for inputState in this.inputs.keys():
if labelling[inputState] < this.inputs[inputState]:
return False  # not enough tokens to fire

return True # good to go

def fire(this, labelling):

print this.transitionName

for inputName in this.inputs.keys():
labelling[inputName] = labelling[inputName] - this.inputs[inputName]

for outputName in this.outputs.keys():
labelling[outputName] = labelling[outputName] + this.outputs[outputName]

class PetriNetDataStructures:
# Fields:
#
# transitionNames
# stateNames
# transitionMap: transitionName -> TransitionObject
# labelling -- mapping (dict) from state name to count

def buildTransitions(this, inputSpecs, outputSpecs):
this.transitionMap = {}

for (transitionName, degree, stateName) in inputSpecs:
this.getTransition(transitionName).inputs[stateName] = degree

for (transitionName, degree, stateName) in outputSpecs:
this.getTransition(transitionName).outputs[stateName] = degree

def getTransition(this, transitionName):
if not(this.transitionMap.has_key(transitionName)):
this.transitionMap[transitionName] = Transition(transitionName)
return this.transitionMap[transitionName]

print string.join(this.stateNames, ", ") + ", Transition"

def printLabelling(this):
for stateName in this.stateNames:
print str(this.labelling[stateName]) + ",",

class PetriNet(PetriNetDataStructures):

def __init__(this, stateNames, transitionNames, inputMap, outputMap):
this.stateNames = stateNames
this.transitionNames = transitionNames
this.buildTransitions(inputMap, outputMap)

def runSimulation(this, iterations, initialLabelling):

this.labelling = initialLabelling
this.printLabelling()

i = 0
while not(this.isHalted()):

this.fireOneRule()
this.printLabelling();
i = i + 1
if i == iterations:
print "done"
return

print "halted"

def enabledTransitions(this):
return filter(
lambda transition: transition.isEnabled(this.labelling),
this.transitionMap.values())

def isHalted(this):
return len(this.enabledTransitions()) == 0

def fireOneRule(this):
selectRandom(this.enabledTransitions()).fire(this.labelling)

# now build a net for two opposite transitions:
# combine: formation of water molecule
# split: dissociation of water molecule

net = PetriNet(
["H", "O", "H2O"],    # states
["combine", "split"], # transitions
[("combine",2,"H"), ("combine",1,"O"), ("split",1,"H2O")], # inputs
[("combine",1,"H2O"), ("split",2,"H"), ("split",1,"O")],   # outputs
#
# combine has 2 H inputs, 1 O input, and 1 H2O output
# split has 1 H20 input, 2 H outputs, and 1 O output
)

initialLabelling = {"H": 5, "O": 3, "H2O": 4}
steps = 20

net.runSimulation(steps, initialLabelling)

## Conclusion

We’ve learned a cool new idea, and how to do something cool with it. This is only the beginning, in terms of the applications and the theory.

There is an important limitation to our current program: it just randomly picks a rule. In our example, the system just made a kind of random walk (back and forth) between the states of full dissociation – all H and O atoms, no H2O molecules – and all H2O molecules. But in a real system, the rates at which the transitions fires are probabilistically determined, and depend, among other things, on the temperature of the system. With a high probability for formation, and a low probability for dissociation, we would expect the system to reach an equilibrium state in which H2O is the predominant “token” in the system. [The relative concentration of H20 would depend on the relative probabilities of the transitions.]

This gives motivation for the topic of our next article, which is stochastic Petri nets.

## Appendix: Notes on the software environment

The sample programs here are in Python, which is a good language for simple proof-of-concept programs.

You have a few options to choose from, in terms of distributions:

• If you are on a Linux/unix type of system, it may already be installed, or use the package manager to install it.

• In Windows, you can use the version from the python.org web site. Alternatively, install cygwin, and choose Python on the setup menu, and then you can try to pretend that you are working in a nix system.

• Another interesting distribution is [from] Enthought, which comes pre-built with an open-source scientific and numeric computing environment, scipy, numpy, matplotlib, …

The program is distributed as a self-contained script, so from Linux and cygwin, you can just execute ./petri1.py. You just have to adjust the first line to point to the interpreter. Even from cygwin, you can refer to the native python executable, or the enthought distribution.

## References

• Network Theory

• Petri Nets – Wikipedia

• python

• cygwin

• enthought

## Stochastic Petri nets

A nice elaboration of the basic model is the stochastic Petri net, which consists of a Petri net, along with data that gives a rate coefficient for each transition. The firing rate for a transition will equal its rate coefficient times the product of the number of tokens at each input state (using multiple factors if a state occurs multiple times as an input).

This definition is motivated by the model of chemical reaction networks where the reaction rates are proportional to the product of the concentrations of the input constituents. We can think of the rate coefficient for a transition as a magnitude that takes into account both the “temperature” of the system of tokens and the “ease” with which the input tokens will combine to trigger the reaction, once they are brought into proximity.