NAME
Graph::Undirected::Hamiltonicity::Tests - a collection of subroutines to decide whether the input Graph::Undirected is Hamiltonian.
VERSION
Version 0.01
SYNOPSIS
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);
...EXPORT
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
SUBROUTINES
test_trivial
Takes a Graph::Undirected and applies some constant-time tests for Hamiltonicity.
test_canonical
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.
test_min_degree
If the graph has a vertex with degree < 2, the graph does not have a Hamiltonian Cycle.
test_articulation_vertex
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.
test_graph_bridge
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.
test_dirac
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
test_required_max_degree
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.
test_required_cyclic
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.
SUPPORT
Please report issues on GitHub.
AUTHOR
Ashwin Dixit, <ashwin at ownlifeful dot com>