Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 09:43:09 

0001 // Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
0002 // Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
0003 // Distributed under the Boost Software License, Version 1.0. (See
0004 // accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 
0007 // NOTE: this final is generated by libs/graph/doc/transitive_closure.w
0008 
0009 #ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
0010 #define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
0011 
0012 #include <vector>
0013 #include <algorithm> // for std::min and std::max
0014 #include <functional>
0015 #include <boost/config.hpp>
0016 #include <boost/bind/bind.hpp>
0017 #include <boost/graph/strong_components.hpp>
0018 #include <boost/graph/topological_sort.hpp>
0019 #include <boost/graph/graph_concepts.hpp>
0020 #include <boost/graph/named_function_params.hpp>
0021 #include <boost/graph/adjacency_list.hpp>
0022 #include <boost/concept/assert.hpp>
0023 
0024 namespace boost
0025 {
0026 
0027 namespace detail
0028 {
0029     inline void union_successor_sets(const std::vector< std::size_t >& s1,
0030         const std::vector< std::size_t >& s2, std::vector< std::size_t >& s3)
0031     {
0032         BOOST_USING_STD_MIN();
0033         for (std::size_t k = 0; k < s1.size(); ++k)
0034             s3[k] = min BOOST_PREVENT_MACRO_SUBSTITUTION(s1[k], s2[k]);
0035     }
0036 } // namespace detail
0037 
0038 namespace detail
0039 {
0040     template < typename TheContainer, typename ST = std::size_t,
0041         typename VT = typename TheContainer::value_type >
0042     struct subscript_t
0043     {
0044         typedef ST argument_type;
0045         typedef VT& result_type;
0046 
0047         subscript_t(TheContainer& c) : container(&c) {}
0048         VT& operator()(const ST& i) const { return (*container)[i]; }
0049 
0050     protected:
0051         TheContainer* container;
0052     };
0053     template < typename TheContainer >
0054     subscript_t< TheContainer > subscript(TheContainer& c)
0055     {
0056         return subscript_t< TheContainer >(c);
0057     }
0058 } // namespace detail
0059 
0060 template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
0061     typename VertexIndexMap >
0062 void transitive_closure(const Graph& g, GraphTC& tc,
0063     G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
0064 {
0065     if (num_vertices(g) == 0)
0066         return;
0067     typedef typename graph_traits< Graph >::vertex_descriptor vertex;
0068     typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator;
0069     typedef typename property_traits< VertexIndexMap >::value_type size_type;
0070     typedef
0071         typename graph_traits< Graph >::adjacency_iterator adjacency_iterator;
0072 
0073     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0074     BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept< Graph >));
0075     BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept< GraphTC >));
0076     BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< GraphTC >));
0077     BOOST_CONCEPT_ASSERT(
0078         (ReadablePropertyMapConcept< VertexIndexMap, vertex >));
0079 
0080     typedef size_type cg_vertex;
0081     std::vector< cg_vertex > component_number_vec(num_vertices(g));
0082     iterator_property_map< cg_vertex*, VertexIndexMap, cg_vertex, cg_vertex& >
0083         component_number(&component_number_vec[0], index_map);
0084 
0085     const cg_vertex num_scc
0086         = strong_components(g, component_number, vertex_index_map(index_map));
0087 
0088     std::vector< std::vector< vertex > > components;
0089     build_component_lists(g, num_scc, component_number, components);
0090 
0091     typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS >
0092         CG_t;
0093     CG_t CG(num_scc);
0094     for (cg_vertex s = 0; s < components.size(); ++s)
0095     {
0096         std::vector< cg_vertex > adj;
0097         for (size_type i = 0; i < components[s].size(); ++i)
0098         {
0099             vertex u = components[s][i];
0100             adjacency_iterator v, v_end;
0101             for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end;
0102                  ++v)
0103             {
0104                 cg_vertex t = component_number[*v];
0105                 if (s != t) // Avoid loops in the condensation graph
0106                     adj.push_back(t);
0107             }
0108         }
0109         std::sort(adj.begin(), adj.end());
0110         const typename std::vector< cg_vertex >::iterator di
0111             = std::unique(adj.begin(), adj.end());
0112 
0113         for (typename std::vector< cg_vertex >::const_iterator i = adj.begin();
0114              i != di; ++i)
0115         {
0116             add_edge(s, *i, CG);
0117         }
0118     }
0119 
0120     std::vector< cg_vertex > topo_order;
0121     std::vector< cg_vertex > topo_number(num_vertices(CG));
0122     topological_sort(CG, std::back_inserter(topo_order),
0123         vertex_index_map(identity_property_map()));
0124     std::reverse(topo_order.begin(), topo_order.end());
0125     size_type n = 0;
0126     for (typename std::vector< cg_vertex >::iterator iter = topo_order.begin();
0127          iter != topo_order.end(); ++iter)
0128         topo_number[*iter] = n++;
0129 
0130     std::vector< std::vector< cg_vertex > > CG_vec(num_vertices(CG));
0131     for (size_type i = 0; i < num_vertices(CG); ++i)
0132     {
0133         using namespace boost::placeholders;
0134 
0135         typedef typename boost::graph_traits< CG_t >::adjacency_iterator
0136             cg_adj_iter;
0137         std::pair< cg_adj_iter, cg_adj_iter > pr = adjacent_vertices(i, CG);
0138         CG_vec[i].assign(pr.first, pr.second);
0139         std::sort(CG_vec[i].begin(), CG_vec[i].end(),
0140             boost::bind(std::less< cg_vertex >(),
0141                 boost::bind(detail::subscript(topo_number), _1),
0142                 boost::bind(detail::subscript(topo_number), _2)));
0143     }
0144 
0145     std::vector< std::vector< cg_vertex > > chains;
0146     {
0147         std::vector< cg_vertex > in_a_chain(CG_vec.size());
0148         for (typename std::vector< cg_vertex >::iterator i = topo_order.begin();
0149              i != topo_order.end(); ++i)
0150         {
0151             cg_vertex v = *i;
0152             if (!in_a_chain[v])
0153             {
0154                 chains.resize(chains.size() + 1);
0155                 std::vector< cg_vertex >& chain = chains.back();
0156                 for (;;)
0157                 {
0158                     chain.push_back(v);
0159                     in_a_chain[v] = true;
0160 
0161                     typename std::vector< cg_vertex >::const_iterator next
0162                     #ifdef __cpp_lib_not_fn
0163                         = std::find_if(CG_vec[v].begin(), CG_vec[v].end(),
0164                                        std::not_fn(detail::subscript(in_a_chain)));
0165                     #else
0166                         = std::find_if(CG_vec[v].begin(), CG_vec[v].end(),
0167                                        std::not1(detail::subscript(in_a_chain)));
0168                     #endif
0169 
0170                     if (next != CG_vec[v].end())
0171                         v = *next;
0172                     else
0173                         break; // end of chain, dead-end
0174                 }
0175             }
0176         }
0177     }
0178     std::vector< size_type > chain_number(CG_vec.size());
0179     std::vector< size_type > pos_in_chain(CG_vec.size());
0180     for (size_type i = 0; i < chains.size(); ++i)
0181         for (size_type j = 0; j < chains[i].size(); ++j)
0182         {
0183             cg_vertex v = chains[i][j];
0184             chain_number[v] = i;
0185             pos_in_chain[v] = j;
0186         }
0187 
0188     cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
0189     std::vector< std::vector< cg_vertex > > successors(
0190         CG_vec.size(), std::vector< cg_vertex >(chains.size(), inf));
0191     for (typename std::vector< cg_vertex >::reverse_iterator i
0192          = topo_order.rbegin();
0193          i != topo_order.rend(); ++i)
0194     {
0195         cg_vertex u = *i;
0196         typename std::vector< cg_vertex >::const_iterator adj, adj_last;
0197         for (adj = CG_vec[u].begin(), adj_last = CG_vec[u].end();
0198              adj != adj_last; ++adj)
0199         {
0200             cg_vertex v = *adj;
0201             if (topo_number[v] < successors[u][chain_number[v]])
0202             {
0203                 // Succ(u) = Succ(u) U Succ(v)
0204                 detail::union_successor_sets(
0205                     successors[u], successors[v], successors[u]);
0206                 // Succ(u) = Succ(u) U {v}
0207                 successors[u][chain_number[v]] = topo_number[v];
0208             }
0209         }
0210     }
0211 
0212     for (size_type i = 0; i < CG_vec.size(); ++i)
0213         CG_vec[i].clear();
0214     for (size_type i = 0; i < CG_vec.size(); ++i)
0215         for (size_type j = 0; j < chains.size(); ++j)
0216         {
0217             size_type topo_num = successors[i][j];
0218             if (topo_num < inf)
0219             {
0220                 cg_vertex v = topo_order[topo_num];
0221                 for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
0222                     CG_vec[i].push_back(chains[j][k]);
0223             }
0224         }
0225 
0226     // Add vertices to the transitive closure graph
0227     {
0228         vertex_iterator i, i_end;
0229         for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
0230             g_to_tc_map[*i] = add_vertex(tc);
0231     }
0232     // Add edges between all the vertices in two adjacent SCCs
0233     typename std::vector< std::vector< cg_vertex > >::const_iterator si, si_end;
0234     for (si = CG_vec.begin(), si_end = CG_vec.end(); si != si_end; ++si)
0235     {
0236         cg_vertex s = si - CG_vec.begin();
0237         typename std::vector< cg_vertex >::const_iterator i, i_end;
0238         for (i = CG_vec[s].begin(), i_end = CG_vec[s].end(); i != i_end; ++i)
0239         {
0240             cg_vertex t = *i;
0241             for (size_type k = 0; k < components[s].size(); ++k)
0242                 for (size_type l = 0; l < components[t].size(); ++l)
0243                     add_edge(g_to_tc_map[components[s][k]],
0244                         g_to_tc_map[components[t][l]], tc);
0245         }
0246     }
0247     // Add edges connecting all vertices in a SCC
0248     for (size_type i = 0; i < components.size(); ++i)
0249         if (components[i].size() > 1)
0250             for (size_type k = 0; k < components[i].size(); ++k)
0251                 for (size_type l = 0; l < components[i].size(); ++l)
0252                 {
0253                     vertex u = components[i][k], v = components[i][l];
0254                     add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
0255                 }
0256 
0257     // Find loopbacks in the original graph.
0258     // Need to add it to transitive closure.
0259     {
0260         vertex_iterator i, i_end;
0261         for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
0262         {
0263             adjacency_iterator ab, ae;
0264             for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
0265             {
0266                 if (*ab == *i)
0267                     if (components[component_number[*i]].size() == 1)
0268                         add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
0269             }
0270         }
0271     }
0272 }
0273 
0274 template < typename Graph, typename GraphTC >
0275 void transitive_closure(const Graph& g, GraphTC& tc)
0276 {
0277     if (num_vertices(g) == 0)
0278         return;
0279     typedef typename property_map< Graph, vertex_index_t >::const_type
0280         VertexIndexMap;
0281     VertexIndexMap index_map = get(vertex_index, g);
0282 
0283     typedef typename graph_traits< GraphTC >::vertex_descriptor tc_vertex;
0284     std::vector< tc_vertex > to_tc_vec(num_vertices(g));
0285     iterator_property_map< tc_vertex*, VertexIndexMap, tc_vertex, tc_vertex& >
0286         g_to_tc_map(&to_tc_vec[0], index_map);
0287 
0288     transitive_closure(g, tc, g_to_tc_map, index_map);
0289 }
0290 
0291 namespace detail
0292 {
0293     template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
0294         typename VertexIndexMap >
0295     void transitive_closure_dispatch(const Graph& g, GraphTC& tc,
0296         G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
0297     {
0298         typedef typename graph_traits< GraphTC >::vertex_descriptor tc_vertex;
0299         typename std::vector< tc_vertex >::size_type n
0300             = is_default_param(g_to_tc_map) ? num_vertices(g) : 1;
0301         std::vector< tc_vertex > to_tc_vec(n);
0302 
0303         transitive_closure(g, tc,
0304             choose_param(g_to_tc_map,
0305                 make_iterator_property_map(
0306                     to_tc_vec.begin(), index_map, to_tc_vec[0])),
0307             index_map);
0308     }
0309 } // namespace detail
0310 
0311 template < typename Graph, typename GraphTC, typename P, typename T,
0312     typename R >
0313 void transitive_closure(
0314     const Graph& g, GraphTC& tc, const bgl_named_params< P, T, R >& params)
0315 {
0316     if (num_vertices(g) == 0)
0317         return;
0318     detail::transitive_closure_dispatch(g, tc,
0319         get_param(params, orig_to_copy_t()),
0320         choose_const_pmap(get_param(params, vertex_index), g, vertex_index));
0321 }
0322 
0323 template < typename G > void warshall_transitive_closure(G& g)
0324 {
0325     typedef typename graph_traits< G >::vertex_iterator vertex_iterator;
0326 
0327     BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< G >));
0328     BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< G >));
0329 
0330     // Matrix form:
0331     // for k
0332     //  for i
0333     //    if A[i,k]
0334     //      for j
0335     //        A[i,j] = A[i,j] | A[k,j]
0336     vertex_iterator ki, ke, ii, ie, ji, je;
0337     for (boost::tie(ki, ke) = vertices(g); ki != ke; ++ki)
0338         for (boost::tie(ii, ie) = vertices(g); ii != ie; ++ii)
0339             if (edge(*ii, *ki, g).second)
0340                 for (boost::tie(ji, je) = vertices(g); ji != je; ++ji)
0341                     if (!edge(*ii, *ji, g).second && edge(*ki, *ji, g).second)
0342                     {
0343                         add_edge(*ii, *ji, g);
0344                     }
0345 }
0346 
0347 template < typename G > void warren_transitive_closure(G& g)
0348 {
0349     using namespace boost;
0350     typedef typename graph_traits< G >::vertex_iterator vertex_iterator;
0351 
0352     BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< G >));
0353     BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< G >));
0354 
0355     // Make sure second loop will work
0356     if (num_vertices(g) == 0)
0357         return;
0358 
0359     // for i = 2 to n
0360     //    for k = 1 to i - 1
0361     //      if A[i,k]
0362     //        for j = 1 to n
0363     //          A[i,j] = A[i,j] | A[k,j]
0364 
0365     vertex_iterator ic, ie, jc, je, kc, ke;
0366     for (boost::tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
0367         for (boost::tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
0368             if (edge(*ic, *kc, g).second)
0369                 for (boost::tie(jc, je) = vertices(g); jc != je; ++jc)
0370                     if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second)
0371                     {
0372                         add_edge(*ic, *jc, g);
0373                     }
0374     //  for i = 1 to n - 1
0375     //    for k = i + 1 to n
0376     //      if A[i,k]
0377     //        for j = 1 to n
0378     //          A[i,j] = A[i,j] | A[k,j]
0379 
0380     for (boost::tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
0381         for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
0382             if (edge(*ic, *kc, g).second)
0383                 for (boost::tie(jc, je) = vertices(g); jc != je; ++jc)
0384                     if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second)
0385                     {
0386                         add_edge(*ic, *jc, g);
0387                     }
0388 }
0389 
0390 } // namespace boost
0391 
0392 #endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!