|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r56881 - in branches/release: . boost/algorithm/string boost/archive boost/config boost/filesystem boost/fusion boost/graph boost/graph/detail boost/graph/distributed boost/iostreams boost/math boost/numeric/ublas boost/program_options boost/property_map boost/property_tree boost/python boost/regex boost/serialization boost/signals boost/signals2 boost/spirit boost/spirit/home boost/spirit/home/qi/nonterminal boost/spirit/home/qi/numeric/detail boost/spirit/home/support boost/spirit/repository/home/qi/nonterminal boost/system boost/tr1 boost/type_traits boost/utility boost/wave libs libs/config libs/filesystem libs/fusion libs/graph/doc libs/graph/doc/figs libs/graph/example libs/graph/test libs/graph_parallel libs/graph_parallel/test libs/iostreams libs/math libs/mpl/doc/refmanual libs/mpl/doc/src/refmanual libs/numeric/ublas libs/program_options libs/property_tree libs/python libs/regex libs/serialization libs/signals libs/signals2 libs/spirit libs/spirit/classic/example libs/spirit/example libs/spirit/phoenix libs/spirit/test libs/spirit/test/qi libs/system libs/timer libs/tr1 libs/type_traits libs/utility libs/wave status tools/boostbook tools/build/v2 tools/quickbook tools/regression tools/release tools/wave
From: jewillco_at_[hidden]
Date: 2009-10-15 16:40:50
Author: jewillco
Date: 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
New Revision: 56881
URL: http://svn.boost.org/trac/boost/changeset/56881
Log:
Merged in changes from trunk for Boost.Graph and Boost.PropertyMap. Includes
r56013, r56014, r56015, r56016, r56017, r56089, r56097, r56116, r56117, r56126,
r56127, r56128, r56140, r56147, r56300, r56301, r56339, r56360, r56454, r56473,
r56563, r56651, r56654, r56658, r56682, r56732, r56796, r56855, r56856, r56868,
r55667, r56860, r55473, r55507, r55528, r55749, r56147, r55723, r56109, r56859,
and r55780.
Added:
branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp
- copied, changed from r56116, /trunk/boost/graph/detail/compressed_sparse_row_struct.hpp
branches/release/boost/graph/detail/histogram_sort.hpp
- copied unchanged from r56116, /trunk/boost/graph/detail/histogram_sort.hpp
branches/release/boost/graph/grid_graph.hpp
- copied, changed from r55473, /trunk/boost/graph/grid_graph.hpp
branches/release/libs/graph/doc/figs/grid_graph_indexed.png
- copied unchanged from r55473, /trunk/libs/graph/doc/figs/grid_graph_indexed.png
branches/release/libs/graph/doc/figs/grid_graph_indexed.svg
- copied, changed from r55473, /trunk/libs/graph/doc/figs/grid_graph_indexed.svg
branches/release/libs/graph/doc/figs/grid_graph_unindexed.svg
- copied, changed from r55473, /trunk/libs/graph/doc/figs/grid_graph_unindexed.svg
branches/release/libs/graph/doc/figs/grid_graph_unwrapped.png
- copied unchanged from r55473, /trunk/libs/graph/doc/figs/grid_graph_unwrapped.png
branches/release/libs/graph/doc/figs/grid_graph_wrapped.png
- copied unchanged from r55473, /trunk/libs/graph/doc/figs/grid_graph_wrapped.png
branches/release/libs/graph/doc/grid_graph.html
- copied, changed from r55473, /trunk/libs/graph/doc/grid_graph.html
branches/release/libs/graph/doc/grid_graph_export_svg.sh
- copied, changed from r55723, /trunk/libs/graph/doc/grid_graph_export_svg.sh
branches/release/libs/graph/example/grid_graph_example.cpp
- copied unchanged from r55473, /trunk/libs/graph/example/grid_graph_example.cpp
branches/release/libs/graph/test/grid_graph_cc.cpp
- copied unchanged from r55473, /trunk/libs/graph/test/grid_graph_cc.cpp
branches/release/libs/graph/test/grid_graph_test.cpp
- copied, changed from r55473, /trunk/libs/graph/test/grid_graph_test.cpp
branches/release/libs/graph/test/incremental_components_test.cpp
- copied, changed from r56017, /trunk/libs/graph/test/incremental_components_test.cpp
branches/release/libs/graph_parallel/index.html (props changed)
- copied unchanged from r56360, /trunk/libs/graph_parallel/index.html
Properties modified:
branches/release/ (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/config/ (props changed)
branches/release/boost/filesystem/ (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/graph/ (props changed)
branches/release/boost/iostreams/ (props changed)
branches/release/boost/math/ (props changed)
branches/release/boost/numeric/ublas/ (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/property_tree/ (props changed)
branches/release/boost/python/ (props changed)
branches/release/boost/regex/ (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/signals/ (props changed)
branches/release/boost/signals2/ (props changed)
branches/release/boost/spirit/ (props changed)
branches/release/boost/spirit/home/ (props changed)
branches/release/boost/spirit/home/qi/nonterminal/rule.hpp (props changed)
branches/release/boost/spirit/home/qi/numeric/detail/numeric_utils.hpp (props changed)
branches/release/boost/spirit/home/support/attributes.hpp (props changed)
branches/release/boost/spirit/repository/home/qi/nonterminal/subrule.hpp (props changed)
branches/release/boost/system/ (props changed)
branches/release/boost/tr1/ (props changed)
branches/release/boost/type_traits/ (props changed)
branches/release/boost/utility/value_init.hpp (props changed)
branches/release/boost/wave/ (props changed)
branches/release/index.html (props changed)
branches/release/libs/config/ (props changed)
branches/release/libs/filesystem/ (props changed)
branches/release/libs/fusion/ (props changed)
branches/release/libs/graph_parallel/ (props changed)
branches/release/libs/iostreams/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/maintainers.txt (props changed)
branches/release/libs/math/ (props changed)
branches/release/libs/mpl/doc/refmanual/broken-compiler-workarounds.html (props changed)
branches/release/libs/mpl/doc/refmanual/categorized-index-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/cfg-no-preprocessed-headers.html (props changed)
branches/release/libs/mpl/doc/refmanual/composition-and-argument-binding.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-miscellaneous.html (props changed)
branches/release/libs/mpl/doc/refmanual/extensible-associative-sequence.html (props changed)
branches/release/libs/mpl/doc/refmanual/inserter-class.html (props changed)
branches/release/libs/mpl/doc/refmanual/tag-dispatched-metafunction.html (props changed)
branches/release/libs/mpl/doc/refmanual/trivial-metafunctions-summary.html (props changed)
branches/release/libs/mpl/doc/src/refmanual/Iterators-Iterator.rst (props changed)
branches/release/libs/numeric/ublas/ (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/property_tree/ (props changed)
branches/release/libs/python/ (props changed)
branches/release/libs/regex/ (props changed)
branches/release/libs/serialization/ (props changed)
branches/release/libs/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/spirit/ (props changed)
branches/release/libs/spirit/classic/example/ (props changed)
branches/release/libs/spirit/example/ (props changed)
branches/release/libs/spirit/phoenix/ (props changed)
branches/release/libs/spirit/test/ (props changed)
branches/release/libs/spirit/test/qi/optional.cpp (props changed)
branches/release/libs/system/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/tr1/ (props changed)
branches/release/libs/type_traits/ (props changed)
branches/release/libs/utility/swap.html (props changed)
branches/release/libs/utility/value_init.htm (props changed)
branches/release/libs/utility/value_init_test.cpp (props changed)
branches/release/libs/wave/ (props changed)
branches/release/status/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/quickbook/ (props changed)
branches/release/tools/regression/ (props changed)
branches/release/tools/release/ (props changed)
branches/release/tools/wave/ (props changed)
Text files modified:
branches/release/boost/graph/compressed_sparse_row_graph.hpp | 1438 ++++++++++++++++++---------------------
branches/release/boost/graph/cuthill_mckee_ordering.hpp | 4
branches/release/boost/graph/depth_first_search.hpp | 1
branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp | 266 +++++++
branches/release/boost/graph/detail/incremental_components.hpp | 160 +---
branches/release/boost/graph/detail/indexed_properties.hpp | 19
branches/release/boost/graph/distributed/betweenness_centrality.hpp | 2
branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp | 125 ++-
branches/release/boost/graph/erdos_renyi_generator.hpp | 4
branches/release/boost/graph/fruchterman_reingold.hpp | 68
branches/release/boost/graph/grid_graph.hpp | 333 ++++++--
branches/release/boost/graph/incremental_components.hpp | 184 +++-
branches/release/boost/graph/properties.hpp | 2
branches/release/boost/property_map/property_map.hpp | 16
branches/release/libs/graph/doc/BUILD_DOCS.sh | 1
branches/release/libs/graph/doc/Graph.html | 5
branches/release/libs/graph/doc/IncidenceGraph.html | 4
branches/release/libs/graph/doc/compressed_sparse_row.html | 49
branches/release/libs/graph/doc/grid_graph.html | 11
branches/release/libs/graph/doc/grid_graph_export_svg.sh | 9
branches/release/libs/graph/doc/incremental_components.html | 218 ++---
branches/release/libs/graph/doc/quick_tour.html | 7
branches/release/libs/graph/doc/table_of_contents.html | 3
branches/release/libs/graph/example/Jamfile.v2 | 1
branches/release/libs/graph/example/incremental-components-eg.cpp | 92 +-
branches/release/libs/graph/example/incremental_components.cpp | 99 +-
branches/release/libs/graph/example/incremental_components.expected | 2
branches/release/libs/graph/example/quick_tour.cpp | 19
branches/release/libs/graph/test/Jamfile.v2 | 3
branches/release/libs/graph/test/csr_graph_test.cpp | 121 +-
branches/release/libs/graph/test/grid_graph_test.cpp | 2
branches/release/libs/graph/test/incremental_components_test.cpp | 4
branches/release/libs/graph/test/layout_test.cpp | 14
branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp | 2
34 files changed, 1829 insertions(+), 1459 deletions(-)
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-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -26,6 +26,8 @@
#include <boost/graph/properties.hpp>
#include <boost/graph/filtered_graph.hpp> // For keep_all
#include <boost/graph/detail/indexed_properties.hpp>
+#include <boost/graph/detail/compressed_sparse_row_struct.hpp>
+#include <boost/graph/iteration_macros.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/iterator/zip_iterator.hpp>
@@ -131,42 +133,21 @@
#define BOOST_CSR_GRAPH_TYPE \
compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, \
GraphProperty, Vertex, EdgeIndex>
-
-// Forward declaration of CSR edge descriptor type, needed to pass to
-// indexed_edge_properties.
-template<typename Vertex, typename EdgeIndex>
-class csr_edge_descriptor;
-
-namespace detail {
- 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());
- }
+#define BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS \
+ typename VertexProperty, typename EdgeProperty, \
+ typename GraphProperty, typename Vertex, typename EdgeIndex
+#define BOOST_DIR_CSR_GRAPH_TYPE \
+ compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, \
+ GraphProperty, Vertex, EdgeIndex>
+#define BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS \
+ typename VertexProperty, typename EdgeProperty, \
+ typename GraphProperty, typename Vertex, typename EdgeIndex
+#define BOOST_BIDIR_CSR_GRAPH_TYPE \
+ compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, \
+ GraphProperty, Vertex, EdgeIndex>
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+namespace detail {
template <typename T>
struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> {
typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type;
@@ -197,8 +178,8 @@
return t.template get<N>();
}
};
-#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
/** Compressed sparse row graph.
*
@@ -211,59 +192,39 @@
typename GraphProperty = no_property,
typename Vertex = std::size_t,
typename EdgeIndex = Vertex>
-class compressed_sparse_row_graph
- : public detail::indexed_vertex_properties<BOOST_CSR_GRAPH_TYPE, VertexProperty,
- Vertex>,
- public detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,
- csr_edge_descriptor<Vertex,
- EdgeIndex> >
+class compressed_sparse_row_graph; // Not defined
+template<typename VertexProperty,
+ typename EdgeProperty,
+ typename GraphProperty,
+ typename Vertex,
+ typename EdgeIndex>
+class compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
+ : public detail::indexed_vertex_properties<BOOST_DIR_CSR_GRAPH_TYPE,
+ VertexProperty, Vertex>
{
public:
typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
VertexProperty, Vertex>
inherited_vertex_properties;
- typedef detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,
- csr_edge_descriptor<Vertex, EdgeIndex> >
- inherited_edge_properties;
-
public:
// For Property Graph
typedef GraphProperty graph_property_type;
- protected:
- template<typename InputIterator>
- void
- maybe_reserve_edge_list_storage(InputIterator, InputIterator,
- std::input_iterator_tag)
- {
- // Do nothing: we have no idea how much storage to reserve.
- }
-
- template<typename InputIterator>
- void
- maybe_reserve_edge_list_storage(InputIterator first, InputIterator last,
- std::forward_iterator_tag)
- {
- using std::distance;
- typename std::iterator_traits<InputIterator>::difference_type n =
- distance(first, last);
- m_column.reserve(n);
- inherited_edge_properties::reserve(n);
- }
+ typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
public:
/* At this time, the compressed sparse row graph can only be used to
- * create a directed graph. In the future, bidirectional and
+ * create directed and bidirectional graphs. In the future,
* undirected CSR graphs will also be supported.
*/
- BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
+ // BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
// Concept requirements:
// For Graph
typedef Vertex vertex_descriptor;
- typedef csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
+ typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
typedef directed_tag directed_category;
typedef allow_parallel_edge_tag edge_parallel_category;
@@ -282,14 +243,14 @@
typedef EdgeIndex edges_size_type;
// For IncidenceGraph
- class out_edge_iterator;
+ typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
typedef EdgeIndex degree_size_type;
// For AdjacencyGraph
typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
// For EdgeListGraph
- class edge_iterator;
+ typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
// For BidirectionalGraph (not implemented)
typedef void in_edge_iterator;
@@ -297,110 +258,20 @@
// For internal use
typedef csr_graph_tag graph_tag;
+ typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
+ typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
+ typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
+
// Constructors
// Default constructor: an empty graph.
- compressed_sparse_row_graph()
- : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property()
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(0)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- {}
+ compressed_sparse_row_graph(): m_property() {}
// With numverts vertices
compressed_sparse_row_graph(vertices_size_type numverts)
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0)
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(numverts)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- {
- for (Vertex v = 0; v < numverts + 1; ++v)
- m_rowstart[v] = 0;
- }
+ : inherited_vertex_properties(numverts), m_forward(numverts) {}
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- // Rebuild graph from number of vertices and multi-pass unsorted list of
- // edges (filtered using edge_pred and mapped using global_to_local)
- template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
- void
- assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
- MultiPassInputIterator edge_end,
- vertices_size_type numlocalverts,
- const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred) {
- m_rowstart.clear();
- m_rowstart.resize(numlocalverts + 1, 0);
- // Put the degree of each vertex v into m_rowstart[v + 1]
- for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
- if (edge_pred(*i))
- ++m_rowstart[get(global_to_local, i->first) + 1];
-
- // Compute the partial sum of the degrees to get the actual values of
- // m_rowstart
- EdgeIndex start_of_this_row = 0;
- m_rowstart[0] = start_of_this_row;
- for (vertices_size_type i = 1; i <= numlocalverts; ++i) {
- start_of_this_row += m_rowstart[i];
- m_rowstart[i] = start_of_this_row;
- }
- m_column.resize(m_rowstart.back());
-
- // Histogram sort the edges by their source vertices, putting the targets
- // into m_column. The index current_insert_positions[v] contains the next
- // location to insert out edges for vertex v.
- std::vector<EdgeIndex>
- current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numlocalverts);
- for (; edge_begin != edge_end; ++edge_begin)
- if (edge_pred(*edge_begin))
- m_column[current_insert_positions[get(global_to_local, edge_begin->first)]++] = edge_begin->second;
- }
-
- // Rebuild graph from number of vertices and multi-pass unsorted list of
- // edges and their properties (filtered using edge_pred and mapped using
- // global_to_local)
- template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
- void
- assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
- MultiPassInputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numlocalverts,
- const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred) {
- m_rowstart.clear();
- m_rowstart.resize(numlocalverts + 1, 0);
- // Put the degree of each vertex v into m_rowstart[v + 1]
- for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
- if (edge_pred(*i))
- ++m_rowstart[get(global_to_local, i->first) + 1];
-
- // Compute the partial sum of the degrees to get the actual values of
- // m_rowstart
- EdgeIndex start_of_this_row = 0;
- m_rowstart[0] = start_of_this_row;
- for (vertices_size_type i = 1; i <= numlocalverts; ++i) {
- start_of_this_row += m_rowstart[i];
- m_rowstart[i] = start_of_this_row;
- }
- m_column.resize(m_rowstart.back());
- inherited_edge_properties::resize(m_rowstart.back());
-
- // Histogram sort the edges by their source vertices, putting the targets
- // into m_column. The index current_insert_positions[v] contains the next
- // location to insert out edges for vertex v.
- std::vector<EdgeIndex>
- current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numlocalverts);
- for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
- if (edge_pred(*edge_begin)) {
- vertices_size_type source = get(global_to_local, 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,
@@ -408,13 +279,9 @@
MultiPassInputIterator edge_end,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, identity_property_map(), keep_all());
-
- // Default-construct properties for edges
- inherited_edge_properties::resize(m_column.size());
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, identity_property_map(), keep_all());
}
// From number of vertices and unsorted list of edges, plus edge properties
@@ -425,116 +292,43 @@
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, identity_property_map(), keep_all());
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, identity_property_map(), keep_all());
}
// From number of vertices and unsorted list of edges, with filter and
// global-to-local map
- template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
+ template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numlocalverts,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, edge_pred);
-
- // Default-construct properties for edges
- inherited_edge_properties::resize(m_column.size());
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
}
// From number of vertices and unsorted list of edges, plus edge properties,
// with filter and global-to-local map
- template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numlocalverts,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, edge_pred);
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- // Assign from number of vertices and sorted list of edges
- template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
- void assign_from_sorted_edges(
- InputIterator edge_begin, InputIterator edge_end,
- const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
- vertices_size_type numlocalverts,
- edges_size_type numedges_or_zero) {
- m_column.clear();
- m_column.reserve(numedges_or_zero);
- inherited_vertex_properties::resize(numlocalverts);
- m_rowstart.resize(numlocalverts + 1);
- EdgeIndex current_edge = 0;
- Vertex current_vertex_plus_one = 1;
- m_rowstart[0] = 0;
- for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
- if (!edge_pred(*ei)) continue;
- Vertex src = get(global_to_local, ei->first);
- Vertex tgt = ei->second;
- for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
- m_column.push_back(tgt);
- ++current_edge;
- }
-
- // The remaining vertices have no edges
- for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
-
- // Default-construct properties for edges
- inherited_edge_properties::resize(m_column.size());
- }
-
- // Assign from number of vertices and sorted list of edges
- template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
- void assign_from_sorted_edges(
- InputIterator edge_begin, InputIterator edge_end,
- EdgePropertyIterator ep_iter,
- const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
- vertices_size_type numlocalverts,
- edges_size_type numedges_or_zero) {
- m_column.clear();
- m_column.reserve(numedges_or_zero);
- inherited_edge_properties::clear();
- inherited_edge_properties::reserve(numedges_or_zero);
- inherited_vertex_properties::resize(numlocalverts);
- m_rowstart.resize(numlocalverts + 1);
- EdgeIndex current_edge = 0;
- Vertex current_vertex_plus_one = 1;
- m_rowstart[0] = 0;
- for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
- if (!edge_pred(*ei)) continue;
- Vertex src = get(global_to_local, ei->first);
- Vertex tgt = ei->second;
- for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
- m_column.push_back(tgt);
- inherited_edge_properties::push_back(*ep_iter);
- ++current_edge;
- }
-
- // The remaining vertices have no edges
- for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
- }
-
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// From number of vertices and sorted list of edges (deprecated
@@ -544,17 +338,10 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : m_property(prop), m_last_source(numverts)
+ : m_property(prop)
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
- }
- assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// From number of vertices and sorted list of edges (deprecated
@@ -565,17 +352,10 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : m_property(prop), m_last_source(numverts)
+ : m_property(prop)
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
- }
- assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -588,19 +368,9 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
: m_property(prop)
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(numverts)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
- }
- assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// From number of vertices and sorted list of edges (new interface)
@@ -612,53 +382,39 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
: m_property(prop)
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(numverts)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
- }
- assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From number of vertices and sorted list of edges, filtered and global (new interface)
- template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
+ template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_sorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
: m_property(prop)
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(numverts)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
{
- assign_from_sorted_edges(edge_begin, edge_end, global_to_local, edge_pred, numverts, 0);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numverts, 0);
+ inherited_vertex_properties::resize(numverts);
}
// From number of vertices and sorted list of edges (new interface)
- template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+ template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_sorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
: m_property(prop)
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(numverts)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
{
- assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, edge_pred, numverts, 0);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, source_pred, numverts, 0);
+ inherited_vertex_properties::resize(numverts);
}
// From number of vertices and mutable vectors of sources and targets;
@@ -669,10 +425,9 @@
std::vector<vertex_descriptor>& targets,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
+ m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
}
// From number of vertices and mutable vectors of sources and targets,
@@ -687,10 +442,9 @@
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
+ m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
}
// From number of vertices and mutable vectors of sources, targets, and edge
@@ -699,13 +453,12 @@
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
std::vector<vertex_descriptor>& sources,
std::vector<vertex_descriptor>& targets,
- std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
+ std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
+ m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
}
// From number of vertices and mutable vectors of sources and targets and
@@ -717,14 +470,13 @@
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
std::vector<vertex_descriptor>& sources,
std::vector<vertex_descriptor>& targets,
- std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
+ std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
+ m_forward.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
@@ -734,19 +486,12 @@
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)
+ : inherited_vertex_properties(numverts), 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());
+ boost::graph::detail::split_into_separate_coords
+ (edge_begin, edge_end, sources, targets);
+ m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
}
// From number of vertices and single-pass range of unsorted edges and
@@ -758,45 +503,35 @@
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- std::vector<typename inherited_edge_properties::edge_bundled> 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);
+ boost::graph::detail::split_into_separate_coords
+ (edge_begin, edge_end, sources, targets);
+ size_t numedges = sources.size();
+ std::vector<typename forward_type::inherited_edge_properties::edge_bundled> edge_props(numedges);
+ for (size_t i = 0; i < numedges; ++i) {
+ edge_props[i] = *ep_iter++;
}
- assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
+ m_forward.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>
+ template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), 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);
+ boost::graph::detail::split_into_separate_coords_filtered
+ (edge_begin, edge_end, sources, targets, source_pred);
+ m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
}
// From number of vertices and single-pass range of unsorted edges and
@@ -804,125 +539,27 @@
// 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>
+ typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- std::vector<typename inherited_edge_properties::edge_bundled> 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.
- template <typename GlobalToLocal>
- void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- vertices_size_type numverts,
- GlobalToLocal global_to_local) {
- assert (sources.size() == targets.size());
- typedef typename std::vector<vertex_descriptor>::iterator vertex_vec_iter;
- EdgeIndex numedges = sources.size();
- // Do an in-place histogram sort (at least that's what I think it is) to
- // sort sources and targets
- // 1. Count degrees; degree of vertex v is in m_rowstart[v + 1]
- m_rowstart.clear();
- m_rowstart.resize(numverts + 1);
- for (size_t i = 0; i < numedges; ++i) {
- assert(get(global_to_local, sources[i]) < numverts);
- ++m_rowstart[get(global_to_local, sources[i]) + 1];
- }
- // 2. Do a prefix sum on those to get starting positions of each row
- for (size_t i = 0; i < numverts; ++i) {
- m_rowstart[i + 1] += m_rowstart[i];
- }
- // 3. Copy m_rowstart (except last element) to get insert positions
- std::vector<EdgeIndex> insert_positions(m_rowstart.begin(), boost::prior(m_rowstart.end()));
- // 4. Swap the sources and targets into place
- for (size_t i = 0; i < numedges; ++i) {
- // While edge i is not in the right bucket:
- while (!(i >= m_rowstart[get(global_to_local, sources[i])] && i < insert_positions[get(global_to_local, sources[i])])) {
- // Add a slot in the right bucket
- size_t target_pos = insert_positions[get(global_to_local, sources[i])]++;
- assert (target_pos < m_rowstart[get(global_to_local, sources[i]) + 1]);
- if (target_pos == i) continue;
- // Swap this edge into place
- using std::swap;
- swap(sources[i], sources[target_pos]);
- swap(targets[i], targets[target_pos]);
- }
- }
- // Now targets is the correct vector (properly sorted by source) for
- // m_column
- m_column.swap(targets);
- }
-
- // Replace graph with sources and targets and edge properties 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.
- template <typename GlobalToLocal>
- void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
- vertices_size_type numverts,
- GlobalToLocal global_to_local) {
- assert (sources.size() == targets.size());
- assert (sources.size() == edge_props.size());
- EdgeIndex numedges = sources.size();
- // Do an in-place histogram sort (at least that's what I think it is) to
- // sort sources and targets
- // 1. Count degrees; degree of vertex v is in m_rowstart[v + 1]
- m_rowstart.clear();
- m_rowstart.resize(numverts + 1);
- for (size_t i = 0; i < numedges; ++i) {
- ++m_rowstart[get(global_to_local, sources[i]) + 1];
- }
- // 2. Do a prefix sum on those to get starting positions of each row
- for (size_t i = 0; i < numverts; ++i) {
- m_rowstart[i + 1] += m_rowstart[i];
- }
- // 3. Copy m_rowstart (except last element) to get insert positions
- std::vector<EdgeIndex> insert_positions(m_rowstart.begin(), boost::prior(m_rowstart.end()));
- // 4. Swap the sources and targets into place
- for (size_t i = 0; i < numedges; ++i) {
- // While edge i is not in the right bucket:
- while (!(i >= m_rowstart[get(global_to_local, sources[i])] && i < insert_positions[get(global_to_local, sources[i])])) {
- // Add a slot in the right bucket
- size_t target_pos = insert_positions[get(global_to_local, sources[i])]++;
- assert (target_pos < m_rowstart[get(global_to_local, sources[i]) + 1]);
- if (target_pos == i) continue;
- // Swap this edge into place
- using std::swap;
- swap(sources[i], sources[target_pos]);
- swap(targets[i], targets[target_pos]);
- swap(edge_props[i], edge_props[target_pos]);
- }
- }
- // Now targets is the correct vector (properly sorted by source) for
- // m_column, and edge_props for m_edge_properties
- m_column.swap(targets);
- this->m_edge_properties.swap(edge_props);
+ std::vector<edge_bundled> edge_props;
+ boost::graph::detail::split_into_separate_coords_filtered
+ (edge_begin, edge_end, ep_iter, sources, targets, edge_props, source_pred);
+ m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- // Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function
+ // Requires IncidenceGraph and a vertex index map
template<typename Graph, typename VertexIndexMap>
compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
vertices_size_type numverts,
@@ -930,6 +567,7 @@
: m_property()
{
assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// Requires VertexListGraph and EdgeListGraph
@@ -937,7 +575,13 @@
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)
+ }
+ vertices_size_type numverts = num_vertices(g);
+ assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// Requires vertex index map plus requirements of previous constructor
@@ -945,61 +589,50 @@
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
+ // Requires IncidenceGraph and a vertex index map
// 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,
vertices_size_type numverts, edges_size_type numedges)
{
+ m_forward.assign(g, vi, numverts, numedges);
inherited_vertex_properties::resize(numverts);
- m_rowstart.resize(numverts + 1);
- m_column.resize(numedges);
- EdgeIndex current_edge = 0;
- typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
- typedef typename boost::graph_traits<Graph>::edge_descriptor g_edge;
- typedef typename boost::graph_traits<Graph>::out_edge_iterator
- g_out_edge_iter;
-
- for (Vertex i = 0; i != numverts; ++i) {
- m_rowstart[i] = current_edge;
- g_vertex v = vertex(i, g);
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- // Out edges in a single vertex are only sorted for the old interface
- EdgeIndex num_edges_before_this_vertex = current_edge;
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- g_out_edge_iter ei, ei_end;
- for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
- m_column[current_edge++] = get(vi, target(*ei, g));
- }
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- // Out edges in a single vertex are only sorted for the old interface
- std::sort(m_column.begin() + num_edges_before_this_vertex,
- m_column.begin() + current_edge);
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- }
- m_rowstart[numverts] = current_edge;
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- m_last_source = numverts;
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
}
// Requires the above, plus VertexListGraph and EdgeListGraph
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)
+ }
+ vertices_size_type numverts = num_vertices(g);
+ m_forward.assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// 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)
+ }
+ vertices_size_type numverts = num_vertices(g);
+ m_forward.assign(g, get(vertex_index, g), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -1013,66 +646,7 @@
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted,
const GlobalToLocal& global_to_local) {
- typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
- typedef boost::reverse_iterator<EPIterOrig> EPIter;
- // Flip sequence
- BidirectionalIterator first(last_sorted);
- BidirectionalIterator last(first_sorted);
- typedef compressed_sparse_row_graph 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;
- edge_num new_edge_count = std::distance(first, last);
-
- EPIter ep_iter(ep_iter_sorted);
- std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
- edge_num edges_added_before_i = new_edge_count; // Count increment to add to rowstarts
- m_column.resize(m_column.size() + new_edge_count);
- inherited_edge_properties::resize(inherited_edge_properties::size() + new_edge_count);
- BidirectionalIterator current_new_edge = first, prev_new_edge = first;
- EPIter current_new_edge_prop = ep_iter;
- for (vertex_num i_plus_1 = num_vertices(*this); 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 != last) {
- if (get(global_to_local, current_new_edge->first) != i) break;
- ++current_new_edge;
- ++current_new_edge_prop;
- ++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 = m_rowstart[i];
- edge_num new_rowstart = m_rowstart[i] + edges_added_before_i;
- edge_num old_degree = m_rowstart[i + 1] - 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(m_column.begin() + old_rowstart,
- m_column.begin() + old_rowstart + old_degree,
- m_column.begin() + new_rowstart + old_degree);
- inherited_edge_properties::move_range(old_rowstart, old_rowstart + old_degree, new_rowstart);
- }
- // Add new edges (reversed because current_new_edge is a
- // const_reverse_iterator)
- BidirectionalIterator temp = current_new_edge;
- EPIter temp_prop = current_new_edge_prop;
- for (; temp != prev_new_edge; ++old_degree) {
- --temp;
- --temp_prop;
- m_column[new_rowstart + old_degree] = temp->second;
- inherited_edge_properties::write_by_index(new_rowstart + old_degree, *temp_prop);
- }
- m_rowstart[i + 1] = new_rowstart + new_degree;
- if (edges_added_before_i == 0) break; // No more edges inserted before this point
- // 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
- // m_rowstart[0] is always 0)
- }
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
}
template <typename BidirectionalIteratorOrig, typename EPIterOrig>
@@ -1081,8 +655,7 @@
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted) {
- add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
- identity_property_map());
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, identity_property_map());
}
// Add edges from a sorted (smallest sources first) range of pairs
@@ -1091,7 +664,7 @@
add_edges_sorted_internal(
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted) {
- add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>());
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>());
}
template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
@@ -1100,8 +673,7 @@
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
const GlobalToLocal& global_to_local) {
- add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>(),
- global_to_local);
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local);
}
template <typename BidirectionalIteratorOrig, typename EPIterOrig,
@@ -1112,8 +684,7 @@
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted,
const GlobalToLocal& global_to_local) {
- add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
- global_to_local);
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
}
// Add edges from a range of (source, target) pairs that are unsorted
@@ -1129,13 +700,13 @@
edge_vector_t new_edges(first, last);
if (new_edges.empty()) return;
std::sort(new_edges.begin(), new_edges.end());
- add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
+ this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
}
template <typename InputIterator>
inline void
add_edges_internal(InputIterator first, InputIterator last) {
- add_edges_internal(first, last, identity_property_map());
+ this->add_edges_internal(first, last, identity_property_map());
}
// Add edges from a range of (source, target) pairs and edge properties that
@@ -1152,7 +723,7 @@
typedef std::pair<vertex_t, vertex_t> vertex_pair;
typedef std::vector<
boost::tuple<vertex_pair,
- typename inherited_edge_properties::edge_bundled> >
+ edge_bundled> >
edge_vector_t;
edge_vector_t new_edges
(boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
@@ -1161,7 +732,7 @@
std::sort(new_edges.begin(), new_edges.end(),
boost::detail::compare_first<
std::less<vertex_pair> >());
- add_edges_sorted_internal
+ m_forward.add_edges_sorted_internal
(boost::make_transform_iterator(
new_edges.begin(),
boost::detail::my_tuple_get_class<0, vertex_pair>()),
@@ -1171,7 +742,7 @@
boost::make_transform_iterator(
new_edges.begin(),
boost::detail::my_tuple_get_class
- <1, typename inherited_edge_properties::edge_bundled>()),
+ <1, edge_bundled>()),
global_to_local);
}
@@ -1181,91 +752,435 @@
inline void
add_edges_internal(InputIterator first, InputIterator last,
EPIterator ep_iter, EPIterator ep_iter_end) {
- add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
+ this->add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
using inherited_vertex_properties::operator[];
- using inherited_edge_properties::operator[];
+
+ // Directly access a edge or edge bundle
+ edge_push_back_type& operator[](const edge_descriptor& v)
+ { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
+
+ const edge_push_back_type& operator[](const edge_descriptor& v) const
+ { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
// private: non-portable, requires friend templates
inherited_vertex_properties& vertex_properties() {return *this;}
const inherited_vertex_properties& vertex_properties() const {return *this;}
- inherited_edge_properties& edge_properties() { return *this; }
- const inherited_edge_properties& edge_properties() const { return *this; }
+ typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
+ const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
- std::vector<EdgeIndex> m_rowstart;
- std::vector<Vertex> m_column;
+ forward_type m_forward;
GraphProperty m_property;
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- // This member is only needed to support add_edge(), which is not provided by
- // the new interface
- Vertex m_last_source; // Last source of added edge, plus one
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
};
-template<typename Vertex, typename EdgeIndex>
-class csr_edge_descriptor
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// Bidir is only supported in this mode
+template<typename VertexProperty,
+ typename EdgeProperty,
+ typename GraphProperty,
+ typename Vertex,
+ typename EdgeIndex>
+class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
+ : public detail::indexed_vertex_properties<BOOST_BIDIR_CSR_GRAPH_TYPE,
+ VertexProperty, Vertex>
{
public:
- Vertex src;
- EdgeIndex idx;
+ typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
+ VertexProperty, Vertex>
+ inherited_vertex_properties;
+
+ public:
+ // For Property Graph
+ typedef GraphProperty graph_property_type;
+
+ typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
+ typedef EdgeIndex /* typename boost::mpl::if_c<boost::is_same<EdgeProperty, boost::no_property>, boost::no_property, EdgeIndex> */ backward_edge_property;
+ typedef detail::compressed_sparse_row_structure<backward_edge_property, Vertex, EdgeIndex> backward_type;
+
+ public:
+ // Concept requirements:
+ // For Graph
+ typedef Vertex vertex_descriptor;
+ typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
+ typedef bidirectional_tag directed_category;
+ typedef allow_parallel_edge_tag edge_parallel_category;
+
+ class traversal_category: public bidirectional_graph_tag,
+ public adjacency_graph_tag,
+ public vertex_list_graph_tag,
+ public edge_list_graph_tag {};
- csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}
- csr_edge_descriptor(): src(0), idx(0) {}
+ static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
- bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}
- bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}
- bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}
- bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
- bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
- bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
+ // For VertexListGraph
+ typedef counting_iterator<Vertex> vertex_iterator;
+ typedef Vertex vertices_size_type;
+
+ // For EdgeListGraph
+ typedef EdgeIndex edges_size_type;
+
+ // For IncidenceGraph
+ typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
+ typedef EdgeIndex degree_size_type;
- template<typename Archiver>
- void serialize(Archiver& ar, const unsigned int /*version*/)
+ // For AdjacencyGraph
+ typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
+
+ // For EdgeListGraph
+ typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
+
+ // For BidirectionalGraph (not implemented)
+ typedef detail::csr_in_edge_iterator<compressed_sparse_row_graph> in_edge_iterator;
+
+ // For internal use
+ typedef csr_graph_tag graph_tag;
+
+ typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
+ typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
+ typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
+
+ // Constructors
+
+ // Default constructor: an empty graph.
+ compressed_sparse_row_graph(): m_property() {}
+
+ // With numverts vertices
+ compressed_sparse_row_graph(vertices_size_type numverts)
+ : inherited_vertex_properties(numverts),
+ m_forward(numverts), m_backward(numverts) {}
+
+ private:
+
+ void set_up_backward_property_links() {
+ std::pair<edge_iterator, edge_iterator> e = edges(*this);
+ m_backward.assign_unsorted_multi_pass_edges
+ (detail::transpose_edges(
+ detail::make_edge_to_index_pair_iter
+ (*this, get(vertex_index, *this), e.first)),
+ detail::transpose_edges(
+ detail::make_edge_to_index_pair_iter
+ (*this, get(vertex_index, *this), e.second)),
+ boost::counting_iterator<EdgeIndex>(0),
+ m_forward.m_rowstart.size() - 1,
+ identity_property_map(),
+ keep_all());
+ }
+
+ public:
+
+ // 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_property(prop)
{
- ar & src & idx;
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, identity_property_map(), keep_all());
+ set_up_backward_property_links();
}
-};
-template<typename Vertex, typename EdgeIndex>
-struct hash<csr_edge_descriptor<Vertex, EdgeIndex> >
-{
- std::size_t operator()(csr_edge_descriptor<Vertex, EdgeIndex> const& x) const
+ // 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_forward(), m_property(prop)
+ {
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, identity_property_map(), keep_all());
+ set_up_backward_property_links();
+ }
+
+ // From number of vertices and unsorted list of edges, with filter and
+ // global-to-local map
+ template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
+ const SourcePred& source_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
+ {
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
+ set_up_backward_property_links();
+ }
+
+ // From number of vertices and unsorted list of edges, plus edge properties,
+ // with filter and global-to-local map
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
+ const SourcePred& source_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
+ {
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
+ set_up_backward_property_links();
+ }
+
+ // Requires IncidenceGraph and a vertex index map
+ template<typename Graph, typename VertexIndexMap>
+ compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
+ vertices_size_type numverts,
+ edges_size_type numedges)
+ : m_property()
+ {
+ assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // Requires VertexListGraph and EdgeListGraph
+ template<typename Graph, typename VertexIndexMap>
+ compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
+ : m_property()
+ {
+ 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)
+ }
+ vertices_size_type numverts = num_vertices(g);
+ assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // Requires vertex index map plus requirements of previous constructor
+ template<typename Graph>
+ explicit compressed_sparse_row_graph(const Graph& g)
+ : m_property()
+ {
+ 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 and a vertex index map
+ // 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,
+ vertices_size_type numverts, edges_size_type numedges)
+ {
+ m_forward.assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // Requires the above, plus VertexListGraph and EdgeListGraph
+ template<typename Graph, typename VertexIndexMap>
+ void assign(const Graph& g, const VertexIndexMap& vi)
{
- std::size_t hash = hash_value(x.src);
- hash_combine(hash, x.idx);
- return hash;
+ 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)
+ }
+ vertices_size_type numverts = num_vertices(g);
+ m_forward.assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // Requires the above, plus a vertex_index map.
+ template<typename Graph>
+ void assign(const Graph& 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)
+ }
+ vertices_size_type numverts = num_vertices(g);
+ m_forward.assign(g, get(vertex_index, g), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs and edge
+ // properties
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig,
+ typename GlobalToLocal>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ const GlobalToLocal& global_to_local) {
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
+ }
+
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted) {
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, identity_property_map());
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs
+ template <typename BidirectionalIteratorOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted) {
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>());
+ }
+
+ template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
+ void
+ add_edges_sorted_internal_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ const GlobalToLocal& global_to_local) {
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local);
+ }
+
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig,
+ typename GlobalToLocal>
+ void
+ add_edges_sorted_internal_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ const GlobalToLocal& global_to_local) {
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
}
+
+ // Add edges from a range of (source, target) pairs that are unsorted
+ template <typename InputIterator, typename GlobalToLocal>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ const GlobalToLocal& global_to_local) {
+ typedef compressed_sparse_row_graph 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());
+ this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
+ }
+
+ template <typename InputIterator>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last) {
+ this->add_edges_internal(first, last, identity_property_map());
+ }
+
+ // Add edges from a range of (source, target) pairs and edge properties that
+ // are unsorted
+ template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end,
+ const GlobalToLocal& global_to_local) {
+ typedef compressed_sparse_row_graph 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::pair<vertex_t, vertex_t> vertex_pair;
+ typedef std::vector<
+ boost::tuple<vertex_pair,
+ edge_bundled> >
+ edge_vector_t;
+ edge_vector_t new_edges
+ (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
+ boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
+ if (new_edges.empty()) return;
+ std::sort(new_edges.begin(), new_edges.end(),
+ boost::detail::compare_first<
+ std::less<vertex_pair> >());
+ m_forward.add_edges_sorted_internal
+ (boost::make_transform_iterator(
+ new_edges.begin(),
+ boost::detail::my_tuple_get_class<0, vertex_pair>()),
+ boost::make_transform_iterator(
+ new_edges.end(),
+ boost::detail::my_tuple_get_class<0, vertex_pair>()),
+ boost::make_transform_iterator(
+ new_edges.begin(),
+ boost::detail::my_tuple_get_class
+ <1, edge_bundled>()),
+ global_to_local);
+ }
+
+ // Add edges from a range of (source, target) pairs and edge properties that
+ // are unsorted
+ template <typename InputIterator, typename EPIterator>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end) {
+ this->add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
+ }
+
+ using inherited_vertex_properties::operator[];
+
+ // Directly access a edge or edge bundle
+ edge_push_back_type& operator[](const edge_descriptor& v)
+ { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
+
+ const edge_push_back_type& operator[](const edge_descriptor& v) const
+ { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
+
+ // private: non-portable, requires friend templates
+ inherited_vertex_properties& vertex_properties() {return *this;}
+ const inherited_vertex_properties& vertex_properties() const {return *this;}
+ typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
+ const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
+
+ forward_type m_forward;
+ backward_type m_backward;
+ GraphProperty m_property;
};
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Construction functions
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
- Vertex old_num_verts_plus_one = g.m_rowstart.size();
- EdgeIndex numedges = g.m_rowstart.back();
- g.m_rowstart.push_back(numedges);
- g.vertex_properties().resize(num_vertices(g));
+ add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled());
+}
+
+template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline Vertex
+add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g,
+ typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
+ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
+ g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
+ g.vertex_properties().push_back(p);
return old_num_verts_plus_one - 1;
}
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
-add_vertex(BOOST_CSR_GRAPH_TYPE& g,
- typename BOOST_CSR_GRAPH_TYPE::vertex_bundled const& p) {
- Vertex old_num_verts_plus_one = g.m_rowstart.size();
- g.m_rowstart.push_back(EdgeIndex(0));
+add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE& g,
+ typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
+ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
+ g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
+ g.m_backward.m_rowstart.push_back(g.m_backward.m_rowstart.back());
g.vertex_properties().push_back(p);
return old_num_verts_plus_one - 1;
}
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
-add_vertices(typename BOOST_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_CSR_GRAPH_TYPE& g) {
- Vertex old_num_verts_plus_one = g.m_rowstart.size();
- EdgeIndex numedges = g.m_rowstart.back();
- g.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
+add_vertices(typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_DIR_CSR_GRAPH_TYPE& g) {
+ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
+ EdgeIndex numedges = g.m_forward.m_rowstart.back();
+ g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
+ g.m_backward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
g.vertex_properties().resize(num_vertices(g));
return old_num_verts_plus_one - 1;
}
@@ -1273,65 +1188,65 @@
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// This function requires that (src, tgt) be lexicographically at least as
// large as the largest edge in the graph so far
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
-add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) {
+template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline typename BOOST_DIR_CSR_GRAPH_TYPE::edge_descriptor
+add_edge(Vertex src, Vertex tgt, BOOST_DIR_CSR_GRAPH_TYPE& g) {
assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&
src < num_vertices(g));
- EdgeIndex num_edges_orig = g.m_column.size();
+ EdgeIndex num_edges_orig = g.m_forward.m_column.size();
for (; g.m_last_source <= src; ++g.m_last_source)
- g.m_rowstart[g.m_last_source] = num_edges_orig;
- g.m_rowstart[src + 1] = num_edges_orig + 1;
- g.m_column.push_back(tgt);
- typedef typename BOOST_CSR_GRAPH_TYPE::edge_push_back_type push_back_type;
+ g.m_forward.m_rowstart[g.m_last_source] = num_edges_orig;
+ g.m_forward.m_rowstart[src + 1] = num_edges_orig + 1;
+ g.m_forward.m_column.push_back(tgt);
+ typedef typename BOOST_DIR_CSR_GRAPH_TYPE::edge_push_back_type push_back_type;
g.edge_properties().push_back(push_back_type());
- return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
+ return typename BOOST_DIR_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
}
// This function requires that src be at least as large as the largest source
// in the graph so far
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
+template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline typename BOOST_DIR_CSR_GRAPH_TYPE::edge_descriptor
add_edge(Vertex src, Vertex tgt,
- typename BOOST_CSR_GRAPH_TYPE::edge_bundled const& p,
- BOOST_CSR_GRAPH_TYPE& g) {
+ typename BOOST_DIR_CSR_GRAPH_TYPE::edge_bundled const& p,
+ BOOST_DIR_CSR_GRAPH_TYPE& g) {
assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&
src < num_vertices(g));
- EdgeIndex num_edges_orig = g.m_column.size();
+ EdgeIndex num_edges_orig = g.m_forward.m_column.size();
for (; g.m_last_source <= src; ++g.m_last_source)
- g.m_rowstart[g.m_last_source] = num_edges_orig;
- g.m_rowstart[src + 1] = num_edges_orig + 1;
- g.m_column.push_back(tgt);
+ g.m_forward.m_rowstart[g.m_last_source] = num_edges_orig;
+ g.m_forward.m_rowstart[src + 1] = num_edges_orig + 1;
+ g.m_forward.m_column.push_back(tgt);
g.edge_properties().push_back(p);
- return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
+ return typename BOOST_DIR_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
}
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Add edges from a sorted (smallest sources first) range of pairs and edge
// properties
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
typename EPIterOrig>
void
add_edges_sorted(
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted,
- BOOST_CSR_GRAPH_TYPE& g) {
+ BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
}
// Add edges from a sorted (smallest sources first) range of pairs
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
void
add_edges_sorted(
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
- BOOST_CSR_GRAPH_TYPE& g) {
+ BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_sorted_internal(first_sorted, last_sorted);
}
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
typename EPIterOrig, typename GlobalToLocal>
void
add_edges_sorted_global(
@@ -1339,57 +1254,57 @@
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted,
const GlobalToLocal& global_to_local,
- BOOST_CSR_GRAPH_TYPE& g) {
+ BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_sorted_internal_global(first_sorted, last_sorted, ep_iter_sorted,
global_to_local);
}
// Add edges from a sorted (smallest sources first) range of pairs
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
typename GlobalToLocal>
void
add_edges_sorted_global(
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
const GlobalToLocal& global_to_local,
- BOOST_CSR_GRAPH_TYPE& g) {
+ BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_sorted_internal_global(first_sorted, last_sorted, global_to_local);
}
// Add edges from a range of (source, target) pairs that are unsorted
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
typename GlobalToLocal>
inline void
add_edges_global(InputIterator first, InputIterator last,
- const GlobalToLocal& global_to_local, BOOST_CSR_GRAPH_TYPE& g) {
+ const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_internal(first, last, global_to_local);
}
// Add edges from a range of (source, target) pairs that are unsorted
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
inline void
- add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
+ add_edges(InputIterator first, InputIterator last, BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_internal(first, last);
}
// Add edges from a range of (source, target) pairs and edge properties that
// are unsorted
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS,
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
typename InputIterator, typename EPIterator>
inline void
add_edges(InputIterator first, InputIterator last,
EPIterator ep_iter, EPIterator ep_iter_end,
- BOOST_CSR_GRAPH_TYPE& g) {
+ BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_internal(first, last, ep_iter, ep_iter_end);
}
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS,
+ template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
typename InputIterator, typename EPIterator, typename GlobalToLocal>
inline void
add_edges_global(InputIterator first, InputIterator last,
EPIterator ep_iter, EPIterator ep_iter_end,
const GlobalToLocal& global_to_local,
- BOOST_CSR_GRAPH_TYPE& g) {
+ BOOST_DIR_CSR_GRAPH_TYPE& g) {
g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -1398,7 +1313,7 @@
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
- return g.m_rowstart.size() - 1;
+ return g.m_forward.m_rowstart.size() - 1;
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1410,40 +1325,6 @@
// From IncidenceGraph
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-class BOOST_CSR_GRAPH_TYPE::out_edge_iterator
- : public iterator_facade<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
- typename BOOST_CSR_GRAPH_TYPE::edge_descriptor,
- std::random_access_iterator_tag,
- const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor&,
- typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast>
-{
- public:
- typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
-
- out_edge_iterator() {}
- // Implicit copy constructor OK
- explicit out_edge_iterator(edge_descriptor edge) : m_edge(edge) { }
-
- private:
- // iterator_facade requirements
- const edge_descriptor& dereference() const { return m_edge; }
-
- bool equal(const out_edge_iterator& other) const
- { return m_edge == other.m_edge; }
-
- void increment() { ++m_edge.idx; }
- void decrement() { ++m_edge.idx; }
- void advance(difference_type n) { m_edge.idx += n; }
-
- difference_type distance_to(const out_edge_iterator& other) const
- { return other.m_edge.idx - m_edge.idx; }
-
- edge_descriptor m_edge;
-
- friend class iterator_core_access;
-};
-
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
const BOOST_CSR_GRAPH_TYPE&)
@@ -1456,7 +1337,22 @@
target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
const BOOST_CSR_GRAPH_TYPE& g)
{
- return g.m_column[e.idx];
+ return g.m_forward.m_column[e.idx];
+}
+
+namespace detail {
+ template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+ inline EdgeIndex get_actual_row_start
+ (const BOOST_CSR_GRAPH_TYPE& g,
+ EdgeIndex rowstart_i_minus_1, EdgeIndex rowstart_i)
+ {
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ return rowstart_i;
+#else
+ // Special case to allow incremental construction
+ return (std::max)(rowstart_i_minus_1, rowstart_i);
+#endif
+ }
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1466,49 +1362,60 @@
{
typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed;
typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
- EdgeIndex v_row_start = g.m_rowstart[v];
- EdgeIndex next_row_start = g.m_rowstart[v + 1];
-#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- return std::make_pair(it(ed(v, v_row_start)),
- it(ed(v, next_row_start)));
-#else
- // Special case to allow incremental construction
+ EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
return std::make_pair(it(ed(v, v_row_start)),
- it(ed(v, (std::max)(v_row_start, next_row_start))));
-#endif
+ it(ed(v, detail::get_actual_row_start
+ (g, v_row_start, next_row_start))));
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline EdgeIndex
out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
{
- EdgeIndex v_row_start = g.m_rowstart[v];
- EdgeIndex next_row_start = g.m_rowstart[v + 1];
+ EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
+ return detail::get_actual_row_start(g, v_row_start, next_row_start) - v_row_start;
+}
+
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline std::pair<typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator,
+ typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator>
+in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
+{
+ typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::edge_descriptor ed;
+ typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
+ EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
+ return std::make_pair(it(ed(v, v_row_start)),
+ it(ed(v, next_row_start)));
+}
+
+template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline EdgeIndex
+in_degree(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
+{
+ EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
return next_row_start - v_row_start;
-#else
- // Special case to allow incremental construction
- return (std::max)(v_row_start, next_row_start) - v_row_start;
-#endif
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
// From AdjacencyGraph
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator>
adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
{
- EdgeIndex v_row_start = g.m_rowstart[v];
- EdgeIndex next_row_start = g.m_rowstart[v + 1];
-#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- return std::make_pair(g.m_column.begin() + v_row_start,
- g.m_column.begin() + next_row_start);
-#else
- // Special case to allow incremental construction
- return std::make_pair(g.m_column.begin() + v_row_start,
- g.m_column.begin() +
- (std::max)(v_row_start, next_row_start));
-#endif
+ EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
+ return std::make_pair(g.m_forward.m_column.begin() + v_row_start,
+ g.m_forward.m_column.begin() +
+ detail::get_actual_row_start
+ (g, v_row_start, next_row_start));
}
// Extra, common functions
@@ -1537,8 +1444,8 @@
std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
std::pair<adj_iter, adj_iter> adjacencies =
std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
- EdgeIndex idx_begin = adjacencies.first - g.m_column.begin();
- EdgeIndex idx_end = adjacencies.second - g.m_column.begin();
+ EdgeIndex idx_begin = adjacencies.first - g.m_forward.m_column.begin();
+ EdgeIndex idx_end = adjacencies.second - g.m_forward.m_column.begin();
return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
out_edge_iter(edge_desc(i, idx_end)));
}
@@ -1555,7 +1462,25 @@
else
return std::make_pair(*range.first, true);
}
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+
+#else // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+// edge() can be provided in linear time for the new interface
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
+edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
+{
+ typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
+ std::pair<out_edge_iter, out_edge_iter> range = out_edges(i, g);
+ for (; range.first != range.second; ++range.first) {
+ if (target(*range.first) == j)
+ return std::make_pair(*range.first, true);
+ }
+ return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
+ false);
+}
+
+#endif // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// Find an edge given its index in the graph
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1565,80 +1490,27 @@
typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
assert (idx < num_edges(g));
row_start_iter src_plus_1 =
- std::upper_bound(g.m_rowstart.begin(),
+ std::upper_bound(g.m_forward.m_rowstart.begin(),
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// This handles the case where there are some vertices
// with rowstart 0 after the last provided vertex; this
// case does not happen with the new interface
- g.m_rowstart.begin() + g.m_last_source + 1,
+ g.m_forward.m_rowstart.begin() + g.m_last_source + 1,
#else // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- g.m_rowstart.end(),
+ g.m_forward.m_rowstart.end(),
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
idx);
// Get last source whose rowstart is at most idx
// upper_bound returns this position plus 1
- Vertex src = (src_plus_1 - g.m_rowstart.begin()) - 1;
+ Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1;
return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
}
-// From EdgeListGraph
-template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-class BOOST_CSR_GRAPH_TYPE::edge_iterator
-{
- public:
- typedef std::forward_iterator_tag iterator_category;
- typedef edge_descriptor value_type;
-
- typedef const edge_descriptor* pointer;
-
- typedef edge_descriptor reference;
- typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
-
- edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0) {}
-
- edge_iterator(const compressed_sparse_row_graph& graph,
- edge_descriptor current_edge,
- EdgeIndex end_of_this_vertex)
- : rowstart_array(&graph.m_rowstart[0]), current_edge(current_edge),
- end_of_this_vertex(end_of_this_vertex) {}
-
- // From InputIterator
- reference operator*() const { return current_edge; }
- pointer operator->() const { return ¤t_edge; }
-
- bool operator==(const edge_iterator& o) const {
- return current_edge == o.current_edge;
- }
- bool operator!=(const edge_iterator& o) const {
- return current_edge != o.current_edge;
- }
-
- edge_iterator& operator++() {
- ++current_edge.idx;
- while (current_edge.idx == end_of_this_vertex) {
- ++current_edge.src;
- end_of_this_vertex = rowstart_array[current_edge.src + 1];
- }
- return *this;
- }
-
- edge_iterator operator++(int) {
- edge_iterator temp = *this;
- ++*this;
- return temp;
- }
-
- private:
- const EdgeIndex* rowstart_array;
- edge_descriptor current_edge;
- EdgeIndex end_of_this_vertex;
-};
-
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline EdgeIndex
num_edges(const BOOST_CSR_GRAPH_TYPE& g)
{
- return g.m_column.size();
+ return g.m_forward.m_column.size();
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1648,14 +1520,14 @@
{
typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
- if (g.m_rowstart.size() == 1 || g.m_column.empty()) {
+ if (g.m_forward.m_rowstart.size() == 1 || g.m_forward.m_column.empty()) {
return std::make_pair(ei(), ei());
} else {
// Find the first vertex that has outgoing edges
Vertex src = 0;
- while (g.m_rowstart[src + 1] == 0) ++src;
- return std::make_pair(ei(g, edgedesc(src, 0), g.m_rowstart[src + 1]),
- ei(g, edgedesc(num_vertices(g), g.m_column.size()), 0));
+ while (g.m_forward.m_rowstart[src + 1] == 0) ++src;
+ return std::make_pair(ei(g, edgedesc(src, 0), g.m_forward.m_rowstart[src + 1]),
+ ei(g, edgedesc(num_vertices(g), g.m_forward.m_column.size()), 0));
}
}
@@ -1798,6 +1670,10 @@
#undef BOOST_CSR_GRAPH_TYPE
#undef BOOST_CSR_GRAPH_TEMPLATE_PARMS
+#undef BOOST_DIR_CSR_GRAPH_TYPE
+#undef BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS
+#undef BOOST_BIDIR_CSR_GRAPH_TYPE
+#undef BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS
} // end namespace boost
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-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -133,7 +133,7 @@
cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
ColorMap color, DegreeMap degree)
{
- if (has_no_vertices(G))
+ if (boost::graph::has_no_vertices(G))
return permutation;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
@@ -169,7 +169,7 @@
cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
VertexIndexMap index_map)
{
- if (has_no_vertices(G))
+ if (boost::graph::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-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -21,7 +21,6 @@
#include <boost/graph/named_function_params.hpp>
#include <boost/ref.hpp>
#include <boost/implicit_cast.hpp>
-#include <boost/spirit/home/phoenix.hpp>
#include <vector>
#include <utility>
Copied: branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp (from r56116, /trunk/boost/graph/detail/compressed_sparse_row_struct.hpp)
==============================================================================
--- /trunk/boost/graph/detail/compressed_sparse_row_struct.hpp (original)
+++ branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -48,12 +48,12 @@
namespace boost {
-// Forward declaration of CSR edge descriptor type, needed to pass to
-// indexed_edge_properties.
-template<typename Vertex, typename EdgeIndex>
-class csr_edge_descriptor;
-
namespace detail {
+ // Forward declaration of CSR edge descriptor type, needed to pass to
+ // indexed_edge_properties.
+ template<typename Vertex, typename EdgeIndex>
+ class csr_edge_descriptor;
+
/** Compressed sparse row graph internal structure.
*
* Vertex and EdgeIndex should be unsigned integral types and should
@@ -115,14 +115,14 @@
boost::graph::detail::count_starts
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
- source_pred, make_property_map_function(global_to_local));
+ source_pred, boost::make_property_map_function(global_to_local));
m_column.resize(m_rowstart.back());
boost::graph::detail::histogram_sort
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
targets_begin, m_column.begin(),
- source_pred, make_property_map_function(global_to_local));
+ source_pred, boost::make_property_map_function(global_to_local));
}
// Rebuild graph from number of vertices and multi-pass unsorted list of
@@ -148,7 +148,7 @@
boost::graph::detail::count_starts
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
- source_pred, make_property_map_function(global_to_local));
+ source_pred, boost::make_property_map_function(global_to_local));
m_column.resize(m_rowstart.back());
inherited_edge_properties::resize(m_rowstart.back());
@@ -157,7 +157,7 @@
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
targets_begin, m_column.begin(),
ep_iter, inherited_edge_properties::begin(),
- source_pred, make_property_map_function(global_to_local));
+ source_pred, boost::make_property_map_function(global_to_local));
}
// Assign from number of vertices and sorted list of edges
@@ -249,10 +249,10 @@
m_rowstart.resize(numverts + 1);
boost::graph::detail::count_starts
(sources.begin(), sources.end(), m_rowstart.begin(), numverts,
- keep_all(), make_property_map_function(global_to_local));
+ keep_all(), boost::make_property_map_function(global_to_local));
boost::graph::detail::histogram_sort_inplace
(sources.begin(), sources.end(), m_rowstart.begin(), numverts,
- targets.begin(), make_property_map_function(global_to_local));
+ targets.begin(), boost::make_property_map_function(global_to_local));
// Now targets is the correct vector (properly sorted by source) for
// m_column
m_column.swap(targets);
@@ -275,11 +275,11 @@
m_rowstart.resize(numverts + 1);
boost::graph::detail::count_starts
(sources.begin(), sources.end(), m_rowstart.begin(), numverts,
- keep_all(), make_property_map_function(global_to_local));
+ keep_all(), boost::make_property_map_function(global_to_local));
boost::graph::detail::histogram_sort_inplace
(sources.begin(), sources.end(), m_rowstart.begin(), numverts,
targets.begin(), edge_props.begin(),
- make_property_map_function(global_to_local));
+ boost::make_property_map_function(global_to_local));
// Now targets is the correct vector (properly sorted by source) for
// m_column, and edge_props for m_edge_properties
m_column.swap(targets);
@@ -403,7 +403,247 @@
};
+ template<typename Vertex, typename EdgeIndex>
+ class csr_edge_descriptor
+ {
+ public:
+ Vertex src;
+ EdgeIndex idx;
+
+ csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}
+ csr_edge_descriptor(): src(0), idx(0) {}
+
+ bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}
+ bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}
+ bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}
+ bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
+ bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
+ bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & src & idx;
+ }
+ };
+
+ // Common out edge and edge iterators
+ template<typename CSRGraph>
+ class csr_out_edge_iterator
+ : public iterator_facade<csr_out_edge_iterator<CSRGraph>,
+ typename CSRGraph::edge_descriptor,
+ std::random_access_iterator_tag,
+ const typename CSRGraph::edge_descriptor&,
+ typename int_t<CHAR_BIT * sizeof(typename CSRGraph::edges_size_type)>::fast>
+ {
+ public:
+ typedef typename CSRGraph::edges_size_type EdgeIndex;
+ typedef typename CSRGraph::edge_descriptor edge_descriptor;
+ typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
+
+ csr_out_edge_iterator() {}
+ // Implicit copy constructor OK
+ explicit csr_out_edge_iterator(edge_descriptor edge) : m_edge(edge) { }
+
+ public: // GCC 4.2.1 doesn't like the private-and-friend thing
+ // iterator_facade requirements
+ const edge_descriptor& dereference() const { return m_edge; }
+
+ bool equal(const csr_out_edge_iterator& other) const
+ { return m_edge == other.m_edge; }
+
+ void increment() { ++m_edge.idx; }
+ void decrement() { --m_edge.idx; }
+ void advance(difference_type n) { m_edge.idx += n; }
+
+ difference_type distance_to(const csr_out_edge_iterator& other) const
+ { return other.m_edge.idx - m_edge.idx; }
+
+ edge_descriptor m_edge;
+
+ friend class iterator_core_access;
+ };
+
+ template<typename CSRGraph>
+ class csr_edge_iterator
+ : public iterator_facade<csr_edge_iterator<CSRGraph>,
+ typename CSRGraph::edge_descriptor,
+ boost::forward_traversal_tag,
+ typename CSRGraph::edge_descriptor>
+ {
+ private:
+ typedef typename CSRGraph::edge_descriptor edge_descriptor;
+ typedef typename CSRGraph::edges_size_type EdgeIndex;
+
+ public:
+ csr_edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0), total_num_edges(0) {}
+
+ csr_edge_iterator(const CSRGraph& graph,
+ edge_descriptor current_edge,
+ EdgeIndex end_of_this_vertex)
+ : rowstart_array(&graph.m_forward.m_rowstart[0]),
+ current_edge(current_edge),
+ end_of_this_vertex(end_of_this_vertex),
+ total_num_edges(num_edges(graph)) {}
+
+ public: // See above
+ friend class boost::iterator_core_access;
+
+ edge_descriptor dereference() const {return current_edge;}
+
+ bool equal(const csr_edge_iterator& o) const {
+ return current_edge == o.current_edge;
+ }
+
+ void increment() {
+ ++current_edge.idx;
+ if (current_edge.idx == total_num_edges) return;
+ while (current_edge.idx == end_of_this_vertex) {
+ ++current_edge.src;
+ end_of_this_vertex = rowstart_array[current_edge.src + 1];
+ }
+ }
+
+ const EdgeIndex* rowstart_array;
+ edge_descriptor current_edge;
+ EdgeIndex end_of_this_vertex;
+ EdgeIndex total_num_edges;
+ };
+
+ // Only for bidirectional graphs
+ template<typename CSRGraph>
+ class csr_in_edge_iterator
+ : public iterator_facade<csr_in_edge_iterator<CSRGraph>,
+ typename CSRGraph::edge_descriptor,
+ boost::forward_traversal_tag,
+ typename CSRGraph::edge_descriptor>
+ {
+ public:
+ typedef typename CSRGraph::edges_size_type EdgeIndex;
+ typedef typename CSRGraph::edge_descriptor edge_descriptor;
+
+ csr_in_edge_iterator() {}
+ // Implicit copy constructor OK
+ csr_in_edge_iterator(const CSRGraph& graph,
+ EdgeIndex index_in_backward_graph)
+ : m_graph(graph), m_index_in_backward_graph(index_in_backward_graph) {}
+
+ public: // See above
+ // iterator_facade requirements
+ edge_descriptor dereference() const {
+ return edge_descriptor(
+ m_graph.m_backward.m_column[m_index_in_backward_graph],
+ m_graph.m_backward.m_edge_properties[m_index_in_backward_graph]);
+ }
+
+ bool equal(const csr_in_edge_iterator& other) const
+ { return m_index_in_backward_graph == other.m_index_in_backward_graph; }
+
+ void increment() { ++m_index_in_backward_graph; }
+ void decrement() { --m_index_in_backward_graph; }
+ void advance(std::ptrdiff_t n) { m_index_in_backward_graph += n; }
+
+ std::ptrdiff_t distance_to(const csr_in_edge_iterator& other) const
+ { return other.m_index_in_backward_graph - m_index_in_backward_graph; }
+
+ EdgeIndex m_index_in_backward_graph;
+ const CSRGraph& m_graph;
+
+ friend class iterator_core_access;
+ };
+
+ template <typename A, typename B>
+ struct transpose_pair {
+ typedef std::pair<B, A> result_type;
+ result_type operator()(const std::pair<A, B>& p) const {
+ return result_type(p.second, p.first);
+ }
+ };
+
+ template <typename Iter>
+ struct transpose_iterator_gen {
+ typedef typename std::iterator_traits<Iter>::value_type vt;
+ typedef typename vt::first_type first_type;
+ typedef typename vt::second_type second_type;
+ typedef transpose_pair<first_type, second_type> transpose;
+ typedef boost::transform_iterator<transpose, Iter> type;
+ static type make(Iter it) {
+ return type(it, transpose());
+ }
+ };
+
+ template <typename Iter>
+ typename transpose_iterator_gen<Iter>::type transpose_edges(Iter i) {
+ return transpose_iterator_gen<Iter>::make(i);
+ }
+
+ template<typename GraphT, typename VertexIndexMap>
+ class edge_to_index_pair
+ {
+ typedef typename boost::graph_traits<GraphT>::vertices_size_type
+ vertices_size_type;
+ typedef typename boost::graph_traits<GraphT>::edge_descriptor edge_descriptor;
+
+ public:
+ typedef std::pair<vertices_size_type, vertices_size_type> result_type;
+
+ edge_to_index_pair() : g(0), index() { }
+ edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
+ : g(&g), index(index)
+ { }
+
+ result_type operator()(edge_descriptor e) const
+ {
+ return result_type(get(index, source(e, *g)), get(index, target(e, *g)));
+ }
+
+ private:
+ const GraphT* g;
+ VertexIndexMap index;
+ };
+
+ template<typename GraphT, typename VertexIndexMap>
+ edge_to_index_pair<GraphT, VertexIndexMap>
+ make_edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
+ {
+ return edge_to_index_pair<GraphT, VertexIndexMap>(g, index);
+ }
+
+ template<typename GraphT>
+ edge_to_index_pair
+ <GraphT,
+ typename boost::property_map<GraphT,boost::vertex_index_t>::const_type>
+ make_edge_to_index_pair(const GraphT& g)
+ {
+ typedef typename boost::property_map<GraphT,
+ boost::vertex_index_t>::const_type
+ VertexIndexMap;
+ return edge_to_index_pair<GraphT, VertexIndexMap>(g,
+ get(boost::vertex_index,
+ g));
+ }
+
+ template<typename GraphT, typename VertexIndexMap, typename Iter>
+ boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>
+ make_edge_to_index_pair_iter(const GraphT& g, const VertexIndexMap& index,
+ Iter it) {
+ return boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>(it, edge_to_index_pair<GraphT, VertexIndexMap>(g, index));
+ }
+
} // namespace detail
+
+ template<typename Vertex, typename EdgeIndex>
+ struct hash<detail::csr_edge_descriptor<Vertex, EdgeIndex> >
+ {
+ std::size_t operator()
+ (detail::csr_edge_descriptor<Vertex, EdgeIndex> const& x) const
+ {
+ std::size_t hash = hash_value(x.src);
+ hash_combine(hash, x.idx);
+ return hash;
+ }
+ };
+
} // namespace boost
#endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
Modified: branches/release/boost/graph/detail/incremental_components.hpp
==============================================================================
--- branches/release/boost/graph/detail/incremental_components.hpp (original)
+++ branches/release/boost/graph/detail/incremental_components.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -1,6 +1,7 @@
//=======================================================================
// Copyright 2002 Indiana University.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -11,129 +12,64 @@
#define BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
#include <boost/operators.hpp>
-#include <boost/pending/disjoint_sets.hpp>
namespace boost {
namespace detail {
- //=========================================================================
- // Implementation detail of incremental_components
+ // Iterator for a component index linked list. The contents of
+ // each array element represent the next index in the list. A
+ // special value (the maximum index + 1) is used to terminate a
+ // list.
+ template <typename IndexRandomAccessIterator>
+ class component_index_iterator :
+ boost::forward_iterator_helper<component_index_iterator<IndexRandomAccessIterator>,
+ typename std::iterator_traits<IndexRandomAccessIterator>::value_type,
+ typename std::iterator_traits<IndexRandomAccessIterator>::difference_type,
+ typename std::iterator_traits<IndexRandomAccessIterator>::pointer,
+ typename std::iterator_traits<IndexRandomAccessIterator>::reference> {
+ private:
+ typedef component_index_iterator<IndexRandomAccessIterator> self;
- //-------------------------------------------------------------------------
- // Helper functions for the component_index class
-
- // Record the representative vertices in the header array.
- // Representative vertices now point to the component number.
-
- template <class Parent, class OutputIterator, class Integer>
- inline void
- build_components_header(Parent p,
- OutputIterator header,
- Integer num_nodes)
- {
- Parent component = p;
- Integer component_num = 0;
- for (Integer v = 0; v != num_nodes; ++v)
- if (p[v] == v) {
- *header++ = v;
- component[v] = component_num++;
- }
- }
-
-
- // Pushes x onto the front of the list. The list is represented in
- // an array.
- template <class Next, class T, class V>
- inline void array_push_front(Next next, T& head, V x)
- {
- T tmp = head;
- head = x;
- next[x] = tmp;
- }
-
-
- // Create a linked list of the vertices in each component
- // by reusing the representative array.
- template <class Parent1, class Parent2,
- class Integer>
- void
- link_components(Parent1 component, Parent2 header,
- Integer num_nodes, Integer num_components)
- {
- // Make the non-representative vertices point to their component
- Parent1 representative = component;
- for (Integer v = 0; v != num_nodes; ++v)
- if (component[v] >= num_components
- || header[component[v]] != v)
- component[v] = component[representative[v]];
-
- // initialize the "head" of the lists to "NULL"
- std::fill_n(header, num_components, num_nodes);
-
- // Add each vertex to the linked list for its component
- Parent1 next = component;
- for (Integer k = 0; k != num_nodes; ++k)
- array_push_front(next, header[component[k]], k);
- }
-
-
-
- template <class IndexContainer, class HeaderContainer>
- void
- construct_component_index(IndexContainer& index, HeaderContainer& header)
- {
- typedef typename IndexContainer::value_type Integer;
- build_components_header(index.begin(),
- std::back_inserter(header),
- Integer(index.end() - index.begin()));
-
- link_components(index.begin(), header.begin(),
- Integer(index.end() - index.begin()),
- Integer(header.end() - header.begin()));
- }
-
-
-
- template <class IndexIterator, class Integer, class Distance>
- class component_iterator
- : boost::forward_iterator_helper<
- component_iterator<IndexIterator,Integer,Distance>,
- Integer, Distance,Integer*, Integer&>
- {
public:
- typedef component_iterator self;
-
- IndexIterator next;
- Integer node;
-
typedef std::forward_iterator_tag iterator_category;
- typedef Integer value_type;
- typedef Integer& reference;
- typedef Integer* pointer;
- typedef Distance difference_type;
-
- component_iterator() {}
- component_iterator(IndexIterator x, Integer i)
- : next(x), node(i) {}
- Integer operator*() const {
- return node;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::value_type value_type;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::difference_type reference;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::pointer pointer;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::reference difference_type;
+
+ // Constructor for "begin" iterator
+ component_index_iterator(IndexRandomAccessIterator index_iterator,
+ value_type begin_index) :
+ m_index_iterator(index_iterator),
+ m_current_index(begin_index) { }
+
+ // Constructor for "end" iterator (end_index should be the linked
+ // list terminator).
+ component_index_iterator(value_type end_index) :
+ m_current_index(end_index) { }
+
+ inline value_type operator*() const {
+ return (m_current_index);
}
+
self& operator++() {
- node = next[node];
- return *this;
+ // Move to the next element in the linked list
+ m_current_index = m_index_iterator[m_current_index];
+ return (*this);
}
- };
-
- template <class IndexIterator, class Integer, class Distance>
- inline bool
- operator==(const component_iterator<IndexIterator, Integer, Distance>& x,
- const component_iterator<IndexIterator, Integer, Distance>& y)
- {
- return x.node == y.node;
- }
-
+
+ bool operator==(self& other_iterator) {
+ return (m_current_index == *other_iterator);
+ }
+
+ protected:
+ IndexRandomAccessIterator m_index_iterator;
+ value_type m_current_index;
+
+ }; // class component_index_iterator
+
} // namespace detail
} // namespace detail
Modified: branches/release/boost/graph/detail/indexed_properties.hpp
==============================================================================
--- branches/release/boost/graph/detail/indexed_properties.hpp (original)
+++ branches/release/boost/graph/detail/indexed_properties.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -179,6 +179,10 @@
m_edge_properties.begin() + dest_begin + (src_end - src_begin));
}
+ typedef typename std::vector<Property>::iterator iterator;
+ iterator begin() {return m_edge_properties.begin();}
+ iterator end() {return m_edge_properties.end();}
+
private:
// Access to the derived object
Derived& derived() { return *static_cast<Derived*>(this); }
@@ -190,6 +194,17 @@
std::vector<Property> m_edge_properties;
};
+struct dummy_no_property_iterator
+: public boost::iterator_facade<dummy_no_property_iterator, no_property, std::random_access_iterator_tag> {
+ mutable no_property prop;
+ no_property& dereference() const {return prop;}
+ bool equal(const dummy_no_property_iterator&) const {return true;}
+ void increment() {}
+ void decrement() {}
+ void advance(std::ptrdiff_t) {}
+ std::ptrdiff_t distance_to(const dummy_no_property_iterator) const {return 0;}
+};
+
template<typename Derived, typename Descriptor>
class indexed_edge_properties<Derived, void, Descriptor>
{
@@ -216,6 +231,10 @@
void push_back(const edge_push_back_type&) { }
void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {}
+ typedef dummy_no_property_iterator iterator;
+ iterator begin() {return dummy_no_property_iterator();}
+ iterator end() {return dummy_no_property_iterator();}
+
};
}
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-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -87,7 +87,7 @@
get_owner_of_first_tuple_element(OwnerMap owner) : owner(owner) { }
- owner_type get_owner(Tuple t) { return boost::get(owner, get<0>(t)); }
+ owner_type get_owner(Tuple t) { return get(owner, get<0>(t)); }
private:
OwnerMap owner;
Modified: branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -48,11 +48,11 @@
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag {};
-template<typename Directed, typename VertexProperty, typename EdgeProperty,
+template<typename VertexProperty, typename EdgeProperty,
typename GraphProperty, typename ProcessGroup, typename InVertex,
typename InDistribution, typename InEdgeIndex>
class compressed_sparse_row_graph<
- Directed, VertexProperty, EdgeProperty, GraphProperty,
+ directedS, VertexProperty, EdgeProperty, GraphProperty,
distributedS<ProcessGroup, InVertex, InDistribution>,
InEdgeIndex>
{
@@ -84,7 +84,7 @@
/**
* The type of the CSR graph that will be stored locally.
*/
- typedef compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty,
+ typedef compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty,
GraphProperty, Vertex, EdgeIndex>
base_type;
@@ -471,7 +471,7 @@
* graph type.
*/
#define BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS \
- typename Directed, typename VertexProperty, typename EdgeProperty, \
+ typename VertexProperty, typename EdgeProperty, \
typename GraphProperty, typename ProcessGroup, typename InVertex, \
typename InDistribution, typename InEdgeIndex
@@ -487,7 +487,7 @@
*/
#define BOOST_DISTRIB_CSR_GRAPH_TYPE \
compressed_sparse_row_graph< \
- Directed, VertexProperty, EdgeProperty, GraphProperty, \
+ directedS, VertexProperty, EdgeProperty, GraphProperty, \
distributedS<ProcessGroup, InVertex, InDistribution>, \
InEdgeIndex>
@@ -525,8 +525,8 @@
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor ed;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator it;
edges_size_type u_local = get(vertex_local, g, u);
- edges_size_type u_row_start = g.base().m_rowstart[u_local];
- edges_size_type next_row_start = g.base().m_rowstart[u_local + 1];
+ edges_size_type u_row_start = g.base().m_forward.m_rowstart[u_local];
+ edges_size_type next_row_start = g.base().m_forward.m_rowstart[u_local + 1];
return std::make_pair(it(ed(u, u_row_start)),
it(ed(u, (std::max)(u_row_start, next_row_start))));
}
@@ -658,7 +658,7 @@
while (current_edge.idx == end_of_this_vertex && local_src < num_vertices(*graph)-1) {
++local_src;
current_edge.src = graph->local_to_global_vertex(local_src);
- end_of_this_vertex = graph->base().m_rowstart[local_src + 1];
+ end_of_this_vertex = graph->base().m_forward.m_rowstart[local_src + 1];
}
return *this;
}
@@ -680,7 +680,7 @@
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
num_edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
- return g.base().m_column.size();
+ return g.base().m_forward.m_column.size();
}
template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
@@ -691,14 +691,15 @@
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator ei;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
- if (g.base().m_rowstart.size() == 1 || g.base().m_column.empty()) {
+ if (g.base().m_forward.m_rowstart.size() == 1 ||
+ g.base().m_forward.m_column.empty()) {
return std::make_pair(ei(), ei());
} else {
// Find the first vertex that has outgoing edges
Vertex src = 0;
- while (g.base().m_rowstart[src + 1] == 0) ++src;
- return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_rowstart[src + 1]),
- ei(g, edgedesc(num_vertices(g), g.base().m_column.size()), 0));
+ while (g.base().m_forward.m_rowstart[src + 1] == 0) ++src;
+ return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_forward.m_rowstart[src + 1]),
+ ei(g, edgedesc(num_vertices(g), g.base().m_forward.m_column.size()), 0));
}
}
@@ -708,6 +709,26 @@
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Returns true if a vertex belongs to a process according to a distribution
template <typename OwnerMap, typename ProcessId>
+struct local_vertex {
+
+ local_vertex(OwnerMap owner, ProcessId id)
+ : owner(owner), id(id) {}
+
+ template <typename Vertex>
+ bool operator()(Vertex x)
+ { return get(owner, x) == id; }
+
+ template <typename Vertex>
+ bool operator()(Vertex x) const
+ { return get(owner, x) == id; }
+
+private:
+ OwnerMap owner;
+ ProcessId id;
+};
+
+// Returns true if a vertex belongs to a process according to a distribution
+template <typename OwnerMap, typename ProcessId>
struct local_edge {
local_edge(OwnerMap owner, ProcessId id)
@@ -827,8 +848,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -848,8 +869,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -870,8 +891,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -894,8 +915,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -914,8 +935,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -935,8 +956,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -958,8 +979,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
ep_iter,
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -982,8 +1003,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
ep_iter,
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -1004,8 +1025,8 @@
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1026,8 +1047,8 @@
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1050,8 +1071,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1075,8 +1096,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1216,8 +1237,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
@@ -1263,8 +1284,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
{
@@ -1308,8 +1329,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
{
@@ -1354,8 +1375,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
{
@@ -1494,8 +1515,8 @@
std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
std::pair<adj_iter, adj_iter> adjacencies =
std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
- EdgeIndex idx_begin = adjacencies.first - g.base().m_column.begin();
- EdgeIndex idx_end = adjacencies.second - g.base().m_column.begin();
+ EdgeIndex idx_begin = adjacencies.first - g.base().m_forward.m_column.begin();
+ EdgeIndex idx_end = adjacencies.second - g.base().m_forward.m_column.begin();
return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
out_edge_iter(edge_desc(i, idx_end)));
}
@@ -1835,7 +1856,7 @@
// Readable Property Map concept requirements
typedef std::pair<ProcessID, EdgeIndex> value_type;
typedef value_type reference;
- typedef csr_edge_descriptor<Vertex, EdgeIndex> key_type;
+ typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> key_type;
typedef readable_property_map_tag category;
};
@@ -2123,21 +2144,21 @@
namespace mpi {
template<typename Vertex, typename EdgeIndex>
- struct is_mpi_datatype<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct is_mpi_datatype<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::true_ { };
}
namespace serialization {
template<typename Vertex, typename EdgeIndex>
- struct is_bitwise_serializable<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct is_bitwise_serializable<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::true_ { };
template<typename Vertex, typename EdgeIndex>
- struct implementation_level<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct implementation_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::int_<object_serializable> {} ;
template<typename Vertex, typename EdgeIndex>
- struct tracking_level<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct tracking_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::int_<track_never> {} ;
}
Modified: branches/release/boost/graph/erdos_renyi_generator.hpp
==============================================================================
--- branches/release/boost/graph/erdos_renyi_generator.hpp (original)
+++ branches/release/boost/graph/erdos_renyi_generator.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -125,7 +125,7 @@
: gen(), rand_vertex(1. - prob), n(n), allow_self_loops(loops), src(0)
, tgt_index(vertices_size_type(-1)), prob(prob)
{
- this->gen.reset(new uniform_01<RandomGenerator>(gen));
+ this->gen.reset(new uniform_01<RandomGenerator*>(&gen));
if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
next();
@@ -181,7 +181,7 @@
if (src == n) src = (std::numeric_limits<vertices_size_type>::max)();
}
- shared_ptr<uniform_01<RandomGenerator> > gen;
+ shared_ptr<uniform_01<RandomGenerator*> > gen;
geometric_distribution<vertices_size_type> rand_vertex;
vertices_size_type n;
bool allow_self_loops;
Modified: branches/release/boost/graph/fruchterman_reingold.hpp
==============================================================================
--- branches/release/boost/graph/fruchterman_reingold.hpp (original)
+++ branches/release/boost/graph/fruchterman_reingold.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -23,8 +23,6 @@
namespace boost {
- bool vertex_migration = false;
-
struct square_distance_attractive_force {
template<typename Graph, typename T>
T
@@ -120,9 +118,9 @@
vertex_iterator v, v_end;
for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
std::size_t column =
- std::size_t((position[*v][0] + topology.extent()[0] / 2) / two_k);
+ std::size_t((get(position, *v)[0] + topology.extent()[0] / 2) / two_k);
std::size_t row =
- std::size_t((position[*v][1] + topology.extent()[1] / 2) / two_k);
+ std::size_t((get(position, *v)[1] + topology.extent()[1] / 2) / two_k);
if (column >= columns) column = columns - 1;
if (row >= rows) row = rows - 1;
@@ -154,7 +152,8 @@
bucket_t& other_bucket
= buckets[other_row * columns + other_column];
for (v = other_bucket.begin(); v != other_bucket.end(); ++v) {
- double dist = topology.distance(position[*u], position[*v]);
+ double dist =
+ topology.distance(get(position, *u), get(position, *v));
if (dist < two_k) apply_force(*u, *v);
}
}
@@ -186,10 +185,10 @@
typedef typename Topology::point_difference_type point_difference_type;
// Find min/max ranges
- Point min_point = position[*vertices(g).first], max_point = min_point;
+ Point min_point = get(position, *vertices(g).first), max_point = min_point;
BGL_FORALL_VERTICES_T(v, g, Graph) {
- min_point = topology.pointwise_min(min_point, position[v]);
- max_point = topology.pointwise_max(max_point, position[v]);
+ min_point = topology.pointwise_min(min_point, get(position, v));
+ max_point = topology.pointwise_max(max_point, get(position, v));
}
Point old_origin = topology.move_position_toward(min_point, 0.5, max_point);
@@ -199,21 +198,24 @@
// Scale to bounding box provided
BGL_FORALL_VERTICES_T(v, g, Graph) {
- point_difference_type relative_loc = topology.difference(position[v], old_origin);
+ point_difference_type relative_loc = topology.difference(get(position, v), old_origin);
relative_loc = (relative_loc / old_size) * new_size;
- position[v] = topology.adjust(new_origin, relative_loc);
+ put(position, v, topology.adjust(new_origin, relative_loc));
}
}
namespace detail {
- template<typename Topology>
+ template<typename Topology, typename PropMap, typename Vertex>
void
maybe_jitter_point(const Topology& topology,
- typename Topology::point_type& p1, const typename Topology::point_type& p2)
+ const PropMap& pm, Vertex v,
+ const typename Topology::point_type& p2)
{
double too_close = topology.norm(topology.extent()) / 10000.;
- if (topology.distance(p1, p2) < too_close) {
- p1 = topology.move_position_toward(p1, 1./200, topology.random_point());
+ if (topology.distance(get(pm, v), p2) < too_close) {
+ put(pm, v,
+ topology.move_position_toward(get(pm, v), 1./200,
+ topology.random_point()));
}
}
@@ -238,18 +240,20 @@
if (u != v) {
// When the vertices land on top of each other, move the
// first vertex away from the boundaries.
- maybe_jitter_point(topology, position[u], position[v]);
+ maybe_jitter_point(topology, position, u, get(position, v));
- double dist = topology.distance(position[u], position[v]);
+ double dist = topology.distance(get(position, u), get(position, v));
+ typename Topology::point_difference_type dispv = get(displacement, v);
if (dist == 0.) {
for (std::size_t i = 0; i < Point::dimensions; ++i) {
- displacement[v][i] += 0.01;
+ dispv[i] += 0.01;
}
} else {
double fr = repulsive_force(u, v, k, dist, g);
- typename Topology::point_difference_type dispv = displacement[v];
- dispv += (fr / dist) * topology.difference(position[v], position[u]);
+ dispv += (fr / dist) *
+ topology.difference(get(position, v), get(position, u));
}
+ put(displacement, v, dispv);
}
}
@@ -296,7 +300,7 @@
// Calculate repulsive forces
vertex_iterator v, v_end;
for (tie(v, v_end) = vertices(g); v != v_end; ++v)
- displacement[*v] = typename Topology::point_difference_type();
+ put(displacement, *v, typename Topology::point_difference_type());
force_pairs(g, apply_force);
// Calculate attractive forces
@@ -307,14 +311,15 @@
// When the vertices land on top of each other, move the
// first vertex away from the boundaries.
- ::boost::detail::maybe_jitter_point(topology, position[u], position[v]);
+ ::boost::detail::maybe_jitter_point(topology, position, u, get(position, v));
- typename Topology::point_difference_type delta = topology.difference(position[v], position[u]);
- double dist = topology.distance(position[u], position[v]);
+ typename Topology::point_difference_type delta =
+ topology.difference(get(position, v), get(position, u));
+ double dist = topology.distance(get(position, u), get(position, v));
double fa = attractive_force(*e, k, dist, g);
- displacement[v] -= (fa / dist) * delta;
- displacement[u] += (fa / dist) * delta;
+ put(displacement, v, get(displacement, v) - (fa / dist) * delta);
+ put(displacement, u, get(displacement, u) + (fa / dist) * delta);
}
if (double temp = cool()) {
@@ -322,16 +327,9 @@
BGL_FORALL_VERTICES_T (v, g, Graph) {
BOOST_USING_STD_MIN();
BOOST_USING_STD_MAX();
- double disp_size = topology.norm(displacement[v]);
- position[v] = topology.adjust(position[v], displacement[v] * (min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp) / disp_size));
- position[v] = topology.bound(position[v]);
-#if 0
- // CEM HACK: Jitter if we're on the edges
- if(position[v].x == 1.0f) // origin.x + extent.x)
- position[v].x -= drand48() * .1 * extent.x;
- else if(position[v].x == -1.0f) // origin.x)
- position[v].x += drand48() * .1 * extent.x;
-#endif
+ double disp_size = topology.norm(get(displacement, v));
+ put(position, v, topology.adjust(get(position, v), get(displacement, v) * (min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp) / disp_size)));
+ put(position, v, topology.bound(get(position, v)));
}
} else {
break;
Copied: branches/release/boost/graph/grid_graph.hpp (from r55473, /trunk/boost/graph/grid_graph.hpp)
==============================================================================
--- /trunk/boost/graph/grid_graph.hpp (original)
+++ branches/release/boost/graph/grid_graph.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -18,7 +18,6 @@
#include <boost/bind.hpp>
#include <boost/limits.hpp>
#include <boost/make_shared.hpp>
-#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/iterator/counting_iterator.hpp>
@@ -32,8 +31,13 @@
#define BOOST_GRID_GRAPH_TYPE \
grid_graph<DimensionsT, VertexIndexT, EdgeIndexT>
+#define BOOST_GRID_GRAPH_TYPE_MEM typename BOOST_GRID_GRAPH_TYPE::
+
+#define BOOST_GRID_GRAPH_TYPE_TD(mem) \
+ typedef typename BOOST_GRID_GRAPH_TYPE::mem mem
+
#define BOOST_GRID_GRAPH_TRAITS_T \
- typename graph_traits<BOOST_GRID_GRAPH_TYPE>
+ typename graph_traits<BOOST_GRID_GRAPH_TYPE >
namespace boost {
@@ -85,6 +89,127 @@
typedef type const_type;
};
+ //=================
+ // Function Objects
+ //=================
+
+ namespace detail {
+
+ // vertex_at
+ template <typename Graph>
+ struct grid_graph_vertex_at {
+
+ typedef typename graph_traits<Graph>::vertex_descriptor result_type;
+
+ grid_graph_vertex_at(const Graph* graph) :
+ m_graph(graph) { }
+
+ result_type
+ operator()
+ (typename graph_traits<Graph>::vertices_size_type vertex_index) const {
+ return (vertex(vertex_index, *m_graph));
+ }
+
+ private:
+ const Graph* m_graph;
+ };
+
+ // out_edge_at
+ template <typename Graph>
+ struct grid_graph_out_edge_at {
+
+ private:
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+ public:
+ typedef typename graph_traits<Graph>::edge_descriptor result_type;
+
+ grid_graph_out_edge_at(vertex_descriptor source_vertex,
+ const Graph* graph) :
+ m_vertex(source_vertex),
+ m_graph(graph) { }
+
+ result_type
+ operator()
+ (typename graph_traits<Graph>::degree_size_type out_edge_index) const {
+ return (out_edge_at(m_vertex, out_edge_index, *m_graph));
+ }
+
+ private:
+ vertex_descriptor m_vertex;
+ const Graph* m_graph;
+ };
+
+ // in_edge_at
+ template <typename Graph>
+ struct grid_graph_in_edge_at {
+
+ private:
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+
+ public:
+ typedef typename graph_traits<Graph>::edge_descriptor result_type;
+
+ grid_graph_in_edge_at(vertex_descriptor target_vertex,
+ const Graph* graph) :
+ m_vertex(target_vertex),
+ m_graph(graph) { }
+
+ result_type
+ operator()
+ (typename graph_traits<Graph>::degree_size_type in_edge_index) const {
+ return (in_edge_at(m_vertex, in_edge_index, *m_graph));
+ }
+
+ private:
+ vertex_descriptor m_vertex;
+ const Graph* m_graph;
+ };
+
+ // edge_at
+ template <typename Graph>
+ struct grid_graph_edge_at {
+
+ typedef typename graph_traits<Graph>::edge_descriptor result_type;
+
+ grid_graph_edge_at(const Graph* graph) :
+ m_graph(graph) { }
+
+ result_type
+ operator()
+ (typename graph_traits<Graph>::edges_size_type edge_index) const {
+ return (edge_at(edge_index, *m_graph));
+ }
+
+ private:
+ const Graph* m_graph;
+ };
+
+ // adjacent_vertex_at
+ template <typename Graph>
+ struct grid_graph_adjacent_vertex_at {
+
+ public:
+ typedef typename graph_traits<Graph>::vertex_descriptor result_type;
+
+ grid_graph_adjacent_vertex_at(result_type source_vertex,
+ const Graph* graph) :
+ m_vertex(source_vertex),
+ m_graph(graph) { }
+
+ result_type
+ operator()
+ (typename graph_traits<Graph>::degree_size_type adjacent_index) const {
+ return (target(out_edge_at(m_vertex, adjacent_index, *m_graph), *m_graph));
+ }
+
+ private:
+ result_type m_vertex;
+ const Graph* m_graph;
+ };
+
+ }; // namespace detail
+
//===========
// Grid Graph
//===========
@@ -113,25 +238,26 @@
// vertex_iterator
typedef counting_iterator<vertices_size_type> vertex_index_iterator;
- typedef boost::function<vertex_descriptor (vertices_size_type)> vertex_function;
+ typedef detail::grid_graph_vertex_at<type> vertex_function;
typedef transform_iterator<vertex_function, vertex_index_iterator> vertex_iterator;
// edge_iterator
typedef counting_iterator<edges_size_type> edge_index_iterator;
- typedef boost::function<edge_descriptor (edges_size_type)> edge_function;
+ typedef detail::grid_graph_edge_at<type> edge_function;
typedef transform_iterator<edge_function, edge_index_iterator> edge_iterator;
// out_edge_iterator
typedef counting_iterator<degree_size_type> degree_iterator;
- typedef boost::function<edge_descriptor (degree_size_type)> degree_function;
- typedef transform_iterator<degree_function, degree_iterator> out_edge_iterator;
+ typedef detail::grid_graph_out_edge_at<type> out_edge_function;
+ typedef transform_iterator<out_edge_function, degree_iterator> out_edge_iterator;
// in_edge_iterator
- typedef transform_iterator<degree_function, degree_iterator> in_edge_iterator;
+ typedef detail::grid_graph_in_edge_at<type> in_edge_function;
+ typedef transform_iterator<in_edge_function, degree_iterator> in_edge_iterator;
// adjacency_iterator
- typedef typename adjacency_iterator_generator<type,
- vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
+ typedef detail::grid_graph_adjacent_vertex_at<type> adjacent_vertex_function;
+ typedef transform_iterator<adjacent_vertex_function, degree_iterator> adjacency_iterator;
// categories
typedef undirected_tag directed_category;
@@ -304,7 +430,7 @@
// dependent upon dimension wrapping.
edge_descriptor edge_at(edges_size_type edge_index) const {
- // Edge indicies are sorted into bins by dimension
+ // Edge indices are sorted into bins by dimension
std::size_t dimension_index = 0;
edges_size_type dimension_edges = num_edges(0);
@@ -474,7 +600,7 @@
return (out_edge_count);
}
- // Returns an out-edge for [vertex] by index. Indicies are in the
+ // Returns an out-edge for [vertex] by index. Indices are in the
// range [0, out_degree(vertex)).
edge_descriptor out_edge_at
(vertex_descriptor vertex,
@@ -522,7 +648,7 @@
return (out_degree(vertex));
}
- // Returns an in-edge for [vertex] by index. Indicies are in the
+ // Returns an in-edge for [vertex] by index. Indices are in the
// range [0, in_degree(vertex)).
edge_descriptor in_edge_at
(vertex_descriptor vertex,
@@ -573,30 +699,29 @@
//================
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline std::pair<vertex_iterator, vertex_iterator>
+ friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM vertex_iterator,
+ BOOST_GRID_GRAPH_TYPE_MEM vertex_iterator>
vertices(const BOOST_GRID_GRAPH_TYPE& graph) {
-
- typedef boost::function<vertex_descriptor (vertices_size_type)>
- vertex_function;
-
- vertex_function transform_function =
- boost::bind(&BOOST_GRID_GRAPH_TYPE::vertex_at, boost::cref(graph), _1);
+ BOOST_GRID_GRAPH_TYPE_TD(vertex_iterator);
+ BOOST_GRID_GRAPH_TYPE_TD(vertex_function);
+ BOOST_GRID_GRAPH_TYPE_TD(vertex_index_iterator);
return (std::make_pair
- (vertex_iterator(vertex_index_iterator(0), transform_function),
+ (vertex_iterator(vertex_index_iterator(0),
+ vertex_function(&graph)),
vertex_iterator(vertex_index_iterator(graph.num_vertices()),
- transform_function)));
+ vertex_function(&graph))));
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline vertices_size_type
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type
num_vertices(const BOOST_GRID_GRAPH_TYPE& graph) {
return (graph.num_vertices());
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline vertex_descriptor
- vertex(vertices_size_type vertex_index,
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor
+ vertex(BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type vertex_index,
const BOOST_GRID_GRAPH_TYPE& graph) {
return (graph.vertex_at(vertex_index));
@@ -607,44 +732,55 @@
//===============
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline std::pair<out_edge_iterator, out_edge_iterator>
- out_edges(vertex_descriptor vertex,
+ friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM out_edge_iterator,
+ BOOST_GRID_GRAPH_TYPE_MEM out_edge_iterator>
+ out_edges(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
const BOOST_GRID_GRAPH_TYPE& graph) {
-
- typedef boost::function<edge_descriptor (degree_size_type)>
- out_edge_at_function;
-
- out_edge_at_function transform_function =
- boost::bind(&BOOST_GRID_GRAPH_TYPE::out_edge_at,
- boost::cref(graph), vertex, _1);
+ BOOST_GRID_GRAPH_TYPE_TD(degree_iterator);
+ BOOST_GRID_GRAPH_TYPE_TD(out_edge_function);
+ BOOST_GRID_GRAPH_TYPE_TD(out_edge_iterator);
return (std::make_pair
- (out_edge_iterator(degree_iterator(0), transform_function),
+ (out_edge_iterator(degree_iterator(0),
+ out_edge_function(vertex, &graph)),
out_edge_iterator(degree_iterator(graph.out_degree(vertex)),
- transform_function)));
+ out_edge_function(vertex, &graph))));
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline degree_size_type out_degree
- (vertex_descriptor vertex, const BOOST_GRID_GRAPH_TYPE& graph) {
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type
+ out_degree
+ (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
return (graph.out_degree(vertex));
}
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor
+ out_edge_at(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
+ BOOST_GRID_GRAPH_TYPE_MEM degree_size_type out_edge_index,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.out_edge_at(vertex, out_edge_index));
+ }
+
//===============
// AdjacencyGraph
//===============
template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend typename std::pair<adjacency_iterator, adjacency_iterator>
- adjacent_vertices (vertex_descriptor vertex,
+ friend typename std::pair<BOOST_GRID_GRAPH_TYPE_MEM adjacency_iterator,
+ BOOST_GRID_GRAPH_TYPE_MEM adjacency_iterator>
+ adjacent_vertices (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
const BOOST_GRID_GRAPH_TYPE& graph) {
-
- out_edge_iterator out_edge_start, out_edge_end;
- tie(out_edge_start, out_edge_end) = out_edges(vertex, graph);
+ BOOST_GRID_GRAPH_TYPE_TD(degree_iterator);
+ BOOST_GRID_GRAPH_TYPE_TD(adjacent_vertex_function);
+ BOOST_GRID_GRAPH_TYPE_TD(adjacency_iterator);
return (std::make_pair
- (adjacency_iterator(out_edge_start, &graph),
- adjacency_iterator(out_edge_end, &graph)));
+ (adjacency_iterator(degree_iterator(0),
+ adjacent_vertex_function(vertex, &graph)),
+ adjacency_iterator(degree_iterator(graph.out_degree(vertex)),
+ adjacent_vertex_function(vertex, &graph))));
}
//==============
@@ -652,32 +788,31 @@
//==============
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline edges_size_type
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM edges_size_type
num_edges(const BOOST_GRID_GRAPH_TYPE& graph) {
return (graph.num_edges());
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline edge_descriptor
- edge_at(edges_size_type edge_index,
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor
+ edge_at(BOOST_GRID_GRAPH_TYPE_MEM edges_size_type edge_index,
const BOOST_GRID_GRAPH_TYPE& graph) {
return (graph.edge_at(edge_index));
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline std::pair<edge_iterator, edge_iterator>
+ friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_iterator,
+ BOOST_GRID_GRAPH_TYPE_MEM edge_iterator>
edges(const BOOST_GRID_GRAPH_TYPE& graph) {
-
- typedef boost::function<edge_descriptor (edges_size_type)>
- edge_at_function;
-
- edge_at_function transform_function =
- boost::bind(&BOOST_GRID_GRAPH_TYPE::edge_at, boost::cref(graph), _1);
+ BOOST_GRID_GRAPH_TYPE_TD(edge_index_iterator);
+ BOOST_GRID_GRAPH_TYPE_TD(edge_function);
+ BOOST_GRID_GRAPH_TYPE_TD(edge_iterator);
return (std::make_pair
- (edge_iterator(edge_index_iterator(0), transform_function),
+ (edge_iterator(edge_index_iterator(0),
+ edge_function(&graph)),
edge_iterator(edge_index_iterator(graph.num_edges()),
- transform_function)));
+ edge_function(&graph))));
}
//===================
@@ -685,56 +820,64 @@
//===================
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline std::pair<in_edge_iterator, in_edge_iterator>
- in_edges(vertex_descriptor vertex,
+ friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM in_edge_iterator,
+ BOOST_GRID_GRAPH_TYPE_MEM in_edge_iterator>
+ in_edges(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
const BOOST_GRID_GRAPH_TYPE& graph) {
-
- typedef boost::function<edge_descriptor (degree_size_type)>
- in_edge_at_function;
-
- in_edge_at_function transform_function =
- boost::bind(&BOOST_GRID_GRAPH_TYPE::in_edge_at,
- boost::cref(graph), vertex, _1);
+ BOOST_GRID_GRAPH_TYPE_TD(in_edge_function);
+ BOOST_GRID_GRAPH_TYPE_TD(degree_iterator);
+ BOOST_GRID_GRAPH_TYPE_TD(in_edge_iterator);
return (std::make_pair
- (in_edge_iterator(degree_iterator(0), transform_function),
+ (in_edge_iterator(degree_iterator(0),
+ in_edge_function(vertex, &graph)),
in_edge_iterator(degree_iterator(graph.in_degree(vertex)),
- transform_function)));
+ in_edge_function(vertex, &graph))));
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline degree_size_type
- in_degree (vertex_descriptor vertex,
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type
+ in_degree (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
const BOOST_GRID_GRAPH_TYPE& graph) {
return (graph.in_degree(vertex));
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline degree_size_type
- degree (vertex_descriptor vertex,
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type
+ degree (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
const BOOST_GRID_GRAPH_TYPE& graph) {
return (graph.out_degree(vertex) * 2);
}
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor
+ in_edge_at(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex,
+ BOOST_GRID_GRAPH_TYPE_MEM degree_size_type in_edge_index,
+ const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (graph.in_edge_at(vertex, in_edge_index));
+ }
+
+
//==================
// Adjacency Matrix
//==================
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend std::pair<edge_descriptor, bool>
- edge (vertex_descriptor source_vertex,
- vertex_descriptor destination_vertex,
+ friend std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, bool>
+ edge (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor source_vertex,
+ BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor destination_vertex,
const BOOST_GRID_GRAPH_TYPE& graph) {
- std::pair<edge_descriptor, bool> edge_exists =
+ std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, bool> edge_exists =
std::make_pair(std::make_pair(source_vertex, destination_vertex), false);
for (std::size_t dimension_index = 0;
dimension_index < Dimensions;
++dimension_index) {
- vertices_size_type dim_difference = 0;
- vertices_size_type source_dim = source_vertex[dimension_index],
+ BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type dim_difference = 0;
+ BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type
+ source_dim = source_vertex[dimension_index],
dest_dim = destination_vertex[dimension_index];
dim_difference = (source_dim > dest_dim) ?
@@ -781,37 +924,43 @@
//=============================
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline vertices_size_type
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type
get(vertex_index_t,
const BOOST_GRID_GRAPH_TYPE& graph,
- vertex_descriptor vertex) {
+ BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex) {
return (graph.index_of(vertex));
}
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline edges_size_type
+ friend inline BOOST_GRID_GRAPH_TYPE_MEM edges_size_type
get(edge_index_t,
const BOOST_GRID_GRAPH_TYPE& graph,
- edge_descriptor edge) {
+ BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor edge) {
return (graph.index_of(edge));
}
template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
- vertex_descriptor,
- vertices_size_type>
+ friend inline grid_graph_index_map<
+ BOOST_GRID_GRAPH_TYPE,
+ BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor,
+ BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type>
get(vertex_index_t, const BOOST_GRID_GRAPH_TYPE& graph) {
- return (grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
- vertex_descriptor, vertices_size_type>(graph));
+ return (grid_graph_index_map<
+ BOOST_GRID_GRAPH_TYPE,
+ BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor,
+ BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type>(graph));
}
template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
- friend inline grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
- edge_descriptor,
- edges_size_type>
+ friend inline grid_graph_index_map<
+ BOOST_GRID_GRAPH_TYPE,
+ BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor,
+ BOOST_GRID_GRAPH_TYPE_MEM edges_size_type>
get(edge_index_t, const BOOST_GRID_GRAPH_TYPE& graph) {
- return (grid_graph_index_map<BOOST_GRID_GRAPH_TYPE,
- edge_descriptor, edges_size_type>(graph));
+ return (grid_graph_index_map<
+ BOOST_GRID_GRAPH_TYPE,
+ BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor,
+ BOOST_GRID_GRAPH_TYPE_MEM edges_size_type>(graph));
}
template<typename Graph,
@@ -834,6 +983,8 @@
} // namespace boost
#undef BOOST_GRID_GRAPH_TYPE
+#undef BOOST_GRID_GRAPH_TYPE_TD
+#undef BOOST_GRID_GRAPH_TYPE_MEM
#undef BOOST_GRID_GRAPH_TEMPLATE_PARAMS
#undef BOOST_GRID_GRAPH_TRAITS_T
Modified: branches/release/boost/graph/incremental_components.hpp
==============================================================================
--- branches/release/boost/graph/incremental_components.hpp (original)
+++ branches/release/boost/graph/incremental_components.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -1,7 +1,8 @@
//
//=======================================================================
// Copyright 1997-2001 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -14,6 +15,9 @@
#include <boost/detail/iterator.hpp>
#include <boost/graph/detail/incremental_components.hpp>
+#include <boost/iterator/counting_iterator.hpp>
+#include <boost/make_shared.hpp>
+#include <boost/pending/disjoint_sets.hpp>
namespace boost {
@@ -42,11 +46,6 @@
// similar to the algorithm described in Ch. 22 of "Intro to
// Algorithms" by Cormen, et. all.
//
- // RankContainer is a random accessable container (operator[] is
- // defined) with a value type that can represent an integer part of
- // a binary log of the value type of the corresponding
- // ParentContainer (char is always enough) its size_type is no less
- // than the size_type of the corresponding ParentContainer
// An implementation of disjoint sets can be found in
// boost/pending/disjoint_sets.hpp
@@ -101,70 +100,131 @@
return ds.find_set(u) == ds.find_set(v);
}
- // considering changing the so that it initializes with a pair of
- // vertex iterators and a parent PA.
-
- template <class IndexT>
- class component_index
- {
- public://protected: (avoid friends for now)
- typedef std::vector<IndexT> MyIndexContainer;
- MyIndexContainer header;
- MyIndexContainer index;
- typedef typename MyIndexContainer::size_type SizeT;
- typedef typename MyIndexContainer::const_iterator IndexIter;
+ // Class that builds a quick-access indexed linked list that allows
+ // for fast iterating through a parent component's children.
+ template <typename IndexType>
+ class component_index {
+
+ private:
+ typedef std::vector<IndexType> IndexContainer;
+
public:
- typedef detail::component_iterator<IndexIter, IndexT, SizeT>
+ typedef counting_iterator<IndexType> iterator;
+ typedef iterator const_iterator;
+ typedef IndexType value_type;
+ typedef IndexType size_type;
+
+ typedef detail::component_index_iterator<typename IndexContainer::iterator>
component_iterator;
- class component {
- friend class component_index;
- protected:
- IndexT number;
- const component_index<IndexT>* comp_ind_ptr;
- component(IndexT i, const component_index<IndexT>* p)
- : number(i), comp_ind_ptr(p) {}
- public:
- typedef component_iterator iterator;
- typedef component_iterator const_iterator;
- typedef IndexT value_type;
- iterator begin() const {
- return iterator( comp_ind_ptr->index.begin(),
- (comp_ind_ptr->header)[number] );
- }
- iterator end() const {
- return iterator( comp_ind_ptr->index.begin(),
- comp_ind_ptr->index.size() );
- }
- };
- typedef SizeT size_type;
- typedef component value_type;
-
-#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
- template <class Iterator>
- component_index(Iterator first, Iterator last)
- : index(std::distance(first, last))
- {
- std::copy(first, last, index.begin());
- detail::construct_component_index(index, header);
+
+ public:
+ template <typename ParentIterator,
+ typename ElementIndexMap>
+ component_index(ParentIterator parent_start,
+ ParentIterator parent_end,
+ const ElementIndexMap& index_map) :
+ m_num_elements(std::distance(parent_start, parent_end)),
+ m_components(make_shared<IndexContainer>()),
+ m_index_list(make_shared<IndexContainer>(m_num_elements)) {
+
+ build_index_lists(parent_start, index_map);
+
+ } // component_index
+
+ template <typename ParentIterator>
+ component_index(ParentIterator parent_start,
+ ParentIterator parent_end) :
+ m_num_elements(std::distance(parent_start, parent_end)),
+ m_components(make_shared<IndexContainer>()),
+ m_index_list(make_shared<IndexContainer>(m_num_elements)) {
+
+ build_index_lists(parent_start, boost::identity_property_map());
+
+ } // component_index
+
+ // Returns the number of components
+ inline std::size_t size() const {
+ return (m_components->size());
}
-#else
- template <class Iterator>
- component_index(Iterator first, Iterator last)
- : index(first, last)
- {
- detail::construct_component_index(index, header);
+
+ // Beginning iterator for component indices
+ iterator begin() const {
+ return (iterator(0));
}
-#endif
- component operator[](IndexT i) const {
- return component(i, this);
+ // End iterator for component indices
+ iterator end() const {
+ return (iterator(this->size()));
}
- SizeT size() const {
- return header.size();
+
+ // Returns a pair of begin and end iterators for the child
+ // elements of component [component_index].
+ std::pair<component_iterator, component_iterator>
+ operator[](IndexType component_index) const {
+
+ IndexType first_index = (*m_components)[component_index];
+
+ return (std::make_pair
+ (component_iterator(m_index_list->begin(), first_index),
+ component_iterator(m_num_elements)));
}
-
- };
+ private:
+ template <typename ParentIterator,
+ typename ElementIndexMap>
+ void build_index_lists(ParentIterator parent_start,
+ const ElementIndexMap& index_map) {
+
+ typedef typename ParentIterator::value_type Element;
+ typename IndexContainer::iterator index_list =
+ m_index_list->begin();
+
+ // First pass - find root elements, construct index list
+ for (IndexType element_index = 0; element_index < m_num_elements;
+ ++element_index) {
+
+ Element parent_element = parent_start[element_index];
+ IndexType parent_index = get(index_map, parent_element);
+
+ if (element_index != parent_index) {
+ index_list[element_index] = parent_index;
+ }
+ else {
+ m_components->push_back(element_index);
+
+ // m_num_elements is the linked list terminator
+ index_list[element_index] = m_num_elements;
+ }
+ }
+
+ // Second pass - build linked list
+ for (IndexType element_index = 0; element_index < m_num_elements;
+ ++element_index) {
+
+ Element parent_element = parent_start[element_index];
+ IndexType parent_index = get(index_map, parent_element);
+
+ if (element_index != parent_index) {
+
+ // Follow list until a component parent is found
+ while (index_list[parent_index] != m_num_elements) {
+ parent_index = index_list[parent_index];
+ }
+
+ // Push element to the front of the linked list
+ index_list[element_index] = index_list[parent_index];
+ index_list[parent_index] = element_index;
+ }
+ }
+
+ } // build_index_lists
+
+ protected:
+ IndexType m_num_elements;
+ shared_ptr<IndexContainer> m_components, m_index_list;
+
+ }; // class component_index
+
} // namespace boost
#endif // BOOST_INCREMENTAL_COMPONENTS_HPP
Modified: branches/release/boost/graph/properties.hpp
==============================================================================
--- branches/release/boost/graph/properties.hpp (original)
+++ branches/release/boost/graph/properties.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -387,7 +387,7 @@
namespace detail {
template<typename VertexBundle, typename EdgeBundle, typename Bundle>
struct is_vertex_bundle
- : mpl::and_<is_convertible<Bundle*, VertexBundle*>,
+ : mpl::and_<is_convertible<VertexBundle*, Bundle*>,
mpl::and_<mpl::not_<is_void<VertexBundle> >,
mpl::not_<is_same<VertexBundle, no_property> > > >
{ };
Modified: branches/release/boost/property_map/property_map.hpp
==============================================================================
--- branches/release/boost/property_map/property_map.hpp (original)
+++ branches/release/boost/property_map/property_map.hpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -581,6 +581,22 @@
value_type c;
};
+ // Convert a Readable property map into a function object
+ template <typename PropMap>
+ class property_map_function {
+ PropMap pm;
+ typedef typename property_traits<PropMap>::key_type param_type;
+ public:
+ explicit property_map_function(const PropMap& pm): pm(pm) {}
+ typedef typename property_traits<PropMap>::value_type result_type;
+ result_type operator()(const param_type& k) const {return get(pm, k);}
+ };
+
+ template <typename PropMap>
+ property_map_function<PropMap>
+ make_property_map_function(const PropMap& pm) {
+ return property_map_function<PropMap>(pm);
+ }
} // namespace boost
Modified: branches/release/libs/graph/doc/BUILD_DOCS.sh
==============================================================================
--- branches/release/libs/graph/doc/BUILD_DOCS.sh (original)
+++ branches/release/libs/graph/doc/BUILD_DOCS.sh 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -10,3 +10,4 @@
for i in read_graphml read_graphviz write_graphml; do
rst2html.py -gdt --link-stylesheet --traceback --trim-footnote-reference-space --footnote-references=superscript --stylesheet=../../../rst.css $i.rst > $i.html
done
+# Also see grid_graph_export_png.sh for figure conversions
Modified: branches/release/libs/graph/doc/Graph.html
==============================================================================
--- branches/release/libs/graph/doc/Graph.html (original)
+++ branches/release/libs/graph/doc/Graph.html 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -62,9 +62,8 @@
An edge descriptor corresponds to a unique edge <i>(u,v)</i> in a
graph. An edge descriptor must be <a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</I>,
-<a
-href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>,
-and Equality Comparable.
+Assignable, and
+Equality Comparable.
</td>
</tr>
Modified: branches/release/libs/graph/doc/IncidenceGraph.html
==============================================================================
--- branches/release/libs/graph/doc/IncidenceGraph.html (original)
+++ branches/release/libs/graph/doc/IncidenceGraph.html 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -76,7 +76,7 @@
<TR>
<TD><pre>boost::graph_traits<G>::degree_size_type</pre>
-The unsigned intergral type used for representing the number
+The unsigned integral type used for representing the number
out-edges or incident edges of a vertex.
</TD>
</TR>
@@ -108,7 +108,7 @@
<TT>u</TT> in graph <TT>g</TT>. The source vertex of an edge obtained
via an out edge iterator is guaranteed (for both directed and
undirected graphs) to be the vertex <tt>u</tt> used in the call to
-<tt>out_edges(u, g)</tt> and the target vertex must the a vertex
+<tt>out_edges(u, g)</tt> and the target vertex must be a vertex
adjacent to <tt>u</tt>.[1]
<br>
Return type: <TT>std::pair<out_edge_iterator, out_edge_iterator></TT>
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-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -40,7 +40,8 @@
<p>The class template <code>compressed_sparse_row_graph</code> is
a graph class that uses the compact Compressed Sparse Row (CSR)
- format to store directed graphs. While CSR graphs have much less
+ format to store directed (and bidirectional) graphs. While CSR graphs have
+ much less
overhead than many other graph formats (e.g., <a
href="adjacency_list.html"><code>adjacency_list</code></a>), they
do not provide any mutability: one cannot add or remove vertices
@@ -67,14 +68,20 @@
providing the offset of the first edge outgoing from each
vertex. Iteration over the out-edges for the <i>i</i><sup>th</sup>
vertex in the graph is achieved by
- visiting <tt>edge_array[vertex_array[i]]</tt>, <tt>edge_array[vertex_array[i]+1]</tt>,
+ visiting <tt>edge_array[vertex_array[i]]</tt>,
+ <tt>edge_array[vertex_array[i]+1]</tt>,
..., <tt>edge_array[vertex_array[i+1]]</tt>. This format minimizes
memory use to <i>O(n + m)</i>, where <i>n</i> and <i>m</i> are the
number of vertices and edges, respectively. The constants
multiplied by <i>n</i> and <i>m</i> are based on the size of the
integers needed to represent indices into the edge and vertex
arrays, respectively, which can be controlled using
- the template parameters.</p>
+ the template parameters. The
+ <tt>Directed</tt> template parameter controls whether one edge direction
+ (the default) or both directions are stored. A directed CSR graph has
+ <tt>Directed</tt> = <tt>directedS</tt> and a bidirectional CSR graph (only
+ supported with the new interface and with a limited set of constructors)
+ has <tt>Directed</tt> = <tt>bidirectionalS</tt>.</p>
<ul>
<li>Synopsis</li>
@@ -155,7 +162,7 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty());
- <i>// New sorted edge list constructors <b>(both interfaces)</b></i>
+ <i>// New sorted edge list constructors <b>(both interfaces, directed only)</b></i>
template<typename InputIterator>
<a href="#edge-sorted-const">compressed_sparse_row_graph</a>(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
@@ -171,7 +178,7 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty());
- <i>// In-place unsorted edge list constructors <b>(new interface only)</b></i>
+ <i>// In-place unsorted edge list constructors <b>(new interface and directed only)</b></i>
template<typename InputIterator>
<a href="#edge-inplace-const">compressed_sparse_row_graph</a>(construct_inplace_from_sources_and_targets_t,
std::vector<vertex_descriptor>& sources,
@@ -187,7 +194,7 @@
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty());
- <i>// Miscellaneous constructors <b>(both interfaces)</b></i>
+ <i>// Miscellaneous constructors <b>(both interfaces, directed only)</b></i>
template<typename Graph, typename VertexIndexMap>
<a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g, const VertexIndexMap& vi,
vertices_size_type numverts,
@@ -199,7 +206,7 @@
template<typename Graph>
explicit compressed_sparse_row_graph(const Graph& g);
- <i>// Graph mutators (both interfaces)</i>
+ <i>// Graph mutators (both interfaces, directed only)</i>
template<typename Graph, typename VertexIndexMap>
void assign(const Graph& g, const VertexIndexMap& vi,
vertices_size_type numverts, edges_size_type numedges);
@@ -224,6 +231,11 @@
out_edges(vertex_descriptor, const compressed_sparse_row_graph&);
degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
+<i>// Bidirectional Graph requirements (new interface and bidirectional only)</i>
+std::pair<in_edge_iterator, in_edge_iterator>
+ in_edges(vertex_descriptor, const compressed_sparse_row_graph&);
+degree_size_type in_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
+
<i>// Adjacency Graph requirements (both interfaces)</i>
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&);
@@ -243,7 +255,7 @@
<b>(old interface only)</b>
std::pair<out_edge_iterator, out_edge_iterator>
<a href="#edge_range">edge_range</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
-<b>(old interface only)</b>
+<b>(both interfaces)</b>
std::pair<edge_descriptor, bool>
<a href="#edge">edge</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
<b>(both interfaces)</b>
@@ -259,7 +271,7 @@
<a href="#get">get</a>(PropertyTag, const compressed_sparse_row_graph& g)
template<typename PropertyTag, class X>
-typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type
+typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type
<a href="#get-x">get</a>(PropertyTag, const compressed_sparse_row_graph& g, X x)
template<typename PropertyTag, class X, class Value>
@@ -290,19 +302,19 @@
template<typename Graph>
edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename InputIterator, typename Graph>
void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename InputIterator, typename EPIter, typename Graph>
void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename BidirectionalIterator, typename Graph>
void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename BidirectionalIterator, typename EPIter, typename Graph>
void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g);
@@ -699,9 +711,7 @@
<p class="indent">
Clears the CSR graph and builds a CSR graph in place from the
structure of another graph. The graph type <tt>Graph</tt> must
- be a model of IncidenceGraph
- and have a <tt>vertex(i, g)</tt> function that retrieves the
- <i>i</i><sup>th</sup> vertex in the graph.
+ be a model of IncidenceGraph.
<br><b>Parameters</b>
@@ -772,7 +782,7 @@
<p class="indent">
Returns all edges from <tt>u</tt> to <tt>v</tt>. Requires time
- linear in the number of edges outgoing from <tt>u</tt>.
+ logarithmic in the number of edges outgoing from <tt>u</tt>.
<b>(This function is only provided by the old interface.)</b>
</p>
@@ -789,8 +799,9 @@
second value in the pair will be <tt>false</tt>. If multiple
edges exist from <tt>u</tt> to <tt>v</tt>, the first edge will
be returned; use edge_range
- to retrieve all edges.
- <b>(This function is only provided by the old interface.)</b>
+ to retrieve all edges. This function requires time logarithmic in the
+ number of edges outgoing from <tt>u</tt> for the old interface, and
+ linear time for the new interface.
</p>
<hr></hr>
Copied: branches/release/libs/graph/doc/figs/grid_graph_indexed.svg (from r55473, /trunk/libs/graph/doc/figs/grid_graph_indexed.svg)
==============================================================================
Binary files. No diff available.
Copied: branches/release/libs/graph/doc/figs/grid_graph_unindexed.svg (from r55473, /trunk/libs/graph/doc/figs/grid_graph_unindexed.svg)
==============================================================================
Binary files. No diff available.
Copied: branches/release/libs/graph/doc/grid_graph.html (from r55473, /trunk/libs/graph/doc/grid_graph.html)
==============================================================================
--- /trunk/libs/graph/doc/grid_graph.html (original)
+++ branches/release/libs/graph/doc/grid_graph.html 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -166,6 +166,17 @@
<span class="name">Traits</span>::<span class="type">edge_descriptor</span> edge,
<span class="keyword">const</span> <span class="name">Graph&</span> graph);
+<span class="comment">// Get the out-edge associated with vertex and out_edge_index</span>
+<span class="name">Traits</span>::<span class="type">edge_descriptor</span>
+out_edge_at(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex,
+ <span class="name">Traits</span>::<span class="type">degree_size_type</span> out_edge_index,
+ <span class="keyword">const</span> <span class="name">Graph&</span> graph);
+
+<span class="comment">// Get the out-edge associated with vertex and in_edge_index</span>
+<span class="name">Traits</span>::<span class="type">edge_descriptor</span>
+in_edge_at(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex,
+ <span class="name">Traits</span>::<span class="type">degree_size_type</span> in_edge_index,
+ <span class="keyword">const</span> <span class="name">Graph&</span> graph);
</pre>
<h4>Example</h4>
Copied: branches/release/libs/graph/doc/grid_graph_export_svg.sh (from r55723, /trunk/libs/graph/doc/grid_graph_export_svg.sh)
==============================================================================
--- /trunk/libs/graph/doc/grid_graph_export_svg.sh (original)
+++ branches/release/libs/graph/doc/grid_graph_export_svg.sh 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -1,5 +1,14 @@
#!/bin/bash
+#=======================================================================
+# Copyright 2009 Trustees of Indiana University.
+# Authors: Michael Hansen, Andrew Lumsdaine
+#
+# 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)
+#=======================================================================
+
# Unindexed, unwrapped
inkscape --export-png grid_graph_unwrapped.png --export-id g3150 --export-id-only grid_graph_unindexed.svg
Modified: branches/release/libs/graph/doc/incremental_components.html
==============================================================================
--- branches/release/libs/graph/doc/incremental_components.html (original)
+++ branches/release/libs/graph/doc/incremental_components.html 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -8,6 +8,18 @@
-->
<Head>
<Title>Boost Graph Library: Incremental Connected Components</Title>
+<style type="text/css">
+ <!--
+ .code
+ {
+ border-left-style: groove;
+ border-left-width: 1px;
+ padding-left: 2em;
+ }
+
+ -->
+</style>
+
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../boost.png"
@@ -88,58 +100,77 @@
href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>.
<P>
-<PRE>
-typedef adjacency_list <vecS, vecS, undirectedS> Graph;
-typedef graph_traits<Graph>::vertex_descriptor Vertex;
-typedef graph_traits<Graph>::vertices_size_type size_type;
-
-const int N = 6;
-Graph G(N);
-
-std::vector<size_type> rank(num_vertices(G));
-std::vector<Vertex> parent(num_vertices(G));
-typedef size_type* Rank;
-typedef Vertex* Parent;
-disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
-
-initialize_incremental_components(G, ds);
-incremental_components(G, ds);
-
-graph_traits<Graph>::edge_descriptor e;
-bool flag;
-boost::tie(e,flag) = add_edge(0, 1, G);
-ds.union_set(0,1);
-
-boost::tie(e,flag) = add_edge(1, 4, G);
-ds.union_set(1,4);
-
-boost::tie(e,flag) = add_edge(4, 0, G);
-ds.union_set(4,0);
-
-boost::tie(e,flag) = add_edge(2, 5, G);
-ds.union_set(2,5);
-
-cout << "An undirected graph:" << endl;
-print_graph(G, get(vertex_index, G));
-cout << endl;
-
-graph_traits<Graph>::vertex_iterator i,end;
-for (boost::tie(i, end) = vertices(G); i != end; ++i)
- cout << "representative[" << *i << "] = " <<
- ds.find_set(*i) << endl;;
-cout << endl;
-
-typedef component_index<unsigned int> Components;
-Components components(&parent[0], &parent[0] + parent.size());
-
-for (Components::size_type c = 0; c < components.size(); ++c) {
- cout << "component " << c << " contains: ";
- Components::value_type::iterator
- j = components[c].begin(),
- jend = components[c].end();
- for ( ; j != jend; ++j)
- cout << *j << " ";
- cout << endl;
+<PRE class="code">
+using namespace boost;
+
+int main(int argc, char* argv[])
+{
+ typedef adjacency_list <vecS, vecS, undirectedS> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits<Graph>::vertices_size_type VertexIndex;
+
+ const int VERTEX_COUNT = 6;
+ Graph graph(VERTEX_COUNT);
+
+ std::vector<VertexIndex> rank(num_vertices(graph));
+ std::vector<Vertex> parent(num_vertices(graph));
+
+ typedef VertexIndex* Rank;
+ typedef Vertex* Parent;
+
+ disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
+
+ initialize_incremental_components(graph, ds);
+ incremental_components(graph, ds);
+
+ graph_traits<Graph>::edge_descriptor edge;
+ bool flag;
+
+ boost::tie(edge, flag) = add_edge(0, 1, graph);
+ ds.union_set(0,1);
+
+ boost::tie(edge, flag) = add_edge(1, 4, graph);
+ ds.union_set(1,4);
+
+ boost::tie(edge, flag) = add_edge(4, 0, graph);
+ ds.union_set(4,0);
+
+ boost::tie(edge, flag) = add_edge(2, 5, graph);
+ ds.union_set(2,5);
+
+ std::cout << "An undirected graph:" << std::endl;
+ print_graph(graph, get(boost::vertex_index, graph));
+ std::cout << std::endl;
+
+ BOOST_FOREACH(Vertex current_vertex, vertices(graph)) {
+ std::cout << "representative[" << current_vertex << "] = " <<
+ ds.find_set(current_vertex) << std::endl;
+ }
+
+ std::cout << std::endl;
+
+ typedef component_index<VertexIndex> Components;
+
+ // NOTE: Because we're using vecS for the graph type, we're
+ // effectively using identity_property_map for a vertex index map.
+ // If we were to use listS instead, the index map would need to be
+ // explicity passed to the component_index constructor.
+ Components components(parent.begin(), parent.end());
+
+ // Iterate through the component indices
+ BOOST_FOREACH(VertexIndex current_index, components) {
+ std::cout << "component " << current_index << " contains: ";
+
+ // Iterate through the child vertex indices for [current_index]
+ BOOST_FOREACH(VertexIndex child_index,
+ components[current_index]) {
+ std::cout << child_index << " ";
+ }
+
+ std::cout << std::endl;
+ }
+
+ return (0);
}
</PRE>
@@ -298,19 +329,14 @@
</PRE>
<P>
-<b>The <tt>component_index</tt> functionality is broken in Boost 1.40 and
-earlier versions (see <a
-href="https://svn.boost.org/trac/boost/ticket/3250">bug 3250</a> for more
-information).</b>
-
-<p>
-
-The is a class that provides an STL container-like view for the
-components of the graph. Each component is a container-like object,
-and the <TT>component_index</TT> object provides access to the
-component objects via <TT>operator[]</TT>. A <TT>component_index</TT>
-object is initialized with the parents property in the disjoint-sets
-calculated from the <TT>incremental_components()</TT> function.
+The <tt>component_index</tt> class provides an STL
+container-like view for the components of the graph. Each component is
+a container-like object, and access is provided via
+the <TT>operator[]</TT>. A <TT>component_index</TT> object is
+initialized with the parents property in the disjoint-sets calculated
+from the <TT>incremental_components()</TT> function. Optionally, a
+vertex -> index property map is passed in
+(<tt>identity_property_map</tt> is used by default).
<P>
@@ -332,81 +358,47 @@
</tr>
<tr>
-<td><tt>size_type</tt></td>
-<td>The type used for representing the number of components.</td>
-</tr>
-
-
-<tr>
-<td><tt>value_type</tt></td>
+<td><tt>value_type/size_type</tt></td>
<td>
-The type for a component object. The component type has the following members.
-</td>
-</tr>
-
-<tr>
-<td><tt>value_type::value_type</tt></td>
-<td>
-The value type of a component object is a vertex ID.
+The type for a component index (same as <tt>Index</tt>).
</td>
</tr>
<tr>
-<td><tt>value_type::iterator</tt></td>
+<td><tt>size_type size()</tt></td>
<td>
-This iterator can be used to traverse all of the vertices
-in the component. This iterator dereferences to give a vertex ID.
+Returns the number of components in the graph.
</td>
</tr>
-<tr>
-<td><tt>value_type::const_iterator</tt></td>
-<td>
-The const iterator.
-</td>
-</tr>
<tr>
-<td><tt>value_type::iterator value_type::begin() const</tt></td>
+<td><tt>iterator/const_iterator</tt></td>
<td>
-Return an iterator pointing to the first vertex in the component.
+Iterators used to traverse the available component indices [0 to <tt>size()</tt>).
</td>
</tr>
<tr>
-<td><tt>value_type::iterator value_type::end() const</tt></td>
+<td><tt>iterator begin() const</tt></td>
<td>
-Return an iterator pointing past the end of the last vertex in the
-component.
-</td>
-<tr>
-
-<tr>
-<td>
-<tt>
-template <class ComponentsContainer>
-component_index(const ComponentsContainer& c)
-</tt>
-</td>
-<td>
-Construct the <TT>component_index</TT> using the information
-from the components container <TT>c</TT> which was the result
-of executing <TT>connected_components_on_edgelist</TT>.
+Returns an iterator at the start of the component indices (0).
</td>
</tr>
<tr>
-<td><tt>value_type operator[](size_type i)</tt></td>
+<td><tt>iterator end() const</tt></td>
<td>
-Returns the <TT>i</TT>th component in the graph.
+Returns an iterator past the end of the component indices (<tt>size()</tt>).
</td>
</tr>
-
+
<tr>
-<td><tt>size_type component_index::size()</tt></td>
+<td><tt>std::pair<component_iterator, component_iterator> operator[size_type index] const</tt></td>
<td>
-Returns the number of components in the graph.
+Returns a pair of iterators for the component at <tt>index</tt> where <tt>index</tt> is in [0, <tt>size()</tt>).
</td>
+</tr>
</table>
Modified: branches/release/libs/graph/doc/quick_tour.html
==============================================================================
--- branches/release/libs/graph/doc/quick_tour.html (original)
+++ branches/release/libs/graph/doc/quick_tour.html 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -210,8 +210,7 @@
</pre>
The output is:
<pre>
- edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0)
- (3,1) (3,4) (4,0) (4,1)
+ edges(g) = (0,1) (0,3) (2,0) (3,2) (2,4) (1,3) (3,4)
</pre>
<p>
<h2>The Adjacency Structure</h2>
@@ -558,14 +557,14 @@
using std::vector;
using std::cout;
using std::endl;
- vector<Vertex> p(num_vertices(G)); //the predecessor array
+ vector<Vertex> p(num_vertices(G), graph_traits<G>::null_vertex()); //the predecessor array
dijkstra_shortest_paths(G, s, distance_map(&d[0]).
visitor(make_predecessor_recorder(&p[0])));
cout << "parents in the tree of shortest paths:" << endl;
for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
cout << "parent(" << *vi;
- if (p[*vi] == Vertex())
+ if (p[*vi] == graph_traits<G>::null_vertex())
cout << ") = no parent" << endl;
else
cout << ") = " << p[*vi] << endl;
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -110,6 +110,9 @@
<LI>Matrix as Graph<a href="#*">*</a>
<LI>Leda Graph <a href="#*">*</a>
<LI>Stanford GraphBase
+ <LI>Implicit Graphs
+ <OL>
+ <LI>Multi-dimensional grid graph
</OL>
<LI>Iterator Adaptors
<OL>
Modified: branches/release/libs/graph/example/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/example/Jamfile.v2 (original)
+++ branches/release/libs/graph/example/Jamfile.v2 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -19,3 +19,4 @@
exe bron_kerbosch_print_cliques : bron_kerbosch_print_cliques.cpp ;
exe bron_kerbosch_clique_number : bron_kerbosch_clique_number.cpp ;
exe mcgregor_subgraphs_example : mcgregor_subgraphs_example.cpp ;
+exe grid_graph_example : grid_graph_example.cpp ;
Modified: branches/release/libs/graph/example/incremental-components-eg.cpp
==============================================================================
--- branches/release/libs/graph/example/incremental-components-eg.cpp (original)
+++ branches/release/libs/graph/example/incremental-components-eg.cpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -1,64 +1,84 @@
//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// 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)
//=======================================================================
-#include <boost/config.hpp>
+
#include <iostream>
#include <vector>
-#include <algorithm>
-#include <utility>
+
+#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
-#include <boost/pending/disjoint_sets.hpp>
#include <boost/graph/incremental_components.hpp>
+#include <boost/pending/disjoint_sets.hpp>
-int
-main(int, char *[])
+using namespace boost;
+
+int main(int argc, char* argv[])
{
- using namespace boost;
+ typedef adjacency_list <vecS, vecS, undirectedS> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits<Graph>::edge_descriptor Edge;
+ typedef graph_traits<Graph>::vertices_size_type VertexIndex;
+
// Create a graph
- typedef adjacency_list < vecS, vecS, undirectedS > Graph;
- typedef graph_traits < Graph >::vertex_descriptor Vertex;
- const int N = 6;
- Graph G(N);
- add_edge(0, 1, G);
- add_edge(1, 4, G);
- // create the disjoint-sets object, which requires rank and parent vertex properties
- std::vector < Vertex > rank(num_vertices(G));
- std::vector < Vertex > parent(num_vertices(G));
- typedef graph_traits<Graph>::vertices_size_type* Rank;
+ const int VERTEX_COUNT = 6;
+ Graph graph(VERTEX_COUNT);
+
+ add_edge(0, 1, graph);
+ add_edge(1, 4, graph);
+
+ // reate the disjoint-sets object, which requires rank and parent
+ // vertex properties.
+ std::vector<Vertex> rank(num_vertices(graph));
+ std::vector<Vertex> parent(num_vertices(graph));
+
+ typedef VertexIndex* Rank;
typedef Vertex* Parent;
- disjoint_sets < Rank, Parent > ds(&rank[0], &parent[0]);
+ disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
- // determine the connected components, storing the results in the disjoint-sets object
- initialize_incremental_components(G, ds);
- incremental_components(G, ds);
+ // Determine the connected components, storing the results in the
+ // disjoint-sets object.
+ initialize_incremental_components(graph, ds);
+ incremental_components(graph, ds);
// Add a couple more edges and update the disjoint-sets
- graph_traits < Graph >::edge_descriptor e;
- bool flag;
- tie(e, flag) = add_edge(4, 0, G);
+ add_edge(4, 0, graph);
+ add_edge(2, 5, graph);
+
ds.union_set(4, 0);
- tie(e, flag) = add_edge(2, 5, G);
ds.union_set(2, 5);
- graph_traits < Graph >::vertex_iterator iter, end;
- for (tie(iter, end) = vertices(G); iter != end; ++iter)
- std::cout << "representative[" << *iter << "] = " <<
- ds.find_set(*iter) << std::endl;;
+ BOOST_FOREACH(Vertex current_vertex, vertices(graph)) {
+ std::cout << "representative[" << current_vertex << "] = " <<
+ ds.find_set(current_vertex) << std::endl;
+ }
+
std::cout << std::endl;
- typedef component_index < unsigned int >Components;
+ // Generate component index. NOTE: We would need to pass in a vertex
+ // index map into the component_index constructor if our graph type
+ // used listS instead of vecS (identity_property_map is used by
+ // default).
+ typedef component_index<VertexIndex> Components;
Components components(parent.begin(), parent.end());
- for (Components::size_type i = 0; i < components.size(); ++i) {
- std::cout << "component " << i << " contains: ";
- for (Components::value_type::iterator j = components[i].begin();
- j != components[i].end(); ++j)
- std::cout << *j << " ";
+
+ // Iterate through the component indices
+ BOOST_FOREACH(VertexIndex component_index, components) {
+ std::cout << "component " << component_index << " contains: ";
+
+ // Iterate through the child vertex indices for [component_index]
+ BOOST_FOREACH(VertexIndex child_index,
+ components[component_index]) {
+ std::cout << child_index << " ";
+ }
+
std::cout << std::endl;
}
- return EXIT_SUCCESS;
+ return (0);
}
Modified: branches/release/libs/graph/example/incremental_components.cpp
==============================================================================
--- branches/release/libs/graph/example/incremental_components.cpp (original)
+++ branches/release/libs/graph/example/incremental_components.cpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -1,20 +1,20 @@
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// 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)
//=======================================================================
-#include <boost/config.hpp>
#include <iostream>
#include <vector>
-#include <algorithm>
-#include <utility>
-#include <boost/graph/graph_utility.hpp>
+
+#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
-#include <boost/pending/disjoint_sets.hpp>
+#include <boost/graph/graph_utility.hpp>
#include <boost/graph/incremental_components.hpp>
+#include <boost/pending/disjoint_sets.hpp>
/*
@@ -45,64 +45,75 @@
*/
-using namespace std;
+using namespace boost;
-int main(int , char* [])
+int main(int argc, char* argv[])
{
- using namespace boost;
typedef adjacency_list <vecS, vecS, undirectedS> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits<Graph>::vertices_size_type size_type;
+ typedef graph_traits<Graph>::vertices_size_type VertexIndex;
+
+ const int VERTEX_COUNT = 6;
+ Graph graph(VERTEX_COUNT);
- const int N = 6;
- Graph G(N);
+ std::vector<VertexIndex> rank(num_vertices(graph));
+ std::vector<Vertex> parent(num_vertices(graph));
- std::vector<size_type> rank(num_vertices(G));
- std::vector<Vertex> parent(num_vertices(G));
- typedef size_type* Rank;
+ typedef VertexIndex* Rank;
typedef Vertex* Parent;
- disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
- initialize_incremental_components(G, ds);
- incremental_components(G, ds);
+ disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
+
+ initialize_incremental_components(graph, ds);
+ incremental_components(graph, ds);
- graph_traits<Graph>::edge_descriptor e;
+ graph_traits<Graph>::edge_descriptor edge;
bool flag;
- boost::tie(e,flag) = add_edge(0, 1, G);
+
+ boost::tie(edge, flag) = add_edge(0, 1, graph);
ds.union_set(0,1);
- boost::tie(e,flag) = add_edge(1, 4, G);
+ boost::tie(edge, flag) = add_edge(1, 4, graph);
ds.union_set(1,4);
- boost::tie(e,flag) = add_edge(4, 0, G);
+ boost::tie(edge, flag) = add_edge(4, 0, graph);
ds.union_set(4,0);
- boost::tie(e,flag) = add_edge(2, 5, G);
+ boost::tie(edge, flag) = add_edge(2, 5, graph);
ds.union_set(2,5);
- cout << "An undirected graph:" << endl;
- print_graph(G, get(vertex_index, G));
- cout << endl;
+ std::cout << "An undirected graph:" << std::endl;
+ print_graph(graph, get(boost::vertex_index, graph));
+ std::cout << std::endl;
- graph_traits<Graph>::vertex_iterator i,end;
- for (boost::tie(i, end) = vertices(G); i != end; ++i)
- cout << "representative[" << *i << "] = " <<
- ds.find_set(*i) << endl;;
- cout << endl;
-
- typedef component_index<unsigned int> Components;
- Components components(&parent[0], &parent[0] + parent.size());
-
- for (Components::size_type c = 0; c < components.size(); ++c) {
- cout << "component " << c << " contains: ";
- Components::value_type::iterator
- j = components[c].begin(),
- jend = components[c].end();
- for ( ; j != jend; ++j)
- cout << *j << " ";
- cout << endl;
+ BOOST_FOREACH(Vertex current_vertex, vertices(graph)) {
+ std::cout << "representative[" << current_vertex << "] = " <<
+ ds.find_set(current_vertex) << std::endl;
+ }
+
+ std::cout << std::endl;
+
+ typedef component_index<VertexIndex> Components;
+
+ // NOTE: Because we're using vecS for the graph type, we're
+ // effectively using identity_property_map for a vertex index map.
+ // If we were to use listS instead, the index map would need to be
+ // explicitly passed to the component_index constructor.
+ Components components(parent.begin(), parent.end());
+
+ // Iterate through the component indices
+ BOOST_FOREACH(VertexIndex current_index, components) {
+ std::cout << "component " << current_index << " contains: ";
+
+ // Iterate through the child vertex indices for [current_index]
+ BOOST_FOREACH(VertexIndex child_index,
+ components[current_index]) {
+ std::cout << child_index << " ";
+ }
+
+ std::cout << std::endl;
}
- return 0;
+ return (0);
}
Modified: branches/release/libs/graph/example/incremental_components.expected
==============================================================================
--- branches/release/libs/graph/example/incremental_components.expected (original)
+++ branches/release/libs/graph/example/incremental_components.expected 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -13,6 +13,6 @@
representative[4] = 1
representative[5] = 5
-component 0 contains: 4 1 0
+component 0 contains: 1 4 0
component 1 contains: 3
component 2 contains: 5 2
Modified: branches/release/libs/graph/example/quick_tour.cpp
==============================================================================
--- branches/release/libs/graph/example/quick_tour.cpp (original)
+++ branches/release/libs/graph/example/quick_tour.cpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -18,14 +18,14 @@
using namespace boost;
template <class Graph> struct exercise_vertex {
- exercise_vertex(Graph& g_) : g(g_) { }
+ exercise_vertex(Graph& g_, const char name_[]) : g(g_),name(name_) { }
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
void operator()(const Vertex& v) const
{
using namespace boost;
typename property_map<Graph, vertex_index_t>::type
vertex_id = get(vertex_index, g);
- std::cout << "vertex: " << get(vertex_id, v) << std::endl;
+ std::cout << "vertex: " << name[get(vertex_id, v)] << std::endl;
// Write out the outgoing edges
std::cout << "\tout-edges: ";
@@ -36,8 +36,8 @@
{
e = *out_i;
Vertex src = source(e, g), targ = target(e, g);
- std::cout << "(" << get(vertex_id, src)
- << "," << get(vertex_id, targ) << ") ";
+ std::cout << "(" << name[get(vertex_id, src)]
+ << "," << name[get(vertex_id, targ)] << ") ";
}
std::cout << std::endl;
@@ -48,8 +48,8 @@
{
e = *in_i;
Vertex src = source(e, g), targ = target(e, g);
- std::cout << "(" << get(vertex_id, src)
- << "," << get(vertex_id, targ) << ") ";
+ std::cout << "(" << name[get(vertex_id, src)]
+ << "," << name[get(vertex_id, targ)] << ") ";
}
std::cout << std::endl;
@@ -57,10 +57,11 @@
std::cout << "\tadjacent vertices: ";
typename graph_traits<Graph>::adjacency_iterator ai, ai_end;
for (tie(ai,ai_end) = adjacent_vertices(v, g); ai != ai_end; ++ai)
- std::cout << get(vertex_id, *ai) << " ";
+ std::cout << name[get(vertex_id, *ai)] << " ";
std::cout << std::endl;
}
Graph& g;
+ const char *name;
};
@@ -73,7 +74,7 @@
// Make convenient labels for the vertices
enum { A, B, C, D, E, N };
const int num_vertices = N;
- const char* name = "ABCDE";
+ const char name[] = "ABCDE";
// writing out the edges in the graph
typedef std::pair<int,int> Edge;
@@ -120,7 +121,7 @@
std::cout << std::endl;
std::for_each(vertices(g).first, vertices(g).second,
- exercise_vertex<Graph>(g));
+ exercise_vertex<Graph>(g, name));
std::map<std::string,std::string> graph_attr, vertex_attr, edge_attr;
graph_attr["size"] = "3,3";
Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 (original)
+++ branches/release/libs/graph/test/Jamfile.v2 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -119,6 +119,9 @@
[ run core_numbers_test.cpp ]
[ run read_propmap.cpp ]
[ run mcgregor_subgraphs_test.cpp ]
+ [ compile grid_graph_cc.cpp ]
+ [ run grid_graph_test.cpp ]
+ [ run incremental_components_test.cpp ]
$(optional_tests)
;
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-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -49,6 +49,9 @@
typedef boost::compressed_sparse_row_graph<boost::directedS, VertexData>
CSRGraphT;
+typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, VertexData>
+ BidirCSRGraphT;
+
template <class G1, class VI1, class G2, class VI2, class IsomorphismMap>
void assert_graphs_equal(const G1& g1, const VI1& vi1,
const G2& g2, const VI2& vi2,
@@ -113,83 +116,81 @@
}
}
-template<typename GraphT, typename VertexIndexMap>
-class edge_to_index_pair
-{
- typedef typename boost::graph_traits<GraphT>::vertices_size_type
- vertices_size_type;
- typedef typename boost::graph_traits<GraphT>::edge_descriptor edge_descriptor;
-
- public:
- typedef std::pair<vertices_size_type, vertices_size_type> result_type;
-
- edge_to_index_pair() : g(0), index() { }
- edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
- : g(&g), index(index)
- { }
-
- result_type operator()(edge_descriptor e) const
- {
- return result_type(get(index, source(e, *g)), get(index, target(e, *g)));
- }
-
- private:
- const GraphT* g;
- VertexIndexMap index;
-};
-
-template<typename GraphT, typename VertexIndexMap>
-edge_to_index_pair<GraphT, VertexIndexMap>
-make_edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
-{
- return edge_to_index_pair<GraphT, VertexIndexMap>(g, index);
-}
-
-template<typename GraphT>
-edge_to_index_pair
- <GraphT,
- typename boost::property_map<GraphT,boost::vertex_index_t>::const_type>
-make_edge_to_index_pair(const GraphT& g)
-{
- typedef typename boost::property_map<GraphT,
- boost::vertex_index_t>::const_type
- VertexIndexMap;
- return edge_to_index_pair<GraphT, VertexIndexMap>(g,
- get(boost::vertex_index,
- g));
-}
-
-void check_consistency(const CSRGraphT& g) {
+template <typename Structure>
+void check_consistency_one(const Structure& g) {
// Do a bunch of tests on the graph internal data
#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check that m_last_source is valid
- BOOST_CHECK(g.m_last_source <= num_vertices(g));
+ BOOST_CHECK(g.m_last_source <= g.m_rowstart.size() - 1);
#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check that m_rowstart entries are valid, and that entries after
// m_last_source + 1 are all zero
BOOST_CHECK(g.m_rowstart[0] == 0);
- for (CSRGraphT::vertices_size_type i = 0;
+ for (size_t i = 0;
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- i < num_vertices(g);
+ i < g.m_rowstart.size() - 1;
#else // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
i < g.m_last_source;
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
++i) {
BOOST_CHECK(g.m_rowstart[i + 1] >= g.m_rowstart[i]);
- BOOST_CHECK(g.m_rowstart[i + 1] <= num_edges(g));
+ BOOST_CHECK(g.m_rowstart[i + 1] <= g.m_rowstart.back());
}
#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- for (CSRGraphT::vertices_size_type i = g.m_last_source + 1;
+ for (size_t i = g.m_last_source + 1;
i < g.m_rowstart.size(); ++i) {
- BOOST_CHECK(g.m_rowstart[i] == 0);
+ BOOST_CHECK(g.m_forward.m_rowstart[i] == 0);
}
#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check that m_column entries are within range
- for (CSRGraphT::edges_size_type i = 0; i < num_edges(g); ++i) {
- BOOST_CHECK(g.m_column[i] < num_vertices(g));
+ for (size_t i = 0; i < g.m_rowstart.back(); ++i) {
+ BOOST_CHECK(g.m_column[i] < g.m_rowstart.size() - 1);
}
}
+template <typename Graph>
+void check_consistency_dispatch(const Graph& g,
+ boost::incidence_graph_tag) {
+ check_consistency_one(g.m_forward);
+}
+
+template <class G>
+void assert_bidir_equal_in_both_dirs(const G& g) {
+ BOOST_CHECK (g.m_forward.m_rowstart.size() == g.m_backward.m_rowstart.size());
+ BOOST_CHECK (g.m_forward.m_column.size() == g.m_backward.m_column.size());
+ typedef typename boost::graph_traits<G>::vertex_descriptor Vertex;
+ typedef typename boost::graph_traits<G>::edges_size_type EdgeIndex;
+ std::vector<boost::tuple<EdgeIndex, Vertex, Vertex> > edges_forward, edges_backward;
+ for (Vertex i = 0; i < g.m_forward.m_rowstart.size() - 1; ++i) {
+ for (EdgeIndex j = g.m_forward.m_rowstart[i];
+ j < g.m_forward.m_rowstart[i + 1]; ++j) {
+ edges_forward.push_back(boost::make_tuple(j, i, g.m_forward.m_column[j]));
+ }
+ }
+ for (Vertex i = 0; i < g.m_backward.m_rowstart.size() - 1; ++i) {
+ for (EdgeIndex j = g.m_backward.m_rowstart[i];
+ j < g.m_backward.m_rowstart[i + 1]; ++j) {
+ edges_backward.push_back(boost::make_tuple(g.m_backward.m_edge_properties[j], g.m_backward.m_column[j], i));
+ }
+ }
+ std::sort(edges_forward.begin(), edges_forward.end());
+ std::sort(edges_backward.begin(), edges_backward.end());
+ BOOST_CHECK (edges_forward == edges_backward);
+}
+
+template <typename Graph>
+void check_consistency_dispatch(const Graph& g,
+ boost::bidirectional_graph_tag) {
+ check_consistency_one(g.m_forward);
+ check_consistency_one(g.m_backward);
+ assert_bidir_equal_in_both_dirs(g);
+}
+
+template <typename Graph>
+void check_consistency(const Graph& g) {
+ check_consistency_dispatch(g, typename boost::graph_traits<Graph>::traversal_category());
+}
+
template<typename OrigGraph>
void graph_test(const OrigGraph& g)
{
@@ -205,9 +206,9 @@
// Check constructing a graph from iterators
CSRGraphT g3(boost::edges_are_sorted,
boost::make_transform_iterator(edges(g2).first,
- make_edge_to_index_pair(g2)),
+ boost::detail::make_edge_to_index_pair(g2)),
boost::make_transform_iterator(edges(g2).second,
- make_edge_to_index_pair(g2)),
+ boost::detail::make_edge_to_index_pair(g2)),
num_vertices(g));
check_consistency(g3);
BOOST_CHECK((std::size_t)std::distance(edges(g3).first, edges(g3).second)
@@ -488,6 +489,12 @@
assert_graphs_equal(g, boost::identity_property_map(),
g2, boost::identity_property_map(),
boost::identity_property_map());
+ std::cout << "Testing bidir CSR graph built from unsorted edges" << std::endl;
+ BidirCSRGraphT g2b(boost::edges_are_unsorted_multi_pass, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+ graph_test(g2b);
+ assert_graphs_equal(g, boost::identity_property_map(),
+ g2b, 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
Copied: branches/release/libs/graph/test/grid_graph_test.cpp (from r55473, /trunk/libs/graph/test/grid_graph_test.cpp)
==============================================================================
--- /trunk/libs/graph/test/grid_graph_test.cpp (original)
+++ branches/release/libs/graph/test/grid_graph_test.cpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -85,7 +85,7 @@
BOOST_REQUIRE(graph.wrapped(dimension_index) == wrapped[dimension_index]);
}
- // Verify matching indicies
+ // Verify matching indices
for (vertices_size_type vertex_index = 0;
vertex_index < num_vertices(graph);
++vertex_index) {
Copied: branches/release/libs/graph/test/incremental_components_test.cpp (from r56017, /trunk/libs/graph/test/incremental_components_test.cpp)
==============================================================================
--- /trunk/libs/graph/test/incremental_components_test.cpp (original)
+++ branches/release/libs/graph/test/incremental_components_test.cpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -16,7 +16,7 @@
#include <boost/graph/incremental_components.hpp>
#include <boost/graph/random.hpp>
#include <boost/lexical_cast.hpp>
-#include <boost/property_map.hpp>
+#include <boost/property_map/property_map.hpp>
#include <boost/random.hpp>
#include <boost/test/minimal.hpp>
@@ -54,7 +54,7 @@
initialize_incremental_components(graph, vertex_sets);
incremental_components(graph, vertex_sets);
-
+
// Build component index from the graph's vertices, its index map,
// and the disjoint sets.
typedef component_index<vertices_size_type> Components;
Modified: branches/release/libs/graph/test/layout_test.cpp
==============================================================================
--- branches/release/libs/graph/test/layout_test.cpp (original)
+++ branches/release/libs/graph/test/layout_test.cpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -203,10 +203,6 @@
typedef square_topology<> Topology;
Topology topology(gen, 50.0);
std::vector<Topology::point_difference_type> displacements(num_vertices(g));
- Topology::point_type origin;
- origin[0] = origin[1] = 50.0;
- Topology::point_difference_type extent;
- extent[0] = extent[1] = 50.0;
rectangle_topology<> rect_top(gen, 0, 0, 50, 50);
random_graph_layout(g, get(vertex_position, g), rect_top);
@@ -214,8 +210,6 @@
(g,
get(vertex_position, g),
topology,
- origin,
- extent,
square_distance_attractive_force(),
square_distance_repulsive_force(),
all_force_pairs(),
@@ -292,8 +286,6 @@
(g,
get(vertex_position, g),
topology,
- origin,
- extent,
attractive_force(square_distance_attractive_force()).
cooling(linear_cooling<double>(100)));
@@ -350,16 +342,10 @@
typedef square_topology<> Topology;
Topology topology(gen, 50.0);
std::vector<Topology::point_difference_type> displacements(num_vertices(g));
- Topology::point_type origin;
- origin[0] = origin[1] = 50.0;
- Topology::point_difference_type extent;
- extent[0] = extent[1] = 50.0;
fruchterman_reingold_force_directed_layout
(g,
get(vertex_position, g),
topology,
- origin,
- extent,
attractive_force(square_distance_attractive_force()).
cooling(linear_cooling<double>(50)));
Modified: branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp 2009-10-15 16:40:46 EDT (Thu, 15 Oct 2009)
@@ -145,7 +145,7 @@
// NOTE: Weighted betweenness centrality only works with non-zero edge weights
// Build graphs
- Graph g(ERIter(gen, n, prob), ERIter(),
+ Graph g(edges_are_sorted, ERIter(gen, n, prob), ERIter(),
make_generator_iterator(gen, uniform_int<int>(1, C)),
n);
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