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(namelystrong_orderingandweak_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;
}
}
weak_ordering) or using additional temporary space. \$\endgroup\${' A', 'A', 'B', 'B', 'B', 'B', 'C', ' D', 'D' }. It's just another data set, but the edges are completely different - andtopological_sortneeds 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. \$\endgroup\$