Line data    Source code

       1             : #include <catch2/catch_test_macros.hpp>
       2             : 
       3             : #include "utils/alg.hpp"
       4             : 
       5             : using namespace std;
       6             : 
       7           3 : TEST_CASE("Topological sort", "[topological-sort]") {
       8           4 :     SECTION("Test 1") {
       9           2 :         vector<int> v = {2, 9, 5, 4, 1, 8, 0, 6, 3, 7};
      10             : 
      11           1 :         utils::alg::topological_sort(
      12             :             v,
      13             :             [](const int &lhs, const int &rhs) -> bool { return lhs < rhs; }
      14             :         );
      15             : 
      16           4 :         REQUIRE(vector<int>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}) == v);
      17             :     }
      18             : 
      19           4 :     SECTION("Test 2") {
      20           2 :         vector<int>      v   = {0, 1, 2, 3, 4, 5};
      21           1 :         vector<set<int>> adj = {
      22             :             {},
      23             :             {},
      24             :             {3},
      25             :             {1},
      26             :             {0, 1},
      27           8 :             {0, 2}};
      28             : 
      29           1 :         utils::alg::topological_sort(
      30             :             v,
      31          49 :             [&adj](const int &lhs, const int &rhs) -> bool {
      32          49 :                 return adj.at(lhs).count(rhs);
      33             :             }
      34             :         );
      35             : 
      36           4 :         REQUIRE(vector<int>({4, 5, 0, 2, 3, 1}) == v);
      37             :     }
      38             : 
      39           4 :     SECTION("Test 3") {
      40           2 :         vector<int>      v   = {0, 1, 2, 3, 4, 5};
      41           1 :         vector<set<int>> adj = {
      42             :             {1, 3},
      43             :             {2},
      44             :             {},
      45             :             {1, 4, 5},
      46             :             {5},
      47           8 :             {}};
      48             : 
      49           1 :         utils::alg::topological_sort(
      50             :             v,
      51          49 :             [&adj](const int &lhs, const int &rhs) -> bool {
      52          49 :                 return adj.at(lhs).count(rhs);
      53             :             }
      54             :         );
      55             : 
      56           4 :         REQUIRE(vector<int>({0, 3, 1, 2, 4, 5}) == v);
      57             :     }
      58           3 : }