Given a graph such as this
Find the shortest path connecting any two specified nodes.
For example the shortest path between a and e is a-b-e (3)
First we need a suitable vocabulary for defining the graph.
For example we could simply define a set of edges: that specifies the distance between two nodes.
And a set of paths that connect multiple nodes:
where the attribute ‘via’ contains a list of the nodes visited.
So how do we generate the Path objects from the Edge objects and find the one that has the shortest distance?
We need this additional entity in the vocabulary now:
If type is not ‘shortest’ then all paths from start to end will be listed.
Also, by omitting the Request object entirely we can get all possible paths between every pair of nodes.
Notice that in the implementation we have moved the test for ‘shortest’ to the filter and made it a precondition. That means this rule sheet does not even execute when type is other than ‘shortest’.
This doesn’t change the functionality but could improve efficiency if you are not looking for the shortest in a large graph. If there is no Request object this rule sheet will not execute.
But how did we get Corticon to draw a picture of the graph?
In my Corticon Studio I have a couple of extended operators that can export this code and run the Graphviz program to generate the picture. If you try running the rule above you probably won’t have my extended operators.
However you can still draw the pictures as follows:
If you want to add functionality to Studio to generate the picture for you here’s what you will need to do:
The entity called ExtendedOperator simply provides a result attribute that can be assigned when the extended operator is executed.
You will also need to write these operators in Java.
Here’s how I implemented them
I use the return value to indicate success or failure.
As you can see the java code is not complex but you will have to package these operators so they can be accessed by Studio.
That topic is a bit outside this article but is covered in the Corticon documentation.
When you are done your extended operators will show up something like this:
Download PDF version.