view release on metacpan or  search on metacpan

lib/Graph/Graph6.pm  view on Meta::CPAN

    #     && (my $edge_matrix = $options{'edge_matrix'})) {
    #   $edge_predicate = sub {
    #     my ($from, $to) = @_;
    #     return $edge_matrix->[$from]->[$to];
    #   };
    # }

1;
__END__

=for stopwords Ryde undirected multi-edges arrayref Nauty tty

=head1 NAME

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

=head1 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);

=head1 DESCRIPTION

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

=over 4

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

=back

These formats represent a graph (a graph theory graph) with vertices
numbered 0 to n-1 encoded into printable ASCII characters in the range C<?>
to C<~>.  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.

=cut

# GP-DEFINE  graph6_size_bits_by_sum(n) = sum(j=1,n-1, sum(i=0, j-1, 1));
# GP-DEFINE  graph6_size_bits_formula(n) = n*(n-1)/2;
# GP-Test  vector(100,n, graph6_size_bits_formula(n)) == \
# GP-Test  vector(100,n, graph6_size_bits_by_sum(n))

# GP-DEFINE  graph6_size_bits_formula(n) = n^2/2 - n/2;
# GP-Test  vector(100,n, graph6_size_bits_formula(n)) == \
# GP-Test  vector(100,n, graph6_size_bits_by_sum(n))

=pod

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

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

=head1 FUNCTIONS

=head2 Reading

=over

=item C<$success = Graph::Graph6::read_graph(key =E<gt> 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

C<filename>, C<fh> or C<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 C<num_vertices_ref> or call to
C<num_vertices_func>, or both.

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

Each edge is stored into C<edge_aref> or call to C<edge_func>, or both.  Any
existing contents of C<edge_aref> array are deleted.  C<$from> and C<$to>
are integers in the range 0 to n-1.  graph6 has C<$from E<lt> $to>.  sparse6
has C<$from E<lt>= $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);

C<error_func> is called for any file error or invalid content.