The Azimuth Project
delete 25 (Rev #12, changes)

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

Contents

Introduction

This is a pedagogical computing page to accompany the article on Petri nets.

This kind of page is addressed to a mixed audience of computationally-oriented readers: coding enthusiasts, programmers, software engineers, computer scientists, and scientists who want to code. The aim is first to provide a tutorial, then to discuss programming approaches, and then to present small programs to demonstrate the concepts.

Here are some guidelines:

  • The readers should be able to run these programs with a minimum of fuss. A scripting language that can represent abstractions is recommended.

  • Try keep the code as succinct and transparent as possible, while still aiming for code that runs.

  • Don’t increase usability if it reduces clarity.

For example, consider this code in our first sample 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)

Usability would be improved by passing the arguments from the environment. But that would swell the code with argument-parsing logic, which is routine and tangential to the subject at hand. It would also make the code less readable:

net = PetriNet(
    ParseStateArguments(argv[1]),
    ParseTransitionNames(argv[2]),
    ...

Definition of Petri nets

A Petri net is a kind of diagram involving two types of nodes: passive container nodes, called states (or places), which can hold some non-negative number of tokens, and active process nodes, called transitions. Each transition is wired to a fixed collection of containers called its inputs, and a fixed collection of containers called its outputs. The input collection for a transition may contain multiple instances of the same container, and similarly for the output collection. When the transition fires, 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 process structure of a Petri net is non-deterministic. In any given labelling, multiple transitions may be enabled, and so there are multiple ways to construct an execution sequence. If no transitions are enabled, then we say that the net is halted.

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

The object containers are called states because each object type can be regarded as a different “state of being.”

Chemical reaction networks are a prime example: tokens are molecule instances, the containers correspond to molecular types, and the transitions are steps of a chemical reaction. Consider the H2O 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.

Application 1: Simulating a Petri net

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

Running the program

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.

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)

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.

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

Code for the program

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

import string
import random

# states are represented by their names 

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):

       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 PetriNet:
    # Fields used in this class:
    #
    # transitionNames 
    # stateNames
    # transitions: transitionName -> TransitionObject
    # labelling -- mapping (dict) from state name to count 

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

        this.BuildTransitions(inputMap, outputMap)

    def FireOneRule(this):

        enabledTransitions = filter(
            lambda transition: transition.IsEnabled(this.labelling),
            this.transitions.values())

        if len(enabledTransitions) == 0:

            # nothing can fire, we are halted
            return False 

        # pick a random enabled transition

        index = random.randrange(len(enabledTransitions))

        transition = enabledTransitions[index] 

        print transition.transitionName  

        transition.Fire(this.labelling)

        return True 

    def RunSimulation(this, iterations, initialLabelling): 

        this.PrintHeader()

        this.labelling = initialLabelling

        this.PrintLabelling() 
        
        for i in range(iterations):
           if this.FireOneRule():
               this.PrintLabelling(); 
           else:
               print "halt"
               break

        print "done"

    def BuildTransitions(this, inputSpecs, outputSpecs):

        this.transitions = {}

        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.transitions.has_key(transitionName)):
            this.transitions[transitionName] = Transition(transitionName)

        return this.transitions[transitionName]

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

# end class PetriNet

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

# and run it:

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

net.RunSimulation(steps, initialLabelling)

Stochastic Petri nets

Things A become nice more elaboration interesting of if we add a parameter to each transition that controls the rate model at is which the it fires.stochatic Petri net, which consists of a Petri net, along with data that specifies a rate coefficient for each of the transitions. The rate at which a transition fires will equal the product of the the number of tokens at each of its input states (using multiple terms for the same state if it occurs multiple times), times the rate coefficient.

We’ll Background: use The the intuition following model for firing this definition comes from chemical reaction networks, where the reaction rates are proportional to the product of the concentrations of the input constituents. Consider the probability of all of the inputs coming together within a chemical very small test rectangle over a small interval of time. The reaction network. coefficient will include factors such as the temperature, and the probability that the inputs will successfully combine once they happen to get near each other.
Assume the objects are freely bouncing around. Assume a fixed distribution of velocities for the objects. In a small sample cube over a small sample time, the probability that a transition will fire will equal the probability that all of its inputs are found in the cube at that time, times a reaction coefficient. The probability that all inputs are found in the test cube during the test interval is proportional to the product of the concentrations of the inputs. The constant of proportionality will depend on the size of the test cube, the during of the test interval, the velocity distribution (temperature), and other physical factors that reflect how easy it is for the inputs to successfully combine once they are in the same proximity.

To summarize: the probability of the transition firing in a very small test region is proportional to the product of the concentrations of each of the inputs.

Note: This is only true in the limiting case of a very small test region. But it does imply that over any test region, the firing rate of each transition will be proportional to the product of the concentrations of the inputs.

A stochatic Petri net is a Petri net, along with data that specifies