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>