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

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

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. The 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 and Graph::Easy interfaces reading and writing those graph objects.

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 (or an empty input string) gives the end of file return 0. It's common to have multiple graph6 or sparse6 in a file, one per line. They can be read successively with read_graph() until at end of file read_graph() returns 0.

For num_vertices_ref and edge_aref a my can be included in the ref taking, as in the following. This is compact and is similar to the common open my $fh, ... which declares the variable in a call which is its first use.

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

The file formats have edges ordered by increasing $to and within that increasing $from, although for sparse6 $from can potentially jump around. But the suggestion is not to rely on edge order.

In perl -T taint mode, $num_vertices and edge $from,$to values are tainted in the usual way when reading from a file, a tainted str, or an fh handle to 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" 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 choose "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 and edge_aref is preferred for writing sparse6, but whichever you have 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

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