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 vertex.  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 vertex.
       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 vertex, $_[2] is a vertex
       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] ] } ]

       Edge conditions are also supported and they always act on the center vertex and its neighbours matching
       their individual conditions, i.e.:

           [ $vertex_condition,
               EDGE { $edge_condition1->( @_ ) }, $vertex_condition1,
               EDGE { $edge_condition2->( @_ ) }, $vertex_condition2,
               # ...
               $action ]

METHODS

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

   "EDGE"
       When used before a neighbour condition, places a condition on edge connecting the center vertex with a
       neighbour matched by the following rule.  Accepts a block or sub {}, i.e.:

           EDGE { $_[0]->get_edge_attribute( $_[1], $_[2], 'color' ) eq 'red' }

       Subroutine is evaluated with three parameters: graph, center vertex and its neighbour matching the
       following neighbour condition.  Subroutine should evaluate to true if condition is fulfilled.

   "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>

perl v5.40.0                                       2024-09-26                                Graph::Grammar(3pm)