Jess Information

Jess Home
Jess 7 Features
Download Now!
Online Demo

Mailing List
Jess Wiki

More information Related Web Sites
User Contributions
JSR94 Info
Developer's Log
About This Site

JESS ®, the Rule Engine for the JavaTM Platform

Jess Wiki: Fan Out Zoom In


Wolfgang Laun
Wolfgang Laun a-t thalesgroup com

Name: Fan Out, Zoom In

Intent: Create partial results related to many facts, then single out the solution.


Whenever facts relate to a set of connected nodes, chances are that there is an algorithm where you start at one node and have to search for a solution, or even an optimum solution.

The example given below illustrates the algorithm for finding the shortest path from A to B, given a set of cities, each of which has some immediate neighbors at a known distance.


Similar approaches may be considered for related tasks. The rules for finding the adjoining nodes may vary. It might be required to find all paths rather than the shortest path.

Sample code:

Given a set of some cities and, for each of them, its immediate neighbors and the distances between them, design an algorithm that will determine the shortest route between any two of the cities.

The solution is achieved in two stages. After creating the initial fact, the Advance rule begins to fire, creating similar but more "advanced" facts for the neighbors of the starting point, and proceeding from there. The accumulated mileage (and the list of cities visited so far) is carried along. Since there is more than one way to Rome (Italy or even NY), propagated results are bound to meet at some city which can be reached in more than one way. Rule Minimum takes care of this, retracting the longer of the two itineraries.

After the dust of going places has settled down, the second stage is triggered by focussing on the module RESULT. Rule Clean removes all the tracks left all over the countryside. The winner is announced by rule Show.

Although some of the cities may sound familiar, readers are advised not to base any travel decisions on the numbers given in this program :-)

(load-function at.laune.jess.Interpolate)
;;   Atlanta  -5-  Boston   -6-  Columbus -4-  Detroit
;;     6|     /14    8|     /14    10|    /20   11|
;;    Erie    -4-  Fresno   -7-   Gary    -8-  Houston
;;     4|     /13    3|     /16     8|    /12    8|
;;Indianapolis -8- Jackson  -8-  Kingston -8-  London
;;     5|     /16    6|     /17     4|    /17    5|
;;   Memphis  -7-  Newark   -5-   Omaha   -6-  Phoenix

(deftemplate Dist
    (slot t1    (type STRING))
    (slot t2    (type STRING))
    (slot miles (type INTEGER)))

(deftemplate Go
    (slot from (type STRING))
    (slot dest (type STRING))
    (slot at   (type STRING))
    (slot miles (type INTEGER)(default 0))
    (multislot route)

(deffacts CityToCity
    (Dist (t1 Atlanta     )(t2 Boston      )(miles  5))
    (Dist (t1 Atlanta     )(t2 Erie        )(miles  6))
    (Dist (t1 Boston      )(t2 Columbus    )(miles  6))
    (Dist (t1 Boston      )(t2 Fresno      )(miles  8))
    (Dist (t1 Columbus    )(t2 Detroit     )(miles  4))
    (Dist (t1 Columbus    )(t2 Gary        )(miles 10))
    (Dist (t1 Detroit     )(t2 Houston     )(miles 11))
    (Dist (t1 Erie        )(t2 Fresno      )(miles  4))
    (Dist (t1 Erie        )(t2 Boston      )(miles 14))
    (Dist (t1 Erie        )(t2 Indianapolis)(miles  4))
    (Dist (t1 Fresno      )(t2 Gary        )(miles  7))
    (Dist (t1 Fresno      )(t2 Columbus    )(miles 14))
    (Dist (t1 Fresno      )(t2 Jackson     )(miles  3))
    (Dist (t1 Gary        )(t2 Houston     )(miles  8))
    (Dist (t1 Gary        )(t2 Detroit     )(miles 20))
    (Dist (t1 Gary        )(t2 Kingston    )(miles  8))
    (Dist (t1 Houston     )(t2 London      )(miles  8))
    (Dist (t1 Indianapolis)(t2 Jackson     )(miles  8))
    (Dist (t1 Indianapolis)(t2 Fresno      )(miles 13))
    (Dist (t1 Indianapolis)(t2 Memphis     )(miles  5))
    (Dist (t1 Jackson     )(t2 Kingston    )(miles  8))
    (Dist (t1 Jackson     )(t2 Newark      )(miles  6))
    (Dist (t1 Jackson     )(t2 Gary        )(miles 16))
    (Dist (t1 Kingston    )(t2 London      )(miles  8))
    (Dist (t1 Kingston    )(t2 Houston     )(miles 12))
    (Dist (t1 Kingston    )(t2 Omaha       )(miles  4))
    (Dist (t1 London      )(t2 Phoenix     )(miles  5))
    (Dist (t1 Memphis     )(t2 Newark      )(miles  7))
    (Dist (t1 Memphis     )(t2 Jackson     )(miles 16))
    (Dist (t1 Newark      )(t2 Omaha       )(miles  5))
    (Dist (t1 Newark      )(t2 Kingston    )(miles 17))
    (Dist (t1 Omaha       )(t2 Phoenix     )(miles  6))
    (Dist (t1 Omaha       )(t2 London      )(miles 17)))


;; Invert all distances
(defquery Distances
    ?dist <- (Dist (t1 ?t1)(t2 ?t2)))

(bind ?res (run-query* Distances))
(while (?res next)
    (duplicate (?res get dist) (t1 (?res get t2))(t2 (?res get t1))))

;; How to go from one city to all immediate neighbors
(defrule Advance
    ?g <- (Go   (from ?from)(dest ?dest )(at ?at)(miles ?tofrom)(route $?route))
    ?d <- (Dist (t1 ?at)(t2 ?t2)(miles ?miles))
    (bind ?msum (+ ?tofrom ?miles)) 
    (bind ?eroute (list $?route ?t2))
    (assert (Go (from ?from)(dest ?dest)(at ?t2)(miles ?msum)(route ?eroute)))

;; Eliminate the longer of two routes
(defrule Minimum
    ?g1 <- (Go (from ?from)(dest ?dest )(at ?at)(miles ?m1))
    ?g2 <- (Go (from ?from)(dest ?dest )(at ?at)(miles ?m2 & ~ ?m1))
    (retract (if (< ?m1 ?m2) then ?g2 else ?g1))

(defmodule RESULT)

;; Remove all intermediary results
(defrule Clean
    ?g <- (Go (dest ?dest)(at ?at & ~ ?dest))
    (retract ?g)

;; Display the solution.
(defrule Show
    ?g <- ( Go (from ?from) (dest ?dest)(at ?dest)(miles ?miles)(route $?route))
    (printout t ?from " to " ?dest ": " ?miles " miles. " ?route crlf)
    (retract ?g)

;; Launcher for computing a minimum distance between two cities.
(deffunction compDist (?from ?dest)
    (assert (Go (from ?from)(dest ?dest)(at ?from)(route ?from)))
    (focus RESULT)

(compDist Indianapolis Columbus)

Front Page | Sandbox | Recent Changes | Powered by Friki | Last Edited: 03 July 2007