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

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

                                                              {
    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;
}

Here is the call graph for this function:

main()

int main	(	int	argc,
		char **	argv )

Main function

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

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

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

                    {
    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";
}

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

                    {
    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";
}

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

                    {
    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";
}

Here is the call graph for this function: