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

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

Contents

Introduction

This is the a “pedagogical computing page” to accompany the article onpedagogical 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 engineers, and computer scientists. 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.

To For illustrate, example, consider the this code in our first sample program program: in this 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:

 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 Usability this pedagogical program, it is better to keep the parameters as literal text in the main body. The usability would have be been improved by passing the arguments from the environment, environment. but But that would have swell increased the mass of the code with argument argument-parsing parsing logic, which is routine and immaterial tangential to the idea subject of at Petri hand. nets. It Transparency would suffer, also because make the new code would less then readable: look something like this:

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

Definition of Petri net nets basics

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 calledstates because each object type can be viewed regarded as a different state “state of nature. 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.

Script Code to for illustrate a basic Petri net

In We our start first with coding classes example, to simulate a random Petri enabled net. transition The rule for sequencing the transitions will be chosen. to randomly choose between the enabled transitions.

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.

Running the application

The following application program will contains be classes for that implement a basic chemical Petri reaction net, 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(initialLabelling, steps)

This produced the output

output
output

Running it again will produce 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. In principle there would be a class for State, but we can get by here by representing states by their names. Less is more, when it comes to a pedagogical program.

The PetriNet class contains the list of state names, the list of transition names, the current marking, which is a map from state names to integers, and a mapping from transition names to the Transition objects.

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