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:

Go to the source code of this file.

Functions
bool	hamilton_cycle (const std::vector< std::vector< bool > > &routes)
static void	test1 ()
static void	test2 ()
static void	test3 ()
int	main ()

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

Definition in file hamiltons_cycle.cpp.

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

routes

nxn 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

Definition at line 30 of file hamiltons_cycle.cpp.

                                                              {
    const size_t n = routes.size();
    // height of dp array which is 2^n
    const size_t height = 1 << n;
    std::vector<std::vector<bool>> dp(height, std::vector<bool>(n, false));
 
    // to fill in the [2^i, i] cells with true
    for (size_t i = 0; i < n; ++i) {
        dp[1 << i][i] = true;
    }
    for (size_t i = 1; i < height; i++) {
        std::vector<size_t> zeros, ones;
        // finding positions with 1s and 0s and separate them
        for (size_t pos = 0; pos < n; ++pos) {
            if ((1 << pos) & i) {
                ones.push_back(pos);
            } else {
                zeros.push_back(pos);
            }
        }
 
        for (auto &o : ones) {
            if (!dp[i][o]) {
                continue;
            }
 
            for (auto &z : zeros) {
                if (!routes[o][z]) {
                    continue;
                }
                dp[i + (1 << z)][z] = true;
            }
        }
    }
 
    bool is_cycle = false;
    for (size_t i = 0; i < n; i++) {
        is_cycle |= dp[height - 1][i];
        if (is_cycle) {  // if true, all subsequent loop will be true. hence
                         // break
            break;
        }
    }
    return is_cycle;
}

main()

int main

(

void

)

Main function

Definition at line 140 of file hamiltons_cycle.cpp.

           {
    test1();
    test2();
    test3();
    return 0;
}

test1()

void test1 ( )

static

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

Returns

None

Definition at line 81 of file hamiltons_cycle.cpp.

                    {
    std::vector<std::vector<bool>> arr{
        std::vector<bool>({true, true, false, false}),
        std::vector<bool>({false, true, true, false}),
        std::vector<bool>({false, false, true, true}),
        std::vector<bool>({false, false, false, true})};
 
    bool ans = hamilton_cycle(arr);
    std::cout << "Test 1... ";
    assert(ans);
    std::cout << "passed\n";
}

test2()

void test2 ( )

static

this test is testing if hamilton_cycle returns false for
graph:

 1 -> 2 -> 3
      |
      V
      4

Returns

None

Definition at line 103 of file hamiltons_cycle.cpp.

                    {
    std::vector<std::vector<bool>> arr{
        std::vector<bool>({true, true, false, false}),
        std::vector<bool>({false, true, true, true}),
        std::vector<bool>({false, false, true, false}),
        std::vector<bool>({false, false, false, true})};
 
    bool ans = hamilton_cycle(arr);
 
    std::cout << "Test 2... ";
    assert(!ans);  // not a cycle
    std::cout << "passed\n";
}

test3()

void test3 ( )

static

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

Returns

None

Definition at line 122 of file hamiltons_cycle.cpp.

                    {
    std::vector<std::vector<bool>> arr{
        std::vector<bool>({true, true, true, true}),
        std::vector<bool>({true, true, true, true}),
        std::vector<bool>({true, true, true, true}),
        std::vector<bool>({true, true, true, true})};
 
    bool ans = hamilton_cycle(arr);
 
    std::cout << "Test 3... ";
    assert(ans);
    std::cout << "passed\n";
}