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

Showing changes from revision #3 to #4: Added | Removed | Changed

Contents

Idea Introduction

Petri nets are a simple model of computation, which have a diverse range of applications to modelling processes such as chemical reaction networks and population biology dynamics. They are a kind of dataflow graph through which entities percolate and have their types transformed. They also have some very interesting and charming mathematical properties, and an extensive literature has been developed on about the them. theory of Petri nets. See the Network Theory series on the Azimuth Blog for an exciting and in-depth treatment of the applications and the theory.

In this these series of articles, we will be approach approaching Petri nets with the aim of learning the concepts and in then order writing to write programs which that put the them concepts to work. We They address are a pitched range to an audience of computationally oriented readers: coding enthusiasts enthusiasts, and programmers, software engineers engineers, and computer scientists, and scientists who interested program. in We programming. begin They contain tutorial material, along with a working compact conceptual tutorial, programs then discuss programming approaches, and then an develop analytical small dissection of these programs. Such programs to model the concepts. That will give the reader some clay “clay” to work with.

In this first article we will introduce define the Petri nets, nets and then give a small program to that simulate simulates them. The application shown will simulate the behavior of a highly simplistic model of a chemical reaction network involving Hydrogen, Oxygen and water. We will see that it doesn’t take much to get started with a nice Petri net.

The Petri net nets: concept basic definition

A Petri net is a kind of diagram involving with two types kinds of nodes: passive container nodes, called states species (or (aka places), “places” aka “states”), which can hold some zero non-negative or number more oftokens, and active process nodes, called transitions . Each transition is wired “wired” to a some fixed collection of containers called itsinputs , and a some fixed collection of containers called itsoutputs . The A input collection for a transition may contain have multiple instances connections of to the same container, input and or similarly for the output collection. container. When the transitionfires, it removes one token from each of its input containers, and adds one token to each of its output containers. When a transition contains multiple copies of the same container in its input collection, then the firing of the transition removes that many tokens from the input container. And if it has multiple outputs to the same container, then than many tokens are added to the container when fires. A transition is enabled if there are a sufficient number of tokens at its input containers. Dataflow can arise whenever one transition outputs to a container that is the input of another transition. The condition of the net as a whole is described by a labelling function that maps each container to the number of tokens that it holds.

The Note: process the structure various of terms a for Petri the net containers is (species/places/states) non-deterministic. each In make any sense given in labelling, the multiple right transitions application may context, but can be enabled, confusing and in so others. there Just are for multiple the ways following to paragraphs, construct an execution sequence. If no transitions are enabled, then we say use that the net agnostic is term “container.”halted.

Petri When nets are a good model for general reaction networks that consist of a collection of entities of various types, along with “reactions” that perform conversions between the types. Each object is represented by a token, and each container node holds all the objects for a certain type. A reaction transforms some input objects into some output objects, and this is reflected by the transition that removes tokens from its input containers and puts new tokens into its output containers.fires, it removes one token from each of its input containers, and adds one token to each of its outputs. When a transition takes multiple inputs from the same container, when it fires, it removes that many tokens from the input container; similarly, if there are multiple connections to an output container, then upon firing, multiple tokens are added to the output. A transition is enabled if there are a sufficient number of tokens at its input containers. The condition of the Petri net is described by a labelling function that maps each container to the number of tokens that it holds.

The object containers are called Dataflowstates arises when one transition outputs tokens to a container that is the input for another transition. But note that the sequencing of transitions is because each object type can be regarded as a different “state of being.”non-deterministic: in any given configuration of tokens in the containers, there may be multiple transitions that are enabled, and so there is not a unique execution sequence that is determined.

Chemical If reaction no networks are a prime example: tokens are molecule instances, the containers correspond to molecular types, and the transitions are steps enabled, of then a we chemical say reaction. that Consider the H net is2halted O . formation example from the main article. There are three states, H, O, and H2O, and one transition T, for the process of forming one H2O molecule from two H’s and one O. H and O are the inputs for T, with H occuring twice. H2O is the output for T. Naturally, when T fires, two tokens will be removed from H, one token will be removed from O, and one token will be added to H2O.

We start with classes to simulate a Petri net. The rule for sequencing the transitions will be to randomly choose between the enabled transitions.

Application: Petri net simulator

Petri nets are a good model for reaction networks that consist of various entities belonging to different species, with “reactions” that perform conversions between the species. Each entity is represented by a token, and each container holds all the entities for one of the species. A reaction transforms input entities into outputs, and this process is reflected by the transition that removes tokens from its input containers and puts new tokens into its output containers.

Chemical reaction networks are a prime example. Here the tokens represent molecules in the system, the containers represent the species of the molecules, and the transitions represent chemical reactions that convert “tokens” of the input species into tokens of the output species. In what follows, we will describe the example from REFERENCE, which describes a simplistic model of water formation and dissociation. The purpose of the example is not to be chemically realistic, but to drive home the idea of of chemical reaction Petri nets.

• There are three species, H, O, and H2O.

• There is one transition “Combine”, for the process of forming one H2O molecule from two H atoms and one O atom. (For starters it’s unrealistic because the real reaction involves H2 and O2, not isolated atoms of H and O – but never mind, we are illustrating a computational model.) Therefore the transition takes two inputs from the container that holds the H tokens, and one input from the container that holds the O tokens. There is one output from Combine to the container for H2O. Naturally, when Combine fires, two tokens will be removed from H, one will be removed from O, and one will be added to H2O.

Another application area is population biology.

Application program: Petri net simulator

The application will be for a chemical reaction network with two transitions: simplistic formation of water molecules, and reverse transition, simplistic dissociation of water molecules.

Running the program

The rule for sequencing the transitions will be to randomly choose between the enabled transitions.

Here is the top-level call in the main program:

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
)
initialLabelling = {"H":5, "O":3, "H2O":4}
steps = 10
petriNet.RunSimulation(steps, initialLabelling)

Data to specify a Petri net

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, done

Running it again gives a different sequence of transitions.

The code is HERE. This is a self-contained Python script, which can be run from the command prompt. Edit the first line of the program to point to the location of the interpreter.

Structure and contents of the program

Anatomy of the program

We use object classes PetriNet and Transition. We can get by with a string to represent a state, by its name. (In a pedagogical program, less is more.)

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

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

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.

Full listing

#!/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)

Summary Conclusion

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.