Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <algorithm>
       4             : #include <cassert>
       5             : #include <iostream>
       6             : #include <list>
       7             : #include <set>
       8             : #include <stdexcept>
       9             : 
      10             : namespace utils::alg {
      11             : 
      12             : template<class T>
      13             : void topological_sort(std::vector<T> &v) {
      14             :     return topological_sort(v, std::less<T>());
      15             : }
      16             : 
      17             : template<class T, class Compare>
      18           2 : void topological_sort(std::vector<T> &v, Compare comp) {
      19           2 :     const size_t N = v.size();
      20             : 
      21           2 :     std::vector<ssize_t> inDegree(N, 0);
      22             : 
      23          14 :     for(size_t i = 0; i < N; ++i) {
      24          84 :         for(size_t j = 0; j < N; ++j) {
      25          72 :             if(comp(v[i], v[j])) {
      26             :                 // Edge from i to j
      27          13 :                 ++inDegree[j];
      28             :             }
      29             :         }
      30             :     }
      31             : 
      32           2 :     std::vector<T> L;
      33           2 :     L.reserve(N);
      34             : 
      35           2 :     std::set<size_t> S;
      36             : 
      37          14 :     for(size_t i = 0; i < N; ++i) {
      38          12 :         if(inDegree[i] == 0) {
      39          12 :             S.insert(i);
      40             :         }
      41             :     }
      42             : 
      43          14 :     while(!S.empty()) {
      44          12 :         size_t n = *S.begin();
      45          12 :         S.erase(S.begin());
      46          12 :         L.emplace_back(v[n]);
      47             : 
      48          84 :         for(size_t m = 0; m < N; ++m) {
      49          72 :             if(inDegree[m] > 0) {
      50          26 :                 if(comp(v[n], v[m])) {
      51          13 :                     --inDegree[m];
      52          13 :                     if(inDegree[m] == 0) {
      53          72 :                         S.insert(m);
      54             :                     }
      55             :                 }
      56             :             }
      57             :         }
      58             :     }
      59             : 
      60           2 :     if(L.size() != N)
      61           0 :         throw std::invalid_argument("Graph has a cycle");
      62             : 
      63           2 :     v = L;
      64           2 : }
      65             : 
      66             : }  // namespace utils::alg