# Constructing a Hamiltonian circuit with existing edges

## A project in graph theory

### Background: A Brief Glossary of Graph Theory Terms [Show Glossary]

- 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 2
`n`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 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`= {

`a`,

_{1}`a`, ยทยทยท,

_{2}`a`,

_{n−1}`a`}, and d(

_{n}`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
`G`based on user input._{1} - Remember the true graph
`G`, but also make a new simple undirected graph_{1}`G`. The new graph_{2}`G`needs to be of the same size_{2}`n`as`G`, but every vertex should be connected to every other vertex; that is, each vertex must be d(n−1)._{1} - Construct a Hamiltonian circuit on
`G`. This is elementary since any attempted circuit will succeed, as all possible edges on_{2}`G`exist._{2} - One by one, remove edges from
`G`if they are not in_{2}`G`. If removing the edge breaks the Hamiltonian circuit on_{1}`G`, then:_{2}- 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.

- Consider the first vertex of the removed edge
- After all edges in
`G`not in_{2}`G`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_{1}`G`. The algorithm has now completed discovering a Hamiltonian circuit in the original graph._{1}

### 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

#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;

}

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