使用std :: sort进行拓扑排序

Question

注意:在写这个问题时,我想我已经找到了答案.随意修改或附加更好的版本.我认为记录我的问题可能会很好.编辑我错了,我的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 &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) 

这几乎是拓扑排序的(通过示例证明;).

但是,部分排序根据tpc创建了!((1,2)<(2,1))和!((1,2)>(2,1)),因此可以得出结论(1,2 )==(2,1).但是,c ++标准(2012年1月工作草案)第25.4.3段规定:

对于采用Compare的所有算法,都有一个使用operator <的版本.也就是说,comp(*i,*j)!= false默认为*i <*j!= false.对于25.4.3中描述的算法之外的算法无法正常工作,comp必须对值进行严格的弱排序.

编辑:根据ecatmur的有效答案:部分排序不一定是严格的弱排序; 它打破了不可比性的传递性.所以我想放弃我的推理,即部分排序总是严格的弱排序和相关的问题,并添加问题:我注定要编写自己的拓扑排序算法或使用boost实现,这需要我构建图形？

解决方案:一个关于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在拓扑上排序; 除了一条评论,没有论证支持.

Answer 1

考虑价值观

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;