Graph-Undirected-Hamiltonicity

 view release on metacpan or  search on metacpan

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

        output( $required_graph, { required => 1 } );
    } else {
        output("The required graph has no edges.<BR/>");
    }

    return ( $required_graph, $g1 );
}

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

# For each required walk, delete the edge connecting its endpoints,
# as such an edge would make the graph non-Hamiltonian, and therefore
# the edge can never be part of a Hamiltonian cycle.

sub delete_cycle_closing_edges {
    output("Entering delete_cycle_closing_edges()<BR/>");
    my ($g, $required_graph) = @_;
    my $deleted_edges = 0;
    my $g1;
    my %eliminated;

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

        my @reachable = $required_graph->all_reachable($vertex);

        my ( $other_vertex ) = grep { $required_graph->degree($_) == 1 } @reachable;
        $g1 //= $g->deep_copy_graph();
        next unless $g1->has_edge($vertex, $other_vertex);
        $g1->delete_edge($vertex, $other_vertex);
        $required_graph->delete_edge($vertex, $other_vertex);
        $deleted_edges++;

        output( "Deleted edge $vertex=$other_vertex"
                . ", between endpoints of a required walk.<BR/>" );
    }

    if ( $deleted_edges ) {
        my $s = $deleted_edges == 1 ? '' : 's';
        output("Shrank the graph by removing $deleted_edges edge$s.<BR/>");
        return ( $deleted_edges, $g1 );
    } else {
        output("Did not shrink the graph.<BR/>");
        return ( $deleted_edges, $g );
    }

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

#
# Returns a Graph::Undirected object, constructed from its string form.

sub string_to_graph {
    my ($string) = @_;
    my %vertices;
    my @edges;

    foreach my $chunk ( split( /\,/, $string ) ) {
        if ( $chunk =~ /=/ ) {
            my @endpoints = map {s/\b0+([1-9])/$1/gr}
                split( /=/, $chunk );

            next if $endpoints[0] == $endpoints[1];
            push @edges, \@endpoints;
            $vertices{ $endpoints[0] } = 1;
            $vertices{ $endpoints[1] } = 1;
        } else {
            $vertices{$chunk} = 1;
        }
    }

    my @vertices = keys %vertices;
    my $g = Graph::Undirected->new( vertices => \@vertices );

    foreach my $edge_ref (@edges) {
        $g->add_edge(@$edge_ref) unless $g->has_edge(@$edge_ref);

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

        output( $required_graph, { required => 1 } );
    } else {
        output("The required graph has no edges.<BR/>");
    }

    return ( $required_graph, $g1 );
}

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

# For each required walk, delete the edge connecting its endpoints,
# as such an edge would make the graph non-Hamiltonian, and therefore
# the edge can never be part of a Hamiltonian cycle.

sub delete_cycle_closing_edges {
    output("Entering delete_cycle_closing_edges()<BR/>");
    my ($g, $required_graph) = @_;
    my $deleted_edges = 0;
    my $g1;
    my %eliminated;

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

        my @reachable = $required_graph->all_reachable($vertex);

        my ( $other_vertex ) = grep { $required_graph->degree($_) == 1 } @reachable;
        $g1 //= $g->deep_copy_graph();
        next unless $g1->has_edge($vertex, $other_vertex);
        $g1->delete_edge($vertex, $other_vertex);
        $required_graph->delete_edge($vertex, $other_vertex);
        $deleted_edges++;

        output( "Deleted edge $vertex=$other_vertex"
                . ", between endpoints of a required walk.<BR/>" );
    }

    if ( $deleted_edges ) {
        my $s = $deleted_edges == 1 ? '' : 's';
        output("Shrank the graph by removing $deleted_edges edge$s.<BR/>");
        return ( $deleted_edges, $g1 );
    } else {
        output("Did not shrink the graph.<BR/>");
        return ( $deleted_edges, $g );
    }

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

#
# Returns a Graph::Undirected object, constructed from its string form.

sub string_to_graph {
    my ($string) = @_;
    my %vertices;
    my @edges;

    foreach my $chunk ( split( /\,/, $string ) ) {
        if ( $chunk =~ /=/ ) {
            my @endpoints = map {s/\b0+([1-9])/$1/gr}
                split( /=/, $chunk );

            next if $endpoints[0] == $endpoints[1];
            push @edges, \@endpoints;
            $vertices{ $endpoints[0] } = 1;
            $vertices{ $endpoints[1] } = 1;
        } else {
            $vertices{$chunk} = 1;
        }
    }

    my @vertices = keys %vertices;
    my $g = Graph::Undirected->new( vertices => \@vertices );

    foreach my $edge_ref (@edges) {
        $g->add_edge(@$edge_ref) unless $g->has_edge(@$edge_ref);