Skip to content

ownlifeful/Graph-Undirected-Hamiltonicity

master
Switch branches/tags
Code

Latest commit

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
t
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

NAME

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

VERSION

version 0.14

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 from CPAN:

If you just want to use the module, choose this method. Install Graph::Undirected::Hamiltonicity from cpan.

cpan Graph::Undirected::Hamiltonicity

To install the code repositories:

If you want to tinker with the module and/or contribute bugfixes and enhancements, choose this method.

Clone the repository:

git clone https://github.com/ownlifeful/Graph-Undirected-Hamiltonicity.git
cd Graph-Undirected-Hamiltonicity

then:

perl ./Makefile.PL
make
make test
make install

To install the optional CGI script:

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

On macOS:

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

On Fedora / Red Hat / CentOS / Rocky Linux:

sudo cp script/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 ( 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 script/hamilton.pl --graph_text 0=1,0=2,1=2

To test multiple graphs:

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

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

perl script/hamilton.pl --vertices 42

To get more detailed help:

perl script/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. Special thanks to my dear friend Dr. Lubomir Ivanov, who instilled in me, a sense of wonder about the P vs. NP conjecture.

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-2022 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.

About

determine the Hamiltonicity of a given undirected graph.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages