Constructing a Hamiltonian circuit with existing edges
A project in graph theory
This project was originally done for “MAT 243: Discrete Math” with Dr. Susanna Fishel as part of a “Footnote 18” project for honors credit with Barrett, the Honors College at ASU, in Fall 2007.
Next spring, this project was presented at SUnMaRC 2008. You may download the presentation here as Keynote (original format, 0.4MB), Interactive QuickTime (full effects, 40MB), Flash (4.7MB), PowerPoint (0.5MB), or PDF (0.6MB). For source code and the original write-up, see below.
Background: A Brief Glossary of Graph Theory Terms
- Graph
- A graph is a collection of vertices (or points) and edges (which connect the vertices). This project deals, specifically, with undirected graphs of size 2n vertices, each of order of at least n.
- Vertex
- Vertices are points or locations on the graph. They can represent people, places, computers, or anything else, but generally an object or resting place.
- Edge
- Edges connect vertices. They can represent roads, relationships, connections, datapaths, or anything connecting vertices. They can be directed or undirected.
- Degree or Order
- The degree or order of vertex A is the number of edges connected to it.
- Directed vs. Undirected
- A directed edge is one that only flows in one direction, from vertex a to vertex b. An undirected edge is bidirectional. In an undirected graph, all edges are undirected.
- Simple Graph
- A simple graph is one that no more than one edge (in each direction, if directed) between vertices, and no loops from a vertex to itself.
- Path
- A path is a series of n edges. Each edge must end in the same vertex where the next edge begins. In a simple graph, this is equivalent to a series of n+1 vertices.
- Circuit or Closed Path
- A circuit is a path which starts and ends at the same vertex.
- Hamiltonian Circuit
- A Hamiltonian circuit is a closed path which visits every vertex in the graph exactly one time, and its first vertex is also its last. (A Hamiltonian path does not make a cycle, but visits every vertex.)
- Ceiling(x)
- Ceiling is a function which takes a real number and rounds up to the nearest integer. (This is not really a graph-theory term.)
(The glossary is hidden. Show glossary)
The Problem
Given an undirected graph, construct a Hamiltonian circuit. (Note: Finding such a circuit or showing none is possible on a certain graph is known as the Hamiltonian cycle problem and is NP-complete, that is, there is likely no efficient way to consistently solve it.)
The Solution
As noted, this problem is very complicated and usually inefficient to solve. Here we use a potentially more usable and efficient algorithm, albeit only able to solve the problem for graphs for which every vertex is of the order ceiling(n/2) where n is the number of vertices in the graph. That is, for a graph G of size n, consisting of vertices A = {a1, a2, ยทยทยท, an−1, an}, and d(a) is “degree” or “order” of vertex a ∈ A, then our solution applies when ∀a[d(a) ≥ ceil(n/2)] is true.
This is possible due to the idea that, in such a graph, an existing “almost-circuit” with a gap where there “should” be the final edge can be repaired. This is done by connecting the first vertex in question to a point early in the almost-circuit and the second vertex in question to a point immediately later in the almost-circuit, and removing the edge between those two earlier points. (We know that at least one pair of such desirable contiguous earlier vertices exist because each vertex has at least half as many edges as there are vertices.) The result is a circuit. This process can be repeated, which is the basis for our algorithm as shown below.
- Construct the simple undirected graph G1 based on user input.
- Remember the true graph G1, but also make a new simple undirected graph G2. The new graph G2 needs to be of the same size n as G1, but every vertex should be connected to every other vertex; that is, each vertex must be d(n−1).
- Construct a Hamiltonian circuit on G2. This is elementary since any attempted circuit will succeed, as all possible edges on G2 exist.
- One by one, remove edges from G2 if they are not in G1. If removing the edge breaks the Hamiltonian circuit on G2, then:
- Consider the first vertex of the removed edge a and the second b (ordered as in the circuit).
- Start at the beginning of the broken circuit and investigate each vertex. If the vertex in question c is connected to a and the immediately next vertex d is connected to b, then connect a to c and b to d in our broken circuit, and then remove the edge (b, c) from the circuit. It has now been repaired.
- If the vertex in question did not satisfy the above condition, then continue until one is found that does.
- After all edges in G2 not in G1 have been removed and the circuit has been continually repaired as above, the circuit is now a Hamiltonian path that applies to the original graph G1. The algorithm has now completed discovering a Hamiltonian circuit in the original graph.
Implementation
This algorithm was implemented using C++ and the Boost library on Xcode. The source code for our implementation is shown below. While it does not use two graphs and a circuit, but rather one graph and one circuit represented as a graph with n vertices, we do not believe this to be the most efficient or elegant solution, as we were not used to the Boost Graph Library and pounded out a hack job.
C++ Implementation Source Code [Show Glossary]
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <boost/graph/adjacency_list.hpp>
/**
* Hamiltonian Circuit source code
* Dec. 2007
*
* See http://alanhogan.com/asu/hamiltonian-circuit/
*
* Requires the Boost library. Set appropriate header include paths in your compiler or IDE.
*
* Copyright Alan Hogan, Dec. 2007. Contact: http://alanhogan.com/contact
*/
using namespace boost;
int main(int argc, char *argv[])
{
typedef adjacency_list<vecS, vecS, undirectedS, disallow_parallel_edge_tag> Graph;
//disallow_parallel_edge_tag is doing nothing for us
//declare global variables
Graph G1; //User's graph
Graph G2; //Naïve circuit
int graphSize; //Vertices of user's graph (and thus G2)
bool found = false;
int tempIterator = 0; int temp2 = 0;
int a, b, c, d, pastC;
int prev, cur, next;
//Get stuff from user
/* new */
std::cout << "Please enter the number of vertices in your graph "
<< "(must be between 4 and 1024, inclusive): ";
std::cin >> graphSize;
if(graphSize < 4 || graphSize > 1024) { std::cout << "Invalid number. Exiting.\n"; return 1; }
while(tempIterator > -1){
std::cout << "Please enter starting vertex of an edge. Should be an int betweeen 1 and "
<< graphSize << ", inclusive. (-1 when finshed adding edges.): ";
std::cin >> tempIterator;
if(tempIterator > 0 && tempIterator <= graphSize) {
std::cout << "Please enter ending vertex of the edge: " ;
std::cin >> temp2;
if(temp2 > 0 && temp2 <= graphSize && temp2 != tempIterator) {
add_edge(tempIterator, temp2, G1);
continue;
}
std::cout << "Invalid vertex...\n";
}
}
/* end new */
/* old: Fake data
graphSize = 8;
std::cout << "Please enter the number of vertices in your graph "
<< "(must be between 4 and 1024, inclusive): " << "--auto: 8--"<< std::endl;
std::cout << "Please enter starting vertex of an edge: " << "--note: auto-building edges--"
<< std::endl;
std::cout << "Please enter ending vertex of the edge: " << "--auto, for now---" << std::endl;
add_edge(1, 4, G1);
add_edge(1, 5, G1);
add_edge(1, 8, G1);
add_edge(1, 7, G1);
add_edge(2, 7, G1);
add_edge(3, 2, G1);
add_edge(3, 6, G1);
add_edge(4, 3, G1);
add_edge(4, 5, G1);
add_edge(4, 6, G1);
add_edge(5, 2, G1);
add_edge(5, 3, G1);
add_edge(5, 6, G1);
add_edge(6, 7, G1);
add_edge(6, 8, G1);
add_edge(7, 8, G1);
add_edge(8, 2, G1);
// end old */
//Validate number of edges
for(int i = 1; i <= graphSize; i++) {
tempIterator = 0; //here count of edges
for(int j = 1; j <= graphSize; j++) {
if (i == j) continue;
if((edge(i,j,G1)).second) tempIterator++;
}
if(tempIterator < (int) std::ceil(0.5*graphSize)) {
std::cout << "Sorry, vertex " << i << " did not have enough edges.\n";
return 1;
}
}
//Add every edge
//Err, well, we modified the algorithm so as to just assume that. The circuit is represented in G2.
//Construct naïve circuit "G2"
for(int i = 1; i < graphSize; i++) {
add_edge(i, i+1, G2);
}
add_edge(graphSize, 1, G2);
//Subtract edges not in G1
//find first edge: always (1,2) in G2
prev = 0; cur = 1; next = 2;
tempIterator = 0; //Number of edges examined and potentially fixed
while(tempIterator < graphSize) {
a = cur;
b = next;
//std::printf("Examining edge (%d, %d)...\n",a,b); //debug
if((edge(a, b, G1)).second == false) { //Needs fixed!
//std::printf("Edge (%d, %d) needs fixed\n",a,b); //debug
pastC = b;
for(int offset = 0; offset < (graphSize-1); offset++) {
c = (pastC + offset) % graphSize + 1;
//std::printf("offset: %d; c: %d.\n",offset,c); //debug
//Is this a proper next element in our circuit? (Should really go by edges from vertex)
if(c != a && c != b && c != prev && (edge(c, pastC, G2)).second) { //yes, it is!
pastC = c; //If this does not work as a c, at least continue from it
offset = -1;
//std::printf("Next c in path (works; G2): %d.\n",c); //debug
} else { //no
continue;
}
//So is it ok to use?
if((edge(a, c, G1)).second == false) {
//std::printf("a & c were not neighbors in G1... Time for a new c\n"); //debug
//No good!
continue;
} else {
//std::printf("a & c ARE neighbors in G1 match up!\n"); //debug
//Attempt to find d
for(int offset2 = 0; offset2 < (graphSize-1); offset2++) {
d = (c + offset2) % graphSize + 1;
if(c != d && d != b && d != a && (edge(d, c, G2)).second) {
//This IS the only d possible
break;
}
} //end for (finding d)
if((edge(d, b, G1)).second) {
//we found our c & d!
break;
}
}//else (it was a good c)
}//for (finding c)
next = c;
//remove (a,b) and (c,d); add (a,c) and (b,d).
add_edge(a, c, G2);
add_edge(b, d, G2);
remove_edge(c, d, G2);
remove_edge(a, b, G2);
} else { //end fixing
//std::printf("Edge (%d, %d) was fine!",a,b); //debug
}
//"Next" will remain "b" (no fixing), or has be changed to "c" (fixed).
//For the next loop, "cur" needs to take on the value of
//"next" and the new "next" needs chosen.
prev = cur; cur = next;
for(int offset = 0; offset < (graphSize-1); offset++) {
next = (cur + offset) % graphSize + 1;
//std::cout << "testing " << next << "\n"; //debug
if(next != prev && (edge(cur, next, G2)).second) {
//found ideal next
break;
}
}
tempIterator++;
}//while tempIterator
//Return path to user!
std::cout << "\nComplete. Hamiltonian circuit has been found:" << std::endl;
//find first edge
found = false; tempIterator = 2;
while(!found) {
if((edge(1, tempIterator, G2)).second) {
found = true;
cur = 1;
next = tempIterator;
std::cout << "1, " << tempIterator;
}
tempIterator++;
if(tempIterator > graphSize) {
std::cout << "Ooops, problem... Nothing attaches to the first vertex...\n";
return 1;
}
}
//Then print all the other edges
while (next != 1) {
//std::cout << "\nprev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
prev = cur;
cur = next;
//std::cout << "prev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
for(int offset = 0; offset < (graphSize-1); offset++) {
next = (cur + offset) % graphSize + 1;
//std::cout << "testing " << next << "\n"; //debug
if(next != prev && (edge(cur, next, G2)).second) {
std::cout << ", " << next;
break;
}
}
//std::cout << "prev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
//for errors:
if(cur == next) {
std::cout << "Ooops, problem... Nothing attaches to vertex " << cur << " except " << prev << "\n";
return 1;
}
}
std::cout << ".\nProgram complete." << std::endl;
return 0;
}
#include <stdlib.h>
#include <cmath>
#include <boost/graph/adjacency_list.hpp>
/**
* Hamiltonian Circuit source code
* Dec. 2007
*
* See http://alanhogan.com/asu/hamiltonian-circuit/
*
* Requires the Boost library. Set appropriate header include paths in your compiler or IDE.
*
* Copyright Alan Hogan, Dec. 2007. Contact: http://alanhogan.com/contact
*/
using namespace boost;
int main(int argc, char *argv[])
{
typedef adjacency_list<vecS, vecS, undirectedS, disallow_parallel_edge_tag> Graph;
//disallow_parallel_edge_tag is doing nothing for us
//declare global variables
Graph G1; //User's graph
Graph G2; //Naïve circuit
int graphSize; //Vertices of user's graph (and thus G2)
bool found = false;
int tempIterator = 0; int temp2 = 0;
int a, b, c, d, pastC;
int prev, cur, next;
//Get stuff from user
/* new */
std::cout << "Please enter the number of vertices in your graph "
<< "(must be between 4 and 1024, inclusive): ";
std::cin >> graphSize;
if(graphSize < 4 || graphSize > 1024) { std::cout << "Invalid number. Exiting.\n"; return 1; }
while(tempIterator > -1){
std::cout << "Please enter starting vertex of an edge. Should be an int betweeen 1 and "
<< graphSize << ", inclusive. (-1 when finshed adding edges.): ";
std::cin >> tempIterator;
if(tempIterator > 0 && tempIterator <= graphSize) {
std::cout << "Please enter ending vertex of the edge: " ;
std::cin >> temp2;
if(temp2 > 0 && temp2 <= graphSize && temp2 != tempIterator) {
add_edge(tempIterator, temp2, G1);
continue;
}
std::cout << "Invalid vertex...\n";
}
}
/* end new */
/* old: Fake data
graphSize = 8;
std::cout << "Please enter the number of vertices in your graph "
<< "(must be between 4 and 1024, inclusive): " << "--auto: 8--"<< std::endl;
std::cout << "Please enter starting vertex of an edge: " << "--note: auto-building edges--"
<< std::endl;
std::cout << "Please enter ending vertex of the edge: " << "--auto, for now---" << std::endl;
add_edge(1, 4, G1);
add_edge(1, 5, G1);
add_edge(1, 8, G1);
add_edge(1, 7, G1);
add_edge(2, 7, G1);
add_edge(3, 2, G1);
add_edge(3, 6, G1);
add_edge(4, 3, G1);
add_edge(4, 5, G1);
add_edge(4, 6, G1);
add_edge(5, 2, G1);
add_edge(5, 3, G1);
add_edge(5, 6, G1);
add_edge(6, 7, G1);
add_edge(6, 8, G1);
add_edge(7, 8, G1);
add_edge(8, 2, G1);
// end old */
//Validate number of edges
for(int i = 1; i <= graphSize; i++) {
tempIterator = 0; //here count of edges
for(int j = 1; j <= graphSize; j++) {
if (i == j) continue;
if((edge(i,j,G1)).second) tempIterator++;
}
if(tempIterator < (int) std::ceil(0.5*graphSize)) {
std::cout << "Sorry, vertex " << i << " did not have enough edges.\n";
return 1;
}
}
//Add every edge
//Err, well, we modified the algorithm so as to just assume that. The circuit is represented in G2.
//Construct naïve circuit "G2"
for(int i = 1; i < graphSize; i++) {
add_edge(i, i+1, G2);
}
add_edge(graphSize, 1, G2);
//Subtract edges not in G1
//find first edge: always (1,2) in G2
prev = 0; cur = 1; next = 2;
tempIterator = 0; //Number of edges examined and potentially fixed
while(tempIterator < graphSize) {
a = cur;
b = next;
//std::printf("Examining edge (%d, %d)...\n",a,b); //debug
if((edge(a, b, G1)).second == false) { //Needs fixed!
//std::printf("Edge (%d, %d) needs fixed\n",a,b); //debug
pastC = b;
for(int offset = 0; offset < (graphSize-1); offset++) {
c = (pastC + offset) % graphSize + 1;
//std::printf("offset: %d; c: %d.\n",offset,c); //debug
//Is this a proper next element in our circuit? (Should really go by edges from vertex)
if(c != a && c != b && c != prev && (edge(c, pastC, G2)).second) { //yes, it is!
pastC = c; //If this does not work as a c, at least continue from it
offset = -1;
//std::printf("Next c in path (works; G2): %d.\n",c); //debug
} else { //no
continue;
}
//So is it ok to use?
if((edge(a, c, G1)).second == false) {
//std::printf("a & c were not neighbors in G1... Time for a new c\n"); //debug
//No good!
continue;
} else {
//std::printf("a & c ARE neighbors in G1 match up!\n"); //debug
//Attempt to find d
for(int offset2 = 0; offset2 < (graphSize-1); offset2++) {
d = (c + offset2) % graphSize + 1;
if(c != d && d != b && d != a && (edge(d, c, G2)).second) {
//This IS the only d possible
break;
}
} //end for (finding d)
if((edge(d, b, G1)).second) {
//we found our c & d!
break;
}
}//else (it was a good c)
}//for (finding c)
next = c;
//remove (a,b) and (c,d); add (a,c) and (b,d).
add_edge(a, c, G2);
add_edge(b, d, G2);
remove_edge(c, d, G2);
remove_edge(a, b, G2);
} else { //end fixing
//std::printf("Edge (%d, %d) was fine!",a,b); //debug
}
//"Next" will remain "b" (no fixing), or has be changed to "c" (fixed).
//For the next loop, "cur" needs to take on the value of
//"next" and the new "next" needs chosen.
prev = cur; cur = next;
for(int offset = 0; offset < (graphSize-1); offset++) {
next = (cur + offset) % graphSize + 1;
//std::cout << "testing " << next << "\n"; //debug
if(next != prev && (edge(cur, next, G2)).second) {
//found ideal next
break;
}
}
tempIterator++;
}//while tempIterator
//Return path to user!
std::cout << "\nComplete. Hamiltonian circuit has been found:" << std::endl;
//find first edge
found = false; tempIterator = 2;
while(!found) {
if((edge(1, tempIterator, G2)).second) {
found = true;
cur = 1;
next = tempIterator;
std::cout << "1, " << tempIterator;
}
tempIterator++;
if(tempIterator > graphSize) {
std::cout << "Ooops, problem... Nothing attaches to the first vertex...\n";
return 1;
}
}
//Then print all the other edges
while (next != 1) {
//std::cout << "\nprev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
prev = cur;
cur = next;
//std::cout << "prev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
for(int offset = 0; offset < (graphSize-1); offset++) {
next = (cur + offset) % graphSize + 1;
//std::cout << "testing " << next << "\n"; //debug
if(next != prev && (edge(cur, next, G2)).second) {
std::cout << ", " << next;
break;
}
}
//std::cout << "prev: " << prev << "; cur: " << cur << "; next: " << next << std::endl; //debug
//for errors:
if(cur == next) {
std::cout << "Ooops, problem... Nothing attaches to vertex " << cur << " except " << prev << "\n";
return 1;
}
}
std::cout << ".\nProgram complete." << std::endl;
return 0;
}
(The source code is hidden. Show source code)
References
- Rosen, Kenneth H. Discrete Mathematics and Its Applications. McGraw-Hill, New York, 2007. Chapter 9: Graphs.
- Ore, Oystein. “Note on Hamilton Circuits.” American Mathematical Monthly, 1960. Cites work done by D. J. Newman.