AI::Menu 0.01

AI::Menu is a Perl object that generates Tree::Nary objects from directed graphs or a description of the function set.

The algorithm is not very efficient (approximately O(F^6), F being the number of functions). It is also not quite as intelligent as it should be. You should cache the results instead of repeatedly calculating them.

As the algorithm is optimized or more efficient algorithms are found, they will be incorporated. The interface for generating the trees should not change too much. The resulting object might become a Tree::Nary object encased in an AI::Menu object.

SYNOPSIS

use AI::Menu;

my $factory = new AI::Menu::Factory;

my $menu = $factory->generate($hash_of_functions);
my $menu = $factory->generate($hash_of_functions, $hash_of_categories);
my $menu = $factory->generate($graph);

METHODS

All of the following methods (except generate) are available in the new function when creating the AI::Menu::Factory object.

generate

This function does some housekeeping before calling a configurable module to generate the tree.

If called with a single hash reference, the hash is assumed to be a list of functions mapping to array references containing a list of categories. It is further assumed that the sets of function names and category names are disjoint. A closure is created for the leaf_q function which returns true if its argument is a key in the hash reference. The complete graph is created from this single hash reference: if a category can reach another category through a function, then an edge is inserted between the two categories. This edge is bidirectional.

If called with two hash references, the first hash is treated as before, but the second hash reference is considered a mapping of categories to categories. This second hash is used instead of automatically generating the information from the first hash.

If called with a single object that is not a hash reference, then the argument is considered a graph object (usually of Graph::Directed). The leaf_q function will need to be defined.

leaf_q

This function returns true if the argument represents a function (leaf in the graph). It returns false if the argument represents a category. This may be set either when the AI::Menu::Factory object is created or through a method call. The method call with no argument returns the current function.

maker

This is the package used to create the menu from the graph. The following call is made:

my $menu = $self -> {maker} -> new(
width => $self->{width},
weight_f => $self -> {weight_f},
leaf_q => $leafq,
);

return $menu -> generate_tree($g, $optscore);

The $optscore value is the score for the optimum tree. Once a tree is found with this score, searching should stop.

new

Creates an AI::Menu::Factory object. Optional arguments are key/value pairs taken from this list of methods except for generate and new.

weight_f

This function is used to calculate the edge weights in the graph. It is called with four arguments: the object generating the tree, the graph object, the originating vertex, the destination vertex. The function should return undef for an infinite weight.

width

This is the desired number of children per node. The optimal number (and default) is three.