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.