docs: def mincost_diameter_augment(graph, max_cost, candidates=None, weight=None, cost=None):
      """
      PROBLEM: Bounded Cost Minimum Diameter Edge Addition (BCMD)
  
      Args:
          graph (nx.Graph): input graph
          max_cost (float): maximum weighted diamter of the graph
          weight (str): key of the edge weight attribute
          cost (str): key of the edge cost attribute
          candidates (list): set of non-edges, optional, defaults
              to the complement of the graph
  
      Returns:
          None: if no solution exists
          list: minimum cost edges if solution exists
  
      Notes:
          We are given a graph G = (V, E) with an edge weight function w, an edge
          cost function c, an a maximum cost B.
  
          The goal is to find a set of candidate non-edges F.
  
          Let x[e] in {0, 1} denote if a non-edge e is excluded or included.
  
          minimize sum(c(e) * x[e] for e in F)
          such that
          weighted_diamter(graph.union({e for e in F if x[e]})) <= B
  
      References:
          https://www.cse.unsw.edu.au/~sergeg/papers/FratiGGM13isaac.pdf
          http://www.cis.upenn.edu/~sanjeev/papers/diameter.pdf
          http://dl.acm.org/citation.cfm?id=2953882
  
      Notes:
          There is a 4-Approximation of the BCMD problem
          Running time is O((3 ** B * B ** 3 + n + log(B * n)) * B * n ** 2)
  
          This algorithm usexs a clustering approach to find a set C, of B + 1
          cluster centers.  Then we create a minimum height rooted tree, T = (U
          \subseteq V, D) so that C \subseteq U.  This tree T approximates an
          optimal B-augmentation.
  
      Example:
          >>> # ENABLE_DOCTEST
          >>> from utool.util_graph import *  # NOQA
          >>> import utool as ut
          >>> graph = nx.Graph()
          >>> if nx.__version__.startswith('1'):
          >>>     nx.add_path = nx.Graph.add_path
          >>> nx.add_path(graph, range(6))
          >>> #cost_func   = lambda e: e[0] + e[1]
          >>> cost_func   = lambda e: 1
          >>> weight_func = lambda e: (e[0]) / e[1]
          >>> comp_graph = nx.complement(graph)
          >>> nx.set_edge_attributes(graph, name='cost', values={e: cost_func(e) for e in graph.edges()})
          >>> nx.set_edge_attributes(graph, name='weight', values={e: weight_func(e) for e in graph.edges()})
          >>> nx.set_edge_attributes(comp_graph, name='cost', values={e: cost_func(e) for e in comp_graph.edges()})
          >>> nx.set_edge_attributes(comp_graph, name='weight', values={e: weight_func(e) for e in comp_graph.edges()})
          >>> candidates = list(comp_graph.edges(data=True))
          >>> max_cost = 2
          >>> cost = 'cost'
          >>> weight = 'weight'
          >>> best_edges = mincost_diameter_augment(graph, max_cost, candidates, weight, cost)
          >>> print('best_edges = %r' % (best_edges,))
          >>> soln_edges = greedy_mincost_diameter_augment(graph, max_cost, candidates, weight, cost)
          >>> print('soln_edges = %r' % (soln_edges,))
      """
      import utool as ut
      import operator as op
  
      if candidates is None:
          candidates = list(graph.complement().edges(data=True))
  
      def augment_add(graph, edges):
          aug_graph = graph.copy()
          aug_graph.add_edges_from(edges)
          return aug_graph
  
      def solution_energy(chosen_edges):
          if weight is None:
              return len(chosen_edges)
          else:
              return sum(d[weight] for (u, v, d) in chosen_edges)
  
      variable_basis = [(0, 1) for _ in candidates]
      best_energy = np.inf
      best_soln = None
  
      soln_generator = ut.product(*variable_basis)
      length = reduce(op.mul, map(len, variable_basis), 1)
      if length > 3000:
          # Let the user know that it might take some time to find a solution
          soln_generator = ut.ProgIter(soln_generator, label='BruteForce BCMD',
                                       length=length)
      # Brute force solution
      for x in soln_generator:
          chosen_edges = ut.compress(candidates, x)
          aug_graph = augment_add(graph, chosen_edges)
          total_cost = weighted_diamter(aug_graph, weight=cost)
          energy = solution_energy(chosen_edges)
          if total_cost <= max_cost:
              if energy < best_energy:
                  best_energy = energy
                  best_soln = x
  
      best_edges = ut.compress(candidates, best_soln)
      return best_edges