10#include <ossia/detail/config.hpp>
12#include <boost/concept/assert.hpp>
13#include <boost/config.hpp>
14#include <boost/graph/adjacency_list.hpp>
15#include <boost/graph/graph_concepts.hpp>
16#include <boost/graph/named_function_params.hpp>
17#include <boost/graph/strong_components.hpp>
18#include <boost/graph/topological_sort.hpp>
28inline void union_successor_sets(
29 const std::vector<std::size_t>& s1,
const std::vector<std::size_t>& s2,
30 std::vector<std::size_t>& s3)
32 BOOST_USING_STD_MIN();
33 for(std::size_t k = 0; k < s1.size(); ++k)
34 s3[k] =
min BOOST_PREVENT_MACRO_SUBSTITUTION(s1[k], s2[k]);
38 typename TheContainer,
typename ST = std::size_t,
39 typename VT =
typename TheContainer::value_type>
42 typedef VT& result_type;
44 subscript_t(TheContainer& c)
48 VT& operator()(
const ST& i)
const {
return (*container)[i]; }
51 TheContainer* container;
53template <
typename TheContainer>
54subscript_t<TheContainer> subscript(TheContainer& c)
56 return subscript_t<TheContainer>(c);
60template <
typename Graph,
typename GraphTC>
61struct TransitiveClosureState
63 using VertexIndexMap =
64 typename boost::property_map<Graph, boost::vertex_index_t>::const_type;
66 using vertex =
typename boost::graph_traits<Graph>::vertex_descriptor;
67 using size_type =
typename boost::property_traits<VertexIndexMap>::value_type;
68 using tc_vertex =
typename boost::graph_traits<GraphTC>::vertex_descriptor;
69 using cg_vertex = size_type;
70 using CG_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS>;
72 std::vector<tc_vertex> to_tc_vec;
74 std::vector<cg_vertex> component_number_vec;
75 std::vector<std::vector<vertex>> components;
79 std::vector<cg_vertex> adj;
81 std::vector<cg_vertex> topo_order;
82 std::vector<cg_vertex> topo_number;
84 std::vector<std::vector<cg_vertex>> CG_vec;
85 std::vector<std::vector<cg_vertex>> chains;
86 std::vector<cg_vertex> in_a_chain;
88 std::vector<size_type> chain_number;
89 std::vector<size_type> pos_in_chain;
91 std::vector<std::vector<cg_vertex>> successors;
95void resize_and_fill(T& vec,
const std::size_t N)
101void resize_and_fill(std::vector<std::vector<T>>& vec,
const std::size_t N)
103 const auto cur = vec.size();
105 for(std::size_t i = 0; i < std::min(cur, N); i++)
113 std::vector<std::vector<T>>& vec,
const std::size_t N,
const std::size_t init_num,
117 for(std::size_t i = 0; i < N; i++)
119 auto cur = vec[i].size();
120 vec[i].resize(init_num, init_val);
121 std::fill(vec[i].begin(), vec[i].begin() + std::min(cur, init_num), init_val);
126 typename Graph,
typename GraphTC,
typename G_to_TC_VertexMap,
127 typename VertexIndexMap>
128void transitive_closure(
129 const Graph& g, GraphTC& tc, G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map,
130 TransitiveClosureState<Graph, GraphTC>& state)
132 using namespace boost;
133 if(num_vertices(g) == 0)
135 typedef typename graph_traits<Graph>::vertex_descriptor vertex;
136 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
137 typedef typename property_traits<VertexIndexMap>::value_type size_type;
139 BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
140 BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept<Graph>));
141 BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept<GraphTC>));
142 BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<GraphTC>));
143 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<VertexIndexMap, vertex>));
145 typedef size_type cg_vertex;
146 const auto n_vtx = num_vertices(g);
147 auto& component_number_vec = state.component_number_vec;
148 resize_and_fill(component_number_vec, n_vtx);
149 iterator_property_map<cg_vertex*, VertexIndexMap, cg_vertex, cg_vertex&>
150 component_number(&component_number_vec[0], index_map);
153 = strong_components(g, component_number, vertex_index_map(index_map));
155 auto& components = state.components;
156 resize_and_fill(components, num_scc);
157 build_component_lists(g, num_scc, component_number, components);
159 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> CG_t;
163 for(cg_vertex s = 0; s < components.size(); ++s)
165 auto& adj = state.adj;
167 for(size_type i = 0; i < components[s].size(); ++i)
169 const auto u = components[s][i];
170 for(
auto [v, v_end] = adjacent_vertices(u, g); v != v_end; ++v)
172 const auto t = component_number[*v];
178 ossia::remove_duplicates(adj);
179 for(
auto i = adj.begin(); i != adj.end(); ++i)
185 assert(num_scc == num_vertices(CG));
186 auto& topo_order = state.topo_order;
188 topo_order.reserve(num_scc);
189 auto& topo_number = state.topo_number;
190 topo_number.resize(num_scc);
192 CG, std::back_inserter(topo_order), vertex_index_map(identity_property_map()));
193 std::reverse(topo_order.begin(), topo_order.end());
195 for(
auto iter = topo_order.begin(); iter != topo_order.end(); ++iter)
196 topo_number[*iter] = n++;
198 auto& CG_vec = state.CG_vec;
199 CG_vec.resize(num_scc);
200 for(size_type i = 0; i < num_scc; ++i)
202 auto pr = adjacent_vertices(i, CG);
203 CG_vec[i].assign(pr.first, pr.second);
204 std::sort(CG_vec[i].begin(), CG_vec[i].end(), [&](cg_vertex lhs, cg_vertex rhs) {
205 return topo_number[lhs] < topo_number[rhs];
209 auto& chains = state.chains;
211 chains.reserve(std::log2(n_vtx));
213 auto& in_a_chain = state.in_a_chain;
214 resize_and_fill(in_a_chain, num_scc);
215 for(cg_vertex v : topo_order)
219 chains.resize(chains.size() + 1);
220 auto& chain = chains.back();
224 in_a_chain[v] =
true;
225 auto next = std::find_if(CG_vec[v].begin(), CG_vec[v].end(), [&](
auto elt) {
226 return !in_a_chain[elt];
228 if(next != CG_vec[v].end())
236 auto& chain_number = state.chain_number;
237 chain_number.resize(num_scc);
238 auto& pos_in_chain = state.pos_in_chain;
239 pos_in_chain.resize(num_scc);
240 for(size_type i = 0; i < chains.size(); ++i)
241 for(size_type j = 0; j < chains[i].size(); ++j)
243 const cg_vertex v = chains[i][j];
248 static const constexpr cg_vertex inf = std::numeric_limits<cg_vertex>::max();
249 auto& successors = state.successors;
250 resize_and_fill(successors, num_scc, chains.size(), inf);
251 for(
auto i = topo_order.rbegin(); i != topo_order.rend(); ++i)
253 const cg_vertex u = *i;
254 for(
auto adj = CG_vec[u].begin(), adj_last = CG_vec[u].end(); adj != adj_last; ++adj)
256 const cg_vertex v = *adj;
257 auto& suc_u = successors[u];
258 auto& suc_v = successors[v];
259 auto& suc_u_v = suc_u[chain_number[v]];
260 auto& topo_v = topo_number[v];
264 detail::union_successor_sets(suc_u, suc_v, suc_u);
271 for(size_type i = 0; i < CG_vec.size(); ++i)
273 for(size_type i = 0; i < CG_vec.size(); ++i)
274 for(size_type j = 0; j < chains.size(); ++j)
276 const size_type topo_num = successors[i][j];
279 cg_vertex v = topo_order[topo_num];
280 const auto chain_j_size = chains[j].size();
281 const auto pos_v = pos_in_chain[v];
282 if(chain_j_size > pos_v)
284 CG_vec[i].reserve(CG_vec[i].size() + chain_j_size - pos_v);
285 for(size_type k = pos_v; k < chain_j_size; ++k)
286 CG_vec[i].push_back(chains[j][k]);
293 vertex_iterator i, i_end;
294 for(boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
295 g_to_tc_map[*i] = add_vertex(tc);
298 for(
auto si = CG_vec.begin(), si_end = CG_vec.end(); si != si_end; ++si)
300 cg_vertex s = si - CG_vec.begin();
301 for(
auto i = CG_vec[s].begin(), i_end = CG_vec[s].end(); i != i_end; ++i)
304 for(size_type k = 0; k < components[s].size(); ++k)
305 for(size_type l = 0; l < components[t].size(); ++l)
306 add_edge(g_to_tc_map[components[s][k]], g_to_tc_map[components[t][l]], tc);
310 for(size_type i = 0; i < components.size(); ++i)
311 if(components[i].size() > 1)
312 for(size_type k = 0; k < components[i].size(); ++k)
313 for(size_type l = 0; l < components[i].size(); ++l)
315 vertex u = components[i][k], v = components[i][l];
316 add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
322 for(
auto [i, i_end] = vertices(g); i != i_end; ++i)
324 for(
auto [ab, ae] = adjacent_vertices(*i, g); ab != ae; ++ab)
327 if(components[component_number[*i]].size() == 1)
328 add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
334template <
typename Graph,
typename GraphTC>
335void transitive_closure(
336 const Graph& g, GraphTC& tc, TransitiveClosureState<Graph, GraphTC>& tc_state)
338 using namespace boost;
339 if(num_vertices(g) == 0)
341 typedef typename property_map<Graph, vertex_index_t>::const_type VertexIndexMap;
342 VertexIndexMap index_map = get(vertex_index, g);
344 typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
346 resize_and_fill(tc_state.to_tc_vec, num_vertices(g));
347 iterator_property_map<tc_vertex*, VertexIndexMap, tc_vertex, tc_vertex&> g_to_tc_map(
348 &tc_state.to_tc_vec[0], index_map);
350 transitive_closure(g, tc, g_to_tc_map, index_map, tc_state);
OSSIA_INLINE constexpr auto min(const T a, const U b) noexcept -> typename std::conditional<(sizeof(T) > sizeof(U)), T, U >::type
min function tailored for values
Definition math.hpp:125