Finding a Hamiltonian Path Efficiently - ADVANCED

[stauffski]

Hello Fellow Code Ninjas,

Working on a humdinger here. I'm getting stuck trying to come up with a solution to finding a Hamiltonian Path. I managed to solve it recursively but the time complexity or the time cost of recursion makes the solution unviable. I've found a few resources online, but I am having trouble telling if the topic is over my head or the resources are poorly assembled.

First, I'll give you my working recursive code so you can get an idea of what I'm doing:

import cProfile
import io
import pstats
import sys

sys.setrecursionlimit(10 ** 6)  # this is a recursive solution that creates n stacks for solve(n), raise the ceiling


# decorator for you to profile my code with
def profile(function):
    def inner(*args, **kwargs):
        profiler = cProfile.Profile()

        profiler.enable()
        returnValue = function(*args, **kwargs)
        profiler.disable()

        stream_ = io.StringIO()
        pstats.Stats(profiler, stream=stream_).sort_stats('cumulative').print_stats()
        print(stream_.getvalue())

        return returnValue

    return inner


def solve(n):  # this function runs all the code and returns a hamiltonian path
    return findHamiltonianPath(getSquareSumsGraph(n))


# generate undirected graph of numbers in a range
# connect all vertices v1 and v2 that sum to a perfect square, where sqrt(v1 + v2) = an integer
# example: given 6 and 10, sqrt(6 + 10) = 4, therefore connect vertex(6) to vertex(10)
def getSquareSumsGraph(n):
    squares = {x for x in range(4, 2 * n) if (x ** (1 / 2)).is_integer()}  # generate perfect squares in range 2n
    graph = {}  # initialize an empty dictionary

    for vertex in range(1, n + 1):  # iterate the range 1 -> n, each is a vertex (v1)
        subVertices = []  # this empty array will represent the vertices connected to vertex
        for square in squares:  # iterate the pre-calculated squares
            candidate = square - vertex  # since v1 + v2 (candidate) = square; v2 = square - v1
            if 0 < candidate <= n and candidate != vertex:  # confirm that candidate exists in the range and != v1
                subVertices.append(candidate)  # keep candidate (v2)
        graph[vertex] = subVertices  # all vertices connected to vertex have been collected, store them in the graph

    return graph


# return the first hamiltonian path found in the graph
# if no path found, return False
def findHamiltonianPath(graph):
    graphLength = len(graph)  # store the graph length for optimization
    subGraph = graph.copy()  # copy the graph. subGraph will be used to add and remove connections as we iterate
    path = []  # path will store our final result

    # recursive child function handles searching for the path
    def search(options):
        if len(path) == graphLength:  # if path and graph are the same length, Hamiltonian Path has been found
            return path  # return the Hamiltonian Path
        options = sorted(options, key=lambda option: len(graph[option]))  # sort by shortest subVertices - optimization
        for option in options:  # iterate all the options. we are starting with the vertices that have the least options
            path.append(option)  # add the option to the path
            for vertex in graph[option]:  # now that option is in the path, remove it from connected subVertices
                subGraph[vertex].remove(option)
            if search(subGraph[option]):  # recurse from the next vertex of position option
                return path  # a member of the stack has found a path, return the path
            path.pop()  # path was not found with that option, remove it from the path
            for vertex in graph[option]:  # put the option back in all the subVertices it should be connected to
                subGraph[vertex].append(option)
        return False  # no path was found, return False

    return search([*range(1, graphLength + 1)])  # seed the search with the full range of options


@profile
def rangeTest(a, b): 
    for n in range(a, b):  # iterate this solution for a -> n
        path = solve(n)  # find Hamiltonian Path for n
        print(f'N = {n}: Path = {path}')  # print n and path

@profile
def singleTest(n):
    path = solve(n)  # find Hamiltonian Path for n
    print(f'N = {n}: Path = {path}')  # print n and path


singleTest(15)  # this is the smallest n that has a hamiltonian path, use this test to debug and walk through the code
singleTest(1000)  # this test would fall without the recursion ceiling extension
rangeTest(100, 300)  # this test needs to complete in at least 20% less time than it currently does

The commenting is extremely verbose, so read that to follow what's going on. In summary: We are testing findHamiltonianPath() by sending it an undirected graph that associates all the numbers in the range 1->n that sum to a perfect square. More on the square sums problem: Square Sums Problem

My code works flawlessly (I think) to solve the problem, but the issue I'm having is the amount of time it takes. Now, there are many very inefficient ways to solve this problem, but this is not one of those. However, I know for sure that there is a way to make the solution faster either by optimization or a complete rewrite (maybe a dynamic solution?). Problem is, there's a ton of resources talking about really slow solutions (not this one) and only a small handful of resources that even acknowledge the problem can be solved faster.

Now, I only need to improve the speed of the program by about 20%, but I've already profiled my code and optimized everything I can think of. Granted, I'm very new at Python so perhaps one of you Gurus can point me in the right direction. Alternatively, if anyone can link me to a good resource that talks about a dynamic solution, that would be awesome. The only dynamic solution that I've found so far is this (and it's despicably slow): Dynamic Programming - Hamiltonian Path

The dynamic solution is presented in section 2.) when you scroll down. The code is in C++ but I translated it to Python. It's been many years since I've worked in C++ and being new to Python, I would not be shocked if I made a translation error. That said, here's my translation:

# Note: This code only returns True or False. I'll implement the rest if I can get it to work faster
def checkHamiltonian(adj, n):
    dp = [[False for i in range(1 << n)] for j in range(n)]
    for i in range(n):
        dp[i][1 << i] = True
    for i in range(2 ** n):
        for j in range(n):
            if i & (1 << j):
                for k in range(n):
                    if i & (1 << k) and adj[k][j] and k != j and dp[k][i ^ (1 << j)]:
                        dp[j][i] = True
                        break
    for i in range(n):
        if dp[i][(2 ** n) - 1]:
            return True
    return False

A couple of issues I'm running into with that code:
The author does not talk about the parameter requirements for the function, which I find odd. So

• I'm not sure if I'm implementing it correctly. I'm assuming that adj is supposed to be an adjacency matrix and n is the length of the path you're trying to find. I could be wrong.
  
• It seems like the author's first language is not English, so I can't tell if I'm having trouble understanding what he is saying or if it's just over my head.
  

In any case, since I don't entirely understand the dynamic solution yet, I'm not sure how or if I can optimize it.

Here's a translation of my own code to create an adjacency matrix to test the dynamic solution with instead of the graph:

def getSquareSumsAdjacencyMatrix(n):
    squares = {x for x in range(4, 2 * n) if (x ** (1 / 2)).is_integer()}
    adjacencyMatrix = [[0 for i in range(n)] for j in range(n)]

    for vertex in range(1, n + 1):
        for square in squares:
            candidate = square - vertex
            if 0 < candidate <= n and candidate != vertex:
                adjacencyMatrix[vertex - 1][candidate - 1] = True

    return adjacencyMatrix

Alright guys, fingers crossed that someone can help me. The question is two-fold. Either help me optimize my code or understand/fix/find the/a dynamic solution. Also, feel free to make any corrections on the way that I use Python or propper conventions. As I said I'm new and would love to learn whatever you have to offer.

Cheers
~Stauffski

Note: precalculating the answer is not an option

[ndc85430]

Also posted here.

[stauffski]

Also posted here.

Yes... I posted the same question on two forums.

[stauffski]

Update: My code was running fast enough. Turns out I was encountering a slowdown at fault of the server. Therefore now I no longer need help. However! I would still love anybody's input on any of the three points:

• Further optimization of my code
  
• A faster dynamic solution
  
• Corrections on my usage of Python
  

Cheers!