Graph::Graph6 - read and write graph6, sparse6, digraph6 format graphs
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);
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 n-1 encoded into printable ASCII characters in the range
~. 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 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 N-1.
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 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
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.
$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
stris 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_refor call to
num_vertices_func, or both.
$$num_vertices_ref = $n; $num_vertices_func->($n);
Each edge is stored into
edge_arefor call to
edge_func, or both. Any existing contents of
edge_arefarray are deleted.
$toare 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 elements stored and multiple calls made.
push @$edge_aref, [ $from, $to ]; # (and emptied first) $edge_func->($from, $to);
error_funcis called for any file error or invalid content.
$error_func->($str, $str, ...);
error_funcreturns then the return from
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
fhhandle. But empty file or empty input string give the end of file return too. This is designed to make the input sources equivalent (
filenameis the same as open and
fh, and either the same as slurp and pass
mycan 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
$toand within that increasing
$from. sparse6 normally likewise, but the format potentially allows
$fromto jump around. digraph6 has edges ordered by increasing
$fromand within that increasing
$to. But the suggestion is not to rely on edge order (only on
$from <= $tofor graph6 and sparse6 noted above).
perl -Ttaint mode,
$from,$tooutputs are tainted in the usual way for reading from file, from tainted
str, or from
fhhandle of file or tie of something tainted.
$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 $!
str_refis the output destination.
str_refis a scalar ref to store to, so for example
my $str; write_graph(str_ref => \$str, ...) # or write_graph(str_ref => \my $str, ...)
"graph6", or can be
write_graph(format => "sparse6", ...)
headerflag writes an initial
">>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_verticesis mandatory, except if
edge_arefis 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 have
num_vertices < 2**36.
edge_arefis 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-1inclusive. For graph6 and sparse6 (being undirected) the
$from,$topairs 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_predicateis another way to specify edges. It is called with integers
$from,$toto 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_predicateis preferred for writing graph6 and digraph6.
edge_arefis 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.
$str = Graph::Graph6::HEADER_GRAPH6 ()
$str = Graph::Graph6::HEADER_SPARSE6 ()
$str = Graph::Graph6::HEADER_DIGRAPH6 ()
Return the header strings
Nothing is exported by default, but the functions can be requested in usual
use Graph::Graph6 'read_graph','write_graph';
Copyright 2015, 2016, 2017, 2018 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/.