Топологическая сортировка с использованием std :: sort
Замечания: При написании этого вопроса, я думаю, я уже нашел ответ. Не стесняйтесь вносить изменения или дополнения в лучшую версию. Я подумал, что было бы неплохо документировать мою проблему. редактировать Я был неправ, мой ответ был не верен.
Рассматривая список целочисленных пар: я хотел бы топологически отсортировать их на основе частичного упорядочения. Это похоже на Достаточно ли частичного порядка, в отличие от общего порядка, чтобы построить кучу? , но я бы хотел использовать 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)) в соответствии с ТПК, и, следовательно, можно заключить (1,2) == (2,1). Однако в пункте 25.4.3 стандарта с ++ (рабочий проект за январь 2012 года) говорится:
Для всех алгоритмов, которые принимают Compare, есть версия, которая использует оператор< вместо. То есть комп (* я,
* j)! = false по умолчанию * i < * j! = ложь. Для работы алгоритмов, отличных от описанных в 25.4.3
правильно, комп должен вызывать строгий слабый порядок значений.
Отредактировано: Согласно действительному ответу ecatmur:
Частичное упорядочение не обязательно является строгим слабым упорядочением; это ломает транзитивность несовместимости. Поэтому я хотел бы отказаться от своих рассуждений о том, что частичное упорядочение — это всегда строго слабое упорядочение и связанные с ним вопросы, и добавить вопрос: обречен ли я написать собственный алгоритм топологической сортировки или использовать реализацию повышения, которая требует от меня построения график?
Решение: Умное предложение экатмура:
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 сортирует топологически; за исключением одного комментария, который не подкреплен аргументацией.
Решение
Рассмотрим значения
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;
Другие решения