import random


def max_weight_paths(k, weight_paths_dict, paths_to_edges, overlap=True, norev=False, rgen=None):
    """
    Returns k largest-weight paths.  The function proceeds in order through descending weight values to select paths,
    and if an entire weight class of paths is not to be included, applies a predictable order to the paths
    before checking them for inclusion (by sorting the (src,dst) pairs in the class and then applying rgen.shuffle).

    :param k: number of paths to select
    :param weight_paths_dict: a dict {weight: set} where keys are weight values, and corresponding values are sets of paths having that weight
    :param paths_to_edges: a dict {(src, dst): set} where the path with endpoints (src, dst) consists of the edges in the corresponding set
    :param overlap: True if max-weight paths selected can share links; False if selected paths should be disjoint
    :param norev: True if (dst,src) should be excluded if (src,dst) is chosen
    :param rgen: RNG object with .shuffle() method to use; random.shuffle() is used if not provided

    :return: (set, set): the set of (src,dst) pairs for paths selected, and the set of edges covered by those paths
    """
    if rgen is None: rgen = random
    
    selected_paths = set()
    probed_edges = set()

    weight_list = sorted(weight_paths_dict, reverse=True)
    weight_index = -1
    while k > 0 and weight_index < len(weight_list)-1:
        weight_index += 1
        weight_class = weight_paths_dict[weight_list[weight_index]]
        l = len(weight_class)
        if k-l >= 0 and overlap and not norev:
            # in this case we will use all paths in the weight class, so no ordering is necessary
            selected_paths.update(weight_class)
            k -= l
        else:
            # in this case we may not use all paths in the weight class, either because:
            # (1) we don't need them all (including them all will result in more than k paths); or
            # (2) we have to check for reverses and/or overlap and thus may skip over some paths in the class
            # so we first sort the paths (deterministic) and then rgen.shuffle them so the weight tie is broken randomly but reproducibly given the RNG
            paths = sorted(weight_class)
            rgen.shuffle(paths)
            if overlap and not norev:
                selected_paths.update(paths[:k])
                k = 0
            elif overlap and norev:
                # paths is an ordered list, so iteration is deterministic
                for s, d in paths:
                    if (d,s) not in selected_paths:
                        selected_paths.add((s,d))
                        k -= 1
                        if k <= 0: break
            else:
                # paths is an ordered list, so iteration is deterministic
                for path in paths:
                    if norev and (path[1],path[0]) in selected_paths: continue
                    path_edges = paths_to_edges[path]
                    if probed_edges.isdisjoint(path_edges):
                        selected_paths.add(path)
                        probed_edges |= path_edges
                        k -= 1
                        if k <= 0: break
    
    # if overlap==True, then we didn't have to update probed_edges, so do it now
    if overlap:
        for path in selected_paths:
            probed_edges |= paths_to_edges[path]

    return selected_paths, probed_edges