Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 :
4 : #pragma once
5 :
6 : #include <brigand/brigand.hpp>
7 : #include <type_traits>
8 :
9 : #include "Utilities/Requires.hpp"
10 :
11 : namespace brigand {
12 :
13 : template <typename Source, typename Destination, typename Weight = int32_t<1>>
14 0 : struct edge {
15 0 : using source = Source;
16 0 : using destination = Destination;
17 0 : using weight = Weight;
18 : };
19 :
20 : template <int Source, int Destination, int Weight = 1>
21 0 : using edge_ = edge<int32_t<Source>, int32_t<Destination>, int32_t<Weight>>;
22 :
23 : template <typename T>
24 0 : struct get_source;
25 : template <typename Source, typename Destination, typename Weight>
26 0 : struct get_source<edge<Source, Destination, Weight>> {
27 0 : using type = Source;
28 : };
29 :
30 : template <typename T>
31 0 : struct get_destination;
32 : template <typename Source, typename Destination, typename Weight>
33 0 : struct get_destination<edge<Source, Destination, Weight>> {
34 0 : using type = Destination;
35 : };
36 :
37 : template <typename T>
38 0 : struct get_weight;
39 : template <typename Source, typename Destination, typename Weight>
40 0 : struct get_weight<edge<Source, Destination, Weight>> {
41 0 : using type = Weight;
42 : };
43 :
44 : template <typename State, typename Element>
45 0 : struct add_unique_vertex;
46 :
47 : template <typename State, typename Source, typename Destination,
48 : typename Weight>
49 0 : struct add_unique_vertex<State, edge<Source, Destination, Weight>> {
50 0 : using source = typename if_<found<State, std::is_same<pin<Source>, _1>>,
51 : list<>, list<Source>>::type;
52 0 : using destination =
53 : typename if_<found<State, std::is_same<pin<Destination>, _1>>, list<>,
54 : list<Destination>>::type;
55 0 : using type = append<State, source, destination>;
56 : };
57 :
58 : template <class E, class S, class = std::nullptr_t>
59 0 : 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 0 : 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 0 : struct has_source_and_destination : std::false_type {};
73 : template <template <class...> class E, class S, class D, class W>
74 0 : struct has_source_and_destination<E<S, D, W>, S, D> : std::true_type {};
75 :
76 : template <class edgeList>
77 0 : 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 0 : struct outgoing_edges_impl;
98 : template <class edgeList>
99 0 : struct outgoing_edges_impl<digraph<edgeList>> {
100 0 : using type = typename digraph<edgeList>::adjacency_list;
101 : };
102 :
103 : template <class Graph>
104 0 : struct ingoing_edges_impl;
105 : template <class edgeList>
106 0 : struct ingoing_edges_impl<digraph<edgeList>> {
107 0 : 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 0 : struct compute_adjacency_list;
113 : template <template <class...> class VertexSeq, class... Vertices, class... Es,
114 : template <class...> class F>
115 0 : struct compute_adjacency_list<VertexSeq<Vertices...>, F, Es...> {
116 0 : 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 0 : struct digraph<List<edges...>> {
122 : public:
123 0 : using edge_list = list<edges...>;
124 : static_assert(is_set<edge_list>::value,
125 : "Cannot have repeated edges in a digraph");
126 0 : using unique_vertex_list =
127 : fold<edge_list, list<>, add_unique_vertex<_state, _element>>;
128 0 : using vertex_count = size<unique_vertex_list>;
129 0 : using edge_count = uint32_t<sizeof...(edges)>;
130 :
131 0 : using adjacency_list =
132 : compute_adjacency_list<unique_vertex_list, has_source, edges...>;
133 :
134 0 : 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 0 : 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 0 : insert(::brigand::type_<E>);
151 : };
152 :
153 : namespace lazy {
154 : template <class Graph, class S, class D>
155 0 : 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 1 : 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 0 : using get_edge = ::brigand::detail::get_edge_impl<Graph, S, D>;
170 : } // namespace lazy
171 :
172 : template <class Graph, class S, class D>
173 0 : using get_edge = typename ::brigand::lazy::get_edge<Graph, S, D>;
174 :
175 : template <class Graph, class Vertex>
176 0 : 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 0 : using ingoing_edges = at<typename Graph::ingoing_list::type,
181 : index_of<typename Graph::unique_vertex_list, Vertex>>;
182 :
183 : template <class Graph>
184 0 : using vertex_count = size<typename Graph::unique_vertex_list>;
185 :
186 : template <class Graph>
187 0 : using edge_count = size<typename Graph::edge_list>;
188 : } // namespace brigand
|
