def hamiltonian_cycles_dynamic_programming(operational_limit=nil)
      stack = DS::Stack.new
      return [] if @vertices.empty?

      origin_vertex = @vertices.to_a[0]
      hamiltonians = []
      num_operations = 0

      # This hash keeps track of subproblems that have already been
      # solved. ie is there a path through vertices that ends in the
      # endpoint
      # Hash of [vertex_set,endpoint] => Array of Path objects.
      # If no path is found, then the key is false
      # The endpoint is not stored in the vertex set to make the programming
      # easier.
      dp_cache = {}

      # First problem is the whole problem. We get the Hamiltonian paths,
      # and then after reject those paths that are not cycles.
      initial_vertex_set = Set.new(@vertices.reject{|v| v==origin_vertex})
      initial_problem = [initial_vertex_set, origin_vertex]
      stack.push initial_problem

      while next_problem = stack.pop
        vertices = next_problem[0]
        destination = next_problem[1]

        if dp_cache[next_problem]
          # No need to do anything - problem already solved

        elsif vertices.empty?
          # The bottom of the problem. Only return a path
          # if there is an edge between the destination and the origin
          # node
          if edge?(destination, origin_vertex)
            path = Path.new [destination]
            dp_cache[next_problem] = [path]
          else
            # Reached dead end
            dp_cache[next_problem] = false
          end

        else
          # This is an unsolved problem and there are at least 2 vertices in the vertex set.
          # Work out which vertices in the set are neighbours
          neighs = Set.new neighbours(destination)
          possibilities = neighs.intersection(vertices)
          if possibilities.length > 0
            # There is still the possibility to go further into this unsolved problem
            subproblems_unsolved = []
            subproblems = []

            possibilities.each do |new_destination|
              new_vertex_set = Set.new(vertices.to_a.reject{|v| v==new_destination})
              subproblem = [new_vertex_set, new_destination]

              subproblems.push subproblem
              if !dp_cache.key?(subproblem)
                subproblems_unsolved.push subproblem
              end
            end

            # if solved all the subproblems, then we can make a decision about this problem
            if subproblems_unsolved.empty?
              answers = []
              subproblems.each do |problem|
                paths = dp_cache[problem]
                if paths == false
                  # Nothing to see here
                else
                  # Add the found sub-paths to the set of answers
                  paths.each do |path|
                    answers.push Path.new(path+[destination])
                  end
                end
              end

              if answers.empty?
                # No paths have been found here
                dp_cache[next_problem] = false
              else
                dp_cache[next_problem] = answers
              end
            else
              # More problems to be solved before a decision can be made
              stack.push next_problem #We have only delayed solving this problem, need to keep going in the future
              subproblems_unsolved.each do |prob|
                unless operational_limit.nil?
                  num_operations += 1
                  raise OperationalLimitReachedException if num_operations > operational_limit
                end
                stack.push prob
              end
            end

          else
            # No neighbours in the set, so reached a dead end, can go no further
            dp_cache[next_problem] = false
          end
        end
      end

      if block_given?
        dp_cache[initial_problem].each do |hpath|
          yield hpath
        end
        return
      else
        return dp_cache[initial_problem]
      end
    end
def hamiltonian_cycles_dynamic_programming(operational_limit=nil)
      stack = DS::Stack.new
      return [] if @vertices.empty?

      origin_vertex = @vertices.to_a[0]
      hamiltonians = []
      num_operations = 0

      # This hash keeps track of subproblems that have already been
      # solved. ie is there a path through vertices that ends in the
      # endpoint
      # Hash of [vertex_set,endpoint] => Array of Path objects.
      # If no path is found, then the key is false
      # The endpoint is not stored in the vertex set to make the programming
      # easier.
      dp_cache = {}

      # First problem is the whole problem. We get the Hamiltonian paths,
      # and then after reject those paths that are not cycles.
      initial_vertex_set = Set.new(@vertices.reject{|v| v==origin_vertex})
      initial_problem = [initial_vertex_set, origin_vertex]
      stack.push initial_problem

      while next_problem = stack.pop
        vertices = next_problem[0]
        destination = next_problem[1]

        if dp_cache[next_problem]
          # No need to do anything - problem already solved

        elsif vertices.empty?
          # The bottom of the problem. Only return a path
          # if there is an edge between the destination and the origin
          # node
          if edge?(destination, origin_vertex)
            path = Path.new [destination]
            dp_cache[next_problem] = [path]
          else
            # Reached dead end
            dp_cache[next_problem] = false
          end

        else
          # This is an unsolved problem and there are at least 2 vertices in the vertex set.
          # Work out which vertices in the set are neighbours
          neighs = Set.new neighbours(destination)
          possibilities = neighs.intersection(vertices)
          if possibilities.length > 0
            # There is still the possibility to go further into this unsolved problem
            subproblems_unsolved = []
            subproblems = []

            possibilities.each do |new_destination|
              new_vertex_set = Set.new(vertices.to_a.reject{|v| v==new_destination})
              subproblem = [new_vertex_set, new_destination]

              subproblems.push subproblem
              if !dp_cache.key?(subproblem)
                subproblems_unsolved.push subproblem
              end
            end

            # if solved all the subproblems, then we can make a decision about this problem
            if subproblems_unsolved.empty?
              answers = []
              subproblems.each do |problem|
                paths = dp_cache[problem]
                if paths == false
                  # Nothing to see here
                else
                  # Add the found sub-paths to the set of answers
                  paths.each do |path|
                    answers.push Path.new(path+[destination])
                  end
                end
              end

              if answers.empty?
                # No paths have been found here
                dp_cache[next_problem] = false
              else
                dp_cache[next_problem] = answers
              end
            else
              # More problems to be solved before a decision can be made
              stack.push next_problem #We have only delayed solving this problem, need to keep going in the future
              subproblems_unsolved.each do |prob|
                unless operational_limit.nil?
                  num_operations += 1
                  raise OperationalLimitReachedException if num_operations > operational_limit
                end
                stack.push prob
              end
            end

          else
            # No neighbours in the set, so reached a dead end, can go no further
            dp_cache[next_problem] = false
          end
        end
      end

      if block_given?
        dp_cache[initial_problem].each do |hpath|
          yield hpath
        end
        return
      else
        return dp_cache[initial_problem]
      end
    end
Use dynamic programming to find all the Hamiltonian cycles in this graph