[m-rev.] for review: library/digraph.m

[Julien Fischer]

On Fri, 7 Sep 2007, Mark Brown wrote:

> Estimated hours taken: 12
> Branches: main
>
> library/digraph.m:
> 	New module for directed graphs.  This is essentially the relation
> 	module but with more consistent terminology, and with argument
> 	ordering that suits state variables.  Other differences with the
> 	relation module:
>
> 	- The digraph_key type has a phantom type parameter, which helps to
> 	  ensure that keys from one digraph are not used with another digraph.
>
> 	- Exports a version of digraph.reduced which also returns the mapping
> 	  between the original digraph keys and the new ones.
>
> 	- The implementation of compose/3 doesn't try to use the "domain" and
> 	  "range" of the graphs (which is meaningless in the relation module
> 	  anyway).
>
> 	- New, more efficient algorithm for is_dag/1.  Correctness proof is
> 	  documented.
>
> 	- components/2 uses a more efficient data representation, and avoids
> 	  some intermediate data structures.
>
> 	- reduced/{2,3} avoids some intermediate data structures.
>
> 	- tc/2 avoids some intermediate data structures.
>
> library/library.m:
> 	Add the new module.
>
> library/relation.m:
> 	Document that this module is deprecated in favour of digraph.
>
> 	Flag relation.init/{0,1} as obsolete (it would be better to flag
> 	the entire module, or the relation/1 type as obsolete, but Mercury
> 	does not support this).
>
> compiler/*.m:
> profiler/*.m:
> 	Use the digraph module rather than the relation module.


Add an entry to the NEWS file as well.
The rest looks fine.

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------