fork(1) download
copy 
  1. #include <iostream>
  2. #include <type_traits>
  3.  
  4. template <std::size_t...> struct index_sequence {};
  5.  
  6. template <std::size_t N, std::size_t... Is>
  7. struct make_index_sequence_helper : make_index_sequence_helper<N-1, N-1, Is...> {};
  8.  
  9. template <std::size_t... Is>
  10. struct make_index_sequence_helper<0, Is...> {
  11.     using type = index_sequence<Is...>;
  12. };
  13.  
  14. template <std::size_t N>
  15. using make_index_sequence = typename make_index_sequence_helper<N>::type;
  16.  
  17. // Merging packs.
  18. template <typename, typename...> struct Merge;
  19.  
  20. template <typename T, template <T...> class P1, template <T...> class P2, T... Is, T... Js>
  21. struct Merge<T, P1<Is...>, P2<Js...>> {
  22. 	using type = P1<Is..., Js...>;
  23. };
  24.  
  25. template <typename T, typename First, typename... Rest>
  26. struct Merge<T, First, Rest...> : Merge<T, First, typename Merge<T, Rest...>::type> {};
  27.  
  28. // Checking if t of type T exists in a pack of T objects.
  29. template <typename T, T t, T...> struct ExistsInPack;
  30.  
  31. template <typename T, T t, T First, T... Rest>
  32. struct ExistsInPack<T, t, First, Rest...> : ExistsInPack<T, t, Rest...> {};
  33.  
  34. template <typename T, T t, T... Rest>
  35. struct ExistsInPack<T, t, t, Rest...> : std::true_type {};
  36.  
  37. template <typename T, T t>
  38. struct ExistsInPack<T, t> : std::false_type {};
  39.  
  40. // Removing duplicates from a pack.
  41. template <typename, typename, typename> struct RemoveDuplicatesHelper;
  42.  
  43. template <typename T, template <T...> class P, T First, T... Rest, T... Accumulated>
  44. struct RemoveDuplicatesHelper<T, P<First, Rest...>, P<Accumulated...>> : std::conditional<ExistsInPack<T, First, Accumulated..., Rest...>::value,
  45. 		RemoveDuplicatesHelper<T, P<Rest...>, P<Accumulated...>>,
  46. 		RemoveDuplicatesHelper<T, P<Rest...>, P<Accumulated..., First>>
  47. 	>::type {};
  48.  
  49. template <typename T, template <T...> class P, T... Accumulated>
  50. struct RemoveDuplicatesHelper<T, P<>, P<Accumulated...>> {
  51. 	using type = P<Accumulated...>;
  52. };
  53.  
  54. template <typename, typename> struct RemoveDuplicates;
  55.  
  56. template <typename T, template <T...> class P, T... Ts>
  57. struct RemoveDuplicates<T, P<Ts...>> : RemoveDuplicatesHelper<T, P<Ts...>, P<>> {};
  58.  
  59. // Obtaining the adjacent vertices of a given vertex.
  60. template <std::size_t, typename, typename> struct AdjacentVerticesHelper;
  61.  
  62. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t From, std::size_t To, std::size_t... RemainingPairs, std::size_t... Accumulated>
  63. struct AdjacentVerticesHelper<Vertex, P<From, To, RemainingPairs...>, P<Accumulated...>> : AdjacentVerticesHelper<Vertex, P<RemainingPairs...>, P<Accumulated...>> {};
  64.  
  65. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t To, std::size_t... RemainingPairs, std::size_t... Accumulated>
  66. struct AdjacentVerticesHelper<Vertex, P<Vertex, To, RemainingPairs...>, P<Accumulated...>> : AdjacentVerticesHelper<Vertex, P<RemainingPairs...>, P<Accumulated..., To>> {};
  67.  
  68. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t... Accumulated>
  69. struct AdjacentVerticesHelper<Vertex, P<>, P<Accumulated...>> {
  70. 	using type = P<Accumulated...>;
  71. 	static const bool nonempty = sizeof...(Accumulated) > 0;
  72. };
  73.  
  74. template <std::size_t, typename> struct AdjacentVertices;
  75.  
  76. template <std::size_t Vertex, template <std::size_t...> class P, std::size_t... Edges>
  77. struct AdjacentVertices<Vertex, P<Edges...>> : AdjacentVerticesHelper<Vertex, P<Edges...>, P<>> {};
  78.  
  79. // Removing from a pack all the elements in P<Visited...>.
  80. template <typename, typename, typename, typename> struct RemoveThoseAlreadyVisitedHelper;
  81.  
  82. template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Accumulated>
  83. struct RemoveThoseAlreadyVisitedHelper<T, P<First, Rest...>, P<Visited...>, P<Accumulated...>> : std::conditional<ExistsInPack<T, First, Visited...>::value,
  84. 		RemoveThoseAlreadyVisitedHelper<T, P<Rest...>, P<Visited...>, P<Accumulated...>>,
  85. 		RemoveThoseAlreadyVisitedHelper<T, P<Rest...>, P<Visited...>, P<Accumulated..., First>>
  86. 	>::type {};
  87.  
  88. template <typename T, template <T...> class P, T... Visited, T... Accumulated>
  89. struct RemoveThoseAlreadyVisitedHelper<T, P<>, P<Visited...>, P<Accumulated...>> {
  90. 	using type = P<Accumulated...>;
  91. };
  92.  
  93. template <typename, typename, typename> struct RemoveThoseAlreadyVisited;
  94.  
  95. template <typename T, template <T...> class P, T... Ts, T... Visited>
  96. struct RemoveThoseAlreadyVisited<T, P<Ts...>, P<Visited...>> : RemoveThoseAlreadyVisitedHelper<T, P<Ts...>, P<Visited...>, P<>> {};
  97.  
  98. template <typename T, template <T...> class P, T... Ts>
  99. struct RemoveThoseAlreadyVisited<T, P<Ts...>, P<>> {  // These remaining specializations are to avoid using the above specialization since 'type' is immediately obvious and needs no computation.
  100. 	using type = P<Ts...>;
  101. };
  102.  
  103. template <typename T, template <T...> class P, T... Visited>
  104. struct RemoveThoseAlreadyVisited<T, P<>, P<Visited...>> {
  105. 	using type = P<>;
  106. };
  107.  
  108. template <typename T, template <T...> class P>
  109. struct RemoveThoseAlreadyVisited<T, P<>, P<>> {  // This is needed to avoid ambiguity with the above two specializations.
  110. 	using type = P<>;
  111. };
  112.  
  113. // Now the main structs.
  114. template <typename, typename, typename, typename, typename> struct TopologicalSort;
  115. template <typename, typename, typename, typename, typename, typename> struct TopologicalSortHelper;
  116. template <typename, typename, typename, typename, typename, typename> struct UpdateStack;
  117. template <typename, typename, typename, typename, typename> struct ReturnToTopologicalSort;
  118.  
  119. // End of the topological sort loop.  Replacing P<Visited...> with typename Visited and/or P<Edges...> with typename Edges and/or P<Vertices...> with typename Stack will cause ambiguity compiling error since neither this nor the above partial specialization is more specialized than the other. 
  120. template <typename T, template <T...> class P, T... Visited, T... Edges, T... Vertices>
  121. struct TopologicalSort<T, P<>, P<Edges...>, P<Visited...>, P<Vertices...>> {
  122. 	using topological_sort = P<Vertices...>;  // The final stack of vertices describing a topological order.
  123. 	using visited = P<Visited...>;  // This is just to check that P<Visited...> does not have repeats (to ensure optimal performance).
  124. };
  125.  
  126. // The topological sort loop.
  127. template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Edges, T... Vertices>  // First, Rest... are the vertices to be visited now (in that order).
  128. struct TopologicalSort<T, P<First, Rest...>, P<Edges...>, P<Visited...>, P<Vertices...>> :
  129. 	TopologicalSortHelper<T, P<First, Rest...>, P<Edges...>, P<Visited..., First>, P<Vertices...>,  // Append First to P<Visited...>.
  130. 			typename RemoveThoseAlreadyVisited<T, typename AdjacentVertices<First, P<Edges...>>::type, P<Visited...>>::type> {};  // Pass the adjacent vertices of First (if any), except those that have already been visited.
  131.  
  132. // The first type in ToVisit... has adjacent edges, so visit its adjacent vertices, and prepend this first type to P<Vertices...> AFTER these visits.
  133. template <typename T, template <T...> class P, T... ToVisit, T... Visited, T... Edges, T... Vertices, typename AdjacentVertices>
  134. struct TopologicalSortHelper<T, P<ToVisit...>, P<Edges...>, P<Visited...>, P<Vertices...>, AdjacentVertices> :
  135. 	UpdateStack<T, P<ToVisit...>, P<Edges...>, P<Visited...>, P<Vertices...>, TopologicalSort<T, AdjacentVertices, P<Edges...>, P<Visited...>, P<>>> {};  // Must use P<> instead of P<Vertices...> here, because we are going to adjoin the topological_sort of this particular subtree to P<Vertices...>.
  136.  
  137. // First has no adjacent vertices, so prepend it to P<Vertices...>.  Simply prepend First to P<Vertices...>, and move on to Rest...
  138. template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Edges, T... Vertices>
  139. struct TopologicalSortHelper<T, P<First, Rest...>, P<Edges...>, P<Visited...>, P<Vertices...>, P<>> : TopologicalSort<T, P<Rest...>, P<Edges...>, P<Visited...>, P<First, Vertices...>> {};
  140.  
  141. // Updating P<Vertices...> after all adjacent (unvisited) edges have been visited.
  142. template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Edges, T... Vertices, typename AdjacentEdgesTopologicalSort>
  143. struct UpdateStack<T, P<First, Rest...>, P<Edges...>, P<Visited...>, P<Vertices...>, AdjacentEdgesTopologicalSort> :
  144. 	ReturnToTopologicalSort<T, P<Rest...>, P<Edges...>,
  145. 		typename RemoveDuplicates<T, typename Merge<T, P<Visited...>, typename AdjacentEdgesTopologicalSort::visited>::type>::type,  // RemoveDuplicates is actually not necessarily (the results are still correct without it), but without it the P<Visited...> will have many duplicates in general and thus lead to slower computation of RemoveThoseAlreadyVisited. 
  146. 		typename Merge<T, P<First>, typename AdjacentEdgesTopologicalSort::topological_sort, P<Vertices...>>::type  // Wrapping the merge result with RemoveDuplicates is apparently not necessary, as it is apparently mathematically impossible for there to be duplicates after this merge.
  147. 	> {};
  148.  
  149. // Return to TopologicalSort, but first remove from ToVisit... all those that are in Visited...
  150. template <typename T, template <T...> class P, T... ToVisit, T... Visited, T... Edges, T... Vertices>
  151. struct ReturnToTopologicalSort<T, P<ToVisit...>, P<Edges...>, P<Visited...>, P<Vertices...>> :
  152. 	TopologicalSort<T, typename RemoveThoseAlreadyVisited<T, P<ToVisit...>, P<Visited...>>::type, P<Edges...>, P<Visited...>, P<Vertices...>> {};  // RemoveThoseAlreadyVisited is absolutely necesary.
  153.  
  154. // Now the Graph classes themselves.
  155. template <std::size_t N, std::size_t... Edges>
  156. struct Graph1 : TopologicalSort<std::size_t, make_index_sequence<N>, index_sequence<Edges...>, index_sequence<>, index_sequence<>> {};
  157.  
  158. // Sorter class needed for class Graph2, where the vertices can be non-consecutive integers, and the number of vertices does not need to be specified.
  159. template <std::size_t I, std::size_t J>
  160. struct IntLessThan : std::conditional<(I < J), std::true_type, std::false_type>::type {};
  161.  
  162. template <std::size_t, typename> struct PrependInt;
  163.  
  164. template <std::size_t N, template <std::size_t...> class Z, std::size_t... Is>  
  165. struct PrependInt<N, Z<Is...>> {  
  166. 	using type = Z<N, Is...>;  
  167. };
  168.  
  169. template <template<std::size_t> class, typename> struct FilterInts;  
  170.  
  171. template <template<std::size_t> class F, template <std::size_t...> class Z, std::size_t I, std::size_t... Is>  
  172. struct FilterInts<F, Z<I, Is...>> {
  173. 	using type = typename std::conditional<F<I>::value,
  174. 		typename PrependInt<I, typename FilterInts<F, Z<Is...>>::type>::type,
  175. 		typename FilterInts<F, Z<Is...>>::type
  176. 	>::type;  
  177. };
  178.  
  179. template <template<std::size_t> class F, template <std::size_t...> class Z>  
  180. struct FilterInts<F, Z<>> {  
  181. 	using type = Z<>;  
  182. };  
  183.  
  184. template <typename, typename> struct MergeIntSequences;  
  185.  
  186. template <template <std::size_t...> class Z, std::size_t... Is, std::size_t... Js>  
  187. struct MergeIntSequences<Z<Is...>, Z<Js...>> {  
  188. 	using type = Z<Is..., Js...>;
  189. };
  190.  
  191. template <typename, template <std::size_t, std::size_t> class = IntLessThan> struct SortIntSequence;  
  192.  
  193. template <template <std::size_t...> class Z, std::size_t N, std::size_t... Is, template <std::size_t, std::size_t> class Comparator>  
  194. struct SortIntSequence<Z<N, Is...>, Comparator> {  
  195. 	template<std::size_t I> struct less_than : std::integral_constant<bool, Comparator<I,N>::value> {};
  196. 	template <std::size_t I> struct more_than : std::integral_constant<bool, Comparator<N,I>::value || I == N> {};  
  197. 	using subsequence_less_than_N = typename FilterInts<less_than, Z<Is...>>::type;
  198. 	using subsequence_more_than_N = typename FilterInts<more_than, Z<Is...>>::type; 
  199. 	using type = typename MergeIntSequences<typename SortIntSequence<subsequence_less_than_N, Comparator>::type,  
  200. 		typename PrependInt<N, typename SortIntSequence<subsequence_more_than_N, Comparator>::type>::type 
  201. 	>::type;
  202. };
  203.  
  204. template<template <std::size_t...> class Z, template <std::size_t, std::size_t> class Comparator>  
  205. struct SortIntSequence<Z<>, Comparator> {  
  206. 	using type = Z<>;  
  207. };
  208.  
  209. // Graph2 is more flexible than Graph1 because the vertices can be non-consecutive integers, and the number of vertices does not need to be specified since that can be deduced by the vertices.
  210. template <std::size_t... Edges>
  211. struct Graph2 : TopologicalSort<std::size_t, typename SortIntSequence<typename RemoveDuplicates<std::size_t, index_sequence<Edges...>>::type>::type,  // All duplicates removed, and the vertices MUST be sorted for this to compile (though I didn't bother tracing why).  Of course, the vertices in Graph1 are already sorted.
  212. 	index_sequence<Edges...>, index_sequence<>, index_sequence<>> {};
  213.  
  214. // -------------------------- Testing --------------------------
  215. template <std::size_t Last>
  216. struct index_sequence<Last> {
  217.     static void print() {std::cout << Last << std::endl;}
  218. };
  219.  
  220. template <std::size_t First, std::size_t... Rest>
  221. struct index_sequence<First, Rest...> {
  222.     static void print() {std::cout << First << ' ';  index_sequence<Rest...>::print();}
  223. };
  224.  
  225. int main() {
  226. 	using DAG1 = Graph1<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>;
  227. 	std::cout << "Topological sort of DAG1:  ";  DAG1::topological_sort::print();  // 5 4 2 3 1 0  (identical to the run-time solution at the top)
  228. 	std::cout << "Vertices visited in DAG1:  ";  DAG1::visited::print();  // 1 2 3 4 5 (no repeats)
  229. 	std::cout << std::boolalpha << std::is_same<DAG1::topological_sort, index_sequence<5,4,2,3,1,0>>::value << std::endl;  // true
  230.  
  231. 	using DAG2 = Graph1<8, 0,1, 0,2, 0,3, 1,4, 1,5, 2,4, 2,6, 3,5, 3,6, 4,7, 5,7, 6,7>;
  232. 	std::cout << "\nTopological sort of DAG2:  ";  DAG2::topological_sort::print();  // 0 3 2 6 1 5 4 7  (identical to the run-time solution at the top)
  233. 	std::cout << "Vertices visited in DAG2:  ";  DAG2::visited::print();  // 0 1 4 7 5 2 6 3 (no repeats)
  234. 	std::cout << std::is_same<DAG2::topological_sort, index_sequence<0,3,2,6,1,5,4,7>>::value << std::endl;  // true
  235.  
  236. 	using DAG3 = Graph1<8, 5,1, 1,2, 1,0, 1,6, 7,1, 7,4, 4,6, 3,0, 3,4>;  // This has the same edges as DAG5, with 11 renamed to 1, 10 renamed to 0, 9 renamed to 6, and 8 renamed to 4.
  237. 	std::cout << "\nTopological sort of DAG3:  ";  DAG3::topological_sort::print();  // 7 5 3 4 1 6 2 0  (identical to the run-time solution at the top)
  238. 	std::cout << "Vertices visited in DAG3:  ";  DAG3::visited::print();  // 0 1 2 6 3 4 5 7 (no repeats)
  239. 	std::cout << std::is_same<DAG3::topological_sort, index_sequence<7,5,3,4,1,6,2,0>>::value << std::endl;  // true
  240.  
  241. 	std::cout << "\n\nUsing Graph2:" << std::endl;
  242. 	using DAG4 = Graph2<0,1, 0,2, 0,3, 1,4, 1,5, 2,4, 2,6, 3,5, 3,6, 4,7, 5,7, 6,7>;
  243. 	DAG4::topological_sort::print();  // 0 3 2 6 1 5 4 7  (same solution as DAG2 using the Graph1 class)
  244. 	std::cout << std::is_same<DAG4::topological_sort, index_sequence<0,3,2,6,1,5,4,7>>::value << std::endl;  // true
  245.  
  246. 	using DAG5 = Graph2<5,11, 11,2, 11,10, 11,9, 7,11, 7,8, 8,9, 3,10, 3,8>;  // See the first diagram in http://e...content-available-to-author-only...a.org/wiki/Directed_acyclic_graph for a picture of this graph.
  247. 	DAG5::topological_sort::print();  // 7 5 11 3 8 9 10 2  (this is indeed a valid topological sort)
  248.  
  249. 	using DAG6 = Graph2<5,1, 1,2, 1,0, 1,6, 7,1, 7,4, 4,6, 3,0, 3,4>;  // This Graph2 type has the same edges as DAG5, with 11 renamed to 1, 10 renamed to 0, 9 renamed to 6, and 8 renamed to 4.
  250. 	DAG6::topological_sort::print();  // 7 5 3 4 1 6 2 0  (identical to the run-time solution at the top)
  251. 	std::cout << std::is_same<DAG6::topological_sort, index_sequence<7,5,3,4,1,6,2,0>>::value << std::endl;  // true
  252. }
Success #stdin #stdout 0s 3100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Topological sort of DAG1:  5 4 2 3 1 0
Vertices visited in DAG1:  0 1 2 3 4 5
true

Topological sort of DAG2:  0 3 2 6 1 5 4 7
Vertices visited in DAG2:  0 1 4 7 5 2 6 3
true

Topological sort of DAG3:  7 5 3 4 1 6 2 0
Vertices visited in DAG3:  0 1 2 6 3 4 5 7
true


Using Graph2:
0 3 2 6 1 5 4 7
true
7 5 11 3 8 9 10 2
7 5 3 4 1 6 2 0
true
https://ideone.com/U1bbRM
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!