I have been looking for a way to do some dependency management within an application I am working on. Specifically, if a row is changed in a database table in my authoritative data source, a set of jobs must be triggered off to propagate the change into a number of secondary data sources. Looking to see what was available, I googled for "Java dependency manager", and got back a result for Apache Ivy, which is a tool tightly integrated with Ant to provide Maven style dependency management. What I was after was a way to build my own Maven Reactor, but after reading through the Ivy documentation, I realized that I was barking up the wrong tree, and what I really wanted was a workflow engine.
Going through the list of available workflow engines, the Bossa engine caught my eye because it was based on Petri Net notation, something I was marginally familiar with.
The Bossa Manifesto explains (in non-mathematical terms) how a Petri Net can be used to model a workflow. In a nutshell, a Petri Net is a graph with nodes which can either be a Place or a Transition connected by directed edges. Each edge has a weight which determines how likely it is to fire. Bossa models the weights as the integers 1 (true) or 0 (false), or as Javascript expressions that evaluate to true or false, which means that either the edge can either fire or not fire depending on the value of the weight.
A back-of-the-envelope sketch of the processes I wanted to trigger off looks something like this.
The equivalent Petri Net, with edge weights set as 1, 0 or a Javascript expression that will evaluate to true or false is shown below. The idea is that each Transition is associated with a Closure object that will execute, and will set the ${Transition.name}_OK Javascript variable to true. Before a Transition is fired from a Place, the edge weight will be evaluated to determine if the Transition can or cannot fire. Similarly, once a Transition is completed, the edge weight connecting it and its neighboring Place nodes will be evaluated to check if it can transition over to the Place node.
I installed Bossa and its dependencies, and followed along with the API-Howto as far as it took me. However, I hit a wall when I needed to get the next Transitions to fire after the initial Transition, so I could traverse the Petri Net. The methods I tried (after looking at the Bossa shell example), returned me Transitions which did not agree with what I specified in the Petri Net. I wasn't sure if it was a bug or if I was missing something, so I tried to look up the mailing lists, but their list server was off the air at the time of this writing. By this time, I understood the abstraction well enough, so after about 2 days of trying out various things, I decided that I could whip up a few classes that would serve my purpose, using an approach similar to Bossa's, but without the complexity it exposed (because it is more general purpose). This post describes this code.
Because a Petri Net is a collection of Places and Transitions connected by Edges, I built classes that model a PetriNet, Place, Transition and Edge. The attempt was to keep the API as similar to Bossa's (so I could reuse as much of my testing code as possible). Here they are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | // Place.java
package com.mycompany.myapp.workflow;
import java.util.ArrayList;
import java.util.List;
/**
* Models a Place node in a Petri Net.
*/
public class Place {
private String name;
private List<Transition> inputTransitions = new ArrayList<Transition>();
private List<Transition> outputTransitions = new ArrayList<Transition>();
public Place(String name) {
setName(name);
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<Transition> getInputTransitions() {
return inputTransitions;
}
public void addInputTransition(Transition transition) {
inputTransitions.add(transition);
}
public List<Transition> getOutputTransitions() {
return outputTransitions;
}
public void addOutputTransition(Transition transition) {
outputTransitions.add(transition);
}
}
|
The Place object has a constructor to set its name, and input and output Transitions. A Place is usually constructed from the PetriNet object.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | // Transition.java
package com.mycompany.myapp.workflow;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import org.apache.bsf.BSFManager;
import org.apache.commons.collections15.Closure;
import org.apache.commons.lang.math.NumberUtils;
/**
* Models a Transition node in a Petri Net.
*/
public class Transition {
private String name;
private Closure<Map<String,Boolean>> closure;
private List<Edge> inputs = new ArrayList<Edge>();
private List<Edge> outputs = new ArrayList<Edge>();
public Transition(String name, Closure<Map<String,Boolean>> closure) {
this.name = name;
this.closure = closure;
}
public String getName() {
return name;
}
public Closure<Map<String,Boolean>> getClosure() {
return closure;
}
public void addInput(Place place, String weightExpr) {
place.addOutputTransition(this);
Edge edge = new Edge();
edge.setPlace(place);
edge.setEdgeWeightExpr(weightExpr);
inputs.add(edge);
}
public List<Edge> getInputs() {
return inputs;
}
public void addOutput(Place place, String weightExpr) {
place.addInputTransition(this);
Edge edge = new Edge();
edge.setPlace(place);
edge.setEdgeWeightExpr(weightExpr);
outputs.add(edge);
}
public List<Edge> getOutputs() {
return outputs;
}
public boolean isFireable(Map<String,Boolean> attributes) throws Exception {
boolean fireable = true;
for (Edge edge : inputs) {
String edgeWeightExpr = edge.getEdgeWeightExpr();
if (NumberUtils.isNumber(edgeWeightExpr)) {
fireable = (edgeWeightExpr.equals("1") ? true : false);
} else {
Boolean canFire = evaluate(attributes, edgeWeightExpr);
fireable = fireable && canFire;
}
}
return fireable;
}
public boolean canReachTo(Place place, String weightExpr, Map<String,Boolean> attributes)
throws Exception {
if (NumberUtils.isNumber(weightExpr)) {
return (weightExpr.equals("1") ? true : false);
} else {
Boolean canReach = evaluate(attributes, weightExpr);
return canReach;
}
}
private Boolean evaluate(Map<String,Boolean> attributes, String edgeWeightExpr)
throws Exception {
BSFManager bsf = new BSFManager();
for (String key : attributes.keySet()) {
bsf.declareBean(key, attributes.get(key), Boolean.class);
}
Boolean result = (Boolean) bsf.eval(
"javascript", "transition", 0, 0, edgeWeightExpr);
return result;
}
}
|
The Transition object has a constructor that sets a name and a Closure object that is responsible for doing the work represented by the Transition. In addition, it provides methods to determine if it can be fired and the Places it can transition to, given the current state of the Petri Net (represented by the attributes object, which is like a symbol table for the Javascript variables being used).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | // Edge.java
package com.mycompany.myapp.workflow;
import org.apache.commons.lang.math.NumberUtils;
/**
* Models and Edge connecting a Place and Transition in a Petri Net.
*/
public class Edge {
private Place place;
private String edgeWeightExpr;
public Place getPlace() {
return place;
}
public void setPlace(Place place) {
this.place = place;
}
public String getEdgeWeightExpr() {
return edgeWeightExpr;
}
public void setEdgeWeightExpr(String edgeWeightExpr) {
if (NumberUtils.isNumber(edgeWeightExpr)) {
if (!edgeWeightExpr.equals("1") && !edgeWeightExpr.equals("0")) {
throw new IllegalArgumentException("Numeric edge weights can only be 0 or 1");
}
}
this.edgeWeightExpr = edgeWeightExpr;
}
}
|
The Edge object models the directed arcs connecting a Place and a Transition. These are all connected together using the PetriNet class shown below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 | // PetriNet.java
package com.mycompany.myapp.workflow;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.apache.commons.collections15.Closure;
/**
* Models a workflow as a Petri Net. See the Bossa Manifesto for details about
* what a Petri Net is and how it can be used to model a workflow. In a nutshell,
* a Petri Net is a graph of Places and Transitions connected by Edges with
* numeric weights. In this implementation, edge weights are represented by 0 and
* 1 (for false and true respectively) or Javascript expressions that evaluate to
* true or false.
* @link {http://www.bigbross.com/bossa/overview.shtml}
*/
public class PetriNet {
private Map<String,Place> places = new HashMap<String,Place>();
private List<Transition> transitions = new ArrayList<Transition>();
private String initialPlaceName;
private Map<String,Boolean> attributes = new HashMap<String,Boolean>();
/**
* Add a Place object to the Petri net.
* @param place the Place to be added.
* @return the Place that was added.
*/
public Place addPlace(Place place) {
places.put(place.getName(), place);
return place;
}
/**
* Overloaded version of {@see PetriNet#addPlace(Place)} to specify the
* initial Place object. A Petri net can have only a single start place.
* This is the Place from which the traversal will be started.
* @param isStartPlace true if this is the start Place.
* @return the Place that was added.
*/
public Place addPlace(Place place, boolean isStartPlace) {
if (isStartPlace) {
if (initialPlaceName != null) {
throw new IllegalArgumentException("Initial Place is already set");
}
initialPlaceName = place.getName();
}
return addPlace(place);
}
/**
* Return a List of Place objects in the Petri Net.
* @return a List of Place objects.
*/
public List<Place> getPlaces() {
return new ArrayList<Place>(places.values());
}
/**
* Add a Transition object to the Petri Net.
* @param transition the Transition to add.
* @return
*/
public Transition addTransition(Transition transition) {
transitions.add(transition);
return transition;
}
/**
* Returns a List of Transitions mapped into the Petri net.
* @return a List of all Transition objects.
*/
public List<Transition> getTransitions() {
return transitions;
}
/**
* Allows setting initial values for Javascript variables that are reset
* during the traversal of the Petri net by the Closures mapped to the
* Transition objects.
* @param variable the name of the Javascript variable.
* @param value the initial value (usually false).
*/
public void setAttributeValue(String variable, boolean value) {
attributes.put(variable, value);
}
/**
* Returns the Javascript variables and their current values in the Petri Net.
* @return the Map of Javascript variable names and their current values.
*/
public Map<String,Boolean> getAttributes() {
return attributes;
}
/**
* Traverse a Petri Net in either a depth first or breadth first order. Sometimes
* it may make sense to order the transitions so that the larger jobs get completed
* first, so this parameter could be used to influence the ordering of the jobs.
* When a Transition is encountered, the Closure associated with the Transition
* will be executed, so a traversal will end up running all the jobs. If you wish
* to test without actually running any jobs, consider using a MockClosure object.
* This method delegates to the recursive traverse_r().
* @param depthFirst true or false. If true, the Petri Net will be traversed depth
* first, and if false, it will be traversed breadth first.
* @throws Exception if one is thrown.
*/
public void traverse(boolean depthFirst) throws Exception {
traverse_r(null, depthFirst);
}
/**
* Returns a List of Transitions that may be reached from the specified Place
* on the Petri net. All output Transitions that are immediate neighbors of the
* specified Place are considered, and reachability is determined by evaluating
* the weight of the edge separating the Place and the Transition.
* @param place the Place from which to determine next fireable Transitions.
* @return a List of Transition objects that can be fired from the Place.
* @throws Exception if one is thrown.
*/
protected List<Transition> getNextFireableTransitions(Place place) throws Exception {
List<Transition> fireableTransitions = new ArrayList<Transition>();
if (place == null) {
place = places.get(initialPlaceName);
}
List<Transition> outputTransitions = place.getOutputTransitions();
for (Transition outputTransition : outputTransitions) {
if (outputTransition.isFireable(attributes)) {
fireableTransitions.add(outputTransition);
}
}
return fireableTransitions;
}
/**
* Returns a List of Places which can be reached from the specified Transition.
* All output edges of the specified Transition are considered, and reachability
* is determined by evaluating the weights of the Edge connecting the Transition
* and the neighboring Place objects.
* @param transition the Transition from which to determine reachable Places.
* @return a List of reachable Places from the Transition.
* @throws Exception if one is thrown.
*/
protected List<Place> getNextReachablePlaces(Transition transition) throws Exception {
List<Place> reachablePlaces = new ArrayList<Place>();
if (transition == null) {
return reachablePlaces;
}
List<Edge> outputEdges = transition.getOutputs();
for (Edge outputEdge : outputEdges) {
Place place = outputEdge.getPlace();
if (transition.canReachTo(place, outputEdge.getEdgeWeightExpr(), attributes)) {
reachablePlaces.add(place);
}
}
return reachablePlaces;
}
private void traverse_r(Place place, boolean depthFirst) throws Exception {
List<Transition> transitions = getNextFireableTransitions(place);
if (transitions.size() == 0) {
return;
}
if (depthFirst) {
// depth first traversal
for (Transition transition : transitions) {
Closure<Map<String,Boolean>> closure = transition.getClosure();
closure.execute(getAttributes());
List<Place> reachablePlaces = getNextReachablePlaces(transition);
for (Place reachablePlace : reachablePlaces) {
traverse_r(reachablePlace, depthFirst);
}
}
} else {
// breadth first traversal
List<Place> reachablePlaces = new ArrayList<Place>();
for (Transition transition : transitions) {
Closure<Map<String,Boolean>> closure = transition.getClosure();
closure.execute(getAttributes());
reachablePlaces.addAll(getNextReachablePlaces(transition));
}
for (Place reachablePlace : reachablePlaces) {
traverse_r(reachablePlace, depthFirst);
}
}
}
}
|
Client code that wants to trigger the workflow will set up the PetriNet object, and then call its traverse() method. The Closures associated with each Transition will be called as the PetriNet is traversed. Traversal can happen either in Depth First or Breadth First order. Here is a JUnit test that illustrates the usage:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | // PetriNet.java
package com.mycompany.myapp.workflow;
import org.junit.Before;
import org.junit.Test;
/**
* Petri Net traversal tests.
*/
public class PetriNetTest {
private PetriNet petriNet;
@Before
public void setUp() throws Exception {
petriNet = new PetriNet();
// add places
Place p0 = petriNet.addPlace(new Place("p0"), true);
Place p1 = petriNet.addPlace(new Place("p1"));
Place p2 = petriNet.addPlace(new Place("p2"));
Place p3 = petriNet.addPlace(new Place("p3"));
Place p4 = petriNet.addPlace(new Place("p4"));
Place p5 = petriNet.addPlace(new Place("p5"));
Place p6 = petriNet.addPlace(new Place("p6"));
Place p7 = petriNet.addPlace(new Place("p7"));
Place p8 = petriNet.addPlace(new Place("p3"));
// add transition
Transition t01 = petriNet.addTransition(new Transition("t01", new MockClosure("t01")));
Transition t12 = petriNet.addTransition(new Transition("t12", new MockClosure("t12")));
Transition t23 = petriNet.addTransition(new Transition("t23", new MockClosure("t23")));
Transition t24 = petriNet.addTransition(new Transition("t24", new MockClosure("t24")));
Transition t345 = petriNet.addTransition(new Transition("t345", new MockClosure("t345")));
Transition t16 = petriNet.addTransition(new Transition("t16", new MockClosure("t16")));
Transition t67 = petriNet.addTransition(new Transition("t67", new MockClosure("t67")));
Transition t578 = petriNet.addTransition(new Transition("t578", new MockClosure("t578")));
// connect transitions to places
t01.addInput(p0, "1");
t01.addOutput(p1, "T01_OK");
t12.addInput(p1, "1");
t12.addOutput(p2, "T12_OK");
t23.addInput(p2, "1");
t23.addOutput(p3, "T23_OK");
t24.addInput(p2, "1");
t24.addOutput(p4, "T24_OK");
t345.addInput(p3, "T23_OK && T24_OK");
t345.addInput(p4, "T23_OK && T24_OK");
t345.addOutput(p5, "T345_OK");
t16.addInput(p1, "1");
t16.addOutput(p6, "T16_OK");
t67.addInput(p6, "1");
t67.addOutput(p7, "T67_OK");
t578.addInput(p5, "T345_OK && T67_OK");
t578.addInput(p7, "T345_OK && T67_OK");
t578.addOutput(p8, "T578_OK");
// initialize Javascript attributes
petriNet.setAttributeValue("T01_OK", false);
petriNet.setAttributeValue("T12_OK", false);
petriNet.setAttributeValue("T23_OK", false);
petriNet.setAttributeValue("T24_OK", false);
petriNet.setAttributeValue("T345_OK", false);
petriNet.setAttributeValue("T16_OK", false);
petriNet.setAttributeValue("T67_OK", false);
petriNet.setAttributeValue("T578_OK", false);
}
@Test
public void testTraversePetriDepthFirst() throws Exception {
System.out.println("Depth first traversal");
petriNet.traverse(true);
}
@Test
public void testTraversePetriBreadthFirst() throws Exception {
System.out.println("Breadth first traversal");
petriNet.traverse(false);
}
}
|
If you are familiar with the Bossa API, you will notice the similarity of the code in the @Before method with how Bossa does it. The setup code is verbose, but Bossa has the ability to consume XML configuration files, which seems to be a better approach anyway, since designing and maintaining the workflow would probably be easier with XML than with code. I have plans to do this also at some point in the future.
For testing, I built a MockClosure object which prints the name of the Transition it was instantiated with, and sets the appropriate Javascript attribute to true once it is done.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | // MockClosure.java
package com.mycompany.myapp.workflow;
import org.apache.commons.collections15.Closure;
import org.apache.commons.lang.StringUtils;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import java.util.Map;
/**
* A mock closure which is instantiated with the process name, and which prints out
* the name of the process in its execute() method, and updates the ${processName}_OK
* attribute to true to indicate to the PetriNet that it completed successfully.
*/
public class MockClosure implements Closure<Map<String,Boolean>> {
private final Log log = LogFactory.getLog(getClass());
private String processName;
public MockClosure(String processName) {
this.processName = processName;
}
public void execute(Map<String,Boolean> attributes) {
System.out.println("Executing " + processName);
attributes.put(StringUtils.upperCase(processName) + "_OK", new Boolean(true));
}
}
|
So, running the test returns the tasks being executed in depth first and breadth first order, as shown below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | Depth first traversal
Executing t01
Executing t12
Executing t23
Executing t24
Executing t345
Executing t16
Executing t67
Executing t578
Breadth first traversal
Executing t01
Executing t12
Executing t16
Executing t23
Executing t24
Executing t345
Executing t345
Executing t67
Executing t578
|
Of course, the workflow I tested with is rather simple, and does not take into account the additional workflow that would need to be in place to take care of error handling. However, this would be fairly simple to do once we know what we want to do (go back to previous step or go back to start) when one of the closures did not succeed normally.
Apart from the Petri Net abstraction, thanks to the Bossa project also for illustrating how to evaluate Javascript expressions using Apache Bean Scripting Framework (BSF).
6 comments (moderated to prevent spam):
Hi!
My nerdy score matches your!
Please search Google for "project-open petri-net", and you'll get some background information on the workflow system integrated into our system (]project-open[, http://www.project-open.com/).
We've got a graphical WF editor based on ImageMagick, but that's no cool... Did you hear about a Flash or Javascript editor or something like this?
Cheers!
Frank
Hi Fraber, nice to hear from a fellow nerd :-).
Thanks for the link, I will look at it. There is a Java based workflow editor used by OSWorkflow and also one from Bossa, but I haven't used it that much (my workflow is a small one, and I modeled it manually).
heyy Sujit...need your help??
I am supposed to do a project on Petrinets.
the project is to develop a Petrinets tool used to edit and run place transition nets...
Can you please let me know how i could start with this project .....I have knowledge in Java and C and jsp but not an expert though.....
Please Help!!!
Regards
Vandana
Hi Vandana, best of luck on your project. I don't think you need a huge amount of special knowledge on Petri nets to do what you are doing...what you probably want to read up is the wikipedia page(s) on this (linked to from my blog, or just google for it). You may also consider using code from Bossa's GUI tool as a learning aid, they have a GUI tool to manipulate a workflow, which they model as a Petri Net.
Hi Sujit!
Great code on Petri Nets!
Do you think that I can use and extend it for my bachelor thesis? I will reference your blog entry and yourself as developer/author.
Any modifications I make would obviously flow back to you.
Please let me know what you think.
Felipe
Hi Felipe, thanks and feel free to use this post as the basis for your thesis if you find it worthy enough. You don't have to do the code fix flow back thing, but if you cite the post I would appreciate that very much. Good luck on your thesis and do send me a URL to it when done, so I can link to it.
Post a Comment