Finding the Shortest Path

Summary

Given a virtual map as start graph, this graph grammar is able to compute the shortest path from some start to some goal position. The well-known Branch-and-Bound algorithm is realized by the graph rules. To solve the problem, a search tree is build up by tracing through possible paths beginning at the start node. The lengths of partial paths already found are compared and the minimal one is further expanded. Expansion continues until there is a path reaching the goal that is of length equal to or shorter than all incomplete paths terminating at open nodes.

Don't forget to select CSP w/o BJ as the completion strategy
and deselect dangling as one of the match conditions in the
Transform -> Options dialog before running this example.

A more detailed description of the following example is available as Postscript document with several comprehensive figures

Screenshots

To give you a first impression of what it's all about, the figure below shows the start graph of the grammar. It is a virtual city map comprising the four cities. The map also displays the paths existing between the cities and their respective length in the attribute d (for "distance").

The start rule is to select the Start and Goal nodes of the tour we want to find the shortest path for, and to initialize the auxiliary data structures. Actually, the Tree node becomes the root of the search tree that will be built up during the search.

The expand Level expands the node with the current minimum value that is, it generates the next level of the search tree. The negative application condition (NAC) ensures that no child is generated twice. The (partial) mappings from the left hand rule side to the NAC are again shown via equal numbers. This rule has to be applied as often as possible, until all children of all nodes with the current minimum value have been found.

The close Level deletes the connection between the Minlist node and the previously expanded node as only values about paths to open nodes are stored, and the previously expanded node is now closed. At the same time, the list entry of the path to the previously expanded node is deleted from the distance list dset at the Minlist node. The deletion is realized by a call to the Java OrderedSet class method s;remove from the Java library com.objectspace.jgl. The rule has to be applied as often as possible, until all previously expanded nodes are closed.

The actualize MinList generates an arc between the Minlist node and each new leaf node in the tree that has just been generated by the expand Level rule. The NAC ensures that only one arc will be generated between the Minlist node and each new leaf node. The distances between the start node and the new leaf nodes are stored in the Minlist attribute dlist containing all distances of partial paths. Again, a Java OrderedSet class method is called to add distances to dlist, namely the method s;add. Setting the Minlist attribute uptodate to false means that the computation of the minimum of the values in the distance list is now out of date. The correct minimum will be computed in the next rule calc Minimum. The rule to be applied as often as possible, until the Minlist node is connected to all leaves in the search tree.

Applying the rule calc Minimum the current minimum of all open paths, stored in the Minlist attribute min is actualized accordingly by calling the Java method calcMin(OrderedSet s) from the class Command. To ensure that the rule can be applied only once, right after the actualization of the distance list, the attribute uptodate is set to true again after one rule application.

The solution rule realizes the termination condition: If the goal node is reached in a current path and the distance from the start node to the goal node is equal to the minimum stored in the Minlist node attribute min, then the minimum is the solution, and the path in the search tree from the start node to the goal node represents the shortest connection between the two City nodes in the graph. The solution goal node in the search tree is marked by a Solution loop. This rule can be applied only once, because the Minlist node is removed when the solution is found.

Revision: November 23, 1999