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

Showing changes from revision #13 to #14: 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 theory and applications of Petri nets.

In this series of articles, we approach the concepts with the aim of writing programs that make them work. The readership would include coding enthusiasts, professional programmers, scientists interested in programming models, software engineers and computer scientists. The articles will present brief tutorials, give programs to exercise the concepts, and analyze the code. These illustrative programs should give the reader some clay to work with.

Here In this first article, we introduce Petri nets and give a simulator program. This will be applied to a “toy” model of a chemical reaction network for the synthesis and dissociation of H2 O molecules. The second article will elaborate the treatment to coverstochastic Petri nets, where the sequencing of the Petri net is probabilistically controlled.

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 transition nodes, which are “wired” to some containers called its inputs and some called its outputs. A transition can have multiple input or output connections to a single container.

When a transition fires, it removes one token from each input container, and adds one token to each output container. When 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 described by a labelling function which maps each container to the number of tokens it holds. A transition is enabled to fire in a labelling if there are enough tokens at its input containers. If no transitions are enabled, the it is halted. The sequencing is non-deterministic, because in a given labelling there may be several transitions that are enabled. Dataflow arises whenever one transition sends tokens to a container that is read by another transition.

Using Petri nets to model Entity Conversion Networks

Petri nets can describe networks consisting of entities of 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 a transition that consumes input tokens and generates output tokens.

One application is to population dynamics. The tokens represent organisms, and the species are biological species. A simplified example, involving two species, Wolf and Rabbit, is given on the Network Theory page. There are three transitions: Birth, which takes one Rabbit in and outputs two Rabbits (like asexual reproduction), Predation, which converts Rabbit plus Wolf to Wolf plus Wolf, and Death, which inputs one Wolf and outputs nothing.

A major application is to chemical reaction networks. The entities are chemical units: molecules, isolated atoms, or ions. Each chemical unit is represented by a token in the net, and a container holds all of the tokens for a chemical species. Chemical reactions are then modeled as transitions that consume input tokens and generate output tokens.

We will be using the following simplified model for water formation and dissociation, which is presented in the Network Theory page.

  • The species are H, O, and H2O.

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

  • Transition split is the reverse process, which inputs one H2 and outputs two H and one O.

Note that the model is intended to show the idea of chemical reaction Petri nets, so it is not physically realistic. The actual reactions involve H2 , and O2 , and there are intermediate transitions involving as OH well. for the stages of the reaction.

A Petri net simulator

Here The is following our Python PROGRAM SCRIPT to will simulate a Petri net. net, It using uses parameters that describe the species, the transition, transitions, and an the initial labelling, labelling. and It then will runs run the net for a specified number of steps. At each stage step of the process it chooses randomly among the enabled transitions, fires it, and prints the new labelling on the console.

Note: in the next article, on stochastic Petri nets, we will enhance the model with statistical parameters that control the relative firing rates of the transitions. Here we are establishing the groundwork.

Running the script

The code is a self-contained Python script. See the APPENDIX for notes on obtaining the interpeter.

The model parameters 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 We 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.

Top-level structure of the script

The First script construct constructs a Petri net object, using parameters for the species Petri and net: transitions, and then runs it.

Construct the net:

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 
)

Sets Then up establish the initial condition labelling: of the net:

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

Then run it for twenty steps:

steps = 20
petriNet.RunSimulation(steps, initialLabelling)

Exercise: Improve the script to accept the model parameters from the command-line.

Anatomy of the program

We Species represent will species be represented simply by strings their that names, name i.e., them, as strings. PetriNet and use object classes for Transition and will PetriNet. be A defined as object classes. Each PetriNet instance will contain a the collection list of Species names, the list of Transition instances, objects, and it will contain the current labelling. The top-level labelling method is in a PetriNet, dictionary called from RunSimulation, species makes name repeated calls to token count. Each transition object contains an input dictionary and an input dictionary. These input dictionary map the name of a method species FireOneRule. to FireOneRule constructs the list number of enabled times transitions, that chooses one randomly, and fires it. This work is supported by the Transition transition class, which provides methods IsEnabled, and Fire. The Fire method takes a it labelling as in, input, and updates similarly for the counts in it—decrementing the input token counts, and incrementing the output token dictionary. counts.

The Transition PetriNet class contains has a map top-level that method describes called the RunSimulation, input which connections. makes It repeated maps calls each species name to FireOneRule. FireOneRule obtains the number list of times enabled that transitions, it chooses is one taken randomly, as and input. fires The it. 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.

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.printHeader()

        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)

The Transition object class contains two maps… Transition exposes two key methods, methods. both IsEnabled of which operate on labellings: isEnabled takes a labeling as parameter, and returns a boolean saying whether it the is transition enabled can 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 Fire method takes a labelling in, and updates the counts in it to reflect the action of removing input tokens and creating output tokens.

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.

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] 

Each Finally, transition observe object contains a map (dictionary) from input species name to the number of times that the species class is line input for PetriNet declares that it inherits from a base class PetriNetDataStructures. This class contains some “housekeeping” methods needed to the support transition, PetriNet: PrintHeader, PrintLabelling, and an crucially, output map with the same constructor, structure. which converts the transition specifications into Transition objects.

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.

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]

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

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]

    def printHeader(this):
        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.printHeader()

        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 about cool an new important idea, model for computation, called Petri nets, and seen how it can be used to do model something a cool general with class it. This is only the beginning, in terms of the entity applications conversion networks, which include chemical reaction networks as a major case. Then we wrote a program to simulate them, and the applied theory. it to a simple model for formation and dissociation of water molecules.

There But this is an only important limitation to our current program: it just randomly picks a rule. In our example, the system beginning, just in made term a kind of random walk (back and forth) between the states applications of full dissociation all H and O atoms, no H2O molecules and all H2O molecules. But in a real system, the rates theory at of which Petri the nets. transitions fires areprobabilistically 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 Observe gives motivation for the topic following limitation of our next current article, program: it just randomly picks a rule. When we run the program, the simulation makes a kind of random walk, back and forth, between the states of full synthesis and full dissociation. But in a real chemical system, the rates at which is the transitions fires are stochastic probabilistically determined , Petri and nets. depend, among other things, on the temperature. 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 the various chemical species would be determined by the relative firing rates of the various transitions.

Appendix: Notes on the software environment

This gives motivation for our next article, which covers stochastic Petri nets. See Blog - Petri net programming (part 2).

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 Theory, Azimuth blog

  • Petri Nets – Wikipedia

  • python python.org

  • cygwin

  • enthought

Stochastic Appendix: Petri Notes nets on the language interpreter

A The nice sample elaboration program of the basic model is the written in Python, which is a low-fuss scripting language with abstraction capabilities. It is well-suited for proof-of-concept programming. It has a medium-sized user base and support community.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 You definition have 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 few as options 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 choose the from, reaction, in once terms they of are distributions: brought into proximity.

  • If you are on a Linux or Mac type of system, it is likely to already be installed. Just open a shell and type “python.” Othewise, use the package manager to install it.

  • In Windows, you can use the version from the python.org web site. Alternatively, install cygwin, and in the installer, select Python, along with any of your other favorite Linux-style packages. Then you can partially pretend that you are working on a Linux type of system.

  • Consider also the Enthought python distribution, which comes packaged with a suite of Python-based open-source scientific and numeric computing packages. This includes scipy, numpy and matplotlib.

The program is distributed as a self-contained script, so in Linux and cygwin, you can just execute ./petri1.py. When running this way under cygwin, you can either refer to the cygwin version of the Python executable, or to any of the native Windows versions of interpreter. You just have to adjust the first line of the script to point to the Python.exe.