view release on metacpan or  search on metacpan

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

package Graph::Undirected::Hamiltonicity::Spoof;

use Modern::Perl;
use Carp;

use Graph::Undirected;
use Graph::Undirected::Hamiltonicity::Transforms qw(&add_random_edges &get_random_isomorph);

use Exporter qw(import);

our @EXPORT_OK = qw(
    &spoof_canonical_hamiltonian_graph
    &spoof_known_hamiltonian_graph
    &spoof_random_graph
    &spoof_randomish_graph
);

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

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

sub spoof_canonical_hamiltonian_graph {
    my ($v) = @_;

    my $last_vertex = $v - 1;
    my @vertices    = ( 0 .. $last_vertex );

    my $g = Graph::Undirected->new( vertices => \@vertices );
    $g->add_edge( 0, $last_vertex );

    for ( my $i = 0; $i < $last_vertex; $i++ ) {
        $g->add_edge( $i, $i + 1 );
    }

    return $g;
}

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

sub spoof_known_hamiltonian_graph {
    my ( $v, $e ) = @_;

    croak "Please provide the number of vertices." unless defined $v and $v;
    croak "A graph with 2 vertices cannot be Hamiltonian." if $v == 2;

    $e ||= get_random_edge_count($v);

    croak "The number of edges must be >= number of vertices." if $e < $v;

    my $g = spoof_canonical_hamiltonian_graph($v);
    $g = get_random_isomorph($g);
    $g = add_random_edges( $g, $e - $v ) if ( $e - $v ) > 0;

    return $g;
}

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

sub spoof_random_graph {

    my ( $v, $e ) = @_;
    $e //= get_random_edge_count($v);