| 1 | // Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
|
|---|
| 2 | // Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
|
|---|
| 3 | // Distributed under the Boost Software License, Version 1.0. (See
|
|---|
| 4 | // accompanying file LICENSE_1_0.txt or copy at
|
|---|
| 5 | // http://www.boost.org/LICENSE_1_0.txt)
|
|---|
| 6 |
|
|---|
| 7 | // NOTE: this final is generated by libs/graph/doc/transitive_closure.w
|
|---|
| 8 |
|
|---|
| 9 | #ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
|
|---|
| 10 | #define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
|
|---|
| 11 |
|
|---|
| 12 | #include <vector>
|
|---|
| 13 | #include <algorithm> // for std::min and std::max
|
|---|
| 14 | #include <functional>
|
|---|
| 15 | #include <boost/config.hpp>
|
|---|
| 16 | #include <boost/bind.hpp>
|
|---|
| 17 | #include <boost/graph/vector_as_graph.hpp>
|
|---|
| 18 | #include <boost/graph/strong_components.hpp>
|
|---|
| 19 | #include <boost/graph/topological_sort.hpp>
|
|---|
| 20 | #include <boost/graph/graph_concepts.hpp>
|
|---|
| 21 | #include <boost/graph/named_function_params.hpp>
|
|---|
| 22 |
|
|---|
| 23 | namespace boost
|
|---|
| 24 | {
|
|---|
| 25 |
|
|---|
| 26 | namespace detail
|
|---|
| 27 | {
|
|---|
| 28 | inline void
|
|---|
| 29 | union_successor_sets(const std::vector < std::size_t > &s1,
|
|---|
| 30 | const std::vector < std::size_t > &s2,
|
|---|
| 31 | std::vector < std::size_t > &s3)
|
|---|
| 32 | {
|
|---|
| 33 | BOOST_USING_STD_MIN();
|
|---|
| 34 | for (std::size_t k = 0; k < s1.size(); ++k)
|
|---|
| 35 | s3[k] = min BOOST_PREVENT_MACRO_SUBSTITUTION(s1[k], s2[k]);
|
|---|
| 36 | }
|
|---|
| 37 | } // namespace detail
|
|---|
| 38 |
|
|---|
| 39 | namespace detail
|
|---|
| 40 | {
|
|---|
| 41 | template < typename Container, typename ST = std::size_t,
|
|---|
| 42 | typename VT = typename Container::value_type >
|
|---|
| 43 | struct subscript_t:public std::unary_function < ST, VT >
|
|---|
| 44 | {
|
|---|
| 45 | typedef VT& result_type;
|
|---|
| 46 |
|
|---|
| 47 | subscript_t(Container & c):container(&c)
|
|---|
| 48 | {
|
|---|
| 49 | }
|
|---|
| 50 | VT & operator() (const ST & i) const
|
|---|
| 51 | {
|
|---|
| 52 | return (*container)[i];
|
|---|
| 53 | }
|
|---|
| 54 | protected:
|
|---|
| 55 | Container * container;
|
|---|
| 56 | };
|
|---|
| 57 | template < typename Container >
|
|---|
| 58 | subscript_t < Container > subscript(Container & c) {
|
|---|
| 59 | return subscript_t < Container > (c);
|
|---|
| 60 | }
|
|---|
| 61 | } // namespace detail
|
|---|
| 62 |
|
|---|
| 63 | template < typename Graph, typename GraphTC,
|
|---|
| 64 | typename G_to_TC_VertexMap,
|
|---|
| 65 | typename VertexIndexMap >
|
|---|
| 66 | void transitive_closure(const Graph & g, GraphTC & tc,
|
|---|
| 67 | G_to_TC_VertexMap g_to_tc_map,
|
|---|
| 68 | VertexIndexMap index_map)
|
|---|
| 69 | {
|
|---|
| 70 | if (num_vertices(g) == 0)
|
|---|
| 71 | return;
|
|---|
| 72 | typedef typename graph_traits < Graph >::vertex_descriptor vertex;
|
|---|
| 73 | typedef typename graph_traits < Graph >::edge_descriptor edge;
|
|---|
| 74 | typedef typename graph_traits < Graph >::vertex_iterator vertex_iterator;
|
|---|
| 75 | typedef typename property_traits < VertexIndexMap >::value_type size_type;
|
|---|
| 76 | typedef typename graph_traits <
|
|---|
| 77 | Graph >::adjacency_iterator adjacency_iterator;
|
|---|
| 78 |
|
|---|
| 79 | function_requires < VertexListGraphConcept < Graph > >();
|
|---|
| 80 | function_requires < AdjacencyGraphConcept < Graph > >();
|
|---|
| 81 | function_requires < VertexMutableGraphConcept < GraphTC > >();
|
|---|
| 82 | function_requires < EdgeMutableGraphConcept < GraphTC > >();
|
|---|
| 83 | function_requires < ReadablePropertyMapConcept < VertexIndexMap,
|
|---|
| 84 | vertex > >();
|
|---|
| 85 |
|
|---|
| 86 | typedef size_type cg_vertex;
|
|---|
| 87 | std::vector < cg_vertex > component_number_vec(num_vertices(g));
|
|---|
| 88 | iterator_property_map < cg_vertex *, VertexIndexMap, cg_vertex, cg_vertex& >
|
|---|
| 89 | component_number(&component_number_vec[0], index_map);
|
|---|
| 90 |
|
|---|
| 91 | int num_scc = strong_components(g, component_number,
|
|---|
| 92 | vertex_index_map(index_map));
|
|---|
| 93 |
|
|---|
| 94 | std::vector < std::vector < vertex > >components;
|
|---|
| 95 | build_component_lists(g, num_scc, component_number, components);
|
|---|
| 96 |
|
|---|
| 97 | typedef std::vector<std::vector<cg_vertex> > CG_t;
|
|---|
| 98 | CG_t CG(num_scc);
|
|---|
| 99 | for (cg_vertex s = 0; s < components.size(); ++s) {
|
|---|
| 100 | std::vector < cg_vertex > adj;
|
|---|
| 101 | for (size_type i = 0; i < components[s].size(); ++i) {
|
|---|
| 102 | vertex u = components[s][i];
|
|---|
| 103 | adjacency_iterator v, v_end;
|
|---|
| 104 | for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {
|
|---|
| 105 | cg_vertex t = component_number[*v];
|
|---|
| 106 | if (s != t) // Avoid loops in the condensation graph
|
|---|
| 107 | adj.push_back(t);
|
|---|
| 108 | }
|
|---|
| 109 | }
|
|---|
| 110 | std::sort(adj.begin(), adj.end());
|
|---|
| 111 | typename std::vector<cg_vertex>::iterator di =
|
|---|
| 112 | std::unique(adj.begin(), adj.end());
|
|---|
| 113 | if (di != adj.end())
|
|---|
| 114 | adj.erase(di, adj.end());
|
|---|
| 115 | CG[s] = adj;
|
|---|
| 116 | }
|
|---|
| 117 |
|
|---|
| 118 | std::vector<cg_vertex> topo_order;
|
|---|
| 119 | std::vector<cg_vertex> topo_number(num_vertices(CG));
|
|---|
| 120 | topological_sort(CG, std::back_inserter(topo_order),
|
|---|
| 121 | vertex_index_map(identity_property_map()));
|
|---|
| 122 | std::reverse(topo_order.begin(), topo_order.end());
|
|---|
| 123 | size_type n = 0;
|
|---|
| 124 | for (typename std::vector<cg_vertex>::iterator iter = topo_order.begin();
|
|---|
| 125 | iter != topo_order.end(); ++iter)
|
|---|
| 126 | topo_number[*iter] = n++;
|
|---|
| 127 |
|
|---|
| 128 | for (size_type i = 0; i < num_vertices(CG); ++i)
|
|---|
| 129 | std::sort(CG[i].begin(), CG[i].end(),
|
|---|
| 130 | boost::bind(std::less<cg_vertex>(),
|
|---|
| 131 | boost::bind(detail::subscript(topo_number), _1),
|
|---|
| 132 | boost::bind(detail::subscript(topo_number), _2)));
|
|---|
| 133 |
|
|---|
| 134 | std::vector<std::vector<cg_vertex> > chains;
|
|---|
| 135 | {
|
|---|
| 136 | std::vector<cg_vertex> in_a_chain(num_vertices(CG));
|
|---|
| 137 | for (typename std::vector<cg_vertex>::iterator i = topo_order.begin();
|
|---|
| 138 | i != topo_order.end(); ++i) {
|
|---|
| 139 | cg_vertex v = *i;
|
|---|
| 140 | if (!in_a_chain[v]) {
|
|---|
| 141 | chains.resize(chains.size() + 1);
|
|---|
| 142 | std::vector<cg_vertex>& chain = chains.back();
|
|---|
| 143 | for (;;) {
|
|---|
| 144 | chain.push_back(v);
|
|---|
| 145 | in_a_chain[v] = true;
|
|---|
| 146 | typename graph_traits<CG_t>::adjacency_iterator adj_first, adj_last;
|
|---|
| 147 | tie(adj_first, adj_last) = adjacent_vertices(v, CG);
|
|---|
| 148 | typename graph_traits<CG_t>::adjacency_iterator next
|
|---|
| 149 | = std::find_if(adj_first, adj_last,
|
|---|
| 150 | std::not1(detail::subscript(in_a_chain)));
|
|---|
| 151 | if (next != adj_last)
|
|---|
| 152 | v = *next;
|
|---|
| 153 | else
|
|---|
| 154 | break; // end of chain, dead-end
|
|---|
| 155 |
|
|---|
| 156 | }
|
|---|
| 157 | }
|
|---|
| 158 | }
|
|---|
| 159 | }
|
|---|
| 160 | std::vector<size_type> chain_number(num_vertices(CG));
|
|---|
| 161 | std::vector<size_type> pos_in_chain(num_vertices(CG));
|
|---|
| 162 | for (size_type i = 0; i < chains.size(); ++i)
|
|---|
| 163 | for (size_type j = 0; j < chains[i].size(); ++j) {
|
|---|
| 164 | cg_vertex v = chains[i][j];
|
|---|
| 165 | chain_number[v] = i;
|
|---|
| 166 | pos_in_chain[v] = j;
|
|---|
| 167 | }
|
|---|
| 168 |
|
|---|
| 169 | cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
|
|---|
| 170 | std::vector<std::vector<cg_vertex> > successors(num_vertices(CG),
|
|---|
| 171 | std::vector<cg_vertex>
|
|---|
| 172 | (chains.size(), inf));
|
|---|
| 173 | for (typename std::vector<cg_vertex>::reverse_iterator
|
|---|
| 174 | i = topo_order.rbegin(); i != topo_order.rend(); ++i) {
|
|---|
| 175 | cg_vertex u = *i;
|
|---|
| 176 | typename graph_traits<CG_t>::adjacency_iterator adj, adj_last;
|
|---|
| 177 | for (tie(adj, adj_last) = adjacent_vertices(u, CG);
|
|---|
| 178 | adj != adj_last; ++adj) {
|
|---|
| 179 | cg_vertex v = *adj;
|
|---|
| 180 | if (topo_number[v] < successors[u][chain_number[v]]) {
|
|---|
| 181 | // Succ(u) = Succ(u) U Succ(v)
|
|---|
| 182 | detail::union_successor_sets(successors[u], successors[v],
|
|---|
| 183 | successors[u]);
|
|---|
| 184 | // Succ(u) = Succ(u) U {v}
|
|---|
| 185 | successors[u][chain_number[v]] = topo_number[v];
|
|---|
| 186 | }
|
|---|
| 187 | }
|
|---|
| 188 | }
|
|---|
| 189 |
|
|---|
| 190 | for (size_type i = 0; i < CG.size(); ++i)
|
|---|
| 191 | CG[i].clear();
|
|---|
| 192 | for (size_type i = 0; i < CG.size(); ++i)
|
|---|
| 193 | for (size_type j = 0; j < chains.size(); ++j) {
|
|---|
| 194 | size_type topo_num = successors[i][j];
|
|---|
| 195 | if (topo_num < inf) {
|
|---|
| 196 | cg_vertex v = topo_order[topo_num];
|
|---|
| 197 | for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
|
|---|
| 198 | CG[i].push_back(chains[j][k]);
|
|---|
| 199 | }
|
|---|
| 200 | }
|
|---|
| 201 |
|
|---|
| 202 |
|
|---|
| 203 | // Add vertices to the transitive closure graph
|
|---|
| 204 | typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
|
|---|
| 205 | {
|
|---|
| 206 | vertex_iterator i, i_end;
|
|---|
| 207 | for (tie(i, i_end) = vertices(g); i != i_end; ++i)
|
|---|
| 208 | g_to_tc_map[*i] = add_vertex(tc);
|
|---|
| 209 | }
|
|---|
| 210 | // Add edges between all the vertices in two adjacent SCCs
|
|---|
| 211 | typename graph_traits<CG_t>::vertex_iterator si, si_end;
|
|---|
| 212 | for (tie(si, si_end) = vertices(CG); si != si_end; ++si) {
|
|---|
| 213 | cg_vertex s = *si;
|
|---|
| 214 | typename graph_traits<CG_t>::adjacency_iterator i, i_end;
|
|---|
| 215 | for (tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) {
|
|---|
| 216 | cg_vertex t = *i;
|
|---|
| 217 | for (size_type k = 0; k < components[s].size(); ++k)
|
|---|
| 218 | for (size_type l = 0; l < components[t].size(); ++l)
|
|---|
| 219 | add_edge(g_to_tc_map[components[s][k]],
|
|---|
| 220 | g_to_tc_map[components[t][l]], tc);
|
|---|
| 221 | }
|
|---|
| 222 | }
|
|---|
| 223 | // Add edges connecting all vertices in a SCC
|
|---|
| 224 | for (size_type i = 0; i < components.size(); ++i)
|
|---|
| 225 | if (components[i].size() > 1)
|
|---|
| 226 | for (size_type k = 0; k < components[i].size(); ++k)
|
|---|
| 227 | for (size_type l = 0; l < components[i].size(); ++l) {
|
|---|
| 228 | vertex u = components[i][k], v = components[i][l];
|
|---|
| 229 | add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
|
|---|
| 230 | }
|
|---|
| 231 |
|
|---|
| 232 | // Find loopbacks in the original graph.
|
|---|
| 233 | // Need to add it to transitive closure.
|
|---|
| 234 | {
|
|---|
| 235 | vertex_iterator i, i_end;
|
|---|
| 236 | for (tie(i, i_end) = vertices(g); i != i_end; ++i)
|
|---|
| 237 | {
|
|---|
| 238 | adjacency_iterator ab, ae;
|
|---|
| 239 | for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
|
|---|
| 240 | {
|
|---|
| 241 | if (*ab == *i)
|
|---|
| 242 | if (components[component_number[*i]].size() == 1)
|
|---|
| 243 | add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
|
|---|
| 244 | }
|
|---|
| 245 | }
|
|---|
| 246 | }
|
|---|
| 247 | }
|
|---|
| 248 |
|
|---|
| 249 | template <typename Graph, typename GraphTC>
|
|---|
| 250 | void transitive_closure(const Graph & g, GraphTC & tc)
|
|---|
| 251 | {
|
|---|
| 252 | if (num_vertices(g) == 0)
|
|---|
| 253 | return;
|
|---|
| 254 | typedef typename property_map<Graph, vertex_index_t>::const_type
|
|---|
| 255 | VertexIndexMap;
|
|---|
| 256 | VertexIndexMap index_map = get(vertex_index, g);
|
|---|
| 257 |
|
|---|
| 258 | typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
|
|---|
| 259 | std::vector<tc_vertex> to_tc_vec(num_vertices(g));
|
|---|
| 260 | iterator_property_map < tc_vertex *, VertexIndexMap, tc_vertex, tc_vertex&>
|
|---|
| 261 | g_to_tc_map(&to_tc_vec[0], index_map);
|
|---|
| 262 |
|
|---|
| 263 | transitive_closure(g, tc, g_to_tc_map, index_map);
|
|---|
| 264 | }
|
|---|
| 265 |
|
|---|
| 266 | namespace detail
|
|---|
| 267 | {
|
|---|
| 268 | template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
|
|---|
| 269 | typename VertexIndexMap>
|
|---|
| 270 | void transitive_closure_dispatch
|
|---|
| 271 | (const Graph & g, GraphTC & tc,
|
|---|
| 272 | G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
|
|---|
| 273 | {
|
|---|
| 274 | typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
|
|---|
| 275 | typename std::vector < tc_vertex >::size_type
|
|---|
| 276 | n = is_default_param(g_to_tc_map) ? num_vertices(g) : 1;
|
|---|
| 277 | std::vector < tc_vertex > to_tc_vec(n);
|
|---|
| 278 |
|
|---|
| 279 | transitive_closure
|
|---|
| 280 | (g, tc,
|
|---|
| 281 | choose_param(g_to_tc_map, make_iterator_property_map
|
|---|
| 282 | (to_tc_vec.begin(), index_map, to_tc_vec[0])),
|
|---|
| 283 | index_map);
|
|---|
| 284 | }
|
|---|
| 285 | } // namespace detail
|
|---|
| 286 |
|
|---|
| 287 | template < typename Graph, typename GraphTC,
|
|---|
| 288 | typename P, typename T, typename R >
|
|---|
| 289 | void transitive_closure(const Graph & g, GraphTC & tc,
|
|---|
| 290 | const bgl_named_params < P, T, R > ¶ms)
|
|---|
| 291 | {
|
|---|
| 292 | if (num_vertices(g) == 0)
|
|---|
| 293 | return;
|
|---|
| 294 | detail::transitive_closure_dispatch
|
|---|
| 295 | (g, tc, get_param(params, orig_to_copy_t()),
|
|---|
| 296 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index) );
|
|---|
| 297 | }
|
|---|
| 298 |
|
|---|
| 299 |
|
|---|
| 300 | template < typename G > void warshall_transitive_closure(G & g)
|
|---|
| 301 | {
|
|---|
| 302 | typedef typename graph_traits < G >::vertex_descriptor vertex;
|
|---|
| 303 | typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
|
|---|
| 304 |
|
|---|
| 305 | function_requires < AdjacencyMatrixConcept < G > >();
|
|---|
| 306 | function_requires < EdgeMutableGraphConcept < G > >();
|
|---|
| 307 |
|
|---|
| 308 | // Matrix form:
|
|---|
| 309 | // for k
|
|---|
| 310 | // for i
|
|---|
| 311 | // if A[i,k]
|
|---|
| 312 | // for j
|
|---|
| 313 | // A[i,j] = A[i,j] | A[k,j]
|
|---|
| 314 | vertex_iterator ki, ke, ii, ie, ji, je;
|
|---|
| 315 | for (tie(ki, ke) = vertices(g); ki != ke; ++ki)
|
|---|
| 316 | for (tie(ii, ie) = vertices(g); ii != ie; ++ii)
|
|---|
| 317 | if (edge(*ii, *ki, g).second)
|
|---|
| 318 | for (tie(ji, je) = vertices(g); ji != je; ++ji)
|
|---|
| 319 | if (!edge(*ii, *ji, g).second && edge(*ki, *ji, g).second) {
|
|---|
| 320 | add_edge(*ii, *ji, g);
|
|---|
| 321 | }
|
|---|
| 322 | }
|
|---|
| 323 |
|
|---|
| 324 |
|
|---|
| 325 | template < typename G > void warren_transitive_closure(G & g)
|
|---|
| 326 | {
|
|---|
| 327 | using namespace boost;
|
|---|
| 328 | typedef typename graph_traits < G >::vertex_descriptor vertex;
|
|---|
| 329 | typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
|
|---|
| 330 |
|
|---|
| 331 | function_requires < AdjacencyMatrixConcept < G > >();
|
|---|
| 332 | function_requires < EdgeMutableGraphConcept < G > >();
|
|---|
| 333 |
|
|---|
| 334 | // Make sure second loop will work
|
|---|
| 335 | if (num_vertices(g) == 0)
|
|---|
| 336 | return;
|
|---|
| 337 |
|
|---|
| 338 | // for i = 2 to n
|
|---|
| 339 | // for k = 1 to i - 1
|
|---|
| 340 | // if A[i,k]
|
|---|
| 341 | // for j = 1 to n
|
|---|
| 342 | // A[i,j] = A[i,j] | A[k,j]
|
|---|
| 343 |
|
|---|
| 344 | vertex_iterator ic, ie, jc, je, kc, ke;
|
|---|
| 345 | for (tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
|
|---|
| 346 | for (tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
|
|---|
| 347 | if (edge(*ic, *kc, g).second)
|
|---|
| 348 | for (tie(jc, je) = vertices(g); jc != je; ++jc)
|
|---|
| 349 | if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
|
|---|
| 350 | add_edge(*ic, *jc, g);
|
|---|
| 351 | }
|
|---|
| 352 | // for i = 1 to n - 1
|
|---|
| 353 | // for k = i + 1 to n
|
|---|
| 354 | // if A[i,k]
|
|---|
| 355 | // for j = 1 to n
|
|---|
| 356 | // A[i,j] = A[i,j] | A[k,j]
|
|---|
| 357 |
|
|---|
| 358 | for (tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
|
|---|
| 359 | for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
|
|---|
| 360 | if (edge(*ic, *kc, g).second)
|
|---|
| 361 | for (tie(jc, je) = vertices(g); jc != je; ++jc)
|
|---|
| 362 | if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
|
|---|
| 363 | add_edge(*ic, *jc, g);
|
|---|
| 364 | }
|
|---|
| 365 | }
|
|---|
| 366 |
|
|---|
| 367 |
|
|---|
| 368 | } // namespace boost
|
|---|
| 369 |
|
|---|
| 370 | #endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
|
|---|
![(please configure the [header_logo] section in trac.ini)](/trac/gametools/chrome/site/your_project_logo.png){kind=logo}
