RuleScript Part 2 : The Algorithm
In part one of this series, we looked at RuleScript at a high level – what it is, where it is and why you are likely to want to use it. As in the previous part of the article, you must remember that this is experimental and that it may therefore change, be removed or otherwise mutate. So don’t go betting the house on it. But from an intellectual perspective and because we want to be ahead of the curve, let’s dig in. We are going to create a route finding Project. It will help users find the quickest route from A to B. Go big or go home!
Dijkstra’s Algorithm to create a Route Finder
This algorithm (named after it’s inventor) can be traced back to a single event. Here is the man himself talking about it:
What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city? It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.
— Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001
So now we have the concept : finding the shortest path from A to B (or indeed A to D or anywhere else on a network “graph”. Take a look at the following as a simple example:
If we have to ask the question; “what is the shortest path between the start and the finish” (assuming the numbers represent the cost in minutes, or some other way to express cost), then this algorithm will help us find it.
The algorithm works by starting with the initial node (“Start” in the above example), and setting the distance to our “Finish” as infinity, or a very large number indeed. This is done to represent nodes that have “not yet been processed”. The algorithm then looks up the cost of going from the “Start” to each of the connecting points “A” and “B” (which would be 5 and 2). Then the algorithm continues, for example for A and B, calculating the cost of reaching their intersections as well. Assuming you are at A, for example, reaching D would cost 4+2 = 7, which is less than proceeding from A to C (4+5=9). And the algorithm continues in this way, using the lowest costing route across the diagram until we have a solution. If there is no solution (for example, if the nodes are not connected) then the result would be Infinity.
So the shortest path in this diagram is Start > A > D > Finish. This algorithm is not about the “most direct route” but about the “smallest cost”. As Wikipedia puts it – one of the weaknesses of this algorithm is it’s slowness in certain network topologies. But it will be just fine for our little experiment.
If you are interested in reading (a far better) explanation of the algorithm, you will enjoy the linked Wikipedia article.
Our RuleScript Implementation
In our Oracle Policy Automation Project we need the following pieces of information:
- Global attributes to hold the user’s choice of start, finish and an attribute to hold the time taken
- The list of nodes or “Stations” on our route map
- The list of nodes connected to those nodes
- A place to store the results of the algorithm as steps in the journey.
I went ahead and gaves names to all the attributes, entities and relationships so that I could reference them in the RuleScript file. So the header of my RuleScript file looks like this:
// RuleScript(theresults,resultstep,totaltime,resultstepnumber) <- (origin,destination, thestations,thechildstations,childstation_cost_minutes,child_station,station)
I am reading the origin, destination, the stations (thats the name of the containment relationship), the child stations of each station, the cost per child station, and the name of a station and I am writing to the results, the results steps, the total time and finally each step will be numbered as they need to be displayed in the correct order.
- In RuleScript, to access a relationship you use the following syntax
global.thestations.get(); // This gets the list of the station instances
thestationlist[s].thechildstations.get() // This gets the child stations for a given station at index "s"
This returns an Array representing the instances of the entity. I had to convert the array into an Object for ease of manipulation and logging using JSON. So in the end, I had an Object with a set of Child Objects to represent the Stations and their children.
- In order to be able to show the path used to the user at the end of the process, we need to remember the “parent” of each of the nodes we select. For example in our cheapest route, the parent of finish is D, and the parent of D is A, and the parent of A is start. Using this we can give the results to the user, except we would want to display it in reverse order (start > A > D > finish).
In the example above the result of the algorithm is stored in an array called myresult. I’m interested in only one area of that array, the “path”. Then I loop through that, according to how many steps there are. I copy the information into an array called resultarray by building an array of objects. Each object contains the result step (“A” or “D” or whatever), and a result step number and push them into my resultarray. I then use the resultarray to create instances of the result entity using
So I can create an Array, order it as I please, add an index and then pass it to Oracle Policy Automation to create instances. Stay tuned for part three, where we put it all together and build the Interview to go with it. When part three is published I will put the RuleScript file in the shop.