# NAME

Graph::Nauty - Perl bindings for Nauty

# SYNOPSIS

```
use Graph::Nauty qw(
are_isomorphic
automorphism_group_size
canonical_order
orbits
);
use Graph::Undirected;
my $A = Graph::Undirected->new;
my $B = Graph::Undirected->new;
# Create graphs here
# Get the size of the automorphism group:
print automorphism_group_size( $A );
# Get automorphism group orbits:
print orbits( $A );
# Check whether two graphs are isomorphs:
print are_isomorphic( $A, $B );
# Get canonical order of vertices:
print canonical_order( $A );
```

# DESCRIPTION

Graph::Nauty provides an interface to Nauty, a set of procedures for determining the automorphism group of a vertex-coloured graph, and for testing graphs for isomorphism.

Currently Graph::Nauty only supports Graph::Undirected, that is, it does not handle directed graphs. Both colored vertices and edges are accounted for when determining equivalence classes.

## Vertex color

As Graph supports any data types as graph vertices, not much can be inferred about them automatically. For now, Graph::Nauty by default stringifies every vertex (using Perl `""`

operator) and splits them into equivalence classes. If different behavior is needed, a custom anonymous subroutine can be passed inside an option hash:

` print orbits( $A, sub { return length $_[0] } );`

Subroutine gets a vertex as its 0th parameter, and is expected to return a string, or anything stringifiable.

In subroutines where the order of returned vertices is important, a second anonymous subroutine can be passed to order vertices inside each of the equivalence classes:

` print orbits( $A, sub { return length $_[0] }, sub { return "$_[0]" } );`

If an ordering subroutine is not given, stringification (Perl `""`

operator) is used by default.

## Edge color

Edge colors are generated from Graph edge attributes. Complete hash of each edge's attributes is stringified (deterministically) and used to divide edges into equivalence classes.

## Working storage size

Nauty needs working storage, which it does not allocate by itself. Graph::Nauty follows the advice of the Nauty user guide by allocating the recommended amount of memory, but for certain graphs this might not be enough, still. To control that, `$Graph::Nauty::worksize`

could be used to set the size of memory in the units of Nauty's `setword`

.

# INSTALLING

Building and installing Graph::Nauty from source requires shared library and C headers for Nauty, which can be downloaded from https://users.cecs.anu.edu.au/~bdm/nauty/. Both the library and C headers have to be installed to locations visible by Perl's C compiler.

# SEE ALSO

For the description of Nauty refer to http://pallini.di.uniroma1.it.

# AUTHOR

Andrius Merkys, mailto:merkys@cpan.org

# COPYRIGHT AND LICENSE

Copyright (C) 2020 by Andrius Merkys

Graph::Nauty is distributed under the BSD-3-Clause license.