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

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

Contents

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

Preface

This page illustrates the idea of “programming companion” pages for the main articles in the Wiki. This one is the companion to the Petri nets article.

These pages are intended as a pragmatic complement to the pages which introduce the concepts themselves. They are pitched to the discourse of programmers, software engineers, computer scientists, and, more generally anyone who wants to take a hands-on approach to learning and working with the concepts. They will lead, step by step, towards an understanding of how to actually program the concept, and should contain small demonstration programs that actually work. The readers should be able to run these programs with a minimum of ado. For this purpose, the use of some “high level” scripting language is recommended.

A pragmatic companion article should refer to the main article and may assume the context that it provides, but it should be able to stand on its own. The conceptual material will need to be reformulated with intended audience in mind. A companion articles will also have a different rhythm than its conceptual counterpart. Whereas the conceptual articles may aspire to a “soaring” architecture, where the ideas are linked together in a beautiful network of ideas that has deep connections with the research literature, the computational companion articles, while guided by the conceptual progression, will have more of “marching” quality. They will start by explaining the most basic concept, then how to implement it in a sample program, then explain the next concept, then may talk about how to tweak the original program to a demonstration of the next program. Interspersed with this will be talk about data structures and algorithms. Everything will be needed to be said more explicitly, and the concepts will be unfolded according to a different schedule.

In any case, they should be lots of fun to write, read, and use.

An effort should be to make the code as transparent as possible, and as brief as possible, while still aiming for code that runs. If polishing the behavior of the program would make it longer or more complex to read, then leave it out. If you give the user a working model, then they work it up themselves. For example, in the first sample program here, which runs a Petri net with chemical reaction transitions, the decision was made to hard-code the network description into the top-level call that the script makes, rather than passing the state and transition specifications as arguments to the script. Although it would have made the script much cooler as a tool, that would have increased the mass of code with argument parsing logic that is routine and irrelevant to the concept under examination. Furthermore, the top-level call to the Petri net simulation method would be made much less obvious, because the literal text in the unsophisticated version:

net = 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 
)

is far more lucid than this call would be in the more usable program:

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

Whatever functionality you leave out of the sample program can be presented to the reader as exercises.

Exercises are recommended, to put the icing on the page.

Petri net basics

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

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.

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 input place of one transition is an output 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})