Топологическая сортировка с использованием std::sort

Примечание. Написав этот вопрос, я думаю, что уже нашел ответ. Не стесняйтесь исправлять или дополнять его лучшей версией. Я подумал, что было бы неплохо задокументировать мою проблему. редактировать Я был неправ, мой ответ был неверным.

Рассматривая список целочисленных пар: я хотел бы топологически отсортировать их на основе частичного порядка. Это похоже на является частичным -order, в отличие от total-order, достаточно для создания кучи? , но я бы хотел использовать std::sort вместо std::priority_queue.

Для этого я написал этот фрагмент кода:

#include <iostream>
#include <vector>
#include <algorithm>


struct pair {
    int a, b;
    pair(int a, int b) : a(a), b(b) {}

    std::ostream &print(std::ostream &out) const {
        return (out << "(" << a << ", " << b << ")");
    }
};

std::ostream &operator<<(std::ostream &out, const pair &p) { return p.print(out); }

struct topological_pair_comparator {
    bool operator()(const pair &p, const pair &q) const { return p.a<q.a && p.b<q.b; }
} tpc;

std::vector<pair> pairs = {
    pair(1,1),
    pair(1,2),
    pair(2,1),
    pair(3,1),
    pair(1,3),
    pair(5,5),
    pair(2,2),
    pair(4,0)
};

int main() {
    std::sort(pairs.begin(), pairs.end(), tpc);
    for(const pair &p : pairs) std::cout << p << " ";
    std::cout << std::endl;
    return 0;
}

Источник: http://ideone.com/CxOVO0

В результате чего:

(1, 1) (1, 2) (2, 1) (3, 1) (1, 3) (2, 2) (4, 0) (5, 5)

Который в значительной степени топологически отсортирован (доказательство на примере;).

Однако частичное упорядочение приводит к тому, что !((1,2) ‹ (2,1)) и !((1,2) > (2,1)) в соответствии с tpc, и, следовательно, можно сделать вывод (1,2 ) == (2,1). Однако в параграфе 25.4.3 стандарта С++ (рабочий проект от января 2012 г.) говорится:

Для всех алгоритмов, использующих Compare, существует версия, в которой вместо этого используется оператор‹. То есть comp(*i, *j) != false по умолчанию *i ‹ *j != false. Для правильной работы алгоритмов, отличных от описанных в 25.4.3, comp должен индуцировать строгое слабое упорядочение значений.

Отредактировано: Согласно правильному ответу ecatmur: Частичный порядок не обязательно является строгим слабым порядком; это нарушает транзитивность несопоставимости. Поэтому я хотел бы отказаться от своих рассуждений о том, что частичное упорядочение всегда является строгим слабым упорядочением и связанными с этим вопросами, и добавить вопрос: обречен ли я писать свои собственные алгоритм топологической сортировки или использовать реализацию boost, которая требует от меня построения графика?

Решение. Разумный вариант экатмура:

struct topological_pair_comparator {
    bool operator()(const pair &p, const pair &q) const { return (p.a + p.b) < (q.a + q.b); }
} tpc;

Источник: http://ideone.com/uoOXNC

Обратите внимание, что в SO о кучах явно не упоминается, что std::sort сортирует топологически; кроме одного комментария, не подкрепленного аргументацией.


c++ sorting c++11 topological-sort
person Herbert    schedule 18.06.2014    source источник
comment
Согласно Википедии, частичное упорядочение также не является строгим слабым упорядочением: en.wikipedia.org/wiki /Weak_ordering#Strict_weak_orderings . Однако я, кажется, не понимаю, какое свойство из четырех упомянутых является недействительным. Он также не утверждает упомянутого вами значения, а просто упоминает, что несравнимость является отношением эквивалентности. Я не слишком уверен, но я не могу найти контрпример частичного порядка, где несравнимость не является отношением эквивалентности.   -  person Herbert    schedule 18.06.2014
comment
где несравнимость a и b определяется как не (a‹b или b‹a) :)   -  person Herbert    schedule 18.06.2014
comment
Я сошел с ума, плевать на меня.   -  person Xeo    schedule 18.06.2014
comment
Ваше предположение неверно. Все строгие слабые порядки являются частичными порядками, но не все частичные порядки являются строгими слабыми порядками. Строгий слабый порядок — это частичный порядок, обладающий дополнительным свойством транзитивности несравнимости.   -  person R. Martinho Fernandes    schedule 18.06.2014
comment
Если вы не знаете априори список смежности и вам не посчастливилось преобразовать частичный порядок в строгий слабый порядок, то я думаю, что этот вопрос должен помочь: stackoverflow.com/questions/4600258/sorting-a-poset   -  person ecatmur    schedule 18.06.2014
comment
Вы можете построить график (например, используя Boost.Graph), взяв вашу входную последовательность в качестве списка вершин (назовем их V). Затем вы можете выполнить O(V^2) полный поиск по всем парам вершин и добавить ребро (x, y) к вашему графу, если tpc(x, y) верно. Затем вы можете запустить топологическую сортировку по O(V + E) на вашем графике (всего O(V^2)).   -  person TemplateRex    schedule 18.11.2016

Ответы (1)


arrow_upward
6
arrow_downward

Рассмотрим значения

pair
    x{0, 1},
    y{2, 0},
    z{1, 2};

Здесь,

!tpc(x, y) && !tpc(y, x);
!tpc(y, z) && !tpc(z, y);

Однако,

tpc(x, z);

Таким образом, ваш компаратор не навязывает строгое слабое упорядочение, и поведение не определено, если вы используете его с std::sort или в любой другой роли, где требуется строгое слабое упорядочение.

Компаратор, который является строго слабым и является усовершенствованием вашего компаратора, будет выглядеть так:

struct refined_comparator {
    bool operator()(const pair &p, const pair &q) const { return p.a + p.b < q.a + q.b; }
} rc;
person ecatmur    schedule 18.06.2014
comment
Я вижу, однако, что мне тогда использовать для топологического упорядочения? :( - person Herbert; 18.06.2014
comment
@Herbert компаратор p.a + p.b < q.a + q.b строго слаб и является усовершенствованием вашего компаратора. - person ecatmur; 18.06.2014
comment
Умный трюк, спасибо. если бы вы были так любезны добавить это к своему ответу, это было бы здорово! - person Herbert; 18.06.2014