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¶

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

AUTHORS¶

Andrius Merkys, <merkys@cpan.org>