NAME

Graph::Graph6 - read and write graph6 or sparse6 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 or sparse6 files. These file formats are per

http://cs.anu.edu.au/~bdm/data/formats.txt

Both represent an undirected 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. sparse6 lists edges as pairs of vertices i,j and is good for large graphs with relatively few edges. graph6 is an upper triangle adjacency matrix of bits. Its encoding is 6 bits per character so N vertices is a file size roughly N^2/12 bytes. sparse6 can have multi-edges and self loops. graph6 does not.

This module reads and writes graph6 and sparse6 in a "native" way just as integer vertex numbers. See "SEE ALSO" below for Graph.pm, Graph::Easy and GraphViz2 interfaces.

FUNCTIONS

Reading

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

Read graph6 or sparse6. 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)
    croak()   if invalid content or file error
    undef     if error_func returns instead of dying

filename, fh or str is the input. The output is the number of vertices and a list of edges.

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 pushed onto edge_aref or call to edge_func, or both. $from and $to are integers in the range 0 to n-1 with $from <= $to (or $from < $to for graph6). For sparse6, multi-edges give multiple elements stored and multiple calls made. Any previous contents of edge_aref are discarded.

    push @$edge_aref, [ $from, $to ];
    $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 graph6 or sparse6 in a file, one per line and perhaps empty 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 empty file or empty input string give the end of file return too. This is designed to make the three input forms equivalent (filename is the same as open and fh, or either the same slurped and passed as 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.

The file formats have edges ordered by increasing $to and within that increasing $from, though for sparse6 $from can potentially jump around. But the suggestion is not to rely on edge order (only on $from <= $to noted above).

In perl -T taint mode, $num_vertices and edge $from,$to outputs are tainted in the usual way for reading a file, a tainted str, or an fh handle to a file or 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" or "sparse6"
                             (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 the dense "graph6", or can be "sparse6"

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

header flag writes an initial ">>graph6<<" or ">>sparse6<<". 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, or if edge_aref is given then the default is from the maximum vertex number there (convenient as long as the maximum vertex has at least one edge).

edge_aref is an arrayref of edges which are arrayref pairs of integers [$from,$to]. The edges and the $from,$to can be in any order but all must be integers be in the range 0 to <$num_vertices-1> inclusive. sparse6 can have self-loops, and repeated entries for multi-edges. graph6 ignores self-loops and writes duplicates just once each.

    edge_aref => [ [0,1], [5,6], [5,4] ]      # any order

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

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

edge_predicate is preferred for writing graph6 or edge_aref is preferred for writing sparse6, but whichever you give is used for either output.

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

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

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

HOME PAGE

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

LICENSE

Copyright 2015 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/.