oracular (3) Graph::Grammar.3pm.gz

NAME

       Graph::Grammar - Graph grammar, i.e. rewriting method

SYNOPSIS

           use Graph::Grammar;
           use Graph::Undirected;

           my $graph = Graph::Undirected->new;

           # Create graph here

           my @rules = (
               [ sub { 1 }, ( sub { 1 } ) x 2, NO_MORE_VERTICES, sub { [ @_[1..3] ] } ],
           );

           parse_graph( $graph, @rules );

DESCRIPTION

       Graph::Grammar is a Perl implementation of a graph rewriting method (a.k.a. graph grammar).  Much of the
       API draws inspiration from Parse::Yapp, but instead of acting on text streams Graph::Grammar is oriented
       at graphs, as implemented in Perl's Graph module.  Graph::Grammar implements a single method
       parse_graph() which accepts an instance of Graph and an array of rules.  Every rule is evaluated for each
       vertex in a graph and, if a match is found, an action associated with the rule is executed.  A rule
       generally looks like this:

           [ $vertex_condition, @neighbour_conditions, $action ]

       Where:

       $vertex_condition is a subroutine reference evaluating the center node.  The subroutine is called with
       the graph in $_[0] and the vertex in <$_[1]>.  Subroutine should evaluate to true if condition is
       fulfilled.

       @neighbour_conditions is an array of subroutine references for the neighbours of the center node.  Inputs
       and outputs of each subroutine reference are the same as defined for $vertex_condition.  Every condition
       has to match at least one of the neighbours (without overlaps).  Thus the rule will automatically fail if
       the number of neighbours is less than @neighbour_conditions.  There can be more neighbours than
       @neighbour_conditions, but if strict number of neighbours is needed, look below for "NO_MORE_VERTICES".
       @neighbour_conditions can be empty.

       $action can be either a subroutine reference, or anything else.  If $action is a subroutine reference,
       then in the case of a match it is called with the graph in $_[0] and remaining @_ members being graph
       vertices corresponding to rule conditions.  That is, $_[1] is the center node, $_[2] is a vertice
       matching the first neighbour condition and so on.  If $action is not a subroutine reference, then it is
       cloned by Clone and inserted instead of the center vertex.

       There are two ways to request a particular number of neighbours for the central vertex.  First of them is
       to include an appropriate requirement into $vertex_condition.  Second is to put "NO_MORE_VERTICES" as the
       last element of @neighbour_conditions, i.e.:

           [ sub { 1 }, ( sub { 1 } ) x 2, NO_MORE_VERTICES, sub { [ @_[1..3] ] } ]

METHODS

   "parse_graph( $graph, @rules )"
       Perform graph rewriting of $graph.  Modifies the supplied graph and returns it upon completion.

   "NO_MORE_VERTICES"
       When used before the rule action in a rule, restricts the number of center vertex neighbours to vertex
       conditions.

AUTHORS

       Andrius Merkys, <merkys@cpan.org>