[Boost-commit] svn:boost r84976 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r84976 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2013-07-07 12:50:24

Author: jewillco
Date: 2013-07-07 12:50:24 EDT (Sun, 07 Jul 2013)
New Revision: 84976
URL: http://svn.boost.org/trac/boost/changeset/84976

Log:
Changed to use adjacency_list for temporary graph, avoiding ADL issues with vector_as_graph; fixes #8791

Text files modified: 
   trunk/boost/graph/transitive_closure.hpp |    56 ++++++++++++++++++++++----------------- 
   1 files changed, 31 insertions(+), 25 deletions(-)

Modified: trunk/boost/graph/transitive_closure.hpp
==============================================================================
--- trunk/boost/graph/transitive_closure.hpp	Sun Jul  7 12:49:36 2013	(r84975)
+++ trunk/boost/graph/transitive_closure.hpp	2013-07-07 12:50:24 EDT (Sun, 07 Jul 2013)	(r84976)
@@ -14,11 +14,11 @@
 #include <functional>
 #include <boost/config.hpp>
 #include <boost/bind.hpp>
-#include <boost/graph/vector_as_graph.hpp>
 #include <boost/graph/strong_components.hpp>
 #include <boost/graph/topological_sort.hpp>
 #include <boost/graph/graph_concepts.hpp>
 #include <boost/graph/named_function_params.hpp>
+#include <boost/graph/adjacency_list.hpp>
 #include <boost/concept/assert.hpp>
 
 namespace boost
@@ -95,7 +95,7 @@
     std::vector < std::vector < vertex > >components;
     build_component_lists(g, num_scc, component_number, components);
 
-    typedef std::vector<std::vector<cg_vertex> > CG_t;
+    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> CG_t;
     CG_t CG(num_scc);
     for (cg_vertex s = 0; s < components.size(); ++s) {
       std::vector < cg_vertex > adj;
@@ -113,7 +113,10 @@
         std::unique(adj.begin(), adj.end());
       if (di != adj.end())
         adj.erase(di, adj.end());
-      CG[s] = adj;
+      for (typename std::vector<cg_vertex>::const_iterator i = adj.begin();
+           i != adj.end(); ++i) {
+        add_edge(s, *i, CG);
+      }
     }
 
     std::vector<cg_vertex> topo_order;
@@ -126,15 +129,20 @@
          iter != topo_order.end(); ++iter)
       topo_number[*iter] = n++;
 
-    for (size_type i = 0; i < num_vertices(CG); ++i)
-      std::sort(CG[i].begin(), CG[i].end(),
+    std::vector<std::vector<cg_vertex> > CG_vec(num_vertices(CG));
+    for (size_type i = 0; i < num_vertices(CG); ++i) {
+      typedef typename boost::graph_traits<CG_t>::adjacency_iterator cg_adj_iter;
+      std::pair<cg_adj_iter, cg_adj_iter> pr = adjacent_vertices(i, CG);
+      CG_vec[i].assign(pr.first, pr.second);
+      std::sort(CG_vec[i].begin(), CG_vec[i].end(),
                 boost::bind(std::less<cg_vertex>(),
                             boost::bind(detail::subscript(topo_number), _1),
                             boost::bind(detail::subscript(topo_number), _2)));
+    }
 
     std::vector<std::vector<cg_vertex> > chains;
     {
-      std::vector<cg_vertex> in_a_chain(num_vertices(CG));
+      std::vector<cg_vertex> in_a_chain(CG_vec.size());
       for (typename std::vector<cg_vertex>::iterator i = topo_order.begin();
            i != topo_order.end(); ++i) {
         cg_vertex v = *i;
@@ -144,12 +152,10 @@
           for (;;) {
             chain.push_back(v);
             in_a_chain[v] = true;
-            typename graph_traits<CG_t>::adjacency_iterator adj_first, adj_last;
-            boost::tie(adj_first, adj_last) = adjacent_vertices(v, CG);
-            typename graph_traits<CG_t>::adjacency_iterator next
-              = std::find_if(adj_first, adj_last,
+            typename std::vector<cg_vertex>::const_iterator next
+              = std::find_if(CG_vec[v].begin(), CG_vec[v].end(),
                              std::not1(detail::subscript(in_a_chain)));
-            if (next != adj_last)
+            if (next != CG_vec[v].end())
               v = *next;
             else
               break;            // end of chain, dead-end
@@ -158,8 +164,8 @@
         }
       }
     }
-    std::vector<size_type> chain_number(num_vertices(CG));
-    std::vector<size_type> pos_in_chain(num_vertices(CG));
+    std::vector<size_type> chain_number(CG_vec.size());
+    std::vector<size_type> pos_in_chain(CG_vec.size());
     for (size_type i = 0; i < chains.size(); ++i)
       for (size_type j = 0; j < chains[i].size(); ++j) {
         cg_vertex v = chains[i][j];
@@ -168,14 +174,14 @@
       }
 
     cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
-    std::vector<std::vector<cg_vertex> > successors(num_vertices(CG),
+    std::vector<std::vector<cg_vertex> > successors(CG_vec.size(),
                                                     std::vector<cg_vertex>
                                                     (chains.size(), inf));
     for (typename std::vector<cg_vertex>::reverse_iterator
            i = topo_order.rbegin(); i != topo_order.rend(); ++i) {
       cg_vertex u = *i;
-      typename graph_traits<CG_t>::adjacency_iterator adj, adj_last;
-      for (boost::tie(adj, adj_last) = adjacent_vertices(u, CG);
+      typename std::vector<cg_vertex>::const_iterator adj, adj_last;
+      for (adj = CG_vec[u].begin(), adj_last = CG_vec[u].end();
            adj != adj_last; ++adj) {
         cg_vertex v = *adj;
         if (topo_number[v] < successors[u][chain_number[v]]) {
@@ -188,15 +194,15 @@
       }
     }
 
-    for (size_type i = 0; i < CG.size(); ++i)
-      CG[i].clear();
-    for (size_type i = 0; i < CG.size(); ++i)
+    for (size_type i = 0; i < CG_vec.size(); ++i)
+      CG_vec[i].clear();
+    for (size_type i = 0; i < CG_vec.size(); ++i)
       for (size_type j = 0; j < chains.size(); ++j) {
         size_type topo_num = successors[i][j];
         if (topo_num < inf) {
           cg_vertex v = topo_order[topo_num];
           for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
-            CG[i].push_back(chains[j][k]);
+            CG_vec[i].push_back(chains[j][k]);
         }
       }
 
@@ -209,11 +215,11 @@
         g_to_tc_map[*i] = add_vertex(tc);
     }
     // Add edges between all the vertices in two adjacent SCCs
-    typename graph_traits<CG_t>::vertex_iterator si, si_end;
-    for (boost::tie(si, si_end) = vertices(CG); si != si_end; ++si) {
-      cg_vertex s = *si;
-      typename graph_traits<CG_t>::adjacency_iterator i, i_end;
-      for (boost::tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) {
+    typename std::vector<std::vector<cg_vertex> >::const_iterator si, si_end;
+    for (si = CG_vec.begin(), si_end = CG_vec.end(); si != si_end; ++si) {
+      cg_vertex s = si - CG_vec.begin();
+      typename std::vector<cg_vertex>::const_iterator i, i_end;
+      for (i = CG_vec[s].begin(), i_end = CG_vec[s].end(); i != i_end; ++i) {
         cg_vertex t = *i;
         for (size_type k = 0; k < components[s].size(); ++k)
           for (size_type l = 0; l < components[t].size(); ++l)