Thursday, April 6, 2006

Archived News: 2006-04

2006-04 30:

The graph module takes a rather
non-directed approach to locating a path from
Node1 to NodeN. This is
fine if the path has no associated cost, but if
one is looking for the best path (where a path has
an associated cost), this laissez-faire
approach becomes problematic.

As I often need a efficient path in a graph, I
have added best_path/5 and other
supporting predicates that cannot be implemented
well operationally given the protocol of module
graph and submitted these changes to
the Mercury team for review. While they consider
these changes, I provide the implementation here
as module doug_graph, with an
associated example. Locating the best path in the
given example using
the naive path implementation took
over 20 seconds; the reimplementation here
completes the computations in less than a


The following Mercury compiler distributions are
available from here on request:


  • mercury-2006-04-26-rotd-sparc.sun.solaris2.8

These distributions include the extras/, the
samples/ (in extras/) and
the HTML documentation (in doc/).