1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/compressed_sparse_row_graph.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,799 @@
1.4 +// Copyright 2005-2006 The Trustees of Indiana University.
1.5 +
1.6 +// Distributed under the Boost Software License, Version 1.0.
1.7 +// (See accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// Authors: Jeremiah Willcock
1.11 +// Douglas Gregor
1.12 +// Andrew Lumsdaine
1.13 +
1.14 +// Compressed sparse row graph type
1.15 +
1.16 +#ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
1.17 +#define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
1.18 +
1.19 +#include <vector>
1.20 +#include <utility>
1.21 +#include <algorithm>
1.22 +#include <climits>
1.23 +#include <iterator>
1.24 +#include <boost/graph/graph_traits.hpp>
1.25 +#include <boost/graph/properties.hpp>
1.26 +#include <boost/graph/detail/indexed_properties.hpp>
1.27 +#include <boost/iterator/counting_iterator.hpp>
1.28 +#include <boost/integer.hpp>
1.29 +#include <boost/iterator/iterator_facade.hpp>
1.30 +#include <boost/mpl/if.hpp>
1.31 +#include <boost/graph/graph_selectors.hpp>
1.32 +#include <boost/static_assert.hpp>
1.33 +
1.34 +#ifdef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.35 +# error The Compressed Sparse Row graph only supports bundled properties.
1.36 +# error You will need a compiler that conforms better to the C++ standard.
1.37 +#endif
1.38 +
1.39 +namespace boost {
1.40 +
1.41 +// A tag type indicating that the graph in question is a compressed
1.42 +// sparse row graph. This is an internal detail of the BGL.
1.43 +struct csr_graph_tag;
1.44 +
1.45 +/****************************************************************************
1.46 + * Local helper macros to reduce typing and clutter later on. *
1.47 + ****************************************************************************/
1.48 +#define BOOST_CSR_GRAPH_TEMPLATE_PARMS \
1.49 + typename Directed, typename VertexProperty, typename EdgeProperty, \
1.50 + typename GraphProperty, typename Vertex, typename EdgeIndex
1.51 +#define BOOST_CSR_GRAPH_TYPE \
1.52 + compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, \
1.53 + GraphProperty, Vertex, EdgeIndex>
1.54 +
1.55 +// Forward declaration of CSR edge descriptor type, needed to pass to
1.56 +// indexed_edge_properties.
1.57 +template<typename Vertex, typename EdgeIndex>
1.58 +class csr_edge_descriptor;
1.59 +
1.60 +/** Compressed sparse row graph.
1.61 + *
1.62 + * Vertex and EdgeIndex should be unsigned integral types and should
1.63 + * specialize numeric_limits.
1.64 + */
1.65 +template<typename Directed = directedS,
1.66 + typename VertexProperty = void,
1.67 + typename EdgeProperty = void,
1.68 + typename GraphProperty = no_property,
1.69 + typename Vertex = std::size_t,
1.70 + typename EdgeIndex = Vertex>
1.71 +class compressed_sparse_row_graph
1.72 + : public detail::indexed_vertex_properties<BOOST_CSR_GRAPH_TYPE, VertexProperty,
1.73 + Vertex>,
1.74 + public detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,
1.75 + csr_edge_descriptor<Vertex,
1.76 + EdgeIndex> >
1.77 +
1.78 +{
1.79 + typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
1.80 + VertexProperty, Vertex>
1.81 + inherited_vertex_properties;
1.82 +
1.83 + typedef detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,
1.84 + csr_edge_descriptor<Vertex, EdgeIndex> >
1.85 + inherited_edge_properties;
1.86 +
1.87 + public:
1.88 + // For Property Graph
1.89 + typedef GraphProperty graph_property_type;
1.90 +
1.91 + protected:
1.92 + template<typename InputIterator>
1.93 + void
1.94 + maybe_reserve_edge_list_storage(InputIterator, InputIterator,
1.95 + std::input_iterator_tag)
1.96 + {
1.97 + // Do nothing: we have no idea how much storage to reserve.
1.98 + }
1.99 +
1.100 + template<typename InputIterator>
1.101 + void
1.102 + maybe_reserve_edge_list_storage(InputIterator first, InputIterator last,
1.103 + std::forward_iterator_tag)
1.104 + {
1.105 + using std::distance;
1.106 + typename std::iterator_traits<InputIterator>::difference_type n =
1.107 + distance(first, last);
1.108 + m_column.reserve(n);
1.109 + inherited_edge_properties::reserve(n);
1.110 + }
1.111 +
1.112 + public:
1.113 + /* At this time, the compressed sparse row graph can only be used to
1.114 + * create a directed graph. In the future, bidirectional and
1.115 + * undirected CSR graphs will also be supported.
1.116 + */
1.117 + BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
1.118 +
1.119 + // Concept requirements:
1.120 + // For Graph
1.121 + typedef Vertex vertex_descriptor;
1.122 + typedef csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
1.123 + typedef directed_tag directed_category;
1.124 + typedef allow_parallel_edge_tag edge_parallel_category;
1.125 +
1.126 + class traversal_category: public incidence_graph_tag,
1.127 + public adjacency_graph_tag,
1.128 + public vertex_list_graph_tag,
1.129 + public edge_list_graph_tag {};
1.130 +
1.131 + static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
1.132 +
1.133 + // For VertexListGraph
1.134 + typedef counting_iterator<Vertex> vertex_iterator;
1.135 + typedef Vertex vertices_size_type;
1.136 +
1.137 + // For EdgeListGraph
1.138 + typedef EdgeIndex edges_size_type;
1.139 +
1.140 + // For IncidenceGraph
1.141 + class out_edge_iterator;
1.142 + typedef EdgeIndex degree_size_type;
1.143 +
1.144 + // For AdjacencyGraph
1.145 + typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
1.146 +
1.147 + // For EdgeListGraph
1.148 + class edge_iterator;
1.149 +
1.150 + // For BidirectionalGraph (not implemented)
1.151 + typedef void in_edge_iterator;
1.152 +
1.153 + // For internal use
1.154 + typedef csr_graph_tag graph_tag;
1.155 +
1.156 + // Constructors
1.157 +
1.158 + // Default constructor: an empty graph.
1.159 + compressed_sparse_row_graph()
1.160 + : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property(),
1.161 + m_last_source(0) {}
1.162 +
1.163 + // From number of vertices and sorted list of edges
1.164 + template<typename InputIterator>
1.165 + compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
1.166 + vertices_size_type numverts,
1.167 + edges_size_type numedges = 0,
1.168 + const GraphProperty& prop = GraphProperty())
1.169 + : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
1.170 + m_column(0), m_property(prop), m_last_source(numverts)
1.171 + {
1.172 + // Reserving storage in advance can save us lots of time and
1.173 + // memory, but it can only be done if we have forward iterators or
1.174 + // the user has supplied the number of edges.
1.175 + if (numedges == 0) {
1.176 + typedef typename std::iterator_traits<InputIterator>::iterator_category
1.177 + category;
1.178 + maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
1.179 + } else {
1.180 + m_column.reserve(numedges);
1.181 + }
1.182 +
1.183 + EdgeIndex current_edge = 0;
1.184 + Vertex current_vertex_plus_one = 1;
1.185 + m_rowstart[0] = 0;
1.186 + for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
1.187 + Vertex src = ei->first;
1.188 + Vertex tgt = ei->second;
1.189 + for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
1.190 + m_rowstart[current_vertex_plus_one] = current_edge;
1.191 + m_column.push_back(tgt);
1.192 + ++current_edge;
1.193 + }
1.194 +
1.195 + // The remaining vertices have no edges
1.196 + for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
1.197 + m_rowstart[current_vertex_plus_one] = current_edge;
1.198 +
1.199 + // Default-construct properties for edges
1.200 + inherited_edge_properties::resize(m_column.size());
1.201 + }
1.202 +
1.203 + // From number of vertices and sorted list of edges
1.204 + template<typename InputIterator, typename EdgePropertyIterator>
1.205 + compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
1.206 + EdgePropertyIterator ep_iter,
1.207 + vertices_size_type numverts,
1.208 + edges_size_type numedges = 0,
1.209 + const GraphProperty& prop = GraphProperty())
1.210 + : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
1.211 + m_column(0), m_property(prop), m_last_source(numverts)
1.212 + {
1.213 + // Reserving storage in advance can save us lots of time and
1.214 + // memory, but it can only be done if we have forward iterators or
1.215 + // the user has supplied the number of edges.
1.216 + if (numedges == 0) {
1.217 + typedef typename std::iterator_traits<InputIterator>::iterator_category
1.218 + category;
1.219 + maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
1.220 + } else {
1.221 + m_column.reserve(numedges);
1.222 + }
1.223 +
1.224 + EdgeIndex current_edge = 0;
1.225 + Vertex current_vertex_plus_one = 1;
1.226 + m_rowstart[0] = 0;
1.227 + for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
1.228 + Vertex src = ei->first;
1.229 + Vertex tgt = ei->second;
1.230 + for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
1.231 + m_rowstart[current_vertex_plus_one] = current_edge;
1.232 + m_column.push_back(tgt);
1.233 + inherited_edge_properties::push_back(*ep_iter);
1.234 + ++current_edge;
1.235 + }
1.236 +
1.237 + // The remaining vertices have no edges
1.238 + for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
1.239 + m_rowstart[current_vertex_plus_one] = current_edge;
1.240 + }
1.241 +
1.242 + // Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function
1.243 + template<typename Graph, typename VertexIndexMap>
1.244 + compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
1.245 + vertices_size_type numverts,
1.246 + edges_size_type numedges)
1.247 + : m_property(), m_last_source(0)
1.248 + {
1.249 + assign(g, vi, numverts, numedges);
1.250 + }
1.251 +
1.252 + // Requires VertexListGraph and EdgeListGraph
1.253 + template<typename Graph, typename VertexIndexMap>
1.254 + compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
1.255 + : m_property(), m_last_source(0)
1.256 + {
1.257 + assign(g, vi, num_vertices(g), num_edges(g));
1.258 + }
1.259 +
1.260 + // Requires vertex index map plus requirements of previous constructor
1.261 + template<typename Graph>
1.262 + explicit compressed_sparse_row_graph(const Graph& g)
1.263 + : m_property(), m_last_source(0)
1.264 + {
1.265 + assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
1.266 + }
1.267 +
1.268 + // From any graph (slow and uses a lot of memory)
1.269 + // Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function
1.270 + // Internal helper function
1.271 + template<typename Graph, typename VertexIndexMap>
1.272 + void
1.273 + assign(const Graph& g, const VertexIndexMap& vi,
1.274 + vertices_size_type numverts, edges_size_type numedges)
1.275 + {
1.276 + inherited_vertex_properties::resize(numverts);
1.277 + m_rowstart.resize(numverts + 1);
1.278 + m_column.resize(numedges);
1.279 + EdgeIndex current_edge = 0;
1.280 + typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
1.281 + typedef typename boost::graph_traits<Graph>::edge_descriptor g_edge;
1.282 + typedef typename boost::graph_traits<Graph>::out_edge_iterator
1.283 + g_out_edge_iter;
1.284 +
1.285 + for (Vertex i = 0; i != numverts; ++i) {
1.286 + m_rowstart[i] = current_edge;
1.287 + g_vertex v = vertex(i, g);
1.288 + EdgeIndex num_edges_before_this_vertex = current_edge;
1.289 + g_out_edge_iter ei, ei_end;
1.290 + for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
1.291 + m_column[current_edge++] = get(vi, target(*ei, g));
1.292 + }
1.293 + std::sort(m_column.begin() + num_edges_before_this_vertex,
1.294 + m_column.begin() + current_edge);
1.295 + }
1.296 + m_rowstart[numverts] = current_edge;
1.297 + m_last_source = numverts;
1.298 + }
1.299 +
1.300 + // Requires the above, plus VertexListGraph and EdgeListGraph
1.301 + template<typename Graph, typename VertexIndexMap>
1.302 + void assign(const Graph& g, const VertexIndexMap& vi)
1.303 + {
1.304 + assign(g, vi, num_vertices(g), num_edges(g));
1.305 + }
1.306 +
1.307 + // Requires the above, plus a vertex_index map.
1.308 + template<typename Graph>
1.309 + void assign(const Graph& g)
1.310 + {
1.311 + assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
1.312 + }
1.313 +
1.314 + using inherited_vertex_properties::operator[];
1.315 + using inherited_edge_properties::operator[];
1.316 +
1.317 + // private: non-portable, requires friend templates
1.318 + inherited_vertex_properties& vertex_properties() {return *this;}
1.319 + const inherited_vertex_properties& vertex_properties() const {return *this;}
1.320 + inherited_edge_properties& edge_properties() { return *this; }
1.321 + const inherited_edge_properties& edge_properties() const { return *this; }
1.322 +
1.323 + std::vector<EdgeIndex> m_rowstart;
1.324 + std::vector<Vertex> m_column;
1.325 + GraphProperty m_property;
1.326 + Vertex m_last_source; // Last source of added edge, plus one
1.327 +};
1.328 +
1.329 +template<typename Vertex, typename EdgeIndex>
1.330 +class csr_edge_descriptor
1.331 +{
1.332 + public:
1.333 + Vertex src;
1.334 + EdgeIndex idx;
1.335 +
1.336 + csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}
1.337 + csr_edge_descriptor(): src(0), idx(0) {}
1.338 +
1.339 + bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}
1.340 + bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}
1.341 + bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}
1.342 + bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
1.343 + bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
1.344 + bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
1.345 +};
1.346 +
1.347 +// Construction functions
1.348 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.349 +inline Vertex
1.350 +add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
1.351 + Vertex old_num_verts_plus_one = g.m_rowstart.size();
1.352 + g.m_rowstart.push_back(EdgeIndex(0));
1.353 + return old_num_verts_plus_one - 1;
1.354 +}
1.355 +
1.356 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.357 +inline Vertex
1.358 +add_vertices(typename BOOST_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_CSR_GRAPH_TYPE& g) {
1.359 + Vertex old_num_verts_plus_one = g.m_rowstart.size();
1.360 + g.m_rowstart.resize(old_num_verts_plus_one + count, EdgeIndex(0));
1.361 + return old_num_verts_plus_one - 1;
1.362 +}
1.363 +
1.364 +// This function requires that (src, tgt) be lexicographically at least as
1.365 +// large as the largest edge in the graph so far
1.366 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.367 +inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
1.368 +add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) {
1.369 + assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&
1.370 + src < num_vertices(g));
1.371 + EdgeIndex num_edges_orig = g.m_column.size();
1.372 + for (; g.m_last_source <= src; ++g.m_last_source)
1.373 + g.m_rowstart[g.m_last_source] = num_edges_orig;
1.374 + g.m_rowstart[src + 1] = num_edges_orig + 1;
1.375 + g.m_column.push_back(tgt);
1.376 + typedef typename BOOST_CSR_GRAPH_TYPE::edge_push_back_type push_back_type;
1.377 + g.edge_properties().push_back(push_back_type());
1.378 + return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
1.379 +}
1.380 +
1.381 +// This function requires that (src, tgt) be lexicographically at least as
1.382 +// large as the largest edge in the graph so far
1.383 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.384 +inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
1.385 +add_edge(Vertex src, Vertex tgt,
1.386 + typename BOOST_CSR_GRAPH_TYPE::edge_bundled const& p,
1.387 + BOOST_CSR_GRAPH_TYPE& g) {
1.388 + assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&
1.389 + src < num_vertices(g));
1.390 + EdgeIndex num_edges_orig = g.m_column.size();
1.391 + for (; g.m_last_source <= src; ++g.m_last_source)
1.392 + g.m_rowstart[g.m_last_source] = num_edges_orig;
1.393 + g.m_rowstart[src + 1] = num_edges_orig + 1;
1.394 + g.m_column.push_back(tgt);
1.395 + g.edge_properties().push_back(p);
1.396 + return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
1.397 +}
1.398 +
1.399 +
1.400 +// From VertexListGraph
1.401 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.402 +inline Vertex
1.403 +num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
1.404 + return g.m_rowstart.size() - 1;
1.405 +}
1.406 +
1.407 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.408 +std::pair<counting_iterator<Vertex>, counting_iterator<Vertex> >
1.409 +inline vertices(const BOOST_CSR_GRAPH_TYPE& g) {
1.410 + return std::make_pair(counting_iterator<Vertex>(0),
1.411 + counting_iterator<Vertex>(num_vertices(g)));
1.412 +}
1.413 +
1.414 +// From IncidenceGraph
1.415 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.416 +class BOOST_CSR_GRAPH_TYPE::out_edge_iterator
1.417 + : public iterator_facade<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
1.418 + typename BOOST_CSR_GRAPH_TYPE::edge_descriptor,
1.419 + std::random_access_iterator_tag,
1.420 + const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor&,
1.421 + typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast>
1.422 +{
1.423 + public:
1.424 + typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
1.425 +
1.426 + out_edge_iterator() {}
1.427 + // Implicit copy constructor OK
1.428 + explicit out_edge_iterator(edge_descriptor edge) : m_edge(edge) { }
1.429 +
1.430 + private:
1.431 + // iterator_facade requirements
1.432 + const edge_descriptor& dereference() const { return m_edge; }
1.433 +
1.434 + bool equal(const out_edge_iterator& other) const
1.435 + { return m_edge == other.m_edge; }
1.436 +
1.437 + void increment() { ++m_edge.idx; }
1.438 + void decrement() { ++m_edge.idx; }
1.439 + void advance(difference_type n) { m_edge.idx += n; }
1.440 +
1.441 + difference_type distance_to(const out_edge_iterator& other) const
1.442 + { return other.m_edge.idx - m_edge.idx; }
1.443 +
1.444 + edge_descriptor m_edge;
1.445 +
1.446 + friend class iterator_core_access;
1.447 +};
1.448 +
1.449 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.450 +inline Vertex
1.451 +source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1.452 + const BOOST_CSR_GRAPH_TYPE&)
1.453 +{
1.454 + return e.src;
1.455 +}
1.456 +
1.457 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.458 +inline Vertex
1.459 +target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1.460 + const BOOST_CSR_GRAPH_TYPE& g)
1.461 +{
1.462 + return g.m_column[e.idx];
1.463 +}
1.464 +
1.465 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.466 +inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
1.467 + typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
1.468 +out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1.469 +{
1.470 + typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed;
1.471 + typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
1.472 + EdgeIndex v_row_start = g.m_rowstart[v];
1.473 + EdgeIndex next_row_start = g.m_rowstart[v + 1];
1.474 + return std::make_pair(it(ed(v, v_row_start)),
1.475 + it(ed(v, (std::max)(v_row_start, next_row_start))));
1.476 +}
1.477 +
1.478 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.479 +inline EdgeIndex
1.480 +out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1.481 +{
1.482 + EdgeIndex v_row_start = g.m_rowstart[v];
1.483 + EdgeIndex next_row_start = g.m_rowstart[v + 1];
1.484 + return (std::max)(v_row_start, next_row_start) - v_row_start;
1.485 +}
1.486 +
1.487 +// From AdjacencyGraph
1.488 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.489 +inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
1.490 + typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator>
1.491 +adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1.492 +{
1.493 + EdgeIndex v_row_start = g.m_rowstart[v];
1.494 + EdgeIndex next_row_start = g.m_rowstart[v + 1];
1.495 + return std::make_pair(g.m_column.begin() + v_row_start,
1.496 + g.m_column.begin() +
1.497 + (std::max)(v_row_start, next_row_start));
1.498 +}
1.499 +
1.500 +// Extra, common functions
1.501 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.502 +inline typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor
1.503 +vertex(typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor i,
1.504 + const BOOST_CSR_GRAPH_TYPE&)
1.505 +{
1.506 + return i;
1.507 +}
1.508 +
1.509 +// Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))
1.510 +// time
1.511 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.512 +inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
1.513 + typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
1.514 +edge_range(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
1.515 +{
1.516 + typedef typename std::vector<Vertex>::const_iterator adj_iter;
1.517 + typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
1.518 + typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edge_desc;
1.519 + std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
1.520 + std::pair<adj_iter, adj_iter> adjacencies =
1.521 + std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
1.522 + EdgeIndex idx_begin = adjacencies.first - g.m_column.begin();
1.523 + EdgeIndex idx_end = adjacencies.second - g.m_column.begin();
1.524 + return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
1.525 + out_edge_iter(edge_desc(i, idx_end)));
1.526 +}
1.527 +
1.528 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.529 +inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
1.530 +edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
1.531 +{
1.532 + typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
1.533 + std::pair<out_edge_iter, out_edge_iter> range = edge_range(i, j, g);
1.534 + if (range.first == range.second)
1.535 + return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
1.536 + false);
1.537 + else
1.538 + return std::make_pair(*range.first, true);
1.539 +}
1.540 +
1.541 +// Find an edge given its index in the graph
1.542 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.543 +inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
1.544 +edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g)
1.545 +{
1.546 + typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
1.547 + assert (idx < num_edges(g));
1.548 + row_start_iter src_plus_1 =
1.549 + std::upper_bound(g.m_rowstart.begin(),
1.550 + g.m_rowstart.begin() + g.m_last_source + 1,
1.551 + idx);
1.552 + // Get last source whose rowstart is at most idx
1.553 + // upper_bound returns this position plus 1
1.554 + Vertex src = (src_plus_1 - g.m_rowstart.begin()) - 1;
1.555 + return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
1.556 +}
1.557 +
1.558 +// From EdgeListGraph
1.559 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.560 +class BOOST_CSR_GRAPH_TYPE::edge_iterator
1.561 +{
1.562 + public:
1.563 + typedef std::forward_iterator_tag iterator_category;
1.564 + typedef edge_descriptor value_type;
1.565 +
1.566 + typedef const edge_descriptor* pointer;
1.567 +
1.568 + typedef edge_descriptor reference;
1.569 + typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
1.570 +
1.571 + edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0) {}
1.572 +
1.573 + edge_iterator(const compressed_sparse_row_graph& graph,
1.574 + edge_descriptor current_edge,
1.575 + EdgeIndex end_of_this_vertex)
1.576 + : rowstart_array(&graph.m_rowstart[0]), current_edge(current_edge),
1.577 + end_of_this_vertex(end_of_this_vertex) {}
1.578 +
1.579 + // From InputIterator
1.580 + reference operator*() const { return current_edge; }
1.581 + pointer operator->() const { return ¤t_edge; }
1.582 +
1.583 + bool operator==(const edge_iterator& o) const {
1.584 + return current_edge == o.current_edge;
1.585 + }
1.586 + bool operator!=(const edge_iterator& o) const {
1.587 + return current_edge != o.current_edge;
1.588 + }
1.589 +
1.590 + edge_iterator& operator++() {
1.591 + ++current_edge.idx;
1.592 + while (current_edge.idx == end_of_this_vertex) {
1.593 + ++current_edge.src;
1.594 + end_of_this_vertex = rowstart_array[current_edge.src + 1];
1.595 + }
1.596 + return *this;
1.597 + }
1.598 +
1.599 + edge_iterator operator++(int) {
1.600 + edge_iterator temp = *this;
1.601 + ++*this;
1.602 + return temp;
1.603 + }
1.604 +
1.605 + private:
1.606 + const EdgeIndex* rowstart_array;
1.607 + edge_descriptor current_edge;
1.608 + EdgeIndex end_of_this_vertex;
1.609 +};
1.610 +
1.611 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.612 +inline EdgeIndex
1.613 +num_edges(const BOOST_CSR_GRAPH_TYPE& g)
1.614 +{
1.615 + return g.m_column.size();
1.616 +}
1.617 +
1.618 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.619 +std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_iterator,
1.620 + typename BOOST_CSR_GRAPH_TYPE::edge_iterator>
1.621 +edges(const BOOST_CSR_GRAPH_TYPE& g)
1.622 +{
1.623 + typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
1.624 + typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
1.625 + if (g.m_rowstart.size() == 1 || g.m_column.empty()) {
1.626 + return std::make_pair(ei(), ei());
1.627 + } else {
1.628 + // Find the first vertex that has outgoing edges
1.629 + Vertex src = 0;
1.630 + while (g.m_rowstart[src + 1] == 0) ++src;
1.631 + return std::make_pair(ei(g, edgedesc(src, 0), g.m_rowstart[src + 1]),
1.632 + ei(g, edgedesc(num_vertices(g), g.m_column.size()), 0));
1.633 + }
1.634 +}
1.635 +
1.636 +// For Property Graph
1.637 +
1.638 +// Graph properties
1.639 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value>
1.640 +inline void
1.641 +set_property(BOOST_CSR_GRAPH_TYPE& g, Tag, const Value& value)
1.642 +{
1.643 + get_property_value(g.m_property, Tag()) = value;
1.644 +}
1.645 +
1.646 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1.647 +inline
1.648 +typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
1.649 +get_property(BOOST_CSR_GRAPH_TYPE& g, Tag)
1.650 +{
1.651 + return get_property_value(g.m_property, Tag());
1.652 +}
1.653 +
1.654 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1.655 +inline
1.656 +const
1.657 +typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
1.658 +get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag)
1.659 +{
1.660 + return get_property_value(g.m_property, Tag());
1.661 +}
1.662 +
1.663 +// Add edge_index property map
1.664 +template<typename Index, typename Descriptor>
1.665 +struct csr_edge_index_map
1.666 +{
1.667 + typedef Index value_type;
1.668 + typedef Index reference;
1.669 + typedef Descriptor key_type;
1.670 + typedef readable_property_map_tag category;
1.671 +};
1.672 +
1.673 +template<typename Index, typename Descriptor>
1.674 +inline Index
1.675 +get(const csr_edge_index_map<Index, Descriptor>&,
1.676 + const typename csr_edge_index_map<Index, Descriptor>::key_type& key)
1.677 +{
1.678 + return key.idx;
1.679 +}
1.680 +
1.681 +// Doing the right thing here (by unifying with vertex_index_t and
1.682 +// edge_index_t) breaks GCC.
1.683 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1.684 +struct property_map<BOOST_CSR_GRAPH_TYPE, Tag>
1.685 +{
1.686 +private:
1.687 + typedef identity_property_map vertex_index_type;
1.688 + typedef typename graph_traits<BOOST_CSR_GRAPH_TYPE>::edge_descriptor
1.689 + edge_descriptor;
1.690 + typedef csr_edge_index_map<EdgeIndex, edge_descriptor> edge_index_type;
1.691 +
1.692 + typedef typename mpl::if_<is_same<Tag, edge_index_t>,
1.693 + edge_index_type,
1.694 + detail::error_property_not_found>::type
1.695 + edge_or_none;
1.696 +
1.697 +public:
1.698 + typedef typename mpl::if_<is_same<Tag, vertex_index_t>,
1.699 + vertex_index_type,
1.700 + edge_or_none>::type type;
1.701 +
1.702 + typedef type const_type;
1.703 +};
1.704 +
1.705 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.706 +inline identity_property_map
1.707 +get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
1.708 +{
1.709 + return identity_property_map();
1.710 +}
1.711 +
1.712 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.713 +inline Vertex
1.714 +get(vertex_index_t,
1.715 + const BOOST_CSR_GRAPH_TYPE&, Vertex v)
1.716 +{
1.717 + return v;
1.718 +}
1.719 +
1.720 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.721 +inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1.722 +get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&)
1.723 +{
1.724 + typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1.725 + result_type;
1.726 + return result_type();
1.727 +}
1.728 +
1.729 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1.730 +inline EdgeIndex
1.731 +get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&,
1.732 + typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1.733 +{
1.734 + return e.idx;
1.735 +}
1.736 +
1.737 +// Support for bundled properties
1.738 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle>
1.739 +struct property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>
1.740 +{
1.741 +private:
1.742 + typedef graph_traits<BOOST_CSR_GRAPH_TYPE> traits;
1.743 + typedef VertexProperty vertex_bundled;
1.744 + typedef EdgeProperty edge_bundled;
1.745 + typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),
1.746 + typename traits::vertex_descriptor,
1.747 + typename traits::edge_descriptor>::type
1.748 + descriptor;
1.749 +
1.750 +public:
1.751 + typedef bundle_property_map<BOOST_CSR_GRAPH_TYPE, descriptor, Bundle, T>
1.752 + type;
1.753 + typedef bundle_property_map<const BOOST_CSR_GRAPH_TYPE, descriptor, Bundle,
1.754 + const T> const_type;
1.755 +};
1.756 +
1.757 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle>
1.758 +inline
1.759 +typename property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>::type
1.760 +get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g)
1.761 +{
1.762 + typedef typename property_map<BOOST_CSR_GRAPH_TYPE,
1.763 + T Bundle::*>::type
1.764 + result_type;
1.765 + return result_type(&g, p);
1.766 +}
1.767 +
1.768 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle>
1.769 +inline
1.770 +typename property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>::const_type
1.771 +get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g)
1.772 +{
1.773 + typedef typename property_map<BOOST_CSR_GRAPH_TYPE,
1.774 + T Bundle::*>::const_type
1.775 + result_type;
1.776 + return result_type(&g, p);
1.777 +}
1.778 +
1.779 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle,
1.780 + typename Key>
1.781 +inline T
1.782 +get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g,
1.783 + const Key& key)
1.784 +{
1.785 + return get(get(p, g), key);
1.786 +}
1.787 +
1.788 +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle,
1.789 + typename Key>
1.790 +inline void
1.791 +put(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g,
1.792 + const Key& key, const T& value)
1.793 +{
1.794 + put(get(p, g), key, value);
1.795 +}
1.796 +
1.797 +#undef BOOST_CSR_GRAPH_TYPE
1.798 +#undef BOOST_CSR_GRAPH_TEMPLATE_PARMS
1.799 +
1.800 +} // end namespace boost
1.801 +
1.802 +#endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP