Work Order Management with Neo4j

I look terrible in a bikini (take my word for it) but I’d love me a Lamborghini. However, in order to afford nice things, we need to do as the song says and get to work…and we need to manage and prioritize that work somehow. Today, I’m going to show you how to build part of a work order management system with Neo4j.

I’m going to build an evented work order model. So let’s say our Order gets created, then based on what it is, pieces of Work need to happen. This work is performed by some Provider (whether internal or external) and that work can be broken down into Tasks that have dependencies on Events that have occurred. How would this look like in the graph? Glad you asked:

You may be thinking, hey where are the dependencies between the Tasks and the Events? Well, we don’t have the events until they occur, and we don’t know the order ahead of time. Plus our dependency may be complicated. If “ex” represents and event, a task may express dependencies as “(e1 and e2) or (e3 but not e4)”. So event 1 and 2 need to have happened, or just event 3 as long as event 4 didn’t happen.

If this sounds familiar to you it’s because I just blogged about a boolean logic rules engine in a recent blog post. We can take the same ideas, turn them side ways and find out for any given order, what tasks are completed, what tasks remain to be done and what events are tasks waiting on.

Let’s create some sample data and see how this works. First we’ll create some nodes:

 
    CREATE (o:Order {id:'o1'})
    CREATE (p1:Provider {name:'Provider One'})
    CREATE (p2:Provider {name:'Provider Two'})
    CREATE (w1:Work {id:'w1'})
    CREATE (w2:Work {id:'w2'})
    CREATE (t1:Task {id:'t1', requires:"(e1 & e2) | (e3 & !e4)"})
    CREATE (t2:Task {id:'t2'})
    CREATE (t3:Task {id:'t3'})
    CREATE (e1:Event {id:'e1'})
    CREATE (e4:Event {id:'e4'})

Then we will connect them together with some relationships:

 
    CREATE (o)-[:HAS_WORK]->(w1)
    CREATE (o)-[:HAS_WORK]->(w2)
    CREATE (p1)-[:PERFORMS]->(w1)
    CREATE (p2)-[:PERFORMS]->(w2)
    CREATE (w1)-[:HAS_TASK]->(t1)
    CREATE (w2)-[:HAS_TASK]->(t2)
    CREATE (w2)-[:HAS_TASK]->(t3)
    CREATE (e1)-[:FIRST]->(o)
    CREATE (e4)-[:PREVIOUS]->(e1)

This will create a graph with one work order, two providers, two work items, 3 tasks and 2 events that looks like this:

Tasks 2 and 3 do not have any event dependencies, they can happen at any time, but Task 1 requires some events to have occurred. Events 1 and 4 have occurred, can we proceed with completing this task? Let’s build a stored procedure to answer this question. We can start by finding the Order in question in the Graph:

 
    @Procedure(name = "com.maxdemarzi.order.tasks", mode = Mode.WRITE)
    @Description("CALL com.maxdemarzi.order.tasks(orderId) - get tasks for orders")
    public Stream<MapResult> orderTasks(@Name("orderId") String orderId) throws IOException {
        ArrayList<Map<String, Object>> tasks = new ArrayList<>();

        // We start by finding the order
        Node order = db.findNode(Labels.Order, "id", orderId);
        if (order != null) {

Once we have the order, we want to find all the events that are associated with this order and get their ids:

            // Create a traversal description that finds all events
            TraversalDescription eventTraversal = db.traversalDescription()
                    .depthFirst().expand(PathExpanders
                            .forTypesAndDirections(
                                    RelationshipTypes.FIRST, Direction.INCOMING,
                                    RelationshipTypes.PREVIOUS, Direction.INCOMING)
                    ).evaluator(Evaluators.excludeStartPosition());

            // Gather all of its event ids in to a Set
            Set<String> eventsIds = new HashSet<>();
            for (Path path : eventTraversal.traverse(order)) {
                String eventId = (String) path.endNode().getProperty("id");
                // If this is a negative event, remove existing event id
                if (eventId.charAt(0) == '-') {
                    eventsIds.remove(eventId.substring(1, eventId.length()));
                } else {
                    eventsIds.add(eventId);
                }
            }

You’ll notice I look for “negative events”. That is events that have an id that starts with a minus sign, for example “-ex2”. If I encounter these I remove the pre-existing event id from the set of events. In a real event based work flow system, your event stream should be immutable, so instead of simply deleting events, you would generate events that would undo existing events (using “-ex” ). Now that we have the events, let’s get the work that needs to be done, the providers who need to do it and the tasks they need to perform:

 
            // Find the work required to complete the order
            for (Relationship r1 : order.getRelationships(Direction.OUTGOING, RelationshipTypes.HAS_WORK)) {
                Node work = r1.getEndNode();
                // Figure out who will perform this work
                Node provider = work.getSingleRelationship(RelationshipTypes.PERFORMS, Direction.INCOMING).getStartNode();
                String providerName = (String) provider.getProperty("name");

                // For each work item, find the associated tasks
                for (Relationship r2 : work.getRelationships(Direction.OUTGOING, RelationshipTypes.HAS_TASK)) {
                    Node task = r2.getEndNode();
                    Map<String, Object> properties = task.getAllProperties();
                    properties.put("provider", providerName);

For each task, we want to find out if it can be performed independently or if it has some requirements. We will create a boolean expression and get all minimum sum-of-products solutions. Instead of creating Path nodes like in the previous blog post, we will simply save them as a string array property on the node itself, so we only ever have to calculate this once:

                    // If the task has requirements see what is left to be done
                    String requires = (String) task.getProperty("requires", null);
                    if (requires != null) {
                        // Have we already calculated dependencies?
                        String[] paths = (String[])task.getProperty("dependencies", null);
                        if (paths == null) {
                            // Calculate the dependencies and save them, so we only ever do this once.
                            BooleanExpression boEx = new BooleanExpression(requires);
                            boEx.doTabulationMethod();
                            boEx.doQuineMcCluskey();
                            boEx.doPetricksMethod();
                            paths = boEx.getPathExpressions().toArray(new String[]{});
                            task.setProperty("dependencies", paths);
                        } 

Just like before we check each path against the events that have occurred, except this time we will also capture the events that have not happened or the ones that need to be removed for this task to continue.

 
                        // Check our dependencies against the events of the order
                        ArrayList<HashMap<String, Object>> dependencies = new ArrayList<>();
                        for (String path : paths) {
                            String[] ids = path.split("[!&]");
                            char[] rels = path.replaceAll("[^&^!]", "").toCharArray();
                            Set<String> missing = new HashSet<>();
                            Set<String> remove = new HashSet<>();

                            // Check the first required event in the path
                            if (!eventsIds.contains(ids[0])) {
                                missing.add(ids[0]);
                            }

                            // Check the rest of the events
                            if (ids.length > 1) {
                                for (int i = 0; i < rels.length; i++) {
                                    if (rels[i] == '&') {
                                        if (!eventsIds.contains(ids[1 + i])) {
                                            missing.add(ids[1 + i]);
                                        }
                                    } else {
                                        if (eventsIds.contains(ids[1 + i])) {
                                            remove.add(ids[1 + i]);
                                        }
                                    }
                                }
                            }

Finally we add these to our properties and then to our task list to be returned from our method.

 
                            // Add the dependencies
                            HashMap<String, Object> dependency = new HashMap<>();
                            dependency.put("missing", missing);
                            dependency.put("remove", remove);
                            dependencies.add(dependency);
                        }
                        properties.put("dependencies", dependencies);
                    }
                    tasks.add(properties);

Now we can call our stored procedure:

 
CALL com.maxdemarzi.order.tasks('o1') yield value return value

and see in our answer that Tasks 2 and 3 done by Provider Two are ready to be performed, but Task 1 done by Provider One requires either Event 2 to occur or Event 3 to occur along with the removal of Event 4.

 
{
  "provider": "Provider Two",
  "id": "t3"
},
{
  "provider": "Provider Two",
  "id": "t2"
},
{
  "provider": "Provider One",
  "id": "t1",
  "requires": "(e1 & e2) | (e3 & !e4)",
  "dependencies": [
    {
      "missing": [
        "e2"
      ],
      "remove": []
    },
    {
      "missing": [
        "e3"
      ],
      "remove": [
        "e4"
      ]
    }
  ]
}

To add Event 2 to our Order, we can run this cypher query:

 
MATCH (order:Order {id:'o1'})<-[:FIRST|PREVIOUS*]-(last:Event) 
WHERE SIZE((last)<-[:PREVIOUS]-()) = 0
CREATE (e2:Event {id:'e2'}) 
CREATE (e2)-[:PREVIOUS]->(last)

…and if we run our stored procedure again we can see that Task 1 can now be performed. So there you have it. The source code as always is on github. Now get to work, sashay, shante!

Update: Instead of using both FIRST and PREVIOUS for the Event list, just use “NEXT_EVENT” as a single relationship type and then you can do:

 
MATCH (order:Order {id:'o1'})-[:NEXT_EVENT*0..]->(last) 
WHERE SIZE((last)-[:NEXT_EVENT]->()) = 0
CREATE (e2:Event {id:'e2'}) 
CREATE (last)-[:NEXT_EVENT]->(e2)

This feels a little bit cleaner right?

Tagged , , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: