Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r54064 - in branches/release: boost/graph boost/graph/distributed libs/graph/doc libs/graph/test libs/graph_parallel/example libs/graph_parallel/test status
From: jewillco_at_[hidden]
Date: 2009-06-18 15:34:29

Author: jewillco
Date: 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
New Revision: 54064
URL: http://svn.boost.org/trac/boost/changeset/54064

Log:
Merged in commits on trunk mentioned in comments 1-32 of #3134, plus r54059 not listed there; refs #3134
Added:
   branches/release/libs/graph_parallel/example/Jamfile.v2
      - copied, changed from r53934, /trunk/libs/graph_parallel/example/Jamfile.v2
   branches/release/libs/graph_parallel/test/Jamfile.v2
      - copied, changed from r53934, /trunk/libs/graph_parallel/test/Jamfile.v2
Text files modified:
   branches/release/boost/graph/adj_list_serialize.hpp | 17
   branches/release/boost/graph/adjacency_list_io.hpp | 44 ++--
   branches/release/boost/graph/astar_search.hpp | 17 -
   branches/release/boost/graph/bc_clustering.hpp | 8
   branches/release/boost/graph/compressed_sparse_row_graph.hpp | 369 ++++++++++++++++++++++++++++++++++-----
   branches/release/boost/graph/cuthill_mckee_ordering.hpp | 5
   branches/release/boost/graph/depth_first_search.hpp | 10
   branches/release/boost/graph/distributed/adjacency_list.hpp | 2
   branches/release/boost/graph/distributed/betweenness_centrality.hpp | 8
   branches/release/boost/graph/distributed/connected_components.hpp | 1
   branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp | 12 -
   branches/release/boost/graph/edge_connectivity.hpp | 6
   branches/release/boost/graph/graph_utility.hpp | 21 ++
   branches/release/boost/graph/howard_cycle_ratio.hpp | 3
   branches/release/boost/graph/isomorphism.hpp | 10
   branches/release/boost/graph/iteration_macros.hpp | 69 ++++---
   branches/release/boost/graph/king_ordering.hpp | 5
   branches/release/boost/graph/metric_tsp_approx.hpp | 2
   branches/release/boost/graph/named_function_params.hpp | 6
   branches/release/boost/graph/properties.hpp | 8
   branches/release/boost/graph/push_relabel_max_flow.hpp | 43 ++--
   branches/release/boost/graph/relax.hpp | 7
   branches/release/boost/graph/rmat_graph_generator.hpp | 21 +
   branches/release/libs/graph/doc/compressed_sparse_row.html | 112 +++++++++++
   branches/release/libs/graph/test/Jamfile.v2 | 2
   branches/release/libs/graph/test/betweenness_centrality_test.cpp | 7
   branches/release/libs/graph/test/csr_graph_test.cpp | 15 +
   branches/release/libs/graph/test/gursoy_atun_layout_test.cpp | 8
   branches/release/libs/graph_parallel/example/Jamfile.v2 | 6
   branches/release/libs/graph_parallel/example/breadth_first_search.cpp | 2
   branches/release/libs/graph_parallel/example/dijkstra_shortest_paths.cpp | 2
   branches/release/libs/graph_parallel/test/Jamfile.v2 | 40 ++--
   branches/release/libs/graph_parallel/test/distributed_adjacency_list_test.cpp | 6
   branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp | 2
   branches/release/libs/graph_parallel/test/distributed_property_map_test.cpp | 4
   branches/release/status/explicit-failures-markup.xml | 12 +
   36 files changed, 671 insertions(+), 241 deletions(-)

Modified: branches/release/boost/graph/adj_list_serialize.hpp
==============================================================================
--- branches/release/boost/graph/adj_list_serialize.hpp (original)
+++ branches/release/boost/graph/adj_list_serialize.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -10,6 +10,7 @@
#define ADJ_LIST_SERIALIZE_HPP

#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/iteration_macros.hpp>
#include <boost/pending/property_serialize.hpp>
#include <boost/config.hpp>
#include <boost/detail/workaround.hpp>
@@ -49,18 +50,16 @@
 // assign indices to vertices
 std::map<Vertex,int> indices;
 int num = 0;
- typename graph_traits<Graph>::vertex_iterator vi;
- for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi) {
- indices[*vi] = num++;
- ar << serialization::make_nvp("vertex_property", get(vertex_all_t(), graph, *vi) );
+ BGL_FORALL_VERTICES_T(v, graph, Graph) {
+ indices[v] = num++;
+ ar << serialization::make_nvp("vertex_property", get(vertex_all_t(), graph, v) );
 }

 // write edges
- typename graph_traits<Graph>::edge_iterator ei;
- for (ei = edges(graph).first; ei != edges(graph).second; ++ei){
- ar << serialization::make_nvp("u" , indices[source(*ei,graph)]);
- ar << serialization::make_nvp("v" , indices[target(*ei,graph)]);
- ar << serialization::make_nvp("edge_property", get(edge_all_t(), graph, *ei) );
+ BGL_FORALL_EDGES_T(e, graph, Graph) {
+ ar << serialization::make_nvp("u" , indices[source(e,graph)]);
+ ar << serialization::make_nvp("v" , indices[target(e,graph)]);
+ ar << serialization::make_nvp("edge_property", get(edge_all_t(), graph, e) );
 }
}

Modified: branches/release/boost/graph/adjacency_list_io.hpp
==============================================================================
--- branches/release/boost/graph/adjacency_list_io.hpp (original)
+++ branches/release/boost/graph/adjacency_list_io.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -12,6 +12,7 @@
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/iteration_macros.hpp>
#include <cctype>

// Method read to parse an adjacency list from an input stream. Examples:
@@ -211,13 +212,13 @@

 PropertyPrinter( const Graph& g ):graph(&g){}

- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream& out, Iterator it )
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream& out, const Val& v )
 {
 typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
- out << ps[ *it ] <<" ";
+ out << ps[ v ] <<" ";
 PropertyPrinter<Graph,Next> print(*graph);
- print(out, it);
+ print(out, v);
 return (*this);
 }
private:
@@ -229,10 +230,10 @@
{
 PropertyPrinter( const Graph& g ):graph(&g){}

- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream& out, Iterator it )
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream& out, const Val& v )
 {
- out << (*graph)[ *it ] <<" ";
+ out << (*graph)[ v ] <<" ";
 return (*this);
 }
private:
@@ -244,13 +245,13 @@
{
 PropertyPrinter( const Graph& g ):graph(&g){}

- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream& out, Iterator it )
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream& out, const Val& v )
 {
 typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
- out << ps[ *it ] <<" ";
+ out << ps[ v ] <<" ";
 PropertyPrinter<Graph,Next> print(*graph);
- print(out, it);
+ print(out, v);
 return (*this);
 }
private:
@@ -263,8 +264,8 @@
{
 PropertyPrinter( const Graph& ){}

- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream&, Iterator it ){ return *this; }
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream&, const Val& ){ return *this; }
};

// property printer
@@ -287,18 +288,16 @@
 // assign indices to vertices
 std::map<Vertex,int> indices;
 int num = 0;
- typename graph_traits<Graph>::vertex_iterator vi;
- for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){
- indices[*vi] = num++;
+ BGL_FORALL_VERTICES_T(v, graph, Graph) {
+ indices[v] = num++;
 }

 // write edges
 PropertyPrinter<Graph, EdgeProperty> print_Edge(graph);
 out << "e" << std::endl;
- typename graph_traits<Graph>::edge_iterator ei;
- for (ei = edges(graph).first; ei != edges(graph).second; ++ei){
- out << indices[source(*ei,graph)] << " " << indices[target(*ei,graph)] << " ";
- print_Edge(out,ei);
+ BGL_FORALL_EDGES_T(e, graph, Graph) {
+ out << indices[source(e,graph)] << " " << indices[target(e,graph)] << " ";
+ print_Edge(out,e);
 out << std::endl;
 }
 out << std::endl;
@@ -322,9 +321,8 @@
 {
 PropertyPrinter<Graph, V> printNode(this->graph);
 out << "v"<<std::endl;
- typename graph_traits<Graph>::vertex_iterator vi;
- for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){
- printNode(out,vi);
+ BGL_FORALL_VERTICES_T(v, this->graph, Graph) {
+ printNode(out,v);
 out << std::endl;
 }

Modified: branches/release/boost/graph/astar_search.hpp
==============================================================================
--- branches/release/boost/graph/astar_search.hpp (original)
+++ branches/release/boost/graph/astar_search.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -172,20 +172,10 @@

 template <class Edge, class Graph>
 void gray_target(Edge e, Graph& g) {
- distance_type old_distance = get(m_distance, target(e, g));
-
 m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
 m_combine, m_compare);

- /* On x86 Linux with optimization, we sometimes get into a
- horrible case where m_decreased is true but the distance hasn't
- actually changed. This occurs when the comparison inside
- relax() occurs with the 80-bit precision of the x87 floating
- point unit, but the difference is lost when the resulting
- values are written back to lower-precision memory (e.g., a
- double). With the eager Dijkstra's implementation, this results
- in looping. */
- if(m_decreased && old_distance != get(m_distance, target(e, g))) {
+ if(m_decreased) {
 put(m_cost, target(e, g),
 m_combine(get(m_distance, target(e, g)),
 m_h(target(e, g))));
@@ -198,13 +188,10 @@

 template <class Edge, class Graph>
 void black_target(Edge e, Graph& g) {
- distance_type old_distance = get(m_distance, target(e, g));
-
 m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
 m_combine, m_compare);

- /* See comment in gray_target */
- if(m_decreased && old_distance != get(m_distance, target(e, g))) {
+ if(m_decreased) {
 m_vis.edge_relaxed(e, g);
 put(m_cost, target(e, g),
 m_combine(get(m_distance, target(e, g)),

Modified: branches/release/boost/graph/bc_clustering.hpp
==============================================================================
--- branches/release/boost/graph/bc_clustering.hpp (original)
+++ branches/release/boost/graph/bc_clustering.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -11,6 +11,7 @@

#include <boost/graph/betweenness_centrality.hpp>
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_utility.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <algorithm>
#include <vector>
@@ -116,7 +117,7 @@
 typedef typename graph_traits<MutableGraph>::vertices_size_type
 vertices_size_type;

- if (edges(g).first == edges(g).second) return;
+ if (has_no_edges(g)) return;

 // Function object that compares the centrality of edges
 indirect_cmp<EdgeCentralityMap, std::less<centrality_type> >
@@ -127,10 +128,11 @@
 brandes_betweenness_centrality(g,
 edge_centrality_map(edge_centrality)
 .vertex_index_map(vertex_index));
- edge_descriptor e = *max_element(edges(g).first, edges(g).second, cmp);
+ std::pair<edge_iterator, edge_iterator> edges_iters = edges(g);
+ edge_descriptor e = *max_element(edges_iters.first, edges_iters.second, cmp);
 is_done = done(get(edge_centrality, e), e, g);
 if (!is_done) remove_edge(e, g);
- } while (!is_done && edges(g).first != edges(g).second);
+ } while (!is_done && !has_no_edges(g));
}

/**

Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -19,9 +19,12 @@
#include <climits>
#include <cassert>
#include <iterator>
-#include <iostream> // FIXME
+#if 0
+#include <iostream> // For some debugging code below
+#endif
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/graph/filtered_graph.hpp> // For keep_all
#include <boost/graph/detail/indexed_properties.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/property_map/property_map.hpp>
@@ -58,26 +61,35 @@
// A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate
// that the edge list passed into the CSR graph is already sorted by source
// vertex.
-struct edges_are_sorted_internal {};
-inline void edges_are_sorted(edges_are_sorted_internal) {}
-typedef void (*edges_are_sorted_t)(edges_are_sorted_internal);
+enum edges_are_sorted_t {edges_are_sorted};

#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
// indicate that the edge list passed into the CSR graph is not sorted by
-// source vertex.
-struct edges_are_unsorted_internal {};
-inline void edges_are_unsorted(edges_are_unsorted_internal) {}
-typedef void (*edges_are_unsorted_t)(edges_are_unsorted_internal);
+// source vertex. This version caches the edge information in memory, and thus
+// requires only a single pass over the input data.
+enum edges_are_unsorted_t {edges_are_unsorted};
+
+// A type (edges_are_unsorted_multi_pass_t) and a value
+// (edges_are_unsorted_multi_pass) used to indicate that the edge list passed
+// into the CSR graph is not sorted by source vertex. This version uses less
+// memory but requires multi-pass capability on the iterators.
+enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
+
+// A type (edges_are_unsorted_multi_pass_filtered_t) and a value
+// (edges_are_unsorted_multi_pass_filtered) used to indicate that the edge list
+// passed into the CSR graph is not sorted by source vertex. This version uses
+// less memory but requires multi-pass capability on the iterators. The
+// filtering is done here because it is often faster and it greatly simplifies
+// handling of edge properties.
+enum edges_are_unsorted_multi_pass_filtered_t {edges_are_unsorted_multi_pass_filtered};

// A type (construct_inplace_from_sources_and_targets_t) and a value
// (construct_inplace_from_sources_and_targets) used to indicate that mutable
// vectors of sources and targets (and possibly edge properties) are being used
// to construct the CSR graph. These vectors are sorted in-place and then the
// targets and properties are swapped into the graph data structure.
-struct construct_inplace_from_sources_and_targets_internal {};
-inline void construct_inplace_from_sources_and_targets(construct_inplace_from_sources_and_targets_internal) {}
-typedef void (*construct_inplace_from_sources_and_targets_t)(construct_inplace_from_sources_and_targets_internal);
+enum construct_inplace_from_sources_and_targets_t {construct_inplace_from_sources_and_targets};

// A type (construct_inplace_from_sources_and_targets_global_t) and a value
// (construct_inplace_from_sources_and_targets_global) used to indicate that
@@ -88,9 +100,16 @@
// used, and a map is required to convert those to local indices. This
// constructor is intended for internal use by the various CSR graphs
// (sequential and distributed).
-struct construct_inplace_from_sources_and_targets_global_internal {};
-inline void construct_inplace_from_sources_and_targets_global(construct_inplace_from_sources_and_targets_global_internal) {}
-typedef void (*construct_inplace_from_sources_and_targets_global_t)(construct_inplace_from_sources_and_targets_global_internal);
+enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
+
+// A type (edges_are_unsorted_for_distributed_graph_t) and a value
+// (edges_are_unsorted_for_distributed_graph) used to indicate that the edge
+// list passed into the CSR graph is not sorted by source vertex. The data is
+// also stored using global vertex indices, and must be filtered to choose only
+// local vertices. This constructor caches the edge information in memory, and
+// thus requires only a single pass over the input data. This constructor is
+// intended for internal use by the distributed CSR constructors.
+enum edges_are_unsorted_for_distributed_graph_t {edges_are_unsorted_for_distributed_graph};

#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE

@@ -111,14 +130,33 @@

#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
namespace detail {
- // Less-than operator for comparing only the first elements of two arbitrary
- // Boost tuples
- struct compare_first_elements_in_tuples {
- template <typename Tuple>
- bool operator()(const Tuple& a, const Tuple& b) const {
- return (a.template get<0>()) < (b.template get<0>());
- }
- };
+ template<typename InputIterator>
+ size_t
+ reserve_count_for_single_pass_helper(InputIterator, InputIterator,
+ std::input_iterator_tag)
+ {
+ // Do nothing: we have no idea how much storage to reserve.
+ return 0;
+ }
+
+ template<typename InputIterator>
+ size_t
+ reserve_count_for_single_pass_helper(InputIterator first, InputIterator last,
+ std::random_access_iterator_tag)
+ {
+ using std::distance;
+ typename std::iterator_traits<InputIterator>::difference_type n =
+ distance(first, last);
+ return (size_t)n;
+ }
+
+ template<typename InputIterator>
+ size_t
+ reserve_count_for_single_pass(InputIterator first, InputIterator last) {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category
+ category;
+ return reserve_count_for_single_pass_helper(first, last, category());
+ }
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE

@@ -241,19 +279,20 @@
 }

#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- // From number of vertices and unsorted list of edges
- template <typename MultiPassInputIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
- MultiPassInputIterator edge_begin,
- MultiPassInputIterator edge_end,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop)
- {
+ // Rebuild graph from number of vertices and multi-pass unsorted list of
+ // edges (filtered using edge_pred)
+ template <typename MultiPassInputIterator, typename EdgePred>
+ void
+ assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ vertices_size_type numverts,
+ const EdgePred& edge_pred) {
+ m_rowstart.clear();
+ m_rowstart.resize(numverts + 1, 0);
 // Put the degree of each vertex v into m_rowstart[v + 1]
 for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
- ++m_rowstart[i->first + 1];
+ if (edge_pred(*i))
+ ++m_rowstart[i->first + 1];

 // Compute the partial sum of the degrees to get the actual values of
 // m_rowstart
@@ -271,26 +310,25 @@
 std::vector<EdgeIndex>
 current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
 for (; edge_begin != edge_end; ++edge_begin)
- m_column[current_insert_positions[edge_begin->first]++] = edge_begin->second;
-
- // Default-construct properties for edges
- inherited_edge_properties::resize(m_column.size());
+ if (edge_pred(*edge_begin))
+ m_column[current_insert_positions[edge_begin->first]++] = edge_begin->second;
 }

- // From number of vertices and unsorted list of edges, plus edge properties
- template <typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
- MultiPassInputIterator edge_begin,
- MultiPassInputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop)
- {
+ // Rebuild graph from number of vertices and multi-pass unsorted list of
+ // edges and their properties (filtered using edge_pred)
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename EdgePred>
+ void
+ assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const EdgePred& edge_pred) {
+ m_rowstart.clear();
+ m_rowstart.resize(numverts + 1, 0);
 // Put the degree of each vertex v into m_rowstart[v + 1]
 for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
- ++m_rowstart[i->first + 1];
+ if (edge_pred(*i))
+ ++m_rowstart[i->first + 1];

 // Compute the partial sum of the degrees to get the actual values of
 // m_rowstart
@@ -309,13 +347,77 @@
 std::vector<EdgeIndex>
 current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
 for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
- vertices_size_type source = edge_begin->first;
- EdgeIndex insert_pos = current_insert_positions[source];
- ++current_insert_positions[source];
- m_column[insert_pos] = edge_begin->second;
- inherited_edge_properties::write_by_index(insert_pos, *ep_iter);
+ if (edge_pred(*edge_begin)) {
+ vertices_size_type source = edge_begin->first;
+ EdgeIndex insert_pos = current_insert_positions[source];
+ ++current_insert_positions[source];
+ m_column[insert_pos] = edge_begin->second;
+ inherited_edge_properties::write_by_index(insert_pos, *ep_iter);
+ }
 }
 }
+
+ // From number of vertices and unsorted list of edges
+ template <typename MultiPassInputIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(),
+ m_column(0), m_property(prop)
+ {
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, keep_all());
+
+ // Default-construct properties for edges
+ inherited_edge_properties::resize(m_column.size());
+ }
+
+ // From number of vertices and unsorted list of edges, plus edge properties
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(),
+ m_column(0), m_property(prop)
+ {
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, keep_all());
+ }
+
+ // From number of vertices and unsorted list of edges, with filter
+ template <typename MultiPassInputIterator, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_filtered_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ vertices_size_type numverts,
+ const EdgePred& edge_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(),
+ m_column(0), m_property(prop)
+ {
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, edge_pred);
+
+ // Default-construct properties for edges
+ inherited_edge_properties::resize(m_column.size());
+ }
+
+ // From number of vertices and unsorted list of edges, plus edge properties, with filter
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_filtered_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const EdgePred& edge_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(),
+ m_column(0), m_property(prop)
+ {
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, edge_pred);
+ }
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE

#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -557,6 +659,106 @@
 assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
 }

+ // From number of vertices and single-pass range of unsorted edges. Data is
+ // cached in coordinate form before creating the actual graph.
+ template<typename InputIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(),
+ m_column(), m_property(prop)
+ {
+ std::vector<vertex_descriptor> sources, targets;
+ size_t reserve_size
+ = detail::reserve_count_for_single_pass(edge_begin, edge_end);
+ sources.reserve(reserve_size);
+ targets.reserve(reserve_size);
+ for (; edge_begin != edge_end; ++edge_begin) {
+ sources.push_back(edge_begin->first);
+ targets.push_back(edge_begin->second);
+ }
+ assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
+ }
+
+ // From number of vertices and single-pass range of unsorted edges and
+ // single-pass range of edge properties. Data is cached in coordinate form
+ // before creating the actual graph.
+ template<typename InputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(),
+ m_column(), m_property(prop)
+ {
+ std::vector<vertex_descriptor> sources, targets;
+ std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+ size_t reserve_size
+ = detail::reserve_count_for_single_pass(edge_begin, edge_end);
+ sources.reserve(reserve_size);
+ targets.reserve(reserve_size);
+ edge_props.reserve(reserve_size);
+ for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
+ sources.push_back(edge_begin->first);
+ targets.push_back(edge_begin->second);
+ edge_props.push_back(*ep_iter);
+ }
+ assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
+ }
+
+ // From number of vertices and single-pass range of unsorted edges. Data is
+ // cached in coordinate form before creating the actual graph. Edges are
+ // filtered and transformed for use in a distributed graph.
+ template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numlocalverts,
+ GlobalToLocal global_to_local,
+ const EdgePred& edge_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numlocalverts), m_rowstart(),
+ m_column(), m_property(prop)
+ {
+ std::vector<vertex_descriptor> sources, targets;
+ for (; edge_begin != edge_end; ++edge_begin) {
+ if (edge_pred(*edge_begin)) {
+ sources.push_back(edge_begin->first);
+ targets.push_back(edge_begin->second);
+ }
+ }
+ assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
+ }
+
+ // From number of vertices and single-pass range of unsorted edges and
+ // single-pass range of edge properties. Data is cached in coordinate form
+ // before creating the actual graph. Edges are filtered and transformed for
+ // use in a distributed graph.
+ template<typename InputIterator, typename EdgePropertyIterator,
+ typename GlobalToLocal, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numlocalverts,
+ GlobalToLocal global_to_local,
+ const EdgePred& edge_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numlocalverts), m_rowstart(),
+ m_column(), m_property(prop)
+ {
+ std::vector<vertex_descriptor> sources, targets;
+ std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+ for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
+ if (edge_pred(*edge_begin)) {
+ sources.push_back(edge_begin->first);
+ targets.push_back(edge_begin->second);
+ edge_props.push_back(*ep_iter);
+ }
+ }
+ assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
+ }
+
 // Replace graph with sources and targets given, sorting them in-place, and
 // using the given global-to-local property map to get local indices from
 // global ones in the two arrays.
@@ -841,6 +1043,65 @@
}
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE

+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// Add edges from a range of (source, target) pairs that are unsorted
+template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
+inline void
+add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
+ typedef BOOST_CSR_GRAPH_TYPE Graph;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+ typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+ typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+ typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
+ edge_vector_t new_edges(first, last);
+ if (new_edges.empty()) return;
+ std::sort(new_edges.begin(), new_edges.end());
+ edge_num edges_added_before_i = new_edges.size(); // Count increment to add to rowstarts
+ g.m_column.resize(g.m_column.size() + new_edges.size());
+ typename edge_vector_t::const_reverse_iterator
+ current_new_edge = new_edges.rbegin(),
+ prev_new_edge = new_edges.rbegin();
+ for (vertex_num i_plus_1 = num_vertices(g); i_plus_1 > 0; --i_plus_1) {
+ vertex_num i = i_plus_1 - 1;
+ prev_new_edge = current_new_edge;
+ // edges_added_to_this_vertex = #mbrs of new_edges with first == i
+ edge_num edges_added_to_this_vertex = 0;
+ while (current_new_edge !=
+ (typename edge_vector_t::const_reverse_iterator)new_edges.rend()) {
+ if (current_new_edge->first != i) break;
+ ++current_new_edge;
+ ++edges_added_to_this_vertex;
+ }
+ edges_added_before_i -= edges_added_to_this_vertex;
+ // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
+ edge_num old_rowstart = g.m_rowstart[i];
+ edge_num new_rowstart = g.m_rowstart[i] + edges_added_before_i;
+ edge_num old_degree = g.m_rowstart[i + 1] - g.m_rowstart[i];
+ edge_num new_degree = old_degree + edges_added_to_this_vertex;
+ // Move old edges forward (by #new_edges before this i) to make room
+ // new_rowstart > old_rowstart, so use copy_backwards
+ if (old_rowstart != new_rowstart) {
+ std::copy_backward(g.m_column.begin() + old_rowstart,
+ g.m_column.begin() + old_rowstart + old_degree,
+ g.m_column.begin() + new_rowstart + old_degree);
+ }
+ // Add new edges (reversed because current_new_edge is a
+ // const_reverse_iterator)
+ typename edge_vector_t::const_reverse_iterator temp = current_new_edge;
+ for (; temp != prev_new_edge; ++old_degree) {
+ --temp;
+ g.m_column[new_rowstart + old_degree] = temp->second;
+ }
+ g.m_rowstart[i + 1] = new_rowstart + new_degree;
+ if (edges_added_before_i == 0) break; // No more edges inserted before this point
+ // g.m_rowstart[i] will be fixed up on the next iteration (to avoid
+ // changing the degree of vertex i - 1); the last iteration never changes
+ // it (either because of the condition of the break or because
+ // g.m_rowstart[0] is always 0)
+ }
+}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
// From VertexListGraph
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex

Modified: branches/release/boost/graph/cuthill_mckee_ordering.hpp
==============================================================================
--- branches/release/boost/graph/cuthill_mckee_ordering.hpp (original)
+++ branches/release/boost/graph/cuthill_mckee_ordering.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -13,6 +13,7 @@

#include <boost/config.hpp>
#include <boost/graph/detail/sparse_ordering.hpp>
+#include <boost/graph/graph_utility.hpp>
#include <algorithm>

@@ -132,7 +133,7 @@
 cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
 ColorMap color, DegreeMap degree)
 {
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
 return permutation;

 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
@@ -168,7 +169,7 @@
 cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
 VertexIndexMap index_map)
 {
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
 return permutation;

 typedef out_degree_property_map<Graph> DegreeMap;

Modified: branches/release/boost/graph/depth_first_search.hpp
==============================================================================
--- branches/release/boost/graph/depth_first_search.hpp (original)
+++ branches/release/boost/graph/depth_first_search.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -214,10 +214,12 @@
 void
 depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color)
 {
- if (vertices(g).first == vertices(g).second)
+ typedef typename boost::graph_traits<VertexListGraph>::vertex_iterator vi;
+ std::pair<vi, vi> verts = vertices(g);
+ if (verts.first == verts.second)
 return;

- depth_first_search(g, vis, color, *vertices(g).first);
+ depth_first_search(g, vis, color, *verts.first);
 }

 template <class Visitors = null_visitor>
@@ -284,7 +286,9 @@
 depth_first_search(const VertexListGraph& g,
 const bgl_named_params<P, T, R>& params)
 {
- if (vertices(g).first == vertices(g).second)
+ typedef typename boost::graph_traits<VertexListGraph>::vertex_iterator vi;
+ std::pair<vi, vi> verts = vertices(g);
+ if (verts.first == verts.second)
 return;
 using namespace boost::graph::keywords;
 typedef bgl_named_params<P, T, R> params_type;

Modified: branches/release/boost/graph/distributed/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/distributed/adjacency_list.hpp (original)
+++ branches/release/boost/graph/distributed/adjacency_list.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -1417,7 +1417,7 @@
 in_edge_iterator;

 /// Iterator over the neighbors of a vertex
- typedef adjacency_iterator<
+ typedef boost::adjacency_iterator<
 adjacency_list, vertex_descriptor, out_edge_iterator,
 typename detail::iterator_traits<base_out_edge_iterator>
 ::difference_type>

Modified: branches/release/boost/graph/distributed/betweenness_centrality.hpp
==============================================================================
--- branches/release/boost/graph/distributed/betweenness_centrality.hpp (original)
+++ branches/release/boost/graph/distributed/betweenness_centrality.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -295,8 +295,8 @@
#endif
 Dist delta)
 : g(g),
- distance(distance),
 incoming(incoming),
+ distance(distance),
 weight(weight),
 path_count(path_count),
#ifdef COMPUTE_PATH_COUNTS_INLINE
@@ -1047,7 +1047,7 @@
 vertices_size_type n = num_vertices(g);
 n = boost::parallel::all_reduce(pg, n, std::plus<vertices_size_type>());

- for (int i = 0; i < n; ++i) {
+ for (vertices_size_type i = 0; i < n; ++i) {
 vertex_descriptor v = vertex(i, g);

 do_brandes_sssp(g, centrality, edge_centrality_map, incoming, distance,
@@ -1189,7 +1189,7 @@
 }

 // DO SSSPs
- for(int i = 0; i < local_sources.size(); ++i)
+ for(size_t i = 0; i < local_sources.size(); ++i)
 do_sequential_brandes_sssp(g, centrality, edge_centrality_map, incoming,
 distance, dependency, path_count, vertex_index,
 shortest_paths, ordered_vertices, local_sources[i]);
@@ -1198,7 +1198,7 @@
 typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
 vertices_size_type n = num_vertices(g);

- for (int i = id; i < n; i += p) {
+ for (vertices_size_type i = id; i < n; i += p) {
 vertex_descriptor v = vertex(i, g);

 do_sequential_brandes_sssp(g, centrality, edge_centrality_map, incoming,

Modified: branches/release/boost/graph/distributed/connected_components.hpp
==============================================================================
--- branches/release/boost/graph/distributed/connected_components.hpp (original)
+++ branches/release/boost/graph/distributed/connected_components.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -409,7 +409,6 @@
#ifdef PBGL_EXPLICIT_SYNCH
       synchronize(p);
#endif
- size_t lone_vertex_count = roots.size();

       // Lastly, remove roots with no adjacent vertices, this is
       // unnecessary but will speed up sparse graphs

Modified: branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp (original)
+++ branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -113,20 +113,10 @@
 boost::parallel::caching_property_map<PredecessorMap> c_pred(m_predecessor);
 boost::parallel::caching_property_map<DistanceMap> c_dist(m_distance);

- distance_type old_distance = get(c_dist, target(e, g));
-
 bool m_decreased = relax(e, g, m_weight, c_pred, c_dist,
 m_combine, m_compare);

- /* On x86 Linux with optimization, we sometimes get into a
- horrible case where m_decreased is true but the distance hasn't
- actually changed. This occurs when the comparison inside
- relax() occurs with the 80-bit precision of the x87 floating
- point unit, but the difference is lost when the resulting
- values are written back to lower-precision memory (e.g., a
- double). With the eager Dijkstra's implementation, this results
- in looping. */
- if (m_decreased && old_distance != get(c_dist, target(e, g))) {
+ if (m_decreased) {
 m_Q.update(target(e, g));
 m_vis.edge_relaxed(e, g);
 } else

Modified: branches/release/boost/graph/edge_connectivity.hpp
==============================================================================
--- branches/release/boost/graph/edge_connectivity.hpp (original)
+++ branches/release/boost/graph/edge_connectivity.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -132,7 +132,8 @@
     detail::neighbors(g, S.begin(), S.end(),
                       std::inserter(neighbor_S, neighbor_S.begin()));

- std::set_difference(vertices(g).first, vertices(g).second,
+ tie(vi, vi_end) = vertices(g);
+ std::set_difference(vi, vi_end,
                         neighbor_S.begin(), neighbor_S.end(),
                         std::back_inserter(non_neighbor_S));

@@ -153,7 +154,8 @@
       neighbor_S.insert(k);
       detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
       non_neighbor_S.clear();
- std::set_difference(vertices(g).first, vertices(g).second,
+ tie(vi, vi_end) = vertices(g);
+ std::set_difference(vi, vi_end,
                           neighbor_S.begin(), neighbor_S.end(),
                           std::back_inserter(non_neighbor_S));
     }

Modified: branches/release/boost/graph/graph_utility.hpp
==============================================================================
--- branches/release/boost/graph/graph_utility.hpp (original)
+++ branches/release/boost/graph/graph_utility.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -445,6 +445,27 @@
 add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
 };

+ template <typename Graph>
+ bool has_no_vertices(const Graph& g) {
+ typedef typename boost::graph_traits<Graph>::vertex_iterator vi;
+ std::pair<vi, vi> p = vertices(g);
+ return (p.first == p.second);
+ }
+
+ template <typename Graph>
+ bool has_no_edges(const Graph& g) {
+ typedef typename boost::graph_traits<Graph>::edge_iterator ei;
+ std::pair<ei, ei> p = edges(g);
+ return (p.first == p.second);
+ }
+
+ template <typename Graph>
+ bool has_no_out_edges(const typename boost::graph_traits<Graph>::vertex_descriptor& v, const Graph& g) {
+ typedef typename boost::graph_traits<Graph>::out_edge_iterator ei;
+ std::pair<ei, ei> p = out_edges(v, g);
+ return (p.first == p.second);
+ }
+
 } // namespace graph

} /* namespace boost */

Modified: branches/release/boost/graph/howard_cycle_ratio.hpp
==============================================================================
--- branches/release/boost/graph/howard_cycle_ratio.hpp (original)
+++ branches/release/boost/graph/howard_cycle_ratio.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -29,6 +29,7 @@
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/graph_utility.hpp>

namespace boost {
 namespace detail {
@@ -172,7 +173,7 @@
 }
 BGL_FORALL_VERTICES_T(vd1, m_g, TGraph)
 {
- if (boost::out_edges(vd1, m_g).first == boost::out_edges(vd1, m_g).second) throw bad_graph(m_vim[vd1]);
+ if (boost::graph::has_no_out_edges(vd1, m_g)) throw bad_graph(m_vim[vd1]);
 mcr_edge_t ed = *boost::out_edges(vd1, m_g).first;
 pi_edge_t pied = boost::add_edge(m_g2pi_g_vm[source(ed, m_g)], m_g2pi_g_vm[target(ed, m_g)], m_pi_g).first;
 boost::put(boost::edge_weight, m_pi_g, pied, m_ew1m[ed]);

Modified: branches/release/boost/graph/isomorphism.hpp
==============================================================================
--- branches/release/boost/graph/isomorphism.hpp (original)
+++ branches/release/boost/graph/isomorphism.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -439,13 +439,11 @@
 return false;
#endif

- for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first;
- e1 != edges(g1).second; ++e1) {
+ BGL_FORALL_EDGES_T(e1, g1, Graph1) {
 bool found_edge = false;
- for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first;
- e2 != edges(g2).second && !found_edge; ++e2) {
- if (source(*e2, g2) == get(iso_map, source(*e1, g1)) &&
- target(*e2, g2) == get(iso_map, target(*e1, g1))) {
+ BGL_FORALL_EDGES_T(e2, g2, Graph2) {
+ if (source(e2, g2) == get(iso_map, source(e1, g1)) &&
+ target(e2, g2) == get(iso_map, target(e1, g1))) {
 found_edge = true;
 }
 }

Modified: branches/release/boost/graph/iteration_macros.hpp
==============================================================================
--- branches/release/boost/graph/iteration_macros.hpp (original)
+++ branches/release/boost/graph/iteration_macros.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -10,9 +10,12 @@
#ifndef BOOST_GRAPH_ITERATION_MACROS_HPP
#define BOOST_GRAPH_ITERATION_MACROS_HPP

+#include <utility>
+
#define BGL_CAT(x,y) x ## y
-#define BGL_FIRST(linenum) BGL_CAT(bgl_first_,linenum)
-#define BGL_LAST(linenum) BGL_CAT(bgl_last_,linenum)
+#define BGL_RANGE(linenum) BGL_CAT(bgl_range_,linenum)
+#define BGL_FIRST(linenum) (BGL_RANGE(linenum).first)
+#define BGL_LAST(linenum) (BGL_RANGE(linenum).second)

/*
 BGL_FORALL_VERTICES_T(v, g, graph_t) // This is on line 9
@@ -22,7 +25,7 @@
 bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
 bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
 for (typename boost::graph_traits<graph_t>::vertex_descriptor v;
- bgl_first_9 != bgl_last ? (v = *bgl_first_9, true) : false;
+ bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
 ++bgl_first_9)

 The purpose of having two for-loops is just to provide a place to
@@ -37,90 +40,98 @@
 Use the _T versions when the graph type is a template parameter or
 dependent on a template parameter. Otherwise use the non _T versions.

+ -----------------------
+ 6/9/09 THK
+
+ The above contains two calls to the vertices function. I modified these
+ macros to expand to
+
+ for (std::pair<typename boost::graph_traits<graph_t>::vertex_iterator,
+ typename boost::graph_traits<graph_t>::vertex_iterator> bgl_range_9 = vertices(g);
+ bgl_range_9.first != bgl_range_9.second;
+ bgl_range_9.first = bgl_range_9.second)
+ for (typename boost::graph_traits<graph_t>::vertex_descriptor v;
+ bgl_range_9.first != bgl_range_9.second ? (v = *bgl_range_9.first, true) : false;
+ ++bgl_range_9.first)
+
 */

#define BGL_FORALL_VERTICES_T(VNAME, GNAME, GraphType) \
-for (typename boost::graph_traits<GraphType>::vertex_iterator \
- BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \
+for (std::pair<typename boost::graph_traits<GraphType>::vertex_iterator, \
+ typename boost::graph_traits<GraphType>::vertex_iterator> BGL_RANGE(__LINE__) = vertices(GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
 for (typename boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true):false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_VERTICES(VNAME, GNAME, GraphType) \
-for (boost::graph_traits<GraphType>::vertex_iterator \
- BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \
+for (std::pair<boost::graph_traits<GraphType>::vertex_iterator, \
+ boost::graph_traits<GraphType>::vertex_iterator> BGL_RANGE(__LINE__) = vertices(GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
 for (boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true):false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_EDGES_T(ENAME, GNAME, GraphType) \
-for (typename boost::graph_traits<GraphType>::edge_iterator \
- BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \
+for (std::pair<typename boost::graph_traits<GraphType>::edge_iterator, \
+ typename boost::graph_traits<GraphType>::edge_iterator> BGL_RANGE(__LINE__) = edges(GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
 for (typename boost::graph_traits<GraphType>::edge_descriptor ENAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true):false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_EDGES(ENAME, GNAME, GraphType) \
-for (boost::graph_traits<GraphType>::edge_iterator \
- BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \
+for (std::pair<boost::graph_traits<GraphType>::edge_iterator, \
+ boost::graph_traits<GraphType>::edge_iterator> BGL_RANGE(__LINE__) = edges(GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
 for (boost::graph_traits<GraphType>::edge_descriptor ENAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true):false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_ADJ_T(UNAME, VNAME, GNAME, GraphType) \
-for (typename boost::graph_traits<GraphType>::adjacency_iterator \
- BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\
- BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \
+for (std::pair<typename boost::graph_traits<GraphType>::adjacency_iterator, \
+ typename boost::graph_traits<GraphType>::adjacency_iterator> BGL_RANGE(__LINE__) = adjacent_vertices(UNAME, GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (typename boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true) : false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_ADJ(UNAME, VNAME, GNAME, GraphType) \
-for (boost::graph_traits<GraphType>::adjacency_iterator \
- BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\
- BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \
+for (std::pair<boost::graph_traits<GraphType>::adjacency_iterator, \
+ boost::graph_traits<GraphType>::adjacency_iterator> BGL_RANGE(__LINE__) = adjacent_vertices(UNAME, GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (boost::graph_traits<GraphType>::vertex_descriptor VNAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (VNAME = *BGL_FIRST(__LINE__), true) : false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_OUTEDGES_T(UNAME, ENAME, GNAME, GraphType) \
-for (typename boost::graph_traits<GraphType>::out_edge_iterator \
- BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\
- BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \
+for (std::pair<typename boost::graph_traits<GraphType>::out_edge_iterator, \
+ typename boost::graph_traits<GraphType>::out_edge_iterator> BGL_RANGE(__LINE__) = out_edges(UNAME, GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (typename boost::graph_traits<GraphType>::edge_descriptor ENAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_OUTEDGES(UNAME, ENAME, GNAME, GraphType) \
-for (boost::graph_traits<GraphType>::out_edge_iterator \
- BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\
- BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \
+for (std::pair<boost::graph_traits<GraphType>::out_edge_iterator, \
+ boost::graph_traits<GraphType>::out_edge_iterator> BGL_RANGE(__LINE__) = out_edges(UNAME, GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (boost::graph_traits<GraphType>::edge_descriptor ENAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_INEDGES_T(UNAME, ENAME, GNAME, GraphType) \
-for (typename boost::graph_traits<GraphType>::in_edge_iterator \
- BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\
- BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \
+for (std::pair<typename boost::graph_traits<GraphType>::in_edge_iterator, \
+ typename boost::graph_traits<GraphType>::in_edge_iterator> BGL_RANGE(__LINE__) = in_edges(UNAME, GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (typename boost::graph_traits<GraphType>::edge_descriptor ENAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \
 ++BGL_FIRST(__LINE__))

#define BGL_FORALL_INEDGES(UNAME, ENAME, GNAME, GraphType) \
-for (boost::graph_traits<GraphType>::in_edge_iterator \
- BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\
- BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \
+for (std::pair<boost::graph_traits<GraphType>::in_edge_iterator, \
+ boost::graph_traits<GraphType>::in_edge_iterator> BGL_RANGE(__LINE__) = in_edges(UNAME, GNAME); \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__); BGL_FIRST(__LINE__) = BGL_LAST(__LINE__)) \
for (boost::graph_traits<GraphType>::edge_descriptor ENAME; \
 BGL_FIRST(__LINE__) != BGL_LAST(__LINE__) ? (ENAME = *BGL_FIRST(__LINE__), true) : false; \

Modified: branches/release/boost/graph/king_ordering.hpp
==============================================================================
--- branches/release/boost/graph/king_ordering.hpp (original)
+++ branches/release/boost/graph/king_ordering.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -13,6 +13,7 @@

#include <boost/config.hpp>
#include <boost/graph/detail/sparse_ordering.hpp>
+#include <boost/graph/graph_utility.hpp>

/*
 King Algorithm for matrix reordering
@@ -262,7 +263,7 @@
 king_ordering(const Graph& G, OutputIterator permutation,
 ColorMap color, DegreeMap degree, VertexIndexMap index_map)
 {
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
 return permutation;

 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
@@ -298,7 +299,7 @@
 king_ordering(const Graph& G, OutputIterator permutation,
 VertexIndexMap index_map)
 {
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
 return permutation;

 typedef out_degree_property_map<Graph> DegreeMap;

Modified: branches/release/boost/graph/metric_tsp_approx.hpp
==============================================================================
--- branches/release/boost/graph/metric_tsp_approx.hpp (original)
+++ branches/release/boost/graph/metric_tsp_approx.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -310,4 +310,4 @@

} //boost

-#endif // BOOST_GRAPH_METRIC_TSP_APPROX_HPP
\ No newline at end of file
+#endif // BOOST_GRAPH_METRIC_TSP_APPROX_HPP

Modified: branches/release/boost/graph/named_function_params.hpp
==============================================================================
--- branches/release/boost/graph/named_function_params.hpp (original)
+++ branches/release/boost/graph/named_function_params.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -49,6 +49,8 @@
 struct iterations_t { };
 struct diameter_range_t { };
 struct learning_constant_range_t { };
+ struct vertices_equivalent_t { };
+ struct edges_equivalent_t { };

#define BOOST_BGL_DECLARE_NAMED_PARAMS \
 BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \
@@ -94,7 +96,9 @@
 BOOST_BGL_ONE_PARAM_CREF(cooling, cooling) \
 BOOST_BGL_ONE_PARAM_CREF(iterations, iterations) \
 BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range) \
- BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range)
+ BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \
+ BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent) \
+ BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent)

 template <typename T, typename Tag, typename Base = no_property>
 struct bgl_named_params : public Base

Modified: branches/release/boost/graph/properties.hpp
==============================================================================
--- branches/release/boost/graph/properties.hpp (original)
+++ branches/release/boost/graph/properties.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -13,6 +13,7 @@
#include <boost/config.hpp>
#include <cassert>
#include <boost/pending/property.hpp>
+#include <boost/detail/workaround.hpp>

// Include the property map library and extensions in the BGL.
#include <boost/property_map/property_map.hpp>
@@ -357,6 +358,13 @@
# define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
#endif

+#if BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x590)) && !defined (BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
+// This compiler cannot define a partial specialization based on a
+// pointer-to-member type, as seen in boost/graph/subgraph.hpp line 985 (as of
+// trunk r53912)
+# define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+#endif
+
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
template<typename Graph, typename Descriptor, typename Bundle, typename T>
struct bundle_property_map

Modified: branches/release/boost/graph/push_relabel_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/push_relabel_max_flow.hpp (original)
+++ branches/release/boost/graph/push_relabel_max_flow.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -121,7 +121,7 @@
 : g(g_), n(num_vertices(g_)), capacity(cap), src(src_), sink(sink_),
 index(idx),
 excess_flow(num_vertices(g_)),
- current(num_vertices(g_), out_edges(*vertices(g_).first, g_).second),
+ current(num_vertices(g_), out_edges(*vertices(g_).first, g_)),
 distance(num_vertices(g_)),
 color(num_vertices(g_)),
 reverse_edge(rev),
@@ -149,7 +149,7 @@
 for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
 vertex_descriptor u = *u_iter;
 excess_flow[u] = 0;
- current[u] = out_edges(u, g).first;
+ current[u] = out_edges(u, g);
 }

 bool overflow_detected = false;
@@ -240,7 +240,7 @@
 && is_residual_edge(reverse_edge[a])) {
 distance[v] = d_v;
 color[v] = ColorTraits::gray();
- current[v] = out_edges(v, g).first;
+ current[v] = out_edges(v, g);
 max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(d_v, max_distance);

 if (excess_flow[v] > 0)
@@ -262,8 +262,7 @@
 assert(excess_flow[u] > 0);
 while (1) {
 out_edge_iterator ai, ai_end;
- for (ai = current[u], ai_end = out_edges(u, g).second;
- ai != ai_end; ++ai) {
+ for (tie(ai, ai_end) = current[u]; ai != ai_end; ++ai) {
 edge_descriptor a = *ai;
 if (is_residual_edge(a)) {
 vertex_descriptor v = target(a, g);
@@ -291,7 +290,7 @@
 if (distance[u] == n)
 break;
 } else { // i is no longer active
- current[u] = ai;
+ current[u].first = ai;
 add_to_inactive_list(u, layer);
 break;
 }
@@ -350,7 +349,7 @@
 ++min_distance;
 if (min_distance < n) {
 distance[u] = min_distance; // this is the main action
- current[u] = min_edge_iter;
+ current[u].first = min_edge_iter;
 max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(min_distance, max_distance);
 }
 return min_distance;
@@ -444,7 +443,7 @@
 u = *u_iter;
 color[u] = ColorTraits::white();
 parent[u] = u;
- current[u] = out_edges(u, g).first;
+ current[u] = out_edges(u, g);
 }
 // eliminate flow cycles and topologically order the vertices
 for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
@@ -455,8 +454,8 @@
 r = u;
 color[r] = ColorTraits::gray();
 while (1) {
- for (; current[u] != out_edges(u, g).second; ++current[u]) {
- edge_descriptor a = *current[u];
+ for (; current[u].first != current[u].second; ++current[u].first) {
+ edge_descriptor a = *current[u].first;
 if (capacity[a] == 0 && is_residual_edge(a)) {
 vertex_descriptor v = target(a, g);
 if (color[v] == ColorTraits::white()) {
@@ -469,16 +468,16 @@
 FlowValue delta = residual_capacity[a];
 while (1) {
 BOOST_USING_STD_MIN();
- delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[*current[v]]);
+ delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[*current[v].first]);
 if (v == u)
 break;
 else
- v = target(*current[v], g);
+ v = target(*current[v].first, g);
 }
 // remove delta flow units
 v = u;
 while (1) {
- a = *current[v];
+ a = *current[v].first;
 residual_capacity[a] -= delta;
 residual_capacity[reverse_edge[a]] += delta;
 v = target(a, g);
@@ -488,25 +487,25 @@

 // back-out of DFS to the first saturated edge
 restart = u;
- for (v = target(*current[u], g); v != u; v = target(a, g)){
- a = *current[v];
+ for (v = target(*current[u].first, g); v != u; v = target(a, g)){
+ a = *current[v].first;
 if (color[v] == ColorTraits::white()
 || is_saturated(a)) {
- color[target(*current[v], g)] = ColorTraits::white();
+ color[target(*current[v].first, g)] = ColorTraits::white();
 if (color[v] != ColorTraits::white())
 restart = v;
 }
 }
 if (restart != u) {
 u = restart;
- ++current[u];
+ ++current[u].first;
 break;
 }
 } // else if (color[v] == ColorTraits::gray())
 } // if (capacity[a] == 0 ...
 } // for out_edges(u, g) (though "u" changes during loop)

- if (current[u] == out_edges(u, g).second) {
+ if ( current[u].first == current[u].second ) {
 // scan of i is complete
 color[u] = ColorTraits::black();
 if (u != src) {
@@ -521,7 +520,7 @@
 }
 if (u != r) {
 u = parent[u];
- ++current[u];
+ ++current[u].first;
 } else
 break;
 }
@@ -533,8 +532,8 @@
 // note that the sink is not on the stack
 if (! bos_null) {
 for (u = tos; u != bos; u = topo_next[u]) {
- ai = out_edges(u, g).first;
- while (excess_flow[u] > 0 && ai != out_edges(u, g).second) {
+ tie(ai, a_end) = out_edges(u, g);
+ while (excess_flow[u] > 0 && ai != a_end) {
 if (capacity[*ai] == 0 && is_residual_edge(*ai))
 push_flow(*ai);
 ++ai;
@@ -632,7 +631,7 @@

 // will need to use random_access_property_map with these
 std::vector< FlowValue > excess_flow;
- std::vector< out_edge_iterator > current;
+ std::vector< std::pair<out_edge_iterator, out_edge_iterator> > current;
 std::vector< distance_size_type > distance;
 std::vector< default_color_type > color;

Modified: branches/release/boost/graph/relax.hpp
==============================================================================
--- branches/release/boost/graph/relax.hpp (original)
+++ branches/release/boost/graph/relax.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -48,14 +48,17 @@
       D d_u = get(d, u), d_v = get(d, v);
       W w_e = get(w, e);

+ // The redundant gets in the return statements are to ensure that extra
+ // floating-point precision in x87 registers does not lead to relax()
+ // returning true when the distance did not actually change.
       if ( compare(combine(d_u, w_e), d_v) ) {
         put(d, v, combine(d_u, w_e));
         put(p, v, u);
- return true;
+ return compare(get(d, v), d_v);
       } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
         put(d, u, combine(d_v, w_e));
         put(p, u, v);
- return true;
+ return compare(get(d, u), d_u);
       } else
         return false;
     }

Modified: branches/release/boost/graph/rmat_graph_generator.hpp
==============================================================================
--- branches/release/boost/graph/rmat_graph_generator.hpp (original)
+++ branches/release/boost/graph/rmat_graph_generator.hpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -17,9 +17,11 @@
#include <map>
#include <boost/shared_ptr.hpp>
#include <boost/random/uniform_int.hpp>
+#include <boost/random/uniform_01.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/type_traits/is_base_and_derived.hpp>
#include <boost/type_traits/is_same.hpp>
+#include <boost/test/floating_point_comparison.hpp>

using boost::shared_ptr;
using boost::uniform_01;
@@ -103,7 +105,10 @@

 double S = a + b + c + d;

- a /= S; b /= S; c /= S; d /= S;
+ a /= S; b /= S; c /= S;
+ // d /= S;
+ // Ensure all values add up to 1, regardless of floating point errors
+ d = 1. - a - b - c;
 }

 return std::make_pair(u, v);
@@ -150,7 +155,7 @@
 {
 this->gen.reset(new uniform_01<RandomGenerator>(gen));

- assert(a + b + c + d == 1);
+ assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

 if (permute_vertices)
 generate_permutation_vector(gen, vertexPermutation, n);
@@ -225,9 +230,9 @@
 bool operator() (const std::pair<T,T>& x, const std::pair<T,T>& y)
 {
 if (x.first == y.first)
- return x.second >= y.second;
+ return x.second > y.second;
 else
- return x.first >= y.first;
+ return x.first > y.first;
 }
 };

@@ -260,7 +265,7 @@
 values(sort_pair<vertices_size_type>()), done(false)

 {
- assert(a + b + c + d == 1);
+ assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

 this->gen.reset(new uniform_01<RandomGenerator>(gen));

@@ -271,7 +276,7 @@
 // TODO: "Clip and flip" if undirected graph
 int SCALE = int_log2(n);

- for (int i = 0; i < m; ++i) {
+ for (edges_size_type i = 0; i < m; ++i) {

 vertices_size_type u, v;
 tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
@@ -361,7 +366,7 @@
 : gen(), done(false)

 {
- assert(a + b + c + d == 1);
+ assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

 this->gen.reset(new uniform_01<RandomGenerator>(gen));

@@ -474,7 +479,7 @@
 values(sort_pair<vertices_size_type>()), done(false)

 {
- assert(a + b + c + d == 1);
+ assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

 this->gen.reset(new uniform_01<RandomGenerator>(gen));

Modified: branches/release/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- branches/release/libs/graph/doc/compressed_sparse_row.html (original)
+++ branches/release/libs/graph/doc/compressed_sparse_row.html 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -115,14 +115,27 @@
 <a href="#default-const">compressed_sparse_row_graph</a>();

 // Unsorted edge list constructors (new interface only)
- template<typename MultiPassInputIterator>
+ template<typename InputIterator>
 <a href="#edge-const">compressed_sparse_row_graph</a>(edges_are_unsorted_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty());
+
+ template<typename InputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty());
+
+ template<typename MultiPassInputIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
 vertices_size_type numverts,
 const GraphProperty& prop = GraphProperty());

 template<typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
 EdgePropertyIterator ep_iter,
 vertices_size_type numverts,
@@ -264,16 +277,23 @@
void set_property(const compressed_sparse_row_graph& g, GraphPropertyTag,
 const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);

-// Incremental construction functions (old interface only)
+// Incremental construction functions
+(old interface only)
template<typename Graph>
vertex_descriptor add_vertex(compressed_sparse_row_graph& g);

+(old interface only)
template<typename Graph>
vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph& g);

+(old interface only)
template<typename Graph>
edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);

+(new interface only)
+template<typename InputIterator, typename Graph>
+void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
+
} // end namespace boost
 </pre>

@@ -401,8 +421,67 @@
 <hr></hr>

 <pre><a name="edge-const"></a>
- template<typename MultiPassInputIterator>
+ template<typename InputIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty());
+ </pre>
+
+ 
+ Constructs a graph with <code>numverts</code> vertices whose
+ edges are specified by the iterator range <code>[edge_begin,
+ edge_end)</code>. The <tt>InputIterator</tt> must be a model of
+ <a
+ href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
+ whose <code>value_type</code> is an <code>std::pair</code> of
+ integer values. These integer values are the source and target
+ vertices for the edges, and must fall within the range <code>[0,
+ numverts)</code>. The edges in <code>[edge_begin,
+ edge_end)</code> do not need to be sorted. This constructor uses extra
+ memory to save the edge information before adding it to the graph,
+ avoiding the requirement for the iterator to have multi-pass capability.
+ (This function is only provided by the new interface.)
+ 
+
+ 
+ The value <code>prop</code> will be used to initialize the graph
+ property.
+ 
+
+ <hr></hr>
+
+ <pre><a name="edge-prop-const"></a>
+ template<typename InputIterator, typename EdgePropertyIterator>
 compressed_sparse_row_graph(edges_are_unsorted_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty());
+ </pre>
+ 
+ This constructor constructs a graph with <code>numverts</code>
+ vertices and the edges provided in the iterator range
+ <code>[edge_begin, edge_end)</code>. Its semantics are identical
+ to the edge range constructor, except
+ that edge properties are also initialized. The type
+ <tt>EdgePropertyIterator</tt> must be a model of the <a
+ href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
+ concept whose <tt>value_type</tt> is convertible to
+ <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
+ m)</tt> will be used to initialize the properties on the edges
+ of the graph, where <tt>m</tt> is distance from
+ <tt>edge_begin</tt> to <tt>edge_end</tt>. This constructor uses extra
+ memory to save the edge information before adding it to the graph,
+ avoiding the requirement for the iterator to have multi-pass capability.
+ (This function is only provided by the new interface.)
+ 
+
+ <hr></hr>
+
+ <pre><a name="edge-const"></a>
+ template<typename MultiPassInputIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
 vertices_size_type numverts,
 const GraphProperty& prop = GraphProperty());
@@ -418,7 +497,8 @@
 integer values. These integer values are the source and target
 vertices for the edges, and must fall within the range <code>[0,
 numverts)</code>. The edges in <code>[edge_begin,
- edge_end)</code> do not need to be sorted.
+ edge_end)</code> do not need to be sorted. Multiple passes will be made
+ over the edge range.
 (This function is only provided by the new interface.)
 

@@ -431,7 +511,7 @@

 <pre><a name="edge-prop-const"></a>
 template<typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
 EdgePropertyIterator ep_iter,
 vertices_size_type numverts,
@@ -449,7 +529,8 @@
 <tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
 m)</tt> will be used to initialize the properties on the edges
 of the graph, where <tt>m</tt> is distance from
- <tt>edge_begin</tt> to <tt>edge_end</tt>.
+ <tt>edge_begin</tt> to <tt>edge_end</tt>. Multiple passes will be made
+ over the edge and property ranges.
 (This function is only provided by the new interface.)
 

@@ -834,6 +915,23 @@
 

 <hr></hr>
+
+ <pre><a name="add_edges"></a>
+template<typename InputIterator>
+edge_descriptor add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
+ </pre>
+
+ 
+ Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+ The <tt>InputIterator</tt> must be a model of <a
+ href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
+ whose <code>value_type</code> is an <code>std::pair</code> of integer
+ values. These integer values are the source and target vertices of the
+ new edges. The edges do not need to be sorted.
+ (This function is only provided by the new interface.)
+ 
+
+ <hr></hr>
 <a name="example"></a><h2>Example</h2>

 [<a

Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 (original)
+++ branches/release/libs/graph/test/Jamfile.v2 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -41,7 +41,7 @@
 [ run bfs.cpp ../../test/build//boost_test_exec_monitor ]
 [ compile bfs_cc.cpp ]
 [ run bellman-test.cpp ]
- [ run betweenness_centrality_test.cpp ]
+ [ run betweenness_centrality_test.cpp : 100 ]
 [ run bidir_remove_edge.cpp ]
 [ run csr_graph_test.cpp : : : : : <variant>release ]
 [ run dag_longest_paths.cpp ]

Modified: branches/release/libs/graph/test/betweenness_centrality_test.cpp
==============================================================================
--- branches/release/libs/graph/test/betweenness_centrality_test.cpp (original)
+++ branches/release/libs/graph/test/betweenness_centrality_test.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -16,6 +16,7 @@
#include <boost/test/minimal.hpp>
#include <boost/random/uniform_01.hpp>
#include <boost/random/linear_congruential.hpp>
+#include <boost/lexical_cast.hpp>

using namespace boost;

@@ -440,8 +441,10 @@
 }
}

-int test_main(int, char*[])
+int test_main(int argc, char* argv[])
{
+ int random_test_num_vertices = 300;
+ if (argc >= 2) random_test_num_vertices = boost::lexical_cast<int>(argv[1]);
 typedef adjacency_list<listS, listS, undirectedS,
 property<vertex_index_t, int>, EdgeProperties>
 Graph;
@@ -512,7 +515,7 @@

 run_wheel_test((Graph*)0, 15);

- random_unweighted_test((Graph*)0, 300);
+ random_unweighted_test((Graph*)0, random_test_num_vertices);

 return 0;
}

Modified: branches/release/libs/graph/test/csr_graph_test.cpp
==============================================================================
--- branches/release/libs/graph/test/csr_graph_test.cpp (original)
+++ branches/release/libs/graph/test/csr_graph_test.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -84,6 +84,7 @@
 std::sort(edges1.begin(), edges1.end());
 std::sort(edges2.begin(), edges2.end());
 if (edges1 != edges2) {
+ std::cerr << "For vertex " << v1 << std::endl;
 std::cerr << "edges1:";
 for (size_t i = 0; i < edges1.size(); ++i) std::cerr << " " << edges1[i];
 std::cerr << std::endl;
@@ -481,7 +482,21 @@
 std::cout << "Testing CSR graph built from unsorted edges" << std::endl;
 std::pair<int, int> unsorted_edges[] = {std::make_pair(5, 0), std::make_pair(3, 2), std::make_pair(4, 1), std::make_pair(4, 0), std::make_pair(0, 2), std::make_pair(5, 2)};
 CSRGraphT g(boost::edges_are_unsorted, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+ CSRGraphT g2(boost::edges_are_unsorted_multi_pass, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
 graph_test(g);
+ graph_test(g2);
+ assert_graphs_equal(g, boost::identity_property_map(),
+ g2, boost::identity_property_map(),
+ boost::identity_property_map());
+ std::cout << "Testing CSR graph built using add_edges" << std::endl;
+ // Test building a graph using add_edges on unsorted lists
+ CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges, 6); // Empty range
+ add_edges(unsorted_edges, unsorted_edges + 3, g3);
+ add_edges(unsorted_edges + 3, unsorted_edges + 6, g3);
+ graph_test(g3);
+ assert_graphs_equal(g, boost::identity_property_map(),
+ g3, boost::identity_property_map(),
+ boost::identity_property_map());
 }
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE

Modified: branches/release/libs/graph/test/gursoy_atun_layout_test.cpp
==============================================================================
--- branches/release/libs/graph/test/gursoy_atun_layout_test.cpp (original)
+++ branches/release/libs/graph/test/gursoy_atun_layout_test.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -59,7 +59,7 @@

 // Make grid, like Gursoy and Atun used
 std::map<int, std::map<int, vertex_descriptor> > verts;
- const int grid_size = 30;
+ const int grid_size = 20;
 boost::minstd_rand edge_weight_gen;
 boost::uniform_01<boost::minstd_rand> random_edge_weight(edge_weight_gen);
 for (int i = 0; i < grid_size; ++i)
@@ -94,7 +94,7 @@
 plod_iterator<minstd_rand, graph_type>(),
 n);
#else
- int n = 100000;
+ int n = 1000;
 int k = 6;
 double p = 0.001;
 minstd_rand gen;
@@ -120,19 +120,23 @@

 boost::gursoy_atun_layout(graph, space, position);

+#if 0
 std::cerr << "--------Unweighted layout--------\n";
 boost::write_graphviz(std::cout, graph,
 position_writer<Position, vertex_descriptor>(position),
 boost::default_writer(),
 graph_writer());
+#endif

 boost::gursoy_atun_layout(graph, space, position,
 weight_map(get(boost::edge_weight, graph)));

+#if 0
 std::cerr << "--------Weighted layout--------\n";
 boost::write_graphviz(std::cout, graph,
 position_writer<Position, vertex_descriptor>(position),
 boost::default_writer(),
 graph_writer());
+#endif
 return 0;
}

Copied: branches/release/libs/graph_parallel/example/Jamfile.v2 (from r53934, /trunk/libs/graph_parallel/example/Jamfile.v2)
==============================================================================
--- /trunk/libs/graph_parallel/example/Jamfile.v2 (original)
+++ branches/release/libs/graph_parallel/example/Jamfile.v2 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -1,3 +1,9 @@
+# Copyright 2009 Vladimir Prus.
+#
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+

project : requirements <library>../build//boost_graph_parallel
<library>../../system/build//boost_system

Modified: branches/release/libs/graph_parallel/example/breadth_first_search.cpp
==============================================================================
--- branches/release/libs/graph_parallel/example/breadth_first_search.cpp (original)
+++ branches/release/libs/graph_parallel/example/breadth_first_search.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -83,7 +83,7 @@
     outfile = argv[2];
   else {
     outfile = filename;
- int i = outfile.rfind('.');
+ size_t i = outfile.rfind('.');
     if (i != std::string::npos)
       outfile.erase(outfile.begin() + i, outfile.end());
     outfile += "-bfs.dot";

Modified: branches/release/libs/graph_parallel/example/dijkstra_shortest_paths.cpp
==============================================================================
--- branches/release/libs/graph_parallel/example/dijkstra_shortest_paths.cpp (original)
+++ branches/release/libs/graph_parallel/example/dijkstra_shortest_paths.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -78,7 +78,7 @@
   if (argc > 2)
     outfile = argv[2];
   else {
- int i = outfile.rfind('.');
+ size_t i = outfile.rfind('.');
     if (i != std::string::npos)
       outfile.erase(outfile.begin() + i, outfile.end());
     outfile += "-dijkstra.dot";

Copied: branches/release/libs/graph_parallel/test/Jamfile.v2 (from r53934, /trunk/libs/graph_parallel/test/Jamfile.v2)
==============================================================================
--- /trunk/libs/graph_parallel/test/Jamfile.v2 (original)
+++ branches/release/libs/graph_parallel/test/Jamfile.v2 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -17,30 +17,30 @@
{
test-suite graph_parallel
 :
- [ mpi-test distributed_property_map_test ]
- [ mpi-test distributed_queue_test ]
+ [ mpi-test distributed_property_map_test : : : 2 ]
+ [ mpi-test distributed_queue_test : : : 2 ]
 [ mpi-test process_group_serialization : : : 2 ]
- [ mpi-test adjlist_build_test ]
- [ mpi-test adjlist_redist_test ]
+ [ mpi-test adjlist_build_test : : : 2 ]
+ [ mpi-test adjlist_redist_test : : : 2 ]
 [ mpi-test adjlist_remove_test : : : 2 ]
- [ mpi-test distributed_adjacency_list_test ]
- [ mpi-test distributed_connected_components_test ]
- [ mpi-test distributed_page_rank_test ]
- [ mpi-test distributed_csr_test ]
- [ mpi-test distributed_dfs_test ]
- [ mpi-test distributed_graph_coloring_test ]
- [ mpi-test distributed_mst_test ]
- [ mpi-test distributed_strong_components_test ]
- [ mpi-test hohberg_biconnected_components_test ]
- [ mpi-test mesh_generator_test : : <testing.arg>"1000 1000 1 0" ]
+ [ mpi-test distributed_adjacency_list_test : : : 2 ]
+ [ mpi-test distributed_connected_components_test : : : 2 ]
+ [ mpi-test distributed_page_rank_test : : : 2 ]
+ [ mpi-test distributed_csr_test : : : 2 ]
+ [ mpi-test distributed_dfs_test : : : 2 ]
+ [ mpi-test distributed_graph_coloring_test : : : 2 ]
+ [ mpi-test distributed_mst_test : : : 2 ]
+ [ mpi-test distributed_strong_components_test : : : 2 ]
+ [ mpi-test hohberg_biconnected_components_test : : : 2 ]
+ [ mpi-test mesh_generator_test : : <testing.arg>"1000 1000 1 0" : 2 ]
 [ mpi-test named_vertices_seq : : : 1 ]
- [ mpi-test distributed_shortest_paths_test ]
+ [ mpi-test distributed_shortest_paths_test : : : 2 ]
 [ mpi-test distributed_csr_algorithm_test : : : 1 ]
- [ mpi-test distributed_betweenness_centrality_test ]
- [ mpi-test distributed_dimacs_reader ]
- [ mpi-test distributed_rmat_cc_ps ]
- [ mpi-test distributed_rmat_cc ]
- [ mpi-test distributed_rmat_pagerank ]
+ [ mpi-test distributed_betweenness_centrality_test : : : 2 ]
+ [ mpi-test distributed_dimacs_reader : : : 2 ]
+ [ mpi-test distributed_rmat_cc_ps : : : 2 ]
+ [ mpi-test distributed_rmat_cc : : : 2 ]
+ [ mpi-test distributed_rmat_pagerank : : : 2 ]
 ;
}

Modified: branches/release/libs/graph_parallel/test/distributed_adjacency_list_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_adjacency_list_test.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_adjacency_list_test.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -198,7 +198,7 @@
 in_degree(*v, g3);
 }

- int added_edges = 0;
+ graph_traits<Graph3>::vertices_size_type added_edges = 0;
 if (num_vertices(g3) >= 2) {
 graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first;
 graph_traits<Graph3>::vertex_descriptor u = *vi++;
@@ -239,7 +239,7 @@
 }

 synchronize(g3);
- assert(std::distance(edges(g3).first, edges(g3).second) == added_edges);
+ assert(std::distance(edges(g3).first, edges(g3).second) == (ptrdiff_t)added_edges);
 assert(num_edges(g3) == added_edges);

 // Verify the remote edges
@@ -250,7 +250,7 @@
 int prior_processor = (process_id(pg) + num_processes(pg) - 1)
 % num_processes(pg);
 const int n = 20;
- int vertices_in_prior = (n / num_processes(pg))
+ graph_traits<Graph3>::vertices_size_type vertices_in_prior = (n / num_processes(pg))
 + (n % num_processes(pg) > prior_processor? 1 : 0);
 if (in_degree(u, g3) != vertices_in_prior + 2) {
 std::cerr << "#" << process_id(pg) << ": " << in_degree(u, g3)

Modified: branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -139,8 +139,10 @@
 make_iterator_property_map(explore.begin(), get(vertex_index, g)),
 get(vertex_index, g));

+#if 0
 std::size_t correct_parents1[N] = {u, u, y, y, v, w};
 std::size_t correct_parents2[N] = {u, u, y, v, x, w};
+#endif

 for (std::size_t i = 0; i < N; ++i) {
 vertex_descriptor v = vertex(i, g);

Modified: branches/release/libs/graph_parallel/test/distributed_property_map_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_property_map_test.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_property_map_test.cpp 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -182,7 +182,7 @@

 bool my_start_value = process_id(pg) % 2;
 int next_processor = (process_id(pg) + 1) % num_processes(pg);
- bool next_start_value = !my_start_value;
+ bool next_start_value = ((process_id(pg) + 1) % num_processes(pg)) % 2;

 // Initial color map: even-numbered processes are false,
 // odd-numbered processes are true
@@ -298,7 +298,7 @@
 // check next processor's strings
 for (int i = 0; i < n; ++i) {
 remote_key k(next_processor, i);
- BOOST_CHECK(get(strings, k) == std::string());
+ BOOST_CHECK(get(strings, k) == (num_processes(pg) == 1 ? my_start_string : std::string()));
 }

 if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing...";

Modified: branches/release/status/explicit-failures-markup.xml
==============================================================================
--- branches/release/status/explicit-failures-markup.xml (original)
+++ branches/release/status/explicit-failures-markup.xml 2009-06-18 15:34:25 EDT (Thu, 18 Jun 2009)
@@ -1790,10 +1790,18 @@
 
 <library name="graph">
 <mark-unusable>
- <toolset name="borland-5.6*"/>
- <toolset name="borland-5.8*"/>
+ <toolset name="borland-5.*"/>
+ <toolset name="borland-6.*"/>
 <toolset name="msvc-6.5*"/>
 <toolset name="sunpro-5_3-sunos"/>
+ 
+ <toolset name="gcc-open64"/>
+ <toolset name="pathscale-3.1"/>
+ 
+ <toolset name="vacpp"/>
 </mark-unusable>
 <mark-expected-failures>
 <test name="adj_matrix_cc"/>

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk