view release on metacpan or  search on metacpan

lib/Graph/Undirected/Hamiltonicity.pm  view on Meta::CPAN

=encoding utf-8

=head1 NAME

Graph::Undirected::Hamiltonicity - decide whether a given Graph::Undirected
    contains a Hamiltonian Cycle.

=head1 VERSION

Version 0.17

=head1 LICENSE

Copyright (C) Ashwin Dixit.

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.

=head1 AUTHOR

Ashwin Dixit, C<< <ashwin at CPAN dot org> >>

=cut


use Modern::Perl;
use lib 'local/lib/perl5';

package Graph::Undirected::Hamiltonicity;

# ABSTRACT: decide whether a given Graph::Undirected contains a Hamiltonian Cycle.

# You can get documentation for this module with this command:
#    perldoc Graph::Undirected::Hamiltonicity

use Graph::Undirected::Hamiltonicity::Output qw(&output);
use Graph::Undirected::Hamiltonicity::Tests qw(:all);
use Graph::Undirected::Hamiltonicity::Transforms qw(:all);

use Exporter qw(import);

our $VERSION     = '0.17';
our @EXPORT      = qw(graph_is_hamiltonian);    # exported by default
our @EXPORT_OK   = qw(graph_is_hamiltonian);
our %EXPORT_TAGS = ( all => \@EXPORT_OK );

our $calls = 0; ### Number of calls to is_hamiltonian()

##########################################################################

# graph_is_hamiltonian()
#
# Takes a Graph::Undirected object.
#
# Returns
#         1 if the given graph contains a Hamiltonian Cycle.
#         0 otherwise.
#

sub graph_is_hamiltonian {
    my ($g) = @_;

    $calls = 0;
    my ( $is_hamiltonian, $reason );
    my $time_begin = time;
    my @once_only_tests = ( \&test_trivial, \&test_dirac );
    foreach my $test_sub (@once_only_tests) {
        ( $is_hamiltonian, $reason ) = &$test_sub($g);
        last unless $is_hamiltonian == $DONT_KNOW;
    }

    my $params = {
        transformed => 0,
        tentative   => 0,
    };

    if ( $is_hamiltonian == $DONT_KNOW ) {
        ( $is_hamiltonian, $reason, $params ) = is_hamiltonian($g, $params);
    } else {
        my $spaced_string = $g->stringify();
        $spaced_string =~ s/\,/, /g;
        output("<HR NOSHADE>");
        output("In graph_is_hamiltonian($spaced_string)");
        output($g);
    }
    my $time_end = time;