Graph::Undirected::Hamiltonicity::Tests - a collection of subroutines to decide whether the input Graph::Undirected is Hamiltonian.
Each subroutine in this module:
Takes: a Graph::Undirected
Returns: ($is_hamilton, $reason)
$is_hamilton can be one of: $DONT_KNOW, $GRAPH_IS_HAMILTONIAN, $GRAPH_IS_NOT_HAMILTONIAN $reason is a string describing the reason for the test conclusion, if any.
Here is an example:
use Graph::Undirected::Hamiltonicity::Tests qw(&test_trivial); use Graph::Undirected::Hamiltonicity::Spoof qw(&spoof_known_hamiltonian_graph); my $g = spoof_known_hamiltonian_graph(30, 50); ### 30 vertices, 50 edges my ( $is_hamiltonian, $reason ) = test_trivial($g); ...
Symbols exported by default are:
$DONT_KNOW
$GRAPH_IS_HAMILTONIAN
$GRAPH_IS_NOT_HAMILTONIAN
All subroutines can be loaded with the qw(:all) tag.
use Graph::Undirected::Hamiltonicity::Tests qw(:all);
The subroutines that can be imported individually, by name, are:
&test_articulation_vertex
&test_canonical
&test_graph_bridge
&test_min_degree
&test_dirac
&test_required_max_degree
&test_required_cyclic
&test_trivial
Takes a Graph::Undirected and applies some constant-time tests for Hamiltonicity.
Tests to see if the input Graph::Undirected is a super-graph of the "canonical" Hamiltonian Cycle.
The "canonical" Hamiltonian Cycle is an isomorph of a graph in which all the edges can be arranged into a regular polygon.
If the graph has a vertex with degree < 2, the graph does not have a Hamiltonian Cycle.
If the graph contains a vertex, removing which would make the graph unconnected, the graph is not Hamiltonian.
Such a vertex is called an Articulation Vertex.
If the graph contains an edge, removing which would make the graph unconnected, the graph is not Hamiltonian.
Such an edge is called a Graph Bridge.
A simple graph with v vertices (v >= 3) is Hamiltonian if every vertex has degree v / 2 or greater. -- Dirac (1952) https://en.wikipedia.org/wiki/Hamiltonian_path
Takes a Graph::Undirected, which is the "required graph" of the input. The "required graph" contains the same vertices as the input graph, but only the edges that the algorithm has marked "required".
If any vertex in the "required graph" has a degree of more than 2, then the input graph cannot be Hamiltonian.
If the "required graph" contains a cycle with fewer than v vertices, then the input graph is not Hamiltonian.
If the cycle has the same number of edges as vertices, then the input graph is Hamiltonian.
Please report issues on GitHub.
Ashwin Dixit, <ashwin at ownlifeful dot com>
<ashwin at ownlifeful dot com>
To install Graph::Undirected::Hamiltonicity, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Undirected::Hamiltonicity
CPAN shell
perl -MCPAN -e shell install Graph::Undirected::Hamiltonicity
For more information on module installation, please visit the detailed CPAN module installation guide.