The Problem

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)

The Solution

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.

For example

So how do we generate the Path objects from the Edge objects and find the one that has the shortest distance?

The Rule Flow

Connect Two Edges to form a simple path

Implementation

Extend Paths

Remove Unwanted Paths

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.

Remove all but the shortest path(s)

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.

Test Case

But how did we get Corticon to draw a picture of the graph?

Drawing a diagram of the Graph using Corticon

Assemble Graph Expression

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:

  1. Download and install Graphviz (it’s free)
  2. Start Graphviz
  3. Copy/paste the string for the chart into Graphviz
  4. Run graphviz

 

Draw Graph Automatically

Notes.

  1. you will need an instance of Graph in your payload
  2. The destination folder must already be created
  3. You will need to download and install Graphviz
  4. You will also need two extended operators

Automating the Entire process

If you want to add functionality to Studio to generate the picture for you here’s what you will need to do:

  1. Read the documentation on creating extended operators
  2. Create two operators
    1. WRITEFILE – to write the chart string to a text file
    2. RUNCOMMAND – to run any command

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

WriteFile

I use the return value to indicate success or failure.

RunCommand

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

Download PDF version.