---
name: "Graph::Grammar"
section: "3pm"
platform: "linux"
package: "libgraph-grammar-perl"
version: "0.2.0-1"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Graph::Grammar"
---

# Graph::Grammar(3pm)

Graph grammar, i.e. rewriting method

## 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\>