1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/transitive_closure.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,370 @@
1.4 +// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
1.5 +// Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
1.6 +// Distributed under the Boost Software License, Version 1.0. (See
1.7 +// accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// NOTE: this final is generated by libs/graph/doc/transitive_closure.w
1.11 +
1.12 +#ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
1.13 +#define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
1.14 +
1.15 +#include <vector>
1.16 +#include <algorithm> // for std::min and std::max
1.17 +#include <functional>
1.18 +#include <boost/config.hpp>
1.19 +#include <boost/bind.hpp>
1.20 +#include <boost/graph/vector_as_graph.hpp>
1.21 +#include <boost/graph/strong_components.hpp>
1.22 +#include <boost/graph/topological_sort.hpp>
1.23 +#include <boost/graph/graph_concepts.hpp>
1.24 +#include <boost/graph/named_function_params.hpp>
1.25 +
1.26 +namespace boost
1.27 +{
1.28 +
1.29 + namespace detail
1.30 + {
1.31 + inline void
1.32 + union_successor_sets(const std::vector < std::size_t > &s1,
1.33 + const std::vector < std::size_t > &s2,
1.34 + std::vector < std::size_t > &s3)
1.35 + {
1.36 + BOOST_USING_STD_MIN();
1.37 + for (std::size_t k = 0; k < s1.size(); ++k)
1.38 + s3[k] = min BOOST_PREVENT_MACRO_SUBSTITUTION(s1[k], s2[k]);
1.39 + }
1.40 + } // namespace detail
1.41 +
1.42 + namespace detail
1.43 + {
1.44 + template < typename Container, typename ST = std::size_t,
1.45 + typename VT = typename Container::value_type >
1.46 + struct subscript_t:public std::unary_function < ST, VT >
1.47 + {
1.48 + typedef VT& result_type;
1.49 +
1.50 + subscript_t(Container & c):container(&c)
1.51 + {
1.52 + }
1.53 + VT & operator() (const ST & i) const
1.54 + {
1.55 + return (*container)[i];
1.56 + }
1.57 + protected:
1.58 + Container * container;
1.59 + };
1.60 + template < typename Container >
1.61 + subscript_t < Container > subscript(Container & c) {
1.62 + return subscript_t < Container > (c);
1.63 + }
1.64 + } // namespace detail
1.65 +
1.66 + template < typename Graph, typename GraphTC,
1.67 + typename G_to_TC_VertexMap,
1.68 + typename VertexIndexMap >
1.69 + void transitive_closure(const Graph & g, GraphTC & tc,
1.70 + G_to_TC_VertexMap g_to_tc_map,
1.71 + VertexIndexMap index_map)
1.72 + {
1.73 + if (num_vertices(g) == 0)
1.74 + return;
1.75 + typedef typename graph_traits < Graph >::vertex_descriptor vertex;
1.76 + typedef typename graph_traits < Graph >::edge_descriptor edge;
1.77 + typedef typename graph_traits < Graph >::vertex_iterator vertex_iterator;
1.78 + typedef typename property_traits < VertexIndexMap >::value_type size_type;
1.79 + typedef typename graph_traits <
1.80 + Graph >::adjacency_iterator adjacency_iterator;
1.81 +
1.82 + function_requires < VertexListGraphConcept < Graph > >();
1.83 + function_requires < AdjacencyGraphConcept < Graph > >();
1.84 + function_requires < VertexMutableGraphConcept < GraphTC > >();
1.85 + function_requires < EdgeMutableGraphConcept < GraphTC > >();
1.86 + function_requires < ReadablePropertyMapConcept < VertexIndexMap,
1.87 + vertex > >();
1.88 +
1.89 + typedef size_type cg_vertex;
1.90 + std::vector < cg_vertex > component_number_vec(num_vertices(g));
1.91 + iterator_property_map < cg_vertex *, VertexIndexMap, cg_vertex, cg_vertex& >
1.92 + component_number(&component_number_vec[0], index_map);
1.93 +
1.94 + int num_scc = strong_components(g, component_number,
1.95 + vertex_index_map(index_map));
1.96 +
1.97 + std::vector < std::vector < vertex > >components;
1.98 + build_component_lists(g, num_scc, component_number, components);
1.99 +
1.100 + typedef std::vector<std::vector<cg_vertex> > CG_t;
1.101 + CG_t CG(num_scc);
1.102 + for (cg_vertex s = 0; s < components.size(); ++s) {
1.103 + std::vector < cg_vertex > adj;
1.104 + for (size_type i = 0; i < components[s].size(); ++i) {
1.105 + vertex u = components[s][i];
1.106 + adjacency_iterator v, v_end;
1.107 + for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {
1.108 + cg_vertex t = component_number[*v];
1.109 + if (s != t) // Avoid loops in the condensation graph
1.110 + adj.push_back(t);
1.111 + }
1.112 + }
1.113 + std::sort(adj.begin(), adj.end());
1.114 + typename std::vector<cg_vertex>::iterator di =
1.115 + std::unique(adj.begin(), adj.end());
1.116 + if (di != adj.end())
1.117 + adj.erase(di, adj.end());
1.118 + CG[s] = adj;
1.119 + }
1.120 +
1.121 + std::vector<cg_vertex> topo_order;
1.122 + std::vector<cg_vertex> topo_number(num_vertices(CG));
1.123 + topological_sort(CG, std::back_inserter(topo_order),
1.124 + vertex_index_map(identity_property_map()));
1.125 + std::reverse(topo_order.begin(), topo_order.end());
1.126 + size_type n = 0;
1.127 + for (typename std::vector<cg_vertex>::iterator iter = topo_order.begin();
1.128 + iter != topo_order.end(); ++iter)
1.129 + topo_number[*iter] = n++;
1.130 +
1.131 + for (size_type i = 0; i < num_vertices(CG); ++i)
1.132 + std::sort(CG[i].begin(), CG[i].end(),
1.133 + boost::bind(std::less<cg_vertex>(),
1.134 + boost::bind(detail::subscript(topo_number), _1),
1.135 + boost::bind(detail::subscript(topo_number), _2)));
1.136 +
1.137 + std::vector<std::vector<cg_vertex> > chains;
1.138 + {
1.139 + std::vector<cg_vertex> in_a_chain(num_vertices(CG));
1.140 + for (typename std::vector<cg_vertex>::iterator i = topo_order.begin();
1.141 + i != topo_order.end(); ++i) {
1.142 + cg_vertex v = *i;
1.143 + if (!in_a_chain[v]) {
1.144 + chains.resize(chains.size() + 1);
1.145 + std::vector<cg_vertex>& chain = chains.back();
1.146 + for (;;) {
1.147 + chain.push_back(v);
1.148 + in_a_chain[v] = true;
1.149 + typename graph_traits<CG_t>::adjacency_iterator adj_first, adj_last;
1.150 + tie(adj_first, adj_last) = adjacent_vertices(v, CG);
1.151 + typename graph_traits<CG_t>::adjacency_iterator next
1.152 + = std::find_if(adj_first, adj_last,
1.153 + std::not1(detail::subscript(in_a_chain)));
1.154 + if (next != adj_last)
1.155 + v = *next;
1.156 + else
1.157 + break; // end of chain, dead-end
1.158 +
1.159 + }
1.160 + }
1.161 + }
1.162 + }
1.163 + std::vector<size_type> chain_number(num_vertices(CG));
1.164 + std::vector<size_type> pos_in_chain(num_vertices(CG));
1.165 + for (size_type i = 0; i < chains.size(); ++i)
1.166 + for (size_type j = 0; j < chains[i].size(); ++j) {
1.167 + cg_vertex v = chains[i][j];
1.168 + chain_number[v] = i;
1.169 + pos_in_chain[v] = j;
1.170 + }
1.171 +
1.172 + cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
1.173 + std::vector<std::vector<cg_vertex> > successors(num_vertices(CG),
1.174 + std::vector<cg_vertex>
1.175 + (chains.size(), inf));
1.176 + for (typename std::vector<cg_vertex>::reverse_iterator
1.177 + i = topo_order.rbegin(); i != topo_order.rend(); ++i) {
1.178 + cg_vertex u = *i;
1.179 + typename graph_traits<CG_t>::adjacency_iterator adj, adj_last;
1.180 + for (tie(adj, adj_last) = adjacent_vertices(u, CG);
1.181 + adj != adj_last; ++adj) {
1.182 + cg_vertex v = *adj;
1.183 + if (topo_number[v] < successors[u][chain_number[v]]) {
1.184 + // Succ(u) = Succ(u) U Succ(v)
1.185 + detail::union_successor_sets(successors[u], successors[v],
1.186 + successors[u]);
1.187 + // Succ(u) = Succ(u) U {v}
1.188 + successors[u][chain_number[v]] = topo_number[v];
1.189 + }
1.190 + }
1.191 + }
1.192 +
1.193 + for (size_type i = 0; i < CG.size(); ++i)
1.194 + CG[i].clear();
1.195 + for (size_type i = 0; i < CG.size(); ++i)
1.196 + for (size_type j = 0; j < chains.size(); ++j) {
1.197 + size_type topo_num = successors[i][j];
1.198 + if (topo_num < inf) {
1.199 + cg_vertex v = topo_order[topo_num];
1.200 + for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
1.201 + CG[i].push_back(chains[j][k]);
1.202 + }
1.203 + }
1.204 +
1.205 +
1.206 + // Add vertices to the transitive closure graph
1.207 + typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
1.208 + {
1.209 + vertex_iterator i, i_end;
1.210 + for (tie(i, i_end) = vertices(g); i != i_end; ++i)
1.211 + g_to_tc_map[*i] = add_vertex(tc);
1.212 + }
1.213 + // Add edges between all the vertices in two adjacent SCCs
1.214 + typename graph_traits<CG_t>::vertex_iterator si, si_end;
1.215 + for (tie(si, si_end) = vertices(CG); si != si_end; ++si) {
1.216 + cg_vertex s = *si;
1.217 + typename graph_traits<CG_t>::adjacency_iterator i, i_end;
1.218 + for (tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) {
1.219 + cg_vertex t = *i;
1.220 + for (size_type k = 0; k < components[s].size(); ++k)
1.221 + for (size_type l = 0; l < components[t].size(); ++l)
1.222 + add_edge(g_to_tc_map[components[s][k]],
1.223 + g_to_tc_map[components[t][l]], tc);
1.224 + }
1.225 + }
1.226 + // Add edges connecting all vertices in a SCC
1.227 + for (size_type i = 0; i < components.size(); ++i)
1.228 + if (components[i].size() > 1)
1.229 + for (size_type k = 0; k < components[i].size(); ++k)
1.230 + for (size_type l = 0; l < components[i].size(); ++l) {
1.231 + vertex u = components[i][k], v = components[i][l];
1.232 + add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
1.233 + }
1.234 +
1.235 + // Find loopbacks in the original graph.
1.236 + // Need to add it to transitive closure.
1.237 + {
1.238 + vertex_iterator i, i_end;
1.239 + for (tie(i, i_end) = vertices(g); i != i_end; ++i)
1.240 + {
1.241 + adjacency_iterator ab, ae;
1.242 + for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
1.243 + {
1.244 + if (*ab == *i)
1.245 + if (components[component_number[*i]].size() == 1)
1.246 + add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
1.247 + }
1.248 + }
1.249 + }
1.250 + }
1.251 +
1.252 + template <typename Graph, typename GraphTC>
1.253 + void transitive_closure(const Graph & g, GraphTC & tc)
1.254 + {
1.255 + if (num_vertices(g) == 0)
1.256 + return;
1.257 + typedef typename property_map<Graph, vertex_index_t>::const_type
1.258 + VertexIndexMap;
1.259 + VertexIndexMap index_map = get(vertex_index, g);
1.260 +
1.261 + typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
1.262 + std::vector<tc_vertex> to_tc_vec(num_vertices(g));
1.263 + iterator_property_map < tc_vertex *, VertexIndexMap, tc_vertex, tc_vertex&>
1.264 + g_to_tc_map(&to_tc_vec[0], index_map);
1.265 +
1.266 + transitive_closure(g, tc, g_to_tc_map, index_map);
1.267 + }
1.268 +
1.269 + namespace detail
1.270 + {
1.271 + template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
1.272 + typename VertexIndexMap>
1.273 + void transitive_closure_dispatch
1.274 + (const Graph & g, GraphTC & tc,
1.275 + G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
1.276 + {
1.277 + typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
1.278 + typename std::vector < tc_vertex >::size_type
1.279 + n = is_default_param(g_to_tc_map) ? num_vertices(g) : 1;
1.280 + std::vector < tc_vertex > to_tc_vec(n);
1.281 +
1.282 + transitive_closure
1.283 + (g, tc,
1.284 + choose_param(g_to_tc_map, make_iterator_property_map
1.285 + (to_tc_vec.begin(), index_map, to_tc_vec[0])),
1.286 + index_map);
1.287 + }
1.288 + } // namespace detail
1.289 +
1.290 + template < typename Graph, typename GraphTC,
1.291 + typename P, typename T, typename R >
1.292 + void transitive_closure(const Graph & g, GraphTC & tc,
1.293 + const bgl_named_params < P, T, R > ¶ms)
1.294 + {
1.295 + if (num_vertices(g) == 0)
1.296 + return;
1.297 + detail::transitive_closure_dispatch
1.298 + (g, tc, get_param(params, orig_to_copy_t()),
1.299 + choose_const_pmap(get_param(params, vertex_index), g, vertex_index) );
1.300 + }
1.301 +
1.302 +
1.303 + template < typename G > void warshall_transitive_closure(G & g)
1.304 + {
1.305 + typedef typename graph_traits < G >::vertex_descriptor vertex;
1.306 + typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
1.307 +
1.308 + function_requires < AdjacencyMatrixConcept < G > >();
1.309 + function_requires < EdgeMutableGraphConcept < G > >();
1.310 +
1.311 + // Matrix form:
1.312 + // for k
1.313 + // for i
1.314 + // if A[i,k]
1.315 + // for j
1.316 + // A[i,j] = A[i,j] | A[k,j]
1.317 + vertex_iterator ki, ke, ii, ie, ji, je;
1.318 + for (tie(ki, ke) = vertices(g); ki != ke; ++ki)
1.319 + for (tie(ii, ie) = vertices(g); ii != ie; ++ii)
1.320 + if (edge(*ii, *ki, g).second)
1.321 + for (tie(ji, je) = vertices(g); ji != je; ++ji)
1.322 + if (!edge(*ii, *ji, g).second && edge(*ki, *ji, g).second) {
1.323 + add_edge(*ii, *ji, g);
1.324 + }
1.325 + }
1.326 +
1.327 +
1.328 + template < typename G > void warren_transitive_closure(G & g)
1.329 + {
1.330 + using namespace boost;
1.331 + typedef typename graph_traits < G >::vertex_descriptor vertex;
1.332 + typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
1.333 +
1.334 + function_requires < AdjacencyMatrixConcept < G > >();
1.335 + function_requires < EdgeMutableGraphConcept < G > >();
1.336 +
1.337 + // Make sure second loop will work
1.338 + if (num_vertices(g) == 0)
1.339 + return;
1.340 +
1.341 + // for i = 2 to n
1.342 + // for k = 1 to i - 1
1.343 + // if A[i,k]
1.344 + // for j = 1 to n
1.345 + // A[i,j] = A[i,j] | A[k,j]
1.346 +
1.347 + vertex_iterator ic, ie, jc, je, kc, ke;
1.348 + for (tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
1.349 + for (tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
1.350 + if (edge(*ic, *kc, g).second)
1.351 + for (tie(jc, je) = vertices(g); jc != je; ++jc)
1.352 + if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
1.353 + add_edge(*ic, *jc, g);
1.354 + }
1.355 + // for i = 1 to n - 1
1.356 + // for k = i + 1 to n
1.357 + // if A[i,k]
1.358 + // for j = 1 to n
1.359 + // A[i,j] = A[i,j] | A[k,j]
1.360 +
1.361 + for (tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
1.362 + for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
1.363 + if (edge(*ic, *kc, g).second)
1.364 + for (tie(jc, je) = vertices(g); jc != je; ++jc)
1.365 + if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
1.366 + add_edge(*ic, *jc, g);
1.367 + }
1.368 + }
1.369 +
1.370 +
1.371 +} // namespace boost
1.372 +
1.373 +#endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP