The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

Graph::Undirected::Hamiltonicity::Tests - a collection of subroutines to decide whether the input Graph::Undirected is Hamiltonian.

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>