/ 
Graph-Undirected-Hamiltonicity-0.1
River stage zero No dependents
/ README.md

Build Status

NAME

Graph::Undirected::Hamiltonicity - determine the Hamiltonicity of a given undirected graph.

VERSION

version 0.01

SYNOPSIS

use Graph::Undirected;
use Graph::Undirected::Hamiltonicity;

# Create and initialize an undirected graph.
my $g = Graph::Undirected->new( vertices => [ 0..3 ] );
$g->add_edge(0,1);
$g->add_edge(0,3);
$g->add_edge(1,2);
$g->add_edge(1,3);

if ( graph_is_hamiltonian( $g ) ) {
    say "The graph contains a Hamiltonian Cycle.";
} else {
    say "The graph does not contain a Hamiltonian Cycle.";
}

DESCRIPTION

This module is dedicated to the Quixotic quest of determining whether "P=NP". It decides whether a given Graph::Undirected contains a Hamiltonian Cycle.

The non-deterministic algorithm systematically simplifies the input graph in a series of recursive tests. This module is not object-oriented, though once work on it is sufficiently advanced, it could be rolled up into an is_hamiltonian() method in Graph::Undirected. For now, it serves as a framework for explorers of this frontier of Computer Science.

The modules in this distribution are:

INSTALLATION

To install the core module:

If you need to get cpanm:

curl -L https://cpanmin.us | perl - App::cpanminus

then:

./Build

If all goes well, you will see output like this:

...
All tests successful.
Files=15, Tests=604,  4 wallclock secs ( 0.08 usr  0.02 sys +  4.20 cusr  0.13 csys =  4.43 CPU)
Result: PASS
[DZ] all's well; removing .build/xHNLTYlN9o

If all is well, then proceed to install the module:

dzil install

If you run into trouble installing Net::SSLeay as part of Dist::Zilla, try the following.

On Red Hat / CentOS / Fedora:

sudo yum install openssl-devel

On Debian / Ubuntu:

sudo apt-get install libssl-dev

To install the optional CGI script:

Copy the script to the appropriate location for your web server.

On macOS:

sudo cp cgi-bin/hc.cgi /Library/WebServer/CGI-Executables/

On Red Hat / CentOS / Fedora Linux:

sudo cp cgi-bin/hc.cgi /var/www/cgi-bin/

To enable verification via Wolfram Open Cloud:

( Optional, but recommended ). To enable result cross-verification via the Wolfram Open Cloud, please read WOLFRAM.md.

use Graph::Undirected::Hamiltonicity::Wolfram;

if ( is_hamiltonian_per_wolfram( $g ) ) {
    say "The graph contains a Hamiltonian Cycle.";
} else {
    say "The graph does not contain a Hamiltonian Cycle.";
}

USAGE

CGI script:

The included CGI script ( cgi-bin/hc.cgi ) lets you visualize and edit graphs through a browser. It draws graphs using inline SVG. A demo of this script is hosted at: http://ownlifeful.com/hamilton.html

Command-line tool:

To test whether a given graph is Hamiltonian:

perl bin/hamilton.pl --graph_text 0=1,0=2,1=2

To test multiple graphs:

perl bin/hamilton.pl --graph_file list_of_graphs.txt

To spoof a random Hamiltonian graph with 42 vertices and test it for Hamiltonicity:

perl bin/hamilton.pl --vertices 42

To get more detailed help:

perl bin/hamilton.pl --help

SUPPORT

Please report issues on GitHub.

ACKNOWLEDGEMENTS

Thanks to Larry Wall, for creating Perl; to Jarkko Hietaniemi, for creating the Graph module; and to Dr. Stephen Wolfram, for creating the Wolfram Programming Language. Thanks to Dirac and Ore, for their results utilized here.

SEE ALSO

  1. Graph - the Graph module.
  2. Hamiltonian Cycle
  3. P versus NP
  4. Hamiltonian Path

REPOSITORY

https://github.com/ownlifeful/Graph-Undirected-Hamiltonicity

AUTHOR

Ashwin Dixit <ashwin at ownlifeful dot com>

COPYRIGHT AND LICENSE

This software is copyright (c) 2016-2021 by Ashwin Dixit.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.