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

Showing changes from revision #1 to #2: Added | Removed | Changed

Contents

Overview

This is the programming companion page to the main article on Petri nets.

A Petri Net is a kind of graph which can be used to simulate discrete processes. There are two kinds of nodes: (1) places, aka states, and (2) transitions. First we will explain the concept using the “place” metaphor. Think of each place as a tray that can hold a finite number of “tokens.” Each transition node is connected to a set of input place nodes, and a set of output place nodes. When the transition “fires,” it removes one token from each of its input places, and adds one token to each of its output places. So it is a kind of dataflow network, where there is just one datatype, the token.

Petri net basics

Note A that one transition may take multiple inputs from the same place, and have multiple outputs to the same place. For example, suppose transition t takes two inputs from p, and sends to outputs to q. Then when it fires, it will remove 2 tokens from p, and add two tokens to q.Petri net is a kind of graph that represents a type of discrete process. It contains two kinds of nodes: one is called “places” or “states”, and the other called “transitions”. A place is a container that can hold any non-negative number of “tokens”. In the basic model, the tokens are atomic objects, all of the same featureless type. The transitions are process nodes that consume tokens from their input places, and produce tokens on their output places.

The Each state transition of node the network as a whole is given connected by to a mapping fixed from collection the set of input places, and a fixed collection of output places. An input place nodes may to occur multiple times in the natural input numbers collection, N. and This similarly is for called the a output marking. places. When the transitionfires, it removes one token from each of its input places, and adds one token to each of its output places. If the same place occurs k times in the input collection, then the firing of the transition will remove k tokens from that input place. Similarly, if a place occurs k times in the output collect, then the firing of the transition will add k tokens to that place.

The If state there metaphor comes from applications such as chemical reaction networks. Picture a fixed collection of atoms, that are assembled an into insufficent various types of molecules. Each state refers to a type of molecule. The number of tokens associated on with any a state (place) indicates how many of that its type input of places, molecule are in the system. transition So, is taking not the enabled H2O to example fire. from For the instance, main if Petri Net page, we have states for H, O and H2O, and a single transition with contains inputs two at occurrences H of and O, and an output input place p, then there must be at H2O. least The two firing tokens of at the p transition in corresponds order for it to the be formation enabled. of one H2O molecule.

Note Dataflow that activity the arises transition when structure an of the net is non-deterministic. In any given configuration, there will be a subset of the transitions that are enabled to fire: namely, all those transitions for which every input place contains at least one token. So there are multiple ways to order the firings of the one transition rules. is an output place of another transition.

The representation state can be enriched with probabilistic parameters to control the firing of the transitions. whole Then net you is could described imagine by function that assigns a non-negative integer to each place the problem function of that finding gives equilibrirum states of the net. token count at each place. This function is called amarking of the net.

f 2:x 21 f_2 : x_2 \to 1

The alternative terminology in which the places are called “states” arises from applications such as chemical reaction networks. Consider a fixed collection of atoms, which are assembled into various types of molecules. Then each type of molecule is a state. The number of tokens stored at a state/place in the net gives the count of how many molecules are in that state. The firing of a transition then represents one step in a chemical reaction.

Here For instance, take the H112 O denotes formation example from the tensor main product page ofnoPetri net . objects. 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 input places for T, with H occuring twice in the input collection. H2O is the output place 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.

tensor We product will symbol be is using written the “state” terminology in our coding examples, for consistency with the rest of the Wiki, and because the examples will be for chemical reaction networks.++’ rather than ‘\otimes’.

For more on this, see:

Petri-net process structure

The process structure of a Petri net is inherently non-deterministic. For a marking m of the net, let T(m) be the set of transitions that are enabled to fire. If T(m) is empty, we say the net is halted. Otherwise, any of the transitions in T(m) may fire, and so we get different execution sequences depending on the rules for choosing the next transition to fire.

Stochastic Petri net

In our first coding example, a random enabled transition will be chosen.

In a subsequent section, we will explore an extension of Petri nets, called “stochastic Petri nets,” which contain rate constants that are associated with the transitions. The rate constants can be used to form probabilistic rules for determining the sequence of transitions.

If we use x 1x_1 to denote “rabbit” and x 2x_2 to denote “fox”, the transitions are:

Script to illustrate a basic Petri net

birth:x 1x 1x 1 birth : x_1 \to x_1 \otimes x_1
#!/usr/bin/python
# for Windows use without cygwin, change the top line to this form: 
#!C:\Python27\python.exe

import string
import random

# for the basic illustration, State is so simple that
# we can get away with representing states by just their names.
# i.e., we don't need a class, just use strings 

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, marking):
       for inputState in this.inputs.keys():
          if marking[inputState] < this.inputs[inputState]: 
              return False  # not enough tokens to fire

       return True # good to go 

    def Fire(this, marking):

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

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

class PetriNet:
    # Fields used in this class:
    #
    # transitionNames 
    # stateNames
    # transitions: transitionName -> TransitionObject
    # marking: state name -> 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.marking),
            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.marking)

        return True 

    def RunSimulation(this, iterations, initialMarking): 
        this.PrintHeader()

        this.marking = initialMarking

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

        print "done"

    def BuildTransitions(this, inputSpecs, outputSpecs):

        this.transitions = {}

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

        for (transitionName, stateName, degree) 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 PrintMarking(this):
        for stateName in this.stateNames:
            print str(this.marking[stateName]) + ",",

# end of definition class PetriNet

# now build a net for two opposite reactions:
# transition "combine": synthesis of water molecule
# transition "split": dissociation of water molecule

net = PetriNet(
    ["H", "O", "H2O"],    # all states
    ["combine", "split"], # all transitions

    [("combine", "H", 2), ("combine", "O", 1), ("split", "H2O", 1)],
    [("combine", "H2O", 1), ("split", "H", 2), ("split", "O", 1)],
    #
    # this means:
    # 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:

net.RunSimulation(10, {"H": 5, "O": 3, "H2O": 4})

in which one rabbit becomes two,

predation:x 1x 2x 2x 2 predation : x_1 \otimes x_2 \to x_2 \otimes x_2

in which a fox eats a rabbit and reproduces, resulting in two foxes, and

death:x 21 death : x_2 \to 1

in which one fox dies. Of course this model is ridiculous — it would be slightly less silly if we replaced ‘fox’ and ‘rabbit’ by asexual micro-organisms, one

  • α\alpha is the birth rate,

Let [x 1][x_1] denote the concentration of rabbits (say, in rabbits per hectare) and let [x 2][x_2] the concentration of

(1)d[x 1]dt=α[x 1]β[x 1][x 2] \frac{d [x_1]}{ d t} = \alpha [x_1] - \beta [x_1] [x_2]
(2)d[x 2]dt=+β[x 1][x 2]γ[x 2] \frac{d [x_2]}{ d t} = + \beta [x_1] [x_2] - \gamma [x_2]

The standard procedure works as follows:

  • Each transition contributes to the time derivative of [x i][x_i] in the obvious way: we take the rate at which that transition occurs, and multiply it by the number of times x ix_i occurs as an output of that transition, minus the number of copies times it occurs as an input.

Chemical reaction networks are diagrams widely used in chemistry. They are quite similar to Petri nets (see below), but in some sense more primitive and less expressive:

chemical reaction network

below, A,BA, B and CC are three molecular species, and we have four reactions between them:

A+AB A + A \to B
CA+A C \to A + A
BC B \to C
CBC \to B

and then try:

The last is apparently not free online, but here’s a quote that explains the philosophy:

The formal kineticist, on the other hand, takes a macroscopic viewpoint and his primitive concept is the elementary reaction. This is defined by a set of stoichiometric coefficients, together with a rule relating The abstract is also useful:

Abstract: The familiar idea of mass action kinetics is extended to embrace situations more general than chemically reacting mixtures in closed vessels. Thus, for

Abstract: Abstract bifurcation theory is one of the most widely used approaches for analysis of dynamical

  • B.L. Clarke and I. Prigogine, Stability of complex reaction networks, Adv. Chem. Phys., Wiley, New York, 43 (1980), 1–-216.

There is an interesting relation between chemical reaction networks (or, better, Petri nets) and toric varieties. See:

References

Besides the works listed above, some good general starting-points include:

For a detailed introduction to stochastic Petri nets, see:

code/stub gen (if i remember correctly. These are also other types of Open source packages on wikipedia: