Digraph.hpp
1 // Distributed under the MIT License.
2 // See LICENSE.txt for details.
3 
4 #pragma once
5 
6 #include <type_traits>
7 
8 #include "Utilities/Requires.hpp"
9 #include "Utilities/TMPL.hpp"
10 
11 namespace brigand {
12 
13 template <typename Source, typename Destination, typename Weight = int32_t<1>>
14 struct edge {
15  using source = Source;
16  using destination = Destination;
17  using weight = Weight;
18 };
19 
20 template <int Source, int Destination, int Weight = 1>
21 using edge_ = edge<int32_t<Source>, int32_t<Destination>, int32_t<Weight>>;
22 
23 template <typename T>
24 struct get_source;
25 template <typename Source, typename Destination, typename Weight>
26 struct get_source<edge<Source, Destination, Weight>> {
27  using type = Source;
28 };
29 
30 template <typename T>
31 struct get_destination;
32 template <typename Source, typename Destination, typename Weight>
33 struct get_destination<edge<Source, Destination, Weight>> {
34  using type = Destination;
35 };
36 
37 template <typename T>
38 struct get_weight;
39 template <typename Source, typename Destination, typename Weight>
40 struct get_weight<edge<Source, Destination, Weight>> {
41  using type = Weight;
42 };
43 
44 template <typename State, typename Element>
45 struct add_unique_vertex;
46 
47 template <typename State, typename Source, typename Destination,
48  typename Weight>
49 struct add_unique_vertex<State, edge<Source, Destination, Weight>> {
50  using source = typename if_<found<State, std::is_same<pin<Source>, _1>>,
51  list<>, list<Source>>::type;
52  using destination =
53  typename if_<found<State, std::is_same<pin<Destination>, _1>>, list<>,
54  list<Destination>>::type;
55  using type = append<State, source, destination>;
56 };
57 
58 template <class E, class S, class = std::nullptr_t>
59 struct has_source : std::false_type {};
60 template <class E, class S>
61 struct has_source<E, S, Requires<std::is_same<typename E::source, S>::value>>
62  : std::true_type {};
63 
64 template <class E, class D, class = void>
65 struct has_destination : std::false_type {};
66 template <class E, class D>
67 struct has_destination<
68  E, D, Requires<std::is_same<typename E::destination, D>::value>>
69  : std::true_type {};
70 
71 template <class E, class S, class D>
72 struct has_source_and_destination : std::false_type {};
73 template <template <class...> class E, class S, class D, class W>
74 struct has_source_and_destination<E<S, D, W>, S, D> : std::true_type {};
75 
76 template <class edgeList>
77 struct digraph;
78 
79 namespace detail {
80 template <class Graph, class S, class D>
81 struct get_edge_impl;
82 template <class S, class D, class edgeList>
83 struct get_edge_impl<digraph<edgeList>, S, D> {
84  using type = find<edgeList, has_source_and_destination<_1, pin<S>, pin<D>>>;
85 };
86 } // namespace detail
87 
88 namespace detail {
89 template <class Graph, class S, class D>
90 struct has_edge_impl;
91 template <class S, class D, class edgeList>
92 struct has_edge_impl<digraph<edgeList>, S, D>
93  : found<edgeList, has_source_and_destination<_1, pin<S>, pin<D>>> {};
94 } // namespace detail
95 
96 template <class Graph>
97 struct outgoing_edges_impl;
98 template <class edgeList>
99 struct outgoing_edges_impl<digraph<edgeList>> {
100  using type = typename digraph<edgeList>::adjacency_list;
101 };
102 
103 template <class Graph>
104 struct ingoing_edges_impl;
105 template <class edgeList>
106 struct ingoing_edges_impl<digraph<edgeList>> {
107  using type = typename digraph<edgeList>::ingoing_list;
108 };
109 
110 // This is what we would like to do, but Intel cannot handle it...
111 template <class T, template <class...> class F, class... Es>
112 struct compute_adjacency_list;
113 template <template <class...> class VertexSeq, class... Vertices, class... Es,
114  template <class...> class F>
115 struct compute_adjacency_list<VertexSeq<Vertices...>, F, Es...> {
116  using type = brigand::list<
117  brigand::filter<brigand::list<Es...>, F<brigand::_1, pin<Vertices>>>...>;
118 };
119 
120 template <template <class...> class List, class... edges>
121 struct digraph<List<edges...>> {
122  public:
123  using edge_list = list<edges...>;
124  static_assert(is_set<edge_list>::value,
125  "Cannot have repeated edges in a digraph");
126  using unique_vertex_list =
127  fold<edge_list, list<>, add_unique_vertex<_state, _element>>;
128  using vertex_count = size<unique_vertex_list>;
129  using edge_count = uint32_t<sizeof...(edges)>;
130 
131  using adjacency_list =
132  compute_adjacency_list<unique_vertex_list, has_source, edges...>;
133 
134  using ingoing_list =
135  compute_adjacency_list<unique_vertex_list, has_destination, edges...>;
136 
137  template <class E>
138  static digraph<::brigand::remove<
139  list<edges...>,
140  detail::get_edge_impl<digraph<List<edges...>>, typename E::source,
141  typename E::destination>>>
142  erase(brigand::type_<E>);
143 
144  template <class E>
145  static digraph<push_back<
146  remove<list<edges...>,
147  detail::get_edge_impl<digraph<List<edges...>>, typename E::source,
148  typename E::destination>>,
149  E>>
150  insert(::brigand::type_<E>);
151 };
152 
153 namespace lazy {
154 template <class Graph, class S, class D>
155 using has_edge = ::brigand::detail::has_edge_impl<Graph, S, D>;
156 } // namespace lazy
157 
158 /*!
159  * \ingroup UtilitiesGroup
160  * \brief Check if a digraph has an edge with source `S` and destination `D`
161  *
162  *
163  */
164 template <class Graph, class S, class D>
165 using has_edge = typename ::brigand::lazy::has_edge<Graph, S, D>::type;
166 
167 namespace lazy {
168 template <class Graph, class S, class D>
169 using get_edge = ::brigand::detail::get_edge_impl<Graph, S, D>;
170 } // namespace lazy
171 
172 template <class Graph, class S, class D>
173 using get_edge = typename ::brigand::lazy::get_edge<Graph, S, D>;
174 
175 template <class Graph, class Vertex>
176 using outgoing_edges = at<typename Graph::adjacency_list::type,
177  index_of<typename Graph::unique_vertex_list, Vertex>>;
178 
179 template <class Graph, class Vertex>
180 using ingoing_edges = at<typename Graph::ingoing_list::type,
181  index_of<typename Graph::unique_vertex_list, Vertex>>;
182 
183 template <class Graph>
184 using vertex_count = size<typename Graph::unique_vertex_list>;
185 
186 template <class Graph>
187 using edge_count = size<typename Graph::edge_list>;
188 } // namespace brigand
Definition: Digraph.hpp:11
Defines the type alias Requires.
Definition: Determinant.hpp:11
bool found(const Container &c, const T &value)
Convenience wrapper around std::find, returns true if value is in c.
Definition: Algorithm.hpp:210
Wraps the template metaprogramming library used (brigand)
typename Requires_detail::requires_impl< B >::template_error_type_failed_to_meet_requirements_on_template_parameters Requires
Express requirements on the template parameters of a function or class, replaces std::enable_if_t ...
Definition: Requires.hpp:67
constexpr T & at(std::array< T, N > &arr, Size index)
Retrieve a entry from a container, with checks in Debug mode that the index being retrieved is valid...
Definition: Gsl.hpp:124