使用std :: sort进行拓扑排序 [英] Topological sorting using std::sort

问题描述

注意：在写这个问题时，我想我已经找到了答案。随意更改或附加一个更好的版本。我认为记录我的问题可能很好。 编辑我错了，我的aswer不正确。

考虑整数对的列表：我想根据部分排序。这类似于部分 - 与总次序相比，足以构建一个堆？，但我想使用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& 
 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 } tpc; 
 
 std :: vector< pair> pair = {
 pair（1,1），
 pair（1,2），
 pair（2,1），
 pair（3,1），
对（1,3），
对（5,5），
对（2,2），
对（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）
  

这是几乎是拓扑排序的（通过例子证明）。

然而，根据tpc，部分排序创建了！（（1,2）<（2,1））和！（（1,2）>（2,1）） ，因此可以得出（1,2）==（2,1）。但是，c ++标准（2012年1月工作草案）的第25.4.3段规定：

对于所有采用Compare的算法，版本，代替。也就是说，comp（* i，
* j）！= false默认为* i < * j！= false。对于25.4.3中正确工作
以外的算法，comp必须对值进行严格的弱排序。

已编辑：根据ecatmur的有效答案：
部分排序不一定是严格的弱排序;它打破了不相容性的传递性。所以我想放弃我的推理，部分顺序总是一个严格的弱顺序和相关的问题，并添加了一个问题：我注定要写我自己

  struct topological_pair_comparator {
 bool operator（）（const pair& p，const pair& q ）const {return（pa + pb） （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）; 
  

但是，

 code> tpc（x，z）; 
  

因此，您的比较器不会施加严格的弱排序，如果您使用 std :: sort 或在需要严格弱排序的任何其他角色中使用它，则未定义。

比较器是严格弱，是比较器的细化将是：

  struct refined_comparator {
 bool operator（）（const pair& p，const pair& q）const {return pa + pb< q.a + q.b; } 
} rc; 
  

Note: While writing this question, I think I already found the answer. Feel free to ammend or append it with a better version. I thought it might be nice to document my problem. edit I was wrong, my aswer was not correct.

Considering a list of integer pairs: I'd like to topologically sort them based on a partial ordering. This is similar to Is partial-order, in contrast to total-order, enough to build a heap? , but I'd like to use std::sort instead of std::priority_queue.

To do so I wrote this piece of code:

#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;
}

Source: http://ideone.com/CxOVO0

Resulting in:

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

Which is pretty much topologially sorted (proof by example ;).

However, the partial ordering creates that !((1,2) < (2,1)) and !((1,2) > (2,1)) according to the tpc, and hence one may conclude (1,2) == (2,1). However, paragraph 25.4.3 of the c++ standard (January 2012 working draft) states:

For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

Edited: According to ecatmur 's valid answer: A partial ordering is not necessarily a strict weak ordering; it breaks the transitivity of incomparibility. So I'd like to drop my reasoning that a partial ordering is always a strict weak ordering and the associated questions, and add the question: am I doomed to write my own topological sorting algorithm or use the boost implementation which requires me to build the graph?

Solution: A smart suggestion of ecatmur:

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

Source: http://ideone.com/uoOXNC

Please note, the SO about heaps does not explicitely mention that std::sort sorts topologically; except for one comment, which is not backed up by argumentation.

解决方案

Consider the values

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

Here,

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

However,

tpc(x, z);

Thus your comparator does not impose a strict weak ordering, and behavior is undefined if you use it with std::sort or in any other role where a strict weak ordering is required.

A comparator that is strict weak and is a refinement of your comparator would be:

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

这篇关于使用std :: sort进行拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！