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,))

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