C++2a comparison-based topological sort algorithm

Question

Here's my attempt at a C++2a Standard Library–friendly "topological sort" algorithm. There are several areas of interest here:

• The algorithm is comparison-based and in-place, just like std::sort. This makes it something like \$\mathcal{O}(n^3)\,ドル which is certainly worse than it ought to be. Can we speed it up somehow without requiring any extra memory?

• Is my use of operator<=>, partial_ordering, etc. idiomatic? (Obviously we're still in the process of developing these idioms, but I think it'd be good to start talking about them.)

• I threw in an "optimization" for comparison categories other than partial_ordering (namely strong_ordering and weak_ordering). Is this safe? Is this smart? Is this sufficiently smart?

---

#include <algorithm>
#include <compare>
#include <iterator>
#include <type_traits>
// Some helpers that should be standard but aren't.
template<class It> using iterator_category_t = typename std::iterator_traits<It>::iterator_category;
template<class It> using iterator_value_type_t = typename std::iterator_traits<It>::value_type;
template<class It> struct is_forward_iterator : std::is_base_of<std::forward_iterator_tag, iterator_category_t<It>> {};
template<class It> inline constexpr bool is_forward_iterator_v = is_forward_iterator<It>::value;
template<class It> struct is_random_access_iterator : std::is_base_of<std::random_access_iterator_tag, iterator_category_t<It>> {};
template<class It> inline constexpr bool is_random_access_iterator_v = is_random_access_iterator<It>::value;
template<class T> struct is_weak_ordering : std::is_convertible<T, std::weak_ordering> {};
template<class T> inline constexpr bool is_weak_ordering_v = is_weak_ordering<T>::value;
// One more helper that WILL be standard but isn't.
template<class T = void>
struct spaceship {
 constexpr auto operator()(const T& a, const T& b) const -> decltype(a <=> b) {
 return a <=> b;
 }
};
template<>
struct spaceship<void> {
 template<class T, class U>
 constexpr auto operator()(T&& t, U&& u) const
 -> decltype(std::forward<T>(t) <=> std::forward<U>(u)) {
 return (std::forward<T>(t) <=> std::forward<U>(u));
 }
 using is_transparent = void;
};
// Here's the topological sorting algorithm itself.
template<class FwdIt, class Comparator = spaceship<iterator_value_type_t<FwdIt>>>
void topological_sort(FwdIt first, FwdIt last, Comparator cmp = Comparator{})
{
 if constexpr (
 is_random_access_iterator_v<FwdIt> &&
 is_weak_ordering_v<decltype(cmp(*first, *first))>
 ) {
 std::sort(first, last, [&](const auto& a, const auto& b) {
 return cmp(a, b) < 0;
 });
 } else {
 for (auto mark = first; mark != last; ++mark) {
 auto current_min = mark;
 auto last_min = current_min;
 while (true) {
 for (auto it = mark; it != last; ++it) {
 if (cmp(*it, *current_min) < 0) {
 current_min = it;
 }
 }
 if (last_min == current_min) break;
 last_min = current_min;
 }
 if (current_min != mark) {
 using std::swap;
 swap(*current_min, *mark);
 }
 }
 }
}

Finally, here's some quick-and-dirty testing code. The Task example is cribbed from one of the answers to https://stackoverflow.com/questions/11230881/stable-topological-sort .

#include <iostream>
#include <list>
#include <vector>
struct Task {
 char k;
 Task(char k): k(k) {}
 bool operator==(Task rhs) const { return k == rhs.k; }
 bool operator!=(Task rhs) const { return k != rhs.k; }
 bool depends_on(Task rhs) const {
 if (k == 'A' && rhs.k == 'B') return true;
 if (k == 'B' && rhs.k == 'D') return true;
 return false;
 }
 struct order {
 std::partial_ordering operator()(Task a, Task b) const {
 if (a == b) return std::partial_ordering::equivalent;
 if (b.depends_on(a)) return std::partial_ordering::less;
 if (a.depends_on(b)) return std::partial_ordering::greater;
 return std::partial_ordering::unordered;
 }
 };
};
float nan() { return 0./0.; }
int main()
{
 std::vector<int> vi {3, 1, 4, 1, 5, 9, 2, 6, 5};
 topological_sort(vi.begin(), vi.end());
 for (auto&& elt : vi) {
 std::cout << elt << std::endl;
 }
 std::vector<float> vec {3, nan(), 1, 4, 1, 5, nan(), 2, 6, nan()};
 topological_sort(vec.begin(), vec.end());
 for (auto&& elt : vec) {
 std::cout << elt << std::endl;
 }
 std::list<Task> tasks { 'A','B','C','D','E','F' };
 topological_sort(tasks.begin(), tasks.end(), Task::order{});
 for (auto&& elt : tasks) {
 std::cout << elt.k << std::endl;
 }
}

Here's the complete code on Godbolt.

• hoffmale: It seems like the DFS approach from the linked wikipedia article could be worked into a general \$\mathcal{O}(n^2)\$ topological sort (well, by using stack space for recursion...). It's really hard to lower the runtime complexity of the task without harder guarantees (like weak_ordering) or using additional temporary space.
• Phil H: Have you looked at Kahn, as described in en.wikipedia.org/wiki/Topological_sorting ? O(Verts+Edges)
• Quuxplusone: @PhilH: I've definitely read the Wikipedia page; it doesn't seem interested in comparison-based topological sort algorithms. O(V+E) is great and all, but merely to compute the value of E takes O(V^2) comparisons... and you can't store the resulting set anywhere unless you can dig up O(V^2) extra space...
• Phil H: I will freely admit this isn't my specialism, but it seems... rare... to do a topological sort on a graph whose edges you do not know. And in the case of a standard, I would expect O(V+E) on normal use to outweigh O(n^3) on an unusual one. But, I may be completely unclear what you mean, so by all means give an example.
• hoffmale: @PhilH: Nothing prevents me in the task example from changing the vector to {' A', 'A', 'B', 'B', 'B', 'B', 'C', ' D', 'D' }. It's just another data set, but the edges are completely different - and topological_sort needs to cope with that. No child knows all the parents, no parent knows all its children, they just know "that specific instance is a parent/child of mine".if you compare them.

Answer 1

What's "C++2a-friendly" anyway?

I'm not sure what you mean by C++2a-friendly. The spaceship operator isn't out yet, and will be part of the next standard. So it isn't C++2a-friendly, it's C++2a period, or what don't I understand?

If by C++2a-friendly you mean: using available features from the next standard (e.g concepts in gcc), I believe you can do a bit better than you do. For instance, type traits should be expressed as concepts, and overloads on concepts should allow for algorithm selection.

Here's an example of how it looks like in gcc, with -fconcepts enabled:

#include <iostream>
#include <iterator>
#include <vector>
#include <list>
template <typename T>
concept bool RandomAccessIterator = requires (T a, T b, std::size_t n) {
 {a - b} -> std::size_t;
 {a < b} -> bool;
 {a[n] } -> typename std::iterator_traits<T>::value_type&;
 // etc.
};
template <typename Iterator> // unconstrained template argument
bool is_long(Iterator, Iterator) {
 std::cout << "Not a random access Iterator, couldn't compute distance!\n";
 return false;
}
template <RandomAccessIterator Iterator> // Iterator must satisfy the concept
bool is_long(Iterator f, Iterator l) {
 std::cout << "computing distance...\n";
 return std::distance(f, l) < 10 ? false : true;
}
int main() {
 std::vector<int> vec(20, 3);
 std::list<int> lst(18,5);
 std::cout << std::boolalpha << is_long(vec.begin(), vec.end()) << std::endl;
 std::cout << is_long(lst.begin(), lst.end());
}

You can be more expressive

I needed time to understand why is_weak_ordering_v is a condition to use std::sort, until I got that it truly means that the elements are totally ordered (strong_ordering is convertible to weak_ordering). It's the kind of little things that affect readability; is_totally_ordered would have been better in my opinion.

You can also be more expressive by using standard algorithms. For instance,

 // ...
 auto current_min = mark;
 for (auto it = mark; it != last; ++it) {
 if (cmp(*it, *current_min) < 0) {
 current_min = it;
 }
 }

can be expressed as:

auto current_min = std::min_element(mark, last, [&cmp](const auto& a, const auto& b) {
 return cmp(a, b) < 0;
});

Can you really make topological sort standard?

I'm skeptical. It means you have to rely on iterators as an abstraction over the set of elements and that, in turn, means: either that the edges are apparent in the elements lay-out (i.e: the range between iterators is already topologically sorted), or that the dependencies are hidden inside the elements, which seems really sub-optimal to me.

• hoffmale: A totally ordered set doesn't allow ties between elements, so that only describes std::strong_ordering. std::weak_ordering does allow ties, so it is more general, and calling it a "total order" would be wrong (as it isn't). // Re last point: Or the dependencies could (only) be known to the Comparer.
• papagaga: @hoffmale: "total order" might not be the right term; by that I meant that all the elements can be compared one to another. is_weak_ordering is generally understood in opposition to is_strong_ordering, not is_partial_ordering.
• Quuxplusone: I believe that to the extent C++ has a notion of "total ordering," it does indeed mean "total weak ordering." Whether ties between different (i.e. non-substitutable) elements are allowed [i.e. weakness/strongness] is orthogonal to whether unorderedness between different elements is allowed [partialness/totalness], but the C++2a Working Draft essentially does not admit the possibility of a "strong partial order," any more than C++03 admitted the possibility of a "bidirectional output iterator." (Also in C++ "strong" is a synonym for what normal people seem to call "strict".)
• Quuxplusone: Good point on min_element. Re "type traits should be expressed as concepts, and overloads on concepts should allow for algorithm selection", I would be delighted to see an example of how that should look in this specific case — naturally, posted as an answer, to reap well-deserved upvotes. :)
• papagaga: @Quuxplusone: I've added a simplified concept example.

Answer 2

Here are some C++20'y things you can use to improve your code even further (and some non-C++20'y things).

Some helpers that should be standard but aren't.

Where's your proposal? :) Just kidding of course.

1. Down with typename! Please remove those typenames in the first two using declarations, they are unnecessary.

2. (削除) What's up with the decltype(a <=> b)? Just use decltype(auto) as the return type. (削除ここまで) SFINAE, although as OP said: It might not make sense to be SFINAE-friendly here because the other comparison function objects aren't.

3. With constraints you can split off topological_sort:

   template<class FwdIt, class Comparator = spaceship<iterator_value_type_t<FwdIt>>>
    requires is_random_access_iterator_v<FwdIt> &&
    is_weak_ordering_v<decltype(cmp(*first, *first))>
   void topological_sort(FwdIt first, FwdIt last, Comparator cmp = Comparator{})
   {
    std::sort(first, last, [&](const auto& a, const auto& b) {
    return cmp(a, b) < 0;
    });
   }
   template<class FwdIt, class Comparator = spaceship<iterator_value_type_t<FwdIt>>>
   void topological_sort(FwdIt first, FwdIt last, Comparator cmp = Comparator{})
   {
    for (auto mark = first; mark != last; ++mark) {
    auto current_min = mark;
    auto last_min = current_min;
    while (true) {
    for (auto it = mark; it != last; ++it) {
    if (cmp(*it, *current_min) < 0) {
    current_min = it;
    }
    }
    if (last_min == current_min) break;
    last_min = current_min;
    }
    if (current_min != mark) {
    using std::swap;
    swap(*current_min, *mark);
    }
    }
   }
   

4. As already mentioned, you can use std::min_element.

5. Use std::iter_swap instead of using std::swap; swap(/*...*/);.

6. You can use concepts to simplify your type traits. For example:

   template<class It>
   concept RandomAccessIterator = std::is_base_of_v<std::random_access_iterator_tag, iterator_category_t<It>>;
   

7. You can drop the explicit specialization of spaceship<void> by using the same trick as topological_sort. You can merge the two call operators into the same class, and then use constraints to the second one better to overload resolution using requires std::is_same_v<void, T>.

• Quuxplusone: "What's up with the decltype(a <=> b)?" — SFINAE! Although I'm not sure if we want to care about SFINAE here. std::plus<T>::operator() just pretends that T + T always returns T, but for T <=> T I don't think there's any even remotely sane "default" return type. Maybe the non-transparent version of std::spaceship really shouldn't exist.
• Rakete1111: @Quuxplusone Oh yeah, I wasn't even thinking about SFINAE. Yeah, probably.
• Quuxplusone: Also: I weakly disagree with 1 (I'd rather write typename the way I've been doing since C++98, than track down compiler errors related to omitting it when it couldn't be omitted — but I am sure I'll come around eventually); 3 is definitely true but doesn't that make the code longer and overload resolution harder, compared to if constexpr?; 4+5 good points; 6 missing a _v but good point; 7 I don't understand quite what you mean here.
• Rakete1111: @Quuxplusone Oh wow, you're the first one to actively like typename ;) I guess you could argue that it does make the code longer, but I think it reduces the cognitive overhead of analysing the function (you are effectively using two separate algorithms => so two overloads IMO). 6) (oops, nvm, you're right.) 7. Merge the two call operators into same class and use a requires on one to make it preferable when T = void.