nodes: 0, module; 1, function_definition; 2, function_name:setcover_greedy; 3, parameters; 4, block; 5, identifier:candidate_sets_dict; 6, default_parameter; 7, default_parameter; 8, default_parameter; 9, default_parameter; 10, expression_statement; 11, import_statement; 12, expression_statement; 13, comment:# If candset_weights or item_values not given use the length as defaults; 14, if_statement; 15, if_statement; 16, if_statement; 17, if_statement; 18, expression_statement; 19, comment:# While we still need covers; 20, while_statement; 21, return_statement; 22, identifier:items; 23, None; 24, identifier:set_weights; 25, None; 26, identifier:item_values; 27, None; 28, identifier:max_weight; 29, None; 30, comment:r"""
      Greedy algorithm for various covering problems.
      approximation gaurentees depending on specifications  like set_weights and item values
  
      Set Cover: log(len(items) + 1) approximation algorithm
      Weighted Maximum Cover: 1 - 1/e == .632 approximation algorithm
      Generalized maximum coverage is not implemented
  
      References:
          https://en.wikipedia.org/wiki/Maximum_coverage_problem
  
      Example:
          >>> # DISABLE_DOCTEST
          >>> from utool.util_alg import *  # NOQA
          >>> import utool as ut
          >>> candidate_sets_dict = {
          >>>     'a': [1, 2, 3, 8, 9, 0],
          >>>     'b': [1, 2, 3, 4, 5],
          >>>     'c': [4, 5, 7],
          >>>     'd': [5, 6, 7],
          >>>     'e': [6, 7, 8, 9, 0],
          >>> }
          >>> max_weight = None
          >>> items = None
          >>> set_weights = None
          >>> item_values = None
          >>> greedy_soln = ut.sort_dict(ut.setcover_greedy(candidate_sets_dict))
          >>> exact_soln = ut.sort_dict(ut.setcover_ilp(candidate_sets_dict))
          >>> print('greedy_soln = %r' % (greedy_soln,))
          >>> print('exact_soln = %r' % (exact_soln,))
      """; 31, aliased_import; 32, assignment; 33, comparison_operator:items is None; 34, block; 35, comparison_operator:set_weights is None; 36, block; 37, else_clause; 38, comparison_operator:item_values is None; 39, block; 40, else_clause; 41, comparison_operator:max_weight is None; 42, block; 43, assignment; 44, boolean_operator; 45, comment:# Find candiate set with the most uncovered items; 46, block; 47, identifier:solution_cover; 48, dotted_name; 49, identifier:ut; 50, identifier:solution_cover; 51, dictionary; 52, identifier:items; 53, None; 54, expression_statement; 55, identifier:set_weights; 56, None; 57, expression_statement; 58, block; 59, identifier:item_values; 60, None; 61, expression_statement; 62, block; 63, identifier:max_weight; 64, None; 65, expression_statement; 66, identifier:avail_covers; 67, dictionary_comprehension; 68, comparison_operator:get_weight(solution_cover) < max_weight; 69, comparison_operator:len(avail_covers) > 0; 70, expression_statement; 71, expression_statement; 72, expression_statement; 73, if_statement; 74, expression_statement; 75, comment:# Add values in this key to the cover; 76, expression_statement; 77, expression_statement; 78, comment:# Remove chosen set from available options and covered items; 79, comment:# from remaining available sets; 80, delete_statement; 81, for_statement; 82, identifier:utool; 83, assignment; 84, assignment; 85, function_definition; 86, assignment; 87, function_definition; 88, assignment; 89, pair; 90, for_in_clause; 91, call; 92, identifier:max_weight; 93, call; 94, integer:0; 95, call; 96, assignment; 97, assignment; 98, comparison_operator:uncovered_values[chosen_idx] <= 0; 99, comment:# needlessly adding value-less items; 100, block; 101, assignment; 102, assignment; 103, assignment; 104, subscript; 105, identifier:vals; 106, call; 107, block; 108, identifier:items; 109, call; 110, identifier:get_weight; 111, identifier:len; 112, function_name:get_weight; 113, parameters; 114, block; 115, identifier:get_value; 116, identifier:len; 117, function_name:get_value; 118, parameters; 119, block; 120, identifier:max_weight; 121, call; 122, identifier:key; 123, call; 124, pattern_list; 125, call; 126, identifier:get_weight; 127, argument_list; 128, identifier:len; 129, argument_list; 130, attribute; 131, argument_list; 132, identifier:uncovered_values; 133, call; 134, identifier:chosen_idx; 135, call; 136, subscript; 137, integer:0; 138, break_statement; 139, identifier:chosen_key; 140, subscript; 141, identifier:chosen_set; 142, subscript; 143, subscript; 144, subscript; 145, identifier:avail_covers; 146, identifier:chosen_key; 147, attribute; 148, argument_list; 149, expression_statement; 150, attribute; 151, argument_list; 152, identifier:solution_cover; 153, expression_statement; 154, identifier:vals; 155, expression_statement; 156, identifier:get_weight; 157, argument_list; 158, identifier:set; 159, argument_list; 160, identifier:key; 161, identifier:val; 162, attribute; 163, argument_list; 164, identifier:solution_cover; 165, identifier:avail_covers; 166, identifier:avail_covers; 167, identifier:values; 168, identifier:list; 169, argument_list; 170, attribute; 171, argument_list; 172, identifier:uncovered_values; 173, identifier:chosen_idx; 174, call; 175, identifier:chosen_idx; 176, identifier:avail_covers; 177, identifier:chosen_key; 178, identifier:solution_cover; 179, identifier:chosen_key; 180, identifier:candidate_sets_dict; 181, identifier:chosen_key; 182, identifier:avail_covers; 183, identifier:values; 184, call; 185, identifier:ut; 186, identifier:flatten; 187, call; 188, call; 189, call; 190, identifier:candidate_sets_dict; 191, identifier:val; 192, identifier:candidate_sets_dict; 193, identifier:items; 194, call; 195, identifier:ut; 196, identifier:argmax; 197, identifier:uncovered_values; 198, identifier:list; 199, argument_list; 200, attribute; 201, argument_list; 202, attribute; 203, argument_list; 204, identifier:sum; 205, argument_list; 206, identifier:sum; 207, argument_list; 208, identifier:map; 209, argument_list; 210, call; 211, identifier:vals; 212, identifier:difference_update; 213, identifier:chosen_set; 214, identifier:candidate_sets_dict; 215, identifier:values; 216, list_comprehension; 217, list_comprehension; 218, identifier:get_value; 219, call; 220, attribute; 221, argument_list; 222, subscript; 223, for_in_clause; 224, subscript; 225, for_in_clause; 226, attribute; 227, argument_list; 228, identifier:avail_covers; 229, identifier:keys; 230, identifier:set_weights; 231, identifier:key; 232, identifier:key; 233, call; 234, identifier:item_values; 235, identifier:v; 236, identifier:v; 237, identifier:vals; 238, identifier:avail_covers; 239, identifier:values; 240, attribute; 241, argument_list; 242, identifier:solution_cover; 243, identifier:keys
code: def setcover_greedy(candidate_sets_dict, items=None, set_weights=None, item_values=None, max_weight=None):
      r"""
      Greedy algorithm for various covering problems.
      approximation gaurentees depending on specifications  like set_weights and item values
  
      Set Cover: log(len(items) + 1) approximation algorithm
      Weighted Maximum Cover: 1 - 1/e == .632 approximation algorithm
      Generalized maximum coverage is not implemented
  
      References:
          https://en.wikipedia.org/wiki/Maximum_coverage_problem
  
      Example:
          >>> # DISABLE_DOCTEST
          >>> from utool.util_alg import *  # NOQA
          >>> import utool as ut
          >>> candidate_sets_dict = {
          >>>     'a': [1, 2, 3, 8, 9, 0],
          >>>     'b': [1, 2, 3, 4, 5],
          >>>     'c': [4, 5, 7],
          >>>     'd': [5, 6, 7],
          >>>     'e': [6, 7, 8, 9, 0],
          >>> }
          >>> max_weight = None
          >>> items = None
          >>> set_weights = None
          >>> item_values = None
          >>> greedy_soln = ut.sort_dict(ut.setcover_greedy(candidate_sets_dict))
          >>> exact_soln = ut.sort_dict(ut.setcover_ilp(candidate_sets_dict))
          >>> print('greedy_soln = %r' % (greedy_soln,))
          >>> print('exact_soln = %r' % (exact_soln,))
      """
      import utool as ut
      solution_cover = {}
      # If candset_weights or item_values not given use the length as defaults
      if items is None:
          items = ut.flatten(candidate_sets_dict.values())
      if set_weights is None:
          get_weight = len
      else:
          def get_weight(solution_cover):
              sum([set_weights[key] for key in solution_cover.keys()])
      if item_values is None:
          get_value = len
      else:
          def get_value(vals):
              sum([item_values[v] for v in vals])
      if max_weight is None:
          max_weight = get_weight(candidate_sets_dict)
      avail_covers = {key: set(val) for key, val in candidate_sets_dict.items()}
      # While we still need covers
      while get_weight(solution_cover) < max_weight and len(avail_covers) > 0:
          # Find candiate set with the most uncovered items
          avail_covers.values()
          uncovered_values = list(map(get_value, avail_covers.values()))
          chosen_idx = ut.argmax(uncovered_values)
          if uncovered_values[chosen_idx] <= 0:
              # needlessly adding value-less items
              break
          chosen_key = list(avail_covers.keys())[chosen_idx]
          # Add values in this key to the cover
          chosen_set = avail_covers[chosen_key]
          solution_cover[chosen_key] = candidate_sets_dict[chosen_key]
          # Remove chosen set from available options and covered items
          # from remaining available sets
          del avail_covers[chosen_key]
          for vals in avail_covers.values():
              vals.difference_update(chosen_set)
      return solution_cover