Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
hamiltons_cycle.cpp File Reference

The implementation of Hamilton's cycle dynamic solution for vertices number less than 20. More...

#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for hamiltons_cycle.cpp:

Functions

bool hamilton_cycle (const std::vector< std::vector< bool >> &routes)
 
static void test1 ()
 
static void test2 ()
 
static void test3 ()
 
int main (int argc, char **argv)
 

Detailed Description

The implementation of Hamilton's cycle dynamic solution for vertices number less than 20.

I use \(2^n\times n\) matrix and for every \([i, j]\) ( \(i < 2^n\) and \(j < n\)) in the matrix I store true if it is possible to get to all vertices on which position in i's binary representation is 1 so as \(j\) would be the last one.

In the the end if any cell in \((2^n - 1)^{\mbox{th}}\) row is true there exists hamiltonian cycle.

Author
vakhokoto
Krishna Vedala

Function Documentation

◆ hamilton_cycle()

bool hamilton_cycle ( const std::vector< std::vector< bool >> &  routes)

The function determines if there is a hamilton's cycle in the graph

Parameters
routesnxn boolean matrix of \([i, j]\) where \([i, j]\) is true if there is a road from \(i\) to \(j\)
Returns
true if there is Hamiltonian cycle in the graph
false if there is no Hamiltonian cycle in the graph
30  {
31  const size_t n = routes.size();
32  // height of dp array which is 2^n
33  const size_t height = 1 << n;
35 
36  // to fill in the [2^i, i] cells with true
37  for (size_t i = 0; i < n; ++i) {
38  dp[1 << i][i] = true;
39  }
40  for (size_t i = 1; i < height; i++) {
41  std::vector<size_t> zeros, ones;
42  // finding positions with 1s and 0s and separate them
43  for (size_t pos = 0; pos < n; ++pos) {
44  if ((1 << pos) & i) {
45  ones.push_back(pos);
46  } else {
47  zeros.push_back(pos);
48  }
49  }
50 
51  for (auto &o : ones) {
52  if (!dp[i][o]) {
53  continue;
54  }
55 
56  for (auto &z : zeros) {
57  if (!routes[o][z]) {
58  continue;
59  }
60  dp[i + (1 << z)][z] = true;
61  }
62  }
63  }
64 
65  bool is_cycle = false;
66  for (size_t i = 0; i < n; i++) {
67  is_cycle |= dp[height - 1][i];
68  if (is_cycle) { // if true, all subsequent loop will be true. hence
69  // break
70  break;
71  }
72  }
73  return is_cycle;
74 }
Here is the call graph for this function:

◆ main()

int main ( int  argc,
char **  argv 
)

Main function

Parameters
argccommandline argument count (ignored)
argvcommandline array of arguments (ignored)
142  {
143  test1();
144  test2();
145  test3();
146  return 0;
147 }
Here is the call graph for this function:

◆ test1()

static void test1 ( )
static

this test is testing if hamilton_cycle returns true for graph: 1 -> 2 -> 3 -> 4

Returns
None
81  {
83  std::vector<bool>({true, true, false, false}),
84  std::vector<bool>({false, true, true, false}),
85  std::vector<bool>({false, false, true, true}),
86  std::vector<bool>({false, false, false, true})};
87 
88  bool ans = hamilton_cycle(arr);
89  std::cout << "Test 1... ";
90  assert(ans);
91  std::cout << "passed\n";
92 }
Here is the call graph for this function:

◆ test2()

static void test2 ( )
static

this test is testing if hamilton_cycle returns false for
graph:

 1 -> 2 -> 3
      |
      V
      4
Returns
None
103  {
105  std::vector<bool>({true, true, false, false}),
106  std::vector<bool>({false, true, true, true}),
107  std::vector<bool>({false, false, true, false}),
108  std::vector<bool>({false, false, false, true})};
109 
110  bool ans = hamilton_cycle(arr);
111 
112  std::cout << "Test 2... ";
113  assert(!ans); // not a cycle
114  std::cout << "passed\n";
115 }
Here is the call graph for this function:

◆ test3()

static void test3 ( )
static

this test is testing if hamilton_cycle returns true for clique with 4 vertices

Returns
None
122  {
124  std::vector<bool>({true, true, true, true}),
125  std::vector<bool>({true, true, true, true}),
126  std::vector<bool>({true, true, true, true}),
127  std::vector<bool>({true, true, true, true})};
128 
129  bool ans = hamilton_cycle(arr);
130 
131  std::cout << "Test 3... ";
132  assert(ans);
133  std::cout << "passed\n";
134 }
Here is the call graph for this function:
std::vector
STL class.
std::vector::size
T size(T... args)
ans
ll ans(ll n)
Definition: matrix_exponentiation.cpp:91
test1
static void test1()
Definition: hamiltons_cycle.cpp:81
std::vector::push_back
T push_back(T... args)
std::cout
test2
static void test2()
Definition: hamiltons_cycle.cpp:103
height
int height(node *root)
Definition: avltree.cpp:31
hamilton_cycle
bool hamilton_cycle(const std::vector< std::vector< bool >> &routes)
Definition: hamiltons_cycle.cpp:30
test3
static void test3()
Definition: hamiltons_cycle.cpp:122