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

# Graph::Nauty(3pm)

Perl bindings for Nauty

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