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

Showing changes from revision #6 to #7: Added | Removed | Changed

Contents

Introduction

This is the “pedagogical computing page page” for to accompany the article onPetri nets . It illustrates the idea of a “pedagogical computing page.” They are pitched to a mixed audience of computationally oriented readers: coding enthusiasts, programmers, software engineers and computer scientists. The idea is to present the basic ideas for this type of reader (who isn’t assumed to be familiar with the natural sciences), and then proceed to discuss programming approaches, and finally to present small programs that demonstrate the material.

This kind of page is addressed to a mixed audience of computationally-oriented readers: coding enthusiasts, programmers, software engineers and computer scientists. 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.

To illustrate, consider the following statements from the first sample program in this article: article, which builds a Petri net for a chemical reaction network with two reactions (simplistic formation of water, and simplistic dissociation of water). Here are the top-level statements:

 # build a Petri net for a chemical reaction network with two reactions: # simplistic formation of water, and simplistic dissociation of water  petriNet = PetriNet(     ["H", "O", "H2O"],    # all states     ["combine", "split"], # all 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(initialLabelling, steps)

For this pedagogical program, it is better to keep the parameters as literal text in the main body. The usability would have been improved by passing the arguments from the environment, but that would have increased the mass of the code with argument parsing logic, which is routine and immaterial to the idea of Petri nets. Transparency would suffer, because the new code would then look something like this:

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

Petri net basics

A Petri net is a kind of diagram involving two types of nodes: passive container nodes, which called can hold some non-negative number ofstates (or places), which can hold some non-negative number of tokens , and active process nodes, which, when fired, perform the operation of removing one token from each of its input containers, and adding one token to each of its output containers. The process nodes are calledtransitions , . and Each the transition container is nodes wired are to a fixed collection of containers called its states inputs , (or and a fixed collection of containers called its places outputs ). . The input collection for a transition may contain multiple instances of the same container, and similarly for the output collection. 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 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.

Chemical The reaction networks are a prime example: tokens are molecule instances, the containers correspond to molecular types, and transitions are chemical called reactions.states because each object type can be viewed as a different state of nature.

The Chemical explanation reaction for networks why are a prime example: tokens are molecule instances, the containers correspond to molecular types, and the transitions are called steps of a chemical reaction. Consider the Hstates2 O is formation that example each from object the type main can article. be There viewed are as three a states, different H, state O, of and matter. 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.

Each transition node is connected to a fixed collection of input places, and a fixed collection of output places. An input place may occur multiple times in the input collection, and similarly for the output places. When the transition fires, 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.

Script to illustrate a basic Petri net

If there are an insufficent number of tokens on any of its input places, the transition is not enabled to fire. For instance, if a transition contains two occurrences of an input place p, then there must be at least two tokens at p in order for it to be enabled.

Dataflow activity arises when an output place of one transition is an input place of another transition.

The state of the whole net is described by function that assigns a non-negative integer to each place – the function that gives the token count at each place. This function is called a marking of the net.

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.

For instance, take the H2O formation example from the main page Petri net. 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.

We will be using 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.

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.

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.

Script to illustrate a basic Petri net

The following program contains classes that implement a basic Petri net,

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