README for Math::PartialOrder
ABSTRACT
Math::PartialOrder - represent rooted finite partial orders in Perl.
REQUIREMENTS
* Carp
* Exporter
* Bit::Vector
for the Masked, Enum, CEnum, and CMasked subclasses
* FileHandle
for storage/retrieval
* Storable
for binary storage/retrieval
* GraphViz
for visualization
* File::Temp
for online visualization
DESCRIPTION
The Math::PartialOrder class is just a wrapper for
Math::PartialOrder::Std.
The classes in the Math::PartialOrder distribution all descend from
Math::PartialOrder::Base, and are capable of representing any finite
rooted partial order (or "datatype hierarchy"), although the single-root
condition is not enforced by Math::PartialOrder::Base itself.
There are a bunch of subclasses of Math::PartialOrder::Base, and they
all do pretty much the same things -- see the Math::PartialOrder::Base
manpage for details on what methods are available, their calling
conventions, and what it is exactly that they do. A brief summary of
each of the subclasses is given below.
Non-Determinism
Some methods will produce warnings if the hierarchy object is
"non-deterministic". For present purposes, a "non-deterministic"
hierarchy is any partial order which is not "consistently complete". See
Davey & Priestley (1990) for a definition of CCPOs, or just call the
"is_deterministic()" method on your hierarchy, and see what it says.
Hierarchy Subclasses
The hierarchy subclasses in the Math::PartialOrder distribution are
briefly described below. See the individual manpages for details.
* "Math::PartialOrder::Std"
Math::PartialOrder::Std is a basic iterative hierarchy
implementation, suitable for use with small hierarchies. It is the
most transparent of all the hierarchy subclasses, but also the least
efficient.
* "Math::PartialOrder::Caching"
Math::PartialOrder::Caching is a hierarchy implementation for
datatype hierarchies which caches the results of all inheritance-
and type-operation lookups using perl hashes, which improves
performance for small- to mid-sized hierarchies. It inherits from
"Math::PartialOrder::Std".
* "Math::PartialOrder::LRUCaching"
Math::PartialOrder::LRUCaching is a Math::PartialOrder
implementation for datatype hierarchies inheriting from
Math::PartialOrder::Caching, which caches the results of
inheritance- and type-operation-lookups in a "Tie::Cache" object,
which implements an LRU (least recently used) cache. This may
improve performance for large hierarchies which must repeatedly
perform the same lookups, or for applications using localized areas
of large hierarchies.
* "Math::PartialOrder::CMasked"
Math::PartialOrder::CMasked is a compiling Math::PartialOrder
implementation for static datatype hierarchies using Steffen Beyer's
Bit::Vector module for hierarchy operations and an internal
representation of immediate inheritance information as 'enum'
strings. It inherits directly from Math::PartialOrder::Base.
This subclass is suitable for mid- to large-sized hierarchies (>= 3K
types), assuming you don't need to perform a lot of destructive
operations on your hierarchies. Space usage is on the order O(n^2).
* "Math::PartialOrder::CEnum"
Math::PartialOrder::CEnum is a Math::PartialOrder implementation for
compiled datatype hierarchies using the Bit::Vector module for
hierarchy operations and an internal representation of hierarchy
information as 'enum' strings.
It differs from Math::PartialOrder::CMasked in that while the
CMasked subclass stores compiled hierarchy information directly as
Bit::Vector objects, the CEnum subclass stores such information as
'enum' strings, which should greatly reduce space requirements. Only
run-time memory usage is reduced, however -- compilation still
requires the full O(n^2) as for the CMasked subclass.
Hierarchy Persistence
The "Math::PartialOrder::Loader" module adds methods to the abstract
base class "Math::PartialOrder::Base" for storage and retrieval of
"Math::PartialOrder::*" objects, as well as for hierarchy-visualization.
Hierarchies may be stored/retrieved as text files, or as binary images.
Binary hierarchy images are compatible across all currently implemented
subclasses (but compiled information might not cross-load correctly).
See the Math::PartialOrder::Loader manpage for details.
AUTHOR
Bryan Jurish
COPYRIGHT
Copyright (c) 2001, Bryan Jurish. All rights reserved.
This package is free software. You may redistribute it and/or modify it
under the same terms as Perl itself.
See the LICENSE file that came with this distribution for details.
REFERENCES
B. A. Davey and H. A. Priestley, *Introduction to Lattices and Order*.
Cambridge University Press, Cambridge. 1990.
marmosets,
Bryan