How can I apply a simple dominance rule?

Question

I have created labels of two properties with the following code.

struct label
{
    double reducedcost;
    int totalload;
};

Lets say i have five labels:

labels.emplace_back(1, 6);
labels.emplace_back(7, 2);
labels.emplace_back(2, 3);
labels.emplace_back(5, 5);
labels.emplace_back(6, 4);

I want to delete the label j if

labels[j].reducedcost > labels[i].reducedcost

and

labels[j].totalload > labels[i].totalload

for any other label i. Is there an easy way to do it?

The simplest way is to use two for loops (but you have to be careful with invalid iterators or pointers by removed elements in previous iterations. (This could possibly by solved by starting from the end). A simple conditional remove can be done with std::remove_if (https://stackoverflow.com/questions/17270837/stdvector-removing-elements-which-fulfill-some-conditions/17270869#17270869). The ranges library could also offer a solution, especially with the cartesian_product_view from C++23. — Sebastian, Oct 14 '22 at 12:51
Alternatively you could have the labels independently sorted by the two criteria and remove the current element from a copy and find the minimum (which is fast for sorted labels). — Sebastian, Oct 14 '22 at 12:54

score 0 · Answer 1 · answered Oct 15 '22 at 09:45

It is somehow not so fully clear, what you mean with dominance.

But I guess you can do that, with an

if first condition then ... else if second condition then ...

For the comparison, we can use a double nested loop with o(N^2) time complexity, so, not very efficient.

And, with your given data, all but the first will element will be erased, because all "reducedcost" of elements will be greater than the first one.

Please check the following example code

#include <iostream>
#include <vector>
#include <iterator>

struct Label {
    double reducedcost{};
    int totalload{};
};

int main() {
    std::vector<Label> labels{};

    labels.emplace_back(1, 6);
    labels.emplace_back(7, 2);
    labels.emplace_back(2, 3);
    labels.emplace_back(5, 5);
    labels.emplace_back(6, 4);

    size_t i{};

    while (i < labels.size()) {
        size_t j{};
        while (j < labels.size()) {
            if (labels[j].reducedcost > labels[i].reducedcost)
                labels.erase(std::next(labels.begin(), j));
            else if (labels[j].totalload > labels[i].totalload)
                labels.erase(std::next(labels.begin(), j));
            else
                ++j;
        }
        ++i;
    }
    for (const auto& [r, t] : labels)
        std::cout << r << '\t' << t << '\n';
}

But, as said, not really sure what you try to attempt.

How can I apply a simple dominance rule?

1 Answers1