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

Subject: [Boost-commit] svn:boost r55667 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2009-08-19 16:54:43

Author: jewillco
Date: 2009-08-19 16:54:42 EDT (Wed, 19 Aug 2009)
New Revision: 55667
URL: http://svn.boost.org/trac/boost/changeset/55667

Log:
Fixed edge doubling for copying from an undirected graph to a CSR graph; fixes #3357
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |    25 +++++++++++++++++++++----               
   1 files changed, 21 insertions(+), 4 deletions(-)

Modified: trunk/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/compressed_sparse_row_graph.hpp	(original)
+++ trunk/boost/graph/compressed_sparse_row_graph.hpp	2009-08-19 16:54:42 EDT (Wed, 19 Aug 2009)
@@ -965,7 +965,11 @@
   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
     : m_property()
   {
-    assign(g, vi, num_vertices(g), num_edges(g));
+    typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+    if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
+      numedges *= 2; // Double each edge (actual doubling done by out_edges function)
+    }
+    assign(g, vi, num_vertices(g), numedges);
   }
 
   // Requires vertex index map plus requirements of previous constructor
@@ -973,12 +977,17 @@
   explicit compressed_sparse_row_graph(const Graph& g)
     : m_property()
   {
-    assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
+    typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+    if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
+      numedges *= 2; // Double each edge (actual doubling done by out_edges function)
+    }
+    assign(g, get(vertex_index, g), num_vertices(g), numedges);
   }
 
   // From any graph (slow and uses a lot of memory)
   //   Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function
   //   Internal helper function
+  //   Note that numedges must be doubled for undirected source graphs
   template<typename Graph, typename VertexIndexMap>
   void
   assign(const Graph& g, const VertexIndexMap& vi,
@@ -1020,14 +1029,22 @@
   template<typename Graph, typename VertexIndexMap>
   void assign(const Graph& g, const VertexIndexMap& vi)
   {
-    assign(g, vi, num_vertices(g), num_edges(g));
+    typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+    if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
+      numedges *= 2; // Double each edge (actual doubling done by out_edges function)
+    }
+    assign(g, vi, num_vertices(g), numedges);
   }
 
   // Requires the above, plus a vertex_index map.
   template<typename Graph>
   void assign(const Graph& g)
   {
-    assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
+    typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+    if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
+      numedges *= 2; // Double each edge (actual doubling done by out_edges function)
+    }
+    assign(g, get(vertex_index, g), num_vertices(g), numedges);
   }
 
 #ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE