view release on metacpan or  search on metacpan

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

package Graph::Undirected::Hamiltonicity::Tests;

use Modern::Perl;
use Exporter qw(import);

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

our $DONT_KNOW                = 0;
our $GRAPH_IS_HAMILTONIAN     = 1;
our $GRAPH_IS_NOT_HAMILTONIAN = 2;

our @EXPORT = qw($DONT_KNOW $GRAPH_IS_HAMILTONIAN $GRAPH_IS_NOT_HAMILTONIAN);

our @EXPORT_OK = (
    @EXPORT, qw(
        &test_articulation_vertex
        &test_canonical
        &test_dirac
        &test_graph_bridge
        &test_min_degree
        &test_ore
        &test_required_max_degree
        &test_required_connected
        &test_required_cyclic
        &test_trivial
        )
);

our %EXPORT_TAGS = ( all => \@EXPORT_OK );

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

sub test_trivial {
    output("Entering test_trivial()<BR/>");
    my ($g) = @_;

    my $e         = scalar( $g->edges );
    my $v         = scalar( $g->vertices );
    my $max_edges = ( $v * $v - $v ) / 2;

    if ( $v == 1 ) {
        return ( $GRAPH_IS_HAMILTONIAN,
                  "By convention, a graph with a single vertex is "
                . "considered to be Hamiltonian." );
    }

    if ( $v < 3 ) {
        return ( $GRAPH_IS_NOT_HAMILTONIAN,
            "A graph with 0 or 2 vertices cannot be Hamiltonian." );
    }

    if ( $e < $v ) {
        foreach my $vertex ( $g->vertices ) {
            say "vertex=[$vertex]"; ### DEBUG: REMOVE!
        }

        
        return ( $GRAPH_IS_NOT_HAMILTONIAN,
            "e < v, therefore the graph is not Hamiltonian. e=$e, v=$v" );
    }

    ### If e > ( ( v * ( v - 1 ) / 2 ) - ( v - 2 ) )