## table of contents

Graph::Nauty(3pm) | User Contributed Perl Documentation | Graph::Nauty(3pm) |

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

# 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

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.26.1 or, at your option, any later version of Perl 5 you may have available.

2021-04-19 | perl v5.32.1 |