Function Repository Resource:

# MultiwayPetriNet

Simulate the evolution of a Petri net configuration as a multiway system

Contributed by: Jonathan Gorard
 ResourceFunction["MultiwayPetriNet"][pnet,n] generates the results of n steps in the evolution of the multiway Petri net configuration defined by the PetriNetObject expression pnet. ResourceFunction["MultiwayPetriNet"][p,t,a,init,n] generates the results of n steps in the evolution of the multiway Petri net defined by the list of places p, the list of transitions t and the list of arcs a, with initial token distribution init. ResourceFunction["MultiwayPetriNet"][assoc,init,n] generates the results of n steps in the evolution of the multiway Petri net defined by the association of places, transitions and arcs assoc, with initial token distribution init. ResourceFunction["MultiwayPetriNet"][…,"prop"] gives the property "prop" for the specified multiway Petri net evolution. ResourceFunction["MultiwayPetriNet"][pnet→sel,n,…] uses the function sel to select which of the events obtained at each step to include in the evolution.

## Details and Options

Argument and option patterns for ResourceFunction["MultiwayPetriNet"] are similar to those of the resource function MultiwaySystem.
A Petri net is an abstract mathematical representation of a distributed system (frequently used for describing chemical reactions, biological processes, concurrent computing, etc.) consisting of a directed bipartite graph whose vertices are classified as either "places" or "transitions". The directed edges connecting places and transitions together are known as "arcs".
Each place can contain a number of "tokens", and a given transition will "fire" if the places connected to it by input arcs all contain at least one token. When a transition fires, it redistributes tokens from places connected to it by input arcs to places connected to it by output arcs.
ResourceFunction["MultiwayPetriNet"] supports the specification of Petri nets either by PetriNetObject expressions, a collection of three lists (places p, transitions t and arcs a) or by an explicit association of the form <|"Places"p,"Transitions"t,"Arcs"a|>. The list of arcs a should be a list of either rules or DirectedEdge objects (each connecting a place to a transition or vice versa).
PetriNetObject expressions can be constructed using the MakePetriNet function.
When specifying Petri nets in terms of lists or associations, the list init should be a list of integers specifying how many initial tokens to assign to each place. If a list init is not given, ResourceFunction["MultiwayPetriNet"] will assume that each place contains no tokens.
ResourceFunction["MultiwayPetriNet"] evolves the specified Petri net by applying all possible transition firings at each step.
The event selection function sel in ResourceFunction["MultiwayPetriNet"][pnetsel,] can be any function; additionally, it can have the following special forms:
 "Sequential" applies the first possible replacement (sequential substitution system) "Random" applies a random replacement {"Random",n} applies n randomly chosen replacements
In ResourceFunction["MultiwayPetriNet"][,"prop"], the following standard multiway system properties can be requested:
 "AllStatesList" the list of all states generated at each successive step "StatesCountsList" the number of distinct states generated at each successive step "AllStatesListUnmerged" the list of all states without any merging "PredecessorRulesList" the list of states and their corresponding predecessor states at each successive step "EvolutionGraph" graph formed by the evolution process, with no merging between different time steps "EvolutionGraphStructure" evolution graph without labeling "EvolutionGraphFull" graph formed by the evolution process, including equivalent events "EvolutionGraphFullStructure" full evolution graph without labeling "EvolutionGraphUnmerged" graph formed by the evolution process, with no merging of equivalent states "EvolutionGraphUnmergedStructure" unmerged evolution graph without labeling "EvolutionGraphWeighted" graph formed by the evolution process, with edges weighted by event multiplicity "EvolutionGraphWeightedStructure" weighted evolution graph without labeling "StatesGraph" graph of how each distinct state leads to other states "StatesGraphStructure" states graph without labeling "AllEventsList" the list of all events that occur at each successive step "EvolutionEventsGraph" graph showing the evolution process with updating events explicitly included "EvolutionEventsGraphStructure" evolution events graph without labeling "CausalGraph" graph of all causal relations between updating events "CausalGraphStructure" causal graph without labeling "EvolutionCausalGraph" combined graph of evolution process and causal relationships between events "EvolutionCausalGraphStructure" evolution causal graph without labeling "CausalGraphInstances" list of distinct causal graphs for all possible choices of event sequences "CausalGraphStructureInstances" causal graph instances without labeling "EvolutionCausalGraphInstances" list of distinct evolution causal graphs for all possible choices of event sequences "EvolutionCausalGraphStructureInstances" evolution causal graph instances without labeling "BranchPairsList" list of all branch pairs (i.e. critical pairs) generated in the states graph "NewBranchPairsList" list of all new branch pairs generated at each successive step "EvolutionBranchPairsList" list of all branch pairs generated in the evolution graph "NewEvolutionBranchPairsList" list of all new evolution branch pairs generated at each successive step "BranchPairEventsList" list of all events yielding branch pairs "NewBranchPairEventsList" list of all events yielding new branch pairs at each successive step "EvolutionBranchPairEventsList" list of all events yielding evolution branch pairs "NewEvolutionBranchPairEventsList" list of all events yielding new evolution branch pairs at each successive step "BranchialGraph" graph of branch pair ancestry at a given step "BranchialGraphStructure" branchial graph without labeling "AllStatesBranchialGraph" graph of branch pair ancestry across all steps "AllStatesBranchialGraphStructure" all states branchial graph without labeling "EventBranchialGraph" graph of branch pair event ancestry at a given step "EventBranchialGraphStructure" event branchial graph without labeling "AllEventsBranchialGraph" graph of branch pair event ancestry across all steps "AllEventsBranchialGraphStructure" all events branchial graph without labeling "EvolutionEventBranchialGraph" graph of evolution branch pair event ancestry at a given step "EvolutionEventBranchialGraphStructure" evolution event branchial graph without labeling "AllEventsEvolutionBranchialGraph" graph of evolution branch pair event ancestry across all steps "AllEventsEvolutionBranchialGraphStructure" all events evolution branchial graph without labeling "BranchPairResolutionsList" association of all resolved and unresolved branch pairs up to a given step "EvolutionBranchPairResolutionsLIst" association of all resolved and unresolved evolution branch pairs up to a given step "CausalInvariantQ" whether the system is causal invariant (all branch pairs converge) "EvolutionCausalInvariantQ" whether the system is evolution causal invariant (all evolution branch pairs converge) "KnuthBendixCompletion" list of Knuth–Bendix completion rules required to force causal invariance "EvolutionKnuthBendixCompletion" list of Knuth–Bendix completion rules required to force evolution causal invariance "StateWeights" list of weights for all vertices in the states graph
In ResourceFunction["MultiwayPetriNet"][,"prop"], the following specialized Petri net properties are also supported:
 "PetriNetObjects" list of PetriNetObject expressions obtained (default) "LabeledGraphs" list of directed graph representations obtained (with token counts represented graphically) "LabeledGraphsHighlighted" list of directed graph representations obtained (with token counts represented graphically, and with transition firings highlighted) "WeightedGraphs" list of directed graph representations obtained (with token counts represented as vertex weights) "WeightedGraphsHighlighted" list of directed graph representations obtained (with token counts represented as vertex weights, and with transition firings highlighted) "Tokens" list of token numbers associated to each place after each firing "TokenFirings" list of token numbers associated to each place after each firing, with the corresponding transition firing specified
Except for "AllStatesListUnmerged", "EvolutionGraphUnmerged" and states containing state IDs, identical states are always merged at each step.
In "StatesGraph", all instances of a given state at any step are merged. Different updating events that connect the same states will only be shown as separate edges if "IncludeEventInstances" is set to True.
Events are represented in the form {rule,input,rest}, where rule is the rule used in the updating event, input is the part of the state to which the rule is applied and rest is the remainder of the state. For substitution systems, rest is given in the form {prefix,suffix}.
Options for ResourceFunction["MultiwayPetriNet"] include:
 "IncludeStepNumber" False whether to label states and events with their respective step numbers "IncludeStateID" False whether to label states and events with unique IDs "IncludeInitializationEvents" False whether to include pseudoevents that set up initial conditions "IncludeEventInstances" False whether to show distinct updating events that connect the same states as separate edges "IncludeStateWeights" False whether to weight state vertices by their rate of occurrence at a particular time step "IncludeStatePathWeights" False whether to weight state vertices by the number of distinct evolution paths that lead to them "StateRenderingFunction" Automatic how to label states that appear in graphs "EventRenderingFunction" Automatic how to label events that appear in graphs MaxItems Infinity how many instances of a causal graph or evolution causal graph to return "GivePredecessors" False whether to label branch pairs with their predecessor state "GiveResolvents" False whether to label branch pairs with their resolvent state "IncludeSelfPairs" False whether to include trivial branch pairs "IncludeFullBranchialSpace" False whether to show all possible states in a given branchial graph "LineThickness" 1 absolute line thickness for graph edges
ResourceFunction["MultiwayPetriNet"] also accepts the same options as Graph.
Possible settings for "StateRenderingFunction" and "EventRenderingFunction" include:
 Inherited use the explicit vertex name as the label None use no label for the vertex "string" use a shape from the VertexShapeFunction collection func apply the function func to the name of the vertex
For "CausalGraphInstances" and "EvolutionCausalGraphInstances", the option MaxItemsn can be used to get only the first n possible instances of causal graphs.
In a PetriNetObject expression, the following properties are supported:
 "AssociationForm" Petri net represented as an association of places, transitions and arcs "Places" list of places in the Petri net "PlaceCount" number of places in the Petri net "Transitions" list of transitions in the Petri net "TransitionCount" number of transitions in the Petri net "Arcs" list of arcs in the Petri net "ArcCount" number of arcs in the Petri net "Tokens" list of token numbers associated to each place in the Petri net "TokenCounts" total number of tokens across all places in the Petri net "UnlabeledGraph" directed graph form of the Petri net without token counts represented graphically "LabeledGraph" directed graph form of the Petri net with token counts represented graphically "WeightedGraph" directed graph form of the Petri net with token counts represented as vertex weights
By convention, ResourceFunction["MultiwayPetriNet"] renders places as circles, transitions as squares, arcs as directed edges and tokens as black dots.

## Examples

### Basic Examples (14)

Construct a simple Petri net from lists of four places, three transitions and eight arcs, with an initial distribution of six tokens:

 In[1]:=
 Out[1]=

Showing basic multiway Petri net evolution:

 In[2]:=
 Out[2]=

Show the sets of labeled graphs obtained after one step, with every possible transition firing highlighted:

 In[3]:=
 Out[3]=

Show the sets of labeled graphs after three steps, without any transition firings highlighted:

 In[4]:=
 Out[4]=

Generate a graph showing how each state is obtained from the others:

 In[5]:=
 Out[5]=

Show the structure of the graph, without labels:

 In[6]:=
 Out[6]=

Generate the list of updating events applied at each step:

 In[7]:=
 Out[7]=

Construct a Petri net representing a reversible chemical reaction, specified by an association of three places, two transitions and six arcs, with an initial distribution of 12 tokens:

 In[8]:=
 Out[8]=

Generate a graph of the evolution history, with updating events included:

 In[9]:=
 Out[9]=

Show the structure of the graph, without labels:

 In[10]:=
 Out[10]=

Generate the causal graph, showing dependencies between updating events:

 In[11]:=
 Out[11]=

Show the structure of the graph, without labels:

 In[12]:=
 Out[12]=

Generate the evolution events graph, with causal connections included:

 In[13]:=
 Out[13]=

Show the structure of the graph, without labels:

 In[14]:=
 Out[14]=

Specify an event selection function that picks a random event at each step:

 In[15]:=
 Out[15]=

Generate causal graphs for all possible choices of event sequences:

 In[16]:=
 Out[16]=

Show the structures of the graphs, without labels:

 In[17]:=
 Out[17]=

Generate the list of all branch pairs (i.e. critical pairs):

 In[18]:=
 Out[18]=

Generate the association showing which branch pairs converged and which did not:

 In[19]:=
 Out[19]=

Prove that the system is causal invariant:

 In[20]:=
 Out[20]=

Construct a Petri net representing a simple producer-consumer problem in concurrency theory:

 In[21]:=
 Out[21]=

Generate a graph showing branch pair ancestry:

 In[22]:=
 Out[22]=

Show the structure of the graph, without labels:

 In[23]:=
 Out[23]=

Generate a graph showing branch pair event ancestry:

 In[24]:=
 Out[24]=

Prevent identical states from being merged by including step numbers and state IDs:

 In[25]:=
 Out[25]=
 In[26]:=
 Out[26]=

Generate a graph of full evolution history, with all events included:

 In[27]:=
 Out[27]=

Generate a graph of full evolution history, with no merging of equivalent states:

 In[28]:=
 Out[28]=

Generate a graph of evolution history, with edges weighted by event multiplicity:

 In[29]:=
 Out[29]=

Generate a states graph with vertices weighted by their rate of occurrence on each time step:

 In[30]:=
 Out[30]=

Show the structure of the graph, without labels:

 In[31]:=
 Out[31]=

Generate a states graph with vertices weighted by the number of distinct evolution paths that lead to them:

 In[32]:=
 Out[32]=

Show the structure of the graph, without labels:

 In[33]:=
 Out[33]=

### Scope (12)

#### Rules and initial conditions (2)

MultiwayPetriNet accepts PetriNetObject expressions:

 In[34]:=
 Out[34]=

Or lists of places, transitions and arcs:

 In[35]:=
 Out[35]=

Or associations of places, transitions and arcs:

 In[36]:=
 Out[36]=

If MultiwayPetriNet is called without an explicit list of token numbers, it is assumed that each place contains no tokens:

 In[37]:=
 Out[37]=

#### Event selection functions (2)

Apply only the first possible event at each step:

 In[38]:=
 Out[38]=

Apply the first and last possible events at each step:

 In[39]:=
 Out[39]=

Apply an event selection function for a Petri net specified in list form:

 In[40]:=
 Out[40]=

Apply an event selection function for a Petri net specified in association form:

 In[41]:=
 Out[41]=

#### Specialized Petri net properties (8)

Construct a Petri net representing a simple producer-consumer problem in concurrency theory:

 In[42]:=
 Out[42]=

Show the list of Petri net objects obtained after two steps of multiway evolution:

 In[43]:=
 Out[43]=

Show the list of directed graph representations (with token counts represented graphically) after two steps of multiway evolution:

 In[44]:=
 Out[44]=

Show the list of directed graph representations (with token counts represented graphically, and with transition firings highlighted) after two steps of multiway evolution:

 In[45]:=
 Out[45]=

Show the list of directed graph representations (with token counts represented as vertex weights) after two steps of multiway evolution:

 In[46]:=
 Out[46]=

Show the list of directed graph representations (with token counts represented as vertex weights, and with transition firings highlighted) after two steps of multiway evolution:

 In[47]:=
 Out[47]=

Show the list of token numbers associated to each place after each firing, following two steps of multiway evolution:

 In[48]:=
 Out[48]=

Show the list of token numbers associated to each place after each firing (with the corresponding transition firings specified), following two steps of multiway evolution:

 In[49]:=
 Out[49]=

### Options (28)

#### State node rendering (5)

By default, states are labeled by their contents:

 In[50]:=
 Out[50]=

Use no labeling for states:

 In[51]:=
 Out[51]=

"StatesGraphStructure" yields the same result:

 In[52]:=
 Out[52]=

Use raw state names as node labels:

 In[53]:=
 Out[53]=

Use a named shape as each state label:

 In[54]:=
 Out[54]=

#### Event node rendering (4)

By default, both states and events are labeled by their contents:

 In[55]:=
 Out[55]=

Use no labels for states or events:

 In[56]:=
 Out[56]=

"EvolutionEventsGraphStructure" yields an equivalent result:

 In[57]:=
 Out[57]=

Use raw event expressions as their labels:

 In[58]:=
 Out[58]=

#### Initialization events (3)

By default, "AllEventsList" does not include initialization events:

 In[59]:=
 Out[59]=

The option "IncludeInitializationEvents" allows one to override this default:

 In[60]:=
 Out[60]=

Initialization events have special default rendering:

 In[61]:=
 Out[61]=

#### Graph layout options (2)

Place arrows in the middle of edges:

 In[62]:=
 Out[62]=

Generate an example of multiway Petri net evolution:

 In[63]:=
 Out[63]=

Force a layered digraph embedding:

 In[64]:=
 Out[64]=

#### Step numbers and state IDs (5)

By default, equivalent states are merged across all time steps:

 In[65]:=
 Out[65]=
 In[66]:=
 Out[66]=

Merging of equivalent states across different time steps can be prevented by including step numbers:

 In[67]:=
 Out[67]=
 In[68]:=
 Out[68]=

Merging of equivalent states at the same time step can be prevented by also including state IDs:

 In[69]:=
 Out[69]=
 In[70]:=
 Out[70]=

Step numbers and IDs also apply to events:

 In[71]:=
 Out[71]=

See the events:

 In[72]:=
 Out[72]=

#### State path weights (2)

Vertices of a states graph can be weighted by their relative rate of occurrence at each time step:

 In[73]:=
 Out[73]=

Vertices can also be weighted by the number of distinct evolution paths that lead to them:

 In[74]:=
 Out[74]=

#### MaxItems (2)

By default, "CausalGraphInstances" returns all possible causal graphs:

 In[75]:=
 Out[75]=

The number of causal graphs returned can be limited using MaxItems:

 In[76]:=
 Out[76]=

#### Predecessors and resolvents (2)

By default, "BranchPairsList" returns only a list of branch pairs:

 In[77]:=
 Out[77]=

Common predecessor states can be shown using "GivePredecessors":

 In[78]:=
 Out[78]=

Similarly, "BranchPairResolutionsList" by default lists only resolved and unresolved branch pairs:

 In[79]:=
 Out[79]=

Common resolvents of resolved branch pairs can be shown using "GiveResolvents":

 In[80]:=
 Out[80]=

Show both common predecessors and common resolvents, where appropriate:

 In[81]:=
 Out[81]=

#### Full branchial space (2)

By default, non-branch pair states are not shown as part of the branchial graph:

 In[82]:=
 Out[82]=

They can be shown using "IncludeFullBranchialSpace":

 In[83]:=
 Out[83]=

#### Graph options (1)

MultiwayPetriNet supports the same options as Graph:

 In[84]:=
 Out[84]=
 In[85]:=
 Out[85]=

Jonathan Gorard

## Version History

• 1.0.0 – 13 December 2021