/ 
Math-PartialOrder-0.01
River stage zero No dependents
/ Math::PartialOrder

NAME

Math::PartialOrder::Base - abstract base class for datatype hierarchies.

SYNOPSIS

#
# Pick your subclass (you only need 1)
#
use Math::PartialOrder::Std;        # ok for small hierarchies
use Math::PartialOrder::Caching;    # caches *everything* in perl hashes
use Math::PartialOrder::LRUCaching; # uses Tie::Cache for an LRU cache
use Math::PartialOrder::CMasked;    # for large, static hierarchies
use Math::PartialOrder::CEnum;      # ... also, but uses less runtime memory

#
# Populate your hierarchy
#
$h = Math::PartialOrder::Std->new({root=>'whatever'});  # make a new hierarchy

$h->add('yup');  # 'yup' is a new child-type of 'whatever'
$h->add('nope'); # ... and so is 'nope'

$h->add(qw(maybe yup nope));    # 'maybe' inherits from 'yup' and 'nope'
$h->add(qw(maybenot yup nope)); # ... and so does 'maybenot'

$h->add(qw(whoknows maybe maybenot)); # 'whoknows' is all of the above

#
# Do stuff with it
#
@types = $h->types;              # get all the types in the hierarchy
@yups = $h->descendants('yup');  # ... or just those that are 'yup's
@kids = $h->children('yup');     # ... or those that are directly 'yup's

@ancs = $h->ancestors('yup');    # get all ancestors of 'yup'
@prts = $h->parents('nope');     # ... or just the direct parents

@sorted = $h->subsort(@types);   # sort @types by inheritance

#
# Type Operations
#
@lubs = $h->lub(qw(maybe maybenot));  # @lubs = ('whoknows')
@glbs = $h->glb(qw(yup nope));        # @glbs = ('whatever')

$lub = $h->njoin(qw(maybe maybenot)); # $lub = 'whoknows'
$lub = $h->njoin(qw(yup nope));       # ... non-CCPO produces a warning

$glb = $h->nmeet(qw(yup nope));       # $glb = 'whatever'
$glb = $h->nmeet(qw(maybe maybenot)); # ... non-CCPO produces a warning

#
# Persistence
#
use Math::PartialOrder::Loader;

$h->save('h.gt');      # save to text file
$h->load('h.gt');      # load from text file

$h->store('h.bin');    # store binary image
$h->retrieve('h.bin'); # retrieve binary image

# ... and much, much (too much) more ....

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, 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 Math::PartialOrder::Base 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.

Terminology

The Math::PartialOrder distribution was previously known (to some) as QuD::Hierarchy, since it was designed for the representation of "datatype hierarchies" or "conceptual hierarchies". Since I have very little desire to re-write all of the documentation, here are some handy synonyms:

  my terminology <-> order-theoretic terminology
     "hierarchy" <-> "partial order"
          "type" <-> "element"
          "root" <-> "bottom element"
        "parent" <-> "covered element"
         "child" <-> "covering element"
  "has ancestor" <-> "is greater than"
"has descendant" <-> "is less than"

Formal definitions of the order-theoretic terms can be found in Davey & Priestley (1990). I hope that my terms are a bit more intuitive to those familiar with datatype- and class-hierarchy systems.

Non-Determinism

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 distributed with the Math::PartialOrder module 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.

    Really, Math::PartialOrder is just an alias for Math::PartialOrder::Std.

  • 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::Std, 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 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 Math::PartialOrder::Loader for details.

ACKNOWLEDGEMENTS

perl by Larry Wall.

AUTHOR

Bryan Jurish <jurish@ling.uni-potsdam.de>

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 ALSO

B. A. Davey and H. A. Priestley, Introduction to Lattices and Order. Cambridge University Press, Cambridge. 1990.

perl(1). Math::PartialOrder::Base(3pm). Math::PartialOrder::Loader(3pm). Math::PartialOrder::Std(3pm). Math::PartialOrder::Caching(3pm). Math::PartialOrder::LRUCaching(3pm). Math::PartialOrder::CMasked(3pm). Math::PartialOrder::CEnum(3pm). Data::Dumper(3pm).