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

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

Contents

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 about them. See the Network Theory series on the Azimuth Blog for an exciting and in-depth treatment of the applications and the theory.

In these articles, we will approach Petri nets with the aim of learning the concepts in order to write programs that put them to work. They are pitched to an audience of coding enthusiasts, programmers, software engineers, computer scientists, and scientists interested in programming. They contain tutorial material, along with working conceptual programs and an analytical dissection of these programs. Such programs will the reader some “clay” to work with.

In this article we introduce Petri nets and then give a small program that 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.

Definition of a Petri nets: net basic definition

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

Note: the various terms for the containers (species/places/states) each make sense in the right application context, but can be confusing in others. Just for the following paragraphs, we use the agnostic term “container.”

When the transition 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.

Dataflow arises when one transition outputs tokens to a container that is the input for another transition. But note that the sequencing of transitions is 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. If zero transitions are enabled, then the net ishalted.

If no transitions are enabled, then we say that the net is halted.

Application to entity reaction networks

Petri nets are can a describe 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.species, with “reactions” that transform entities of the input species into entities of the output species. Each token represents an entity, each container holds all the entities for some species, and each reaction is represented by transition that converts input tokens into output tokens.

Chemical We reaction now networks describe are two a prime example. Here the tokens represent molecules in the system, the containers represent the species of the molecules, model and applications from the transitions Network represent Theory chemical page, reactions in that convert “tokens” of the input areas species into tokens of the (1) output chemical species. reaction In networks what follows, we will describe the example from REFERENCE, which describes a simplistic model of water formation and dissociation. (2) The population purpose biology of dynamics. the They example are is purposely not simplistic, to because be they chemically are realistic, intended but to drive home theidea of of how chemical to reaction apply Petri nets. nets to entity reaction networks. By the way, the Network Theory pages provide nicepictures that show the Petri nets as diagrams, and how the tokens flow through them.

  • 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.

  1. Population biology dynamics.

Another application area is population biology.

  • There are two species, Rabbit and Wolf.

  • The transition Birth takes one input from Rabbit, and sends two outputs to Rabbit.

  • The transition Predation takes one input from Rabbit and one from Wolf, and sends two outputs to Wolf.

  • The transition Death has one input from Wolf, and zero outputs.

  1. Chemical reaction networks. 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. Here is the model for water formation and dissociation:
  • 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. (Unrealistic, for starters, because the real reaction involves H2 and O2, but never mind – we are exercising a model of computation.) So the the transition takes two inputs from the H container that holds the H tokens, takes one input from the O container, and sends one output to the H2O container.

Application program: Petri net simulator

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

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. – as described above.

Running the program

Let’s start running the program:

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

Running it again gives a different sequence of transitions.

[Explain output]

You input transition specifications, and an initial labelling of the states. It then repeatedly chooses an enabled transition, and prints the labelling.

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

Here is the data for the Petri net under specification:

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.

Anatomy of the program

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

The We PetriNet represent class states contains by the their list of state names, the list of transition names, the current labelling, which is a map from state names to (strings), integers, and a use map classes from for transition names to Transition objects. and Petri net.

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.

A Petri net object has a member that holds the current labelling, which is a map 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 state name to the number of times that the state is input to the transition, and an output map with the same structure.

The PetriNet class contains the list of state names, the list of transition names, the current labelling, which maps state 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.

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

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 input states, and increasing the values for the output states.

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 toplevel 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

A We’ve nice learned elaboration a cool new idea, and how to do something cool with it. This is only the beginning, in terms of the basic applications model and is the theory.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 There definition is motivated an by important the limitation model of chemical reaction networks where the reaction rates are proportional to the our product current of program: the it concentrations just of randomly the picks input constituents. We can think of the rate coefficient for a transition rule. as In a our magnitude example, that takes into account both the “temperature” system just made a kind of random walk (back and forth) between the system states of tokens full dissociation all H and O atoms, no H2O molecules and all H2O molecules. But in a real system, the “ease” rates with at which the input transitions tokens fires will combine to trigger the reaction, once they are brought into proximity.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.