lib/yargraph.rb
# Use dynamic programming to find all the Hamiltonian cycles in this graph
Use dynamic programming to find all the Hamiltonian cycles in this graph
Use dynamic programming to find all the Hamiltonian cycles in this graph
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
      dp_cache = {}
      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]
        elsif vertices.empty?
          if edge?(destination, origin_vertex)
            path = Path.new [destination]
            dp_cache[next_problem] = [path]
          else
            dp_cache[next_problem] = false
          end
        else
          neighs = Set.new neighbours(destination)
          possibilities = neighs.intersection(vertices)
          if possibilities.length > 0
            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 subproblems_unsolved.empty?
              answers = []
              subproblems.each do |problem|
                paths = dp_cache[problem]
                if paths == false
                else
                  paths.each do |path|
                    answers.push Path.new(path+[destination])
                  end
                end
              end
              if answers.empty?
                dp_cache[next_problem] = false
              else
                dp_cache[next_problem] = answers
              end
            else
              stack.push next_problem 
              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
            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 dp_cache = { } 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 ] elsif vertices . empty? if edge? ( destination , origin_vertex ) path = Path . new [ destination ] dp_cache [ next_problem ] = [ path ] else dp_cache [ next_problem ] = false end else neighs = Set . new neighbours ( destination ) possibilities = neighs . intersection ( vertices ) if possibilities . length > 0 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 subproblems_unsolved . empty? answers = [ ] subproblems . each do | problem | paths = dp_cache [ problem ] if paths == false else paths . each do | path | answers . push Path . new ( path + [ destination ] ) end end end if answers . empty? dp_cache [ next_problem ] = false else dp_cache [ next_problem ] = answers end else stack . push next_problem 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 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
Use dynamic programming to find all the Hamiltonian cycles in this graph
# 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. # First problem is the whole problem. We get the Hamiltonian paths, # and then after reject those paths that are not cycles. # No need to do anything - problem already solved # The bottom of the problem. Only return a path # if there is an edge between the destination and the origin # node # Reached dead end # 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 # There is still the possibility to go further into this unsolved problem # if solved all the subproblems, then we can make a decision about this problem # Nothing to see here # Add the found sub-paths to the set of answers # No paths have been found here # More problems to be solved before a decision can be made #We have only delayed solving this problem, need to keep going in the future # No neighbours in the set, so reached a dead end, can go no further
operational_limit
<not_specific>