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. These file formats are per
These formats represent a graph (a graph theory graph) with vertices numbered 0 to n1 encoded into printable ASCII characters in the range ?
to ~
. The maximum number of vertices is 2^361.
graph6 represents an undirected graph by an upper triangle adjacency matrix of bits. It has no selfloops or multiedges. 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 selfloops and multiedges. The file size is somewhere from B=E*(W+1)/6 to 2*B bytes for E edges and bit width W bits for the biggest vertex number N1.
digraph6 represents a directed graph as an NxN adjacency matrix encoded 6 bits per character so file size N^2/6 bytes. It can include selfloops but no multiedges.
This module reads and writes in a "native" way as integer vertex numbers 0 to n1. 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) croak() if invalid content or file error undef if error_func returns instead of dying
filename
,fh
orstr
is the input. The output is number of vertices and list of edges provided by calls or ref targets.The number of vertices n is stored to
num_vertices_ref
or call tonum_vertices_func
, or both.$$num_vertices_ref = $n; $num_vertices_func>($n);
Each edge is stored into
edge_aref
or call toedge_func
, or both. Any existing contents ofedge_aref
array are deleted.$from
and$to
are integers in the range 0 to n1. graph6 has$from < $to
. sparse6 has$from <= $to
. digraph6 has any values. For sparse6, multiedges give multiple elements 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
iscroak()
. Iferror_func
returns then the return fromread_graph()
isundef
.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 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 andfh
, and either the same as slurp and passstr
).For
num_vertices_ref
andedge_aref
, amy
can be included in the reftaking 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 taintedstr
, or fromfh
handle of 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", "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
orstr_ref
is the output destination.str_ref
is a scalar ref to store to, so for examplemy $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 forread_graph()
above, but may help a human reader distinguish a graph from tty line noise.num_vertices
is mandatory, except ifedge_aref
is given then the default is from the maximum vertex number there (which is convenient as long as the maximum vertex has at least one edge). Must havenum_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_vertices1
inclusive. For graph6 and sparse6 (being undirected) the$from,$to
pairs can be either way around. graph6 ignores selfloops and writes duplicates just once each. sparse6 can have selfloops and repeated entries for multiedges. digraph6 can have selfloops 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 selfloops can be written this way, but not sparse6 multiedges.$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
nautyshowg(1), nautycopyg(1)
HOME PAGE
http://user42.tuxfamily.org/graphgraph6/index.html
LICENSE
Copyright 2015, 2016, 2017, 2018 Kevin Ryde
GraphGraph6 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.
GraphGraph6 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 GraphGraph6. If not, see http://www.gnu.org/licenses/.