boost/graph/transitive_closure.hpp

   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 > &params)
 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