/ 
Graph-Graph6-9
River stage one • 2 direct dependents • 2 total dependents
/ Graph::Graph6

NAME

Graph::Graph6 - read and write graph6, sparse6, digraph6 format graphs

SYNOPSIS

use Graph::Graph6;
my ($num_vertices, @edges);
Graph::Graph6::read_graph(filename         => 'foo.g6',
                          num_vertices_ref => \$num_vertices,
                          edge_aref        => \@edges);

Graph::Graph6::write_graph(filename     => 'bar.s6',
                           format       => 'sparse6',
                           num_vertices => $num_vertices,
                           edge_aref    => \@edges);

DESCRIPTION

This module reads and writes graph6, sparse6 and digraph6 files or strings as per

These formats represent a graph (a graph theory graph) with vertices numbered 0 to n-1 encoded into printable ASCII characters in the range ? to ~. The maximum number of vertices is 2^36-1.

graph6 represents an undirected graph by an upper triangle adjacency matrix of bits. It has no self-loops or multi-edges. Its encoding is 6 bits per character so N vertices is a file size roughly N^2/12 bytes.

sparse6 represents an undirected graph by a list of edges i,j. This is good for graphs with relatively few edges. It can have self-loops and multi-edges. The file size ranges from B = E*(W+1)/6 bytes up to 2*B bytes, for E edges and bit width W bits for the biggest vertex number N-1.

digraph6 represents a directed graph as an NxN adjacency matrix of bits encoded as 6 bits per character so file size N^2/6 bytes. It can include self-loops but no multi-edges.

This module reads and writes in a "native" way as integer vertex numbers 0 to n-1. See "SEE ALSO" below for Graph.pm, Graph::Easy and GraphViz2 interfaces.

These formats are used by the Nauty tools http://cs.anu.edu.au/~bdm/nauty and http://pallini.di.uniroma1.it as output for generated graphs and input for calculations of automorphism groups, canonicalizing, and more. The House of Graphs http://hog.grinvin.org takes graph6 for searches and uploads and includes it among download formats.

FUNCTIONS

Reading

$success = Graph::Graph6::read_graph(key => value, ...)

Read graph6, sparse6 or digraph6. The key/value options are

filename           => filename (string)
fh                 => filehandle (glob ref)
str                => string
num_vertices_ref   => scalar ref
num_vertices_func  => coderef
edge_aref          => array ref
edge_func          => coderef
error_func         => coderef

The return value is

1         if graph successfully read
0         if end of file (no graph read)
croak()   if invalid content or file error
undef     if error_func returns

filename, fh or str is the input. The output is number of vertices and list of edges as callbacks or ref targets.

The number of vertices n is stored to num_vertices_ref or call to num_vertices_func, or both.

$$num_vertices_ref = $n;
$num_vertices_func->($n);

Each edge is stored into edge_aref or call to edge_func, or both. Any existing contents of edge_aref array are deleted. $from and $to are integers in the range 0 to n-1. graph6 has $from < $to. sparse6 has $from <= $to. digraph6 has any values. For sparse6, multi-edges give multiple edges stored and multiple calls made.

push @$edge_aref, [ $from, $to ];   # (and emptied first)
$edge_func->($from, $to);

error_func is called for any file error or invalid content.

$error_func->($str, $str, ...);

The default error_func is croak(). If error_func returns then the return from read_graph() is undef.

An immediate end of file gives the end of file return 0. It's common to have multiple graphs in a file, one per line, and possibly an empty file if no graphs of some kind. They can be read successively with read_graph() until 0 at end of file.

End of file is usually only of interest when reading an fh handle. But an empty file or empty input string give the end of file return too. This is designed to make the input sources equivalent (filename is the same as open and fh, and either the same as slurp and pass str).

For num_vertices_ref and edge_aref, a my can be included in the ref-taking in the usual way if desired,

# "my" included in refs
read_graph(filename         => 'foo.g6',
           num_vertices_ref => \my $num_vertices,
           edge_aref        => \my @edges);

This is compact and is similar to the common open my $fh, ... declaring an output variable in the call which is its first use.

graph6 has edges ordered by increasing $to and within that increasing $from. sparse6 normally likewise, but the format potentially allows $from to jump around. digraph6 has edges ordered by increasing $from and within that increasing $to. But the suggestion is not to rely on edge order (only on $from <= $to for graph6 and sparse6 noted above).

In perl -T taint mode, $num_vertices and edge $from, $to outputs are tainted in the usual way for reading from file, from tainted str, or from fh handle of a file or a tie of something tainted.

Writing

$ret = Graph::Graph6::write_graph(key => value, ...)

Write graph6 or sparse6. The key/value options are

filename           => filename (string)
fh                 => filehandle (glob ref)
str_ref            => output string (string ref)
format             => "graph6", "sparse6", "digraph6"
                         (string, default "graph6")
header             => boolean (default false)
num_vertices       => integer
edge_aref          => array ref
edge_predicate     => coderef

The return value is

1       if graph successfully written
0       if some write error, error in $!

filename, fh or str_ref is the output destination. str_ref is a scalar ref to store to, so for example

my $str;
write_graph(str_ref => \$str, ...)

# or
write_graph(str_ref => \my $str, ...)

format defaults to "graph6", or can be "sparse6" or "digraph6"

write_graph(format => "sparse6", ...)

header flag writes an initial ">>graph6<<", ">>sparse6<<" or ">>digraph6<<" as appropriate. This is optional for the Nauty programs and for read_graph() above, but may help a human reader distinguish a graph from tty line noise.

num_vertices is mandatory, except if edge_aref is given then the default is the maximum vertex number there. (This is convenient, as long as the maximum vertex has at least one edge.) Must have num_vertices < 2**36.

edge_aref is an arrayref of edges which are in turn arrayref pairs of integers [$from,$to]. They can be in any order but all must be integers in the range 0 to $num_vertices-1 inclusive. For graph6 and sparse6 (being undirected) the $from,$to pairs can be either way around. graph6 ignores self-loops and writes duplicates just once each. sparse6 can have self-loops and repeated entries for multi-edges. digraph6 can have self-loops but writes all duplicates just once each.

edge_aref => [ [5,6], [0,1] ]    # edges in any order
edge_aref => [ [5,4] ]      # pairs either way for undirected

edge_predicate is another way to specify edges. It is called with integers $from,$to to test whether such an edge exists. graph6 has $from < $to. sparse6 has $from <= $to. digraph6 has any. digraph6 and sparse6 self-loops can be written this way, but not sparse6 multi-edges.

$bool = $edge_predicate->($from, $to);    # $from <= $to

edge_predicate is preferred for writing graph6 and digraph6. edge_aref is preferred for writing sparse6. But whichever you give is used for any format.

The output includes a final newline "\n" so graphs can be written to a file handle one after the other.

Other

$str = Graph::Graph6::HEADER_GRAPH6 ()
$str = Graph::Graph6::HEADER_SPARSE6 ()
$str = Graph::Graph6::HEADER_DIGRAPH6 ()

Return the header strings >>graph6<<, >>sparse6<< or >>digraph6<<.

EXPORTS

Nothing is exported by default, but the functions can be requested in usual Exporter style,

use Graph::Graph6 'read_graph','write_graph';

SEE ALSO

Graph::Reader::Graph6, Graph::Writer::Graph6, Graph::Writer::Sparse6

Graph::Easy::Parser::Graph6, Graph::Easy::As_graph6, Graph::Easy::As_sparse6

GraphViz2::Parse::Graph6

Carp

nauty-showg(1), nauty-copyg(1)

HOME PAGE

http://user42.tuxfamily.org/graph-graph6/index.html

LICENSE

Copyright 2015, 2016, 2017, 2018, 2021 Kevin Ryde

Graph-Graph6 is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Graph-Graph6 is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Graph-Graph6. If not, see http://www.gnu.org/licenses/.