williamr@2: // Copyright 2005-2006 The Trustees of Indiana University. williamr@2: williamr@2: // Distributed under the Boost Software License, Version 1.0. williamr@2: // (See accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: williamr@2: // Authors: Jeremiah Willcock williamr@2: // Douglas Gregor williamr@2: // Andrew Lumsdaine williamr@2: williamr@2: // Compressed sparse row graph type williamr@2: williamr@2: #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP williamr@2: #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: #ifdef BOOST_GRAPH_NO_BUNDLED_PROPERTIES williamr@2: # error The Compressed Sparse Row graph only supports bundled properties. williamr@2: # error You will need a compiler that conforms better to the C++ standard. williamr@2: #endif williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: // A tag type indicating that the graph in question is a compressed williamr@2: // sparse row graph. This is an internal detail of the BGL. williamr@2: struct csr_graph_tag; williamr@2: williamr@2: /**************************************************************************** williamr@2: * Local helper macros to reduce typing and clutter later on. * williamr@2: ****************************************************************************/ williamr@2: #define BOOST_CSR_GRAPH_TEMPLATE_PARMS \ williamr@2: typename Directed, typename VertexProperty, typename EdgeProperty, \ williamr@2: typename GraphProperty, typename Vertex, typename EdgeIndex williamr@2: #define BOOST_CSR_GRAPH_TYPE \ williamr@2: compressed_sparse_row_graph williamr@2: williamr@2: // Forward declaration of CSR edge descriptor type, needed to pass to williamr@2: // indexed_edge_properties. williamr@2: template williamr@2: class csr_edge_descriptor; williamr@2: williamr@2: /** Compressed sparse row graph. williamr@2: * williamr@2: * Vertex and EdgeIndex should be unsigned integral types and should williamr@2: * specialize numeric_limits. williamr@2: */ williamr@2: template williamr@2: class compressed_sparse_row_graph williamr@2: : public detail::indexed_vertex_properties, williamr@2: public detail::indexed_edge_properties > williamr@2: williamr@2: { williamr@2: typedef detail::indexed_vertex_properties williamr@2: inherited_vertex_properties; williamr@2: williamr@2: typedef detail::indexed_edge_properties > williamr@2: inherited_edge_properties; williamr@2: williamr@2: public: williamr@2: // For Property Graph williamr@2: typedef GraphProperty graph_property_type; williamr@2: williamr@2: protected: williamr@2: template williamr@2: void williamr@2: maybe_reserve_edge_list_storage(InputIterator, InputIterator, williamr@2: std::input_iterator_tag) williamr@2: { williamr@2: // Do nothing: we have no idea how much storage to reserve. williamr@2: } williamr@2: williamr@2: template williamr@2: void williamr@2: maybe_reserve_edge_list_storage(InputIterator first, InputIterator last, williamr@2: std::forward_iterator_tag) williamr@2: { williamr@2: using std::distance; williamr@2: typename std::iterator_traits::difference_type n = williamr@2: distance(first, last); williamr@2: m_column.reserve(n); williamr@2: inherited_edge_properties::reserve(n); williamr@2: } williamr@2: williamr@2: public: williamr@2: /* At this time, the compressed sparse row graph can only be used to williamr@2: * create a directed graph. In the future, bidirectional and williamr@2: * undirected CSR graphs will also be supported. williamr@2: */ williamr@2: BOOST_STATIC_ASSERT((is_same::value)); williamr@2: williamr@2: // Concept requirements: williamr@2: // For Graph williamr@2: typedef Vertex vertex_descriptor; williamr@2: typedef csr_edge_descriptor edge_descriptor; williamr@2: typedef directed_tag directed_category; williamr@2: typedef allow_parallel_edge_tag edge_parallel_category; williamr@2: williamr@2: class traversal_category: public incidence_graph_tag, williamr@2: public adjacency_graph_tag, williamr@2: public vertex_list_graph_tag, williamr@2: public edge_list_graph_tag {}; williamr@2: williamr@2: static vertex_descriptor null_vertex() { return vertex_descriptor(-1); } williamr@2: williamr@2: // For VertexListGraph williamr@2: typedef counting_iterator vertex_iterator; williamr@2: typedef Vertex vertices_size_type; williamr@2: williamr@2: // For EdgeListGraph williamr@2: typedef EdgeIndex edges_size_type; williamr@2: williamr@2: // For IncidenceGraph williamr@2: class out_edge_iterator; williamr@2: typedef EdgeIndex degree_size_type; williamr@2: williamr@2: // For AdjacencyGraph williamr@2: typedef typename std::vector::const_iterator adjacency_iterator; williamr@2: williamr@2: // For EdgeListGraph williamr@2: class edge_iterator; williamr@2: williamr@2: // For BidirectionalGraph (not implemented) williamr@2: typedef void in_edge_iterator; williamr@2: williamr@2: // For internal use williamr@2: typedef csr_graph_tag graph_tag; williamr@2: williamr@2: // Constructors williamr@2: williamr@2: // Default constructor: an empty graph. williamr@2: compressed_sparse_row_graph() williamr@2: : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property(), williamr@2: m_last_source(0) {} williamr@2: williamr@2: // From number of vertices and sorted list of edges williamr@2: template williamr@2: compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, williamr@2: vertices_size_type numverts, williamr@2: edges_size_type numedges = 0, williamr@2: const GraphProperty& prop = GraphProperty()) williamr@2: : inherited_vertex_properties(numverts), m_rowstart(numverts + 1), williamr@2: m_column(0), m_property(prop), m_last_source(numverts) williamr@2: { williamr@2: // Reserving storage in advance can save us lots of time and williamr@2: // memory, but it can only be done if we have forward iterators or williamr@2: // the user has supplied the number of edges. williamr@2: if (numedges == 0) { williamr@2: typedef typename std::iterator_traits::iterator_category williamr@2: category; williamr@2: maybe_reserve_edge_list_storage(edge_begin, edge_end, category()); williamr@2: } else { williamr@2: m_column.reserve(numedges); williamr@2: } williamr@2: williamr@2: EdgeIndex current_edge = 0; williamr@2: Vertex current_vertex_plus_one = 1; williamr@2: m_rowstart[0] = 0; williamr@2: for (InputIterator ei = edge_begin; ei != edge_end; ++ei) { williamr@2: Vertex src = ei->first; williamr@2: Vertex tgt = ei->second; williamr@2: for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one) williamr@2: m_rowstart[current_vertex_plus_one] = current_edge; williamr@2: m_column.push_back(tgt); williamr@2: ++current_edge; williamr@2: } williamr@2: williamr@2: // The remaining vertices have no edges williamr@2: for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one) williamr@2: m_rowstart[current_vertex_plus_one] = current_edge; williamr@2: williamr@2: // Default-construct properties for edges williamr@2: inherited_edge_properties::resize(m_column.size()); williamr@2: } williamr@2: williamr@2: // From number of vertices and sorted list of edges williamr@2: template williamr@2: compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, williamr@2: EdgePropertyIterator ep_iter, williamr@2: vertices_size_type numverts, williamr@2: edges_size_type numedges = 0, williamr@2: const GraphProperty& prop = GraphProperty()) williamr@2: : inherited_vertex_properties(numverts), m_rowstart(numverts + 1), williamr@2: m_column(0), m_property(prop), m_last_source(numverts) williamr@2: { williamr@2: // Reserving storage in advance can save us lots of time and williamr@2: // memory, but it can only be done if we have forward iterators or williamr@2: // the user has supplied the number of edges. williamr@2: if (numedges == 0) { williamr@2: typedef typename std::iterator_traits::iterator_category williamr@2: category; williamr@2: maybe_reserve_edge_list_storage(edge_begin, edge_end, category()); williamr@2: } else { williamr@2: m_column.reserve(numedges); williamr@2: } williamr@2: williamr@2: EdgeIndex current_edge = 0; williamr@2: Vertex current_vertex_plus_one = 1; williamr@2: m_rowstart[0] = 0; williamr@2: for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) { williamr@2: Vertex src = ei->first; williamr@2: Vertex tgt = ei->second; williamr@2: for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one) williamr@2: m_rowstart[current_vertex_plus_one] = current_edge; williamr@2: m_column.push_back(tgt); williamr@2: inherited_edge_properties::push_back(*ep_iter); williamr@2: ++current_edge; williamr@2: } williamr@2: williamr@2: // The remaining vertices have no edges williamr@2: for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one) williamr@2: m_rowstart[current_vertex_plus_one] = current_edge; williamr@2: } williamr@2: williamr@2: // Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function williamr@2: template williamr@2: compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi, williamr@2: vertices_size_type numverts, williamr@2: edges_size_type numedges) williamr@2: : m_property(), m_last_source(0) williamr@2: { williamr@2: assign(g, vi, numverts, numedges); williamr@2: } williamr@2: williamr@2: // Requires VertexListGraph and EdgeListGraph williamr@2: template williamr@2: compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi) williamr@2: : m_property(), m_last_source(0) williamr@2: { williamr@2: assign(g, vi, num_vertices(g), num_edges(g)); williamr@2: } williamr@2: williamr@2: // Requires vertex index map plus requirements of previous constructor williamr@2: template williamr@2: explicit compressed_sparse_row_graph(const Graph& g) williamr@2: : m_property(), m_last_source(0) williamr@2: { williamr@2: assign(g, get(vertex_index, g), num_vertices(g), num_edges(g)); williamr@2: } williamr@2: williamr@2: // From any graph (slow and uses a lot of memory) williamr@2: // Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function williamr@2: // Internal helper function williamr@2: template williamr@2: void williamr@2: assign(const Graph& g, const VertexIndexMap& vi, williamr@2: vertices_size_type numverts, edges_size_type numedges) williamr@2: { williamr@2: inherited_vertex_properties::resize(numverts); williamr@2: m_rowstart.resize(numverts + 1); williamr@2: m_column.resize(numedges); williamr@2: EdgeIndex current_edge = 0; williamr@2: typedef typename boost::graph_traits::vertex_descriptor g_vertex; williamr@2: typedef typename boost::graph_traits::edge_descriptor g_edge; williamr@2: typedef typename boost::graph_traits::out_edge_iterator williamr@2: g_out_edge_iter; williamr@2: williamr@2: for (Vertex i = 0; i != numverts; ++i) { williamr@2: m_rowstart[i] = current_edge; williamr@2: g_vertex v = vertex(i, g); williamr@2: EdgeIndex num_edges_before_this_vertex = current_edge; williamr@2: g_out_edge_iter ei, ei_end; williamr@2: for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) { williamr@2: m_column[current_edge++] = get(vi, target(*ei, g)); williamr@2: } williamr@2: std::sort(m_column.begin() + num_edges_before_this_vertex, williamr@2: m_column.begin() + current_edge); williamr@2: } williamr@2: m_rowstart[numverts] = current_edge; williamr@2: m_last_source = numverts; williamr@2: } williamr@2: williamr@2: // Requires the above, plus VertexListGraph and EdgeListGraph williamr@2: template williamr@2: void assign(const Graph& g, const VertexIndexMap& vi) williamr@2: { williamr@2: assign(g, vi, num_vertices(g), num_edges(g)); williamr@2: } williamr@2: williamr@2: // Requires the above, plus a vertex_index map. williamr@2: template williamr@2: void assign(const Graph& g) williamr@2: { williamr@2: assign(g, get(vertex_index, g), num_vertices(g), num_edges(g)); williamr@2: } williamr@2: williamr@2: using inherited_vertex_properties::operator[]; williamr@2: using inherited_edge_properties::operator[]; williamr@2: williamr@2: // private: non-portable, requires friend templates williamr@2: inherited_vertex_properties& vertex_properties() {return *this;} williamr@2: const inherited_vertex_properties& vertex_properties() const {return *this;} williamr@2: inherited_edge_properties& edge_properties() { return *this; } williamr@2: const inherited_edge_properties& edge_properties() const { return *this; } williamr@2: williamr@2: std::vector m_rowstart; williamr@2: std::vector m_column; williamr@2: GraphProperty m_property; williamr@2: Vertex m_last_source; // Last source of added edge, plus one williamr@2: }; williamr@2: williamr@2: template williamr@2: class csr_edge_descriptor williamr@2: { williamr@2: public: williamr@2: Vertex src; williamr@2: EdgeIndex idx; williamr@2: williamr@2: csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {} williamr@2: csr_edge_descriptor(): src(0), idx(0) {} williamr@2: williamr@2: bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;} williamr@2: bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;} williamr@2: bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;} williamr@2: bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;} williamr@2: bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;} williamr@2: bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;} williamr@2: }; williamr@2: williamr@2: // Construction functions williamr@2: template williamr@2: inline Vertex williamr@2: add_vertex(BOOST_CSR_GRAPH_TYPE& g) { williamr@2: Vertex old_num_verts_plus_one = g.m_rowstart.size(); williamr@2: g.m_rowstart.push_back(EdgeIndex(0)); williamr@2: return old_num_verts_plus_one - 1; williamr@2: } williamr@2: williamr@2: template williamr@2: inline Vertex williamr@2: add_vertices(typename BOOST_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_CSR_GRAPH_TYPE& g) { williamr@2: Vertex old_num_verts_plus_one = g.m_rowstart.size(); williamr@2: g.m_rowstart.resize(old_num_verts_plus_one + count, EdgeIndex(0)); williamr@2: return old_num_verts_plus_one - 1; williamr@2: } williamr@2: williamr@2: // This function requires that (src, tgt) be lexicographically at least as williamr@2: // large as the largest edge in the graph so far williamr@2: template williamr@2: inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor williamr@2: add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) { williamr@2: assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) && williamr@2: src < num_vertices(g)); williamr@2: EdgeIndex num_edges_orig = g.m_column.size(); williamr@2: for (; g.m_last_source <= src; ++g.m_last_source) williamr@2: g.m_rowstart[g.m_last_source] = num_edges_orig; williamr@2: g.m_rowstart[src + 1] = num_edges_orig + 1; williamr@2: g.m_column.push_back(tgt); williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::edge_push_back_type push_back_type; williamr@2: g.edge_properties().push_back(push_back_type()); williamr@2: return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig); williamr@2: } williamr@2: williamr@2: // This function requires that (src, tgt) be lexicographically at least as williamr@2: // large as the largest edge in the graph so far williamr@2: template williamr@2: inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor williamr@2: add_edge(Vertex src, Vertex tgt, williamr@2: typename BOOST_CSR_GRAPH_TYPE::edge_bundled const& p, williamr@2: BOOST_CSR_GRAPH_TYPE& g) { williamr@2: assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) && williamr@2: src < num_vertices(g)); williamr@2: EdgeIndex num_edges_orig = g.m_column.size(); williamr@2: for (; g.m_last_source <= src; ++g.m_last_source) williamr@2: g.m_rowstart[g.m_last_source] = num_edges_orig; williamr@2: g.m_rowstart[src + 1] = num_edges_orig + 1; williamr@2: g.m_column.push_back(tgt); williamr@2: g.edge_properties().push_back(p); williamr@2: return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig); williamr@2: } williamr@2: williamr@2: williamr@2: // From VertexListGraph williamr@2: template williamr@2: inline Vertex williamr@2: num_vertices(const BOOST_CSR_GRAPH_TYPE& g) { williamr@2: return g.m_rowstart.size() - 1; williamr@2: } williamr@2: williamr@2: template williamr@2: std::pair, counting_iterator > williamr@2: inline vertices(const BOOST_CSR_GRAPH_TYPE& g) { williamr@2: return std::make_pair(counting_iterator(0), williamr@2: counting_iterator(num_vertices(g))); williamr@2: } williamr@2: williamr@2: // From IncidenceGraph williamr@2: template williamr@2: class BOOST_CSR_GRAPH_TYPE::out_edge_iterator williamr@2: : public iterator_facade::fast> williamr@2: { williamr@2: public: williamr@2: typedef typename int_t::fast difference_type; williamr@2: williamr@2: out_edge_iterator() {} williamr@2: // Implicit copy constructor OK williamr@2: explicit out_edge_iterator(edge_descriptor edge) : m_edge(edge) { } williamr@2: williamr@2: private: williamr@2: // iterator_facade requirements williamr@2: const edge_descriptor& dereference() const { return m_edge; } williamr@2: williamr@2: bool equal(const out_edge_iterator& other) const williamr@2: { return m_edge == other.m_edge; } williamr@2: williamr@2: void increment() { ++m_edge.idx; } williamr@2: void decrement() { ++m_edge.idx; } williamr@2: void advance(difference_type n) { m_edge.idx += n; } williamr@2: williamr@2: difference_type distance_to(const out_edge_iterator& other) const williamr@2: { return other.m_edge.idx - m_edge.idx; } williamr@2: williamr@2: edge_descriptor m_edge; williamr@2: williamr@2: friend class iterator_core_access; williamr@2: }; williamr@2: williamr@2: template williamr@2: inline Vertex williamr@2: source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e, williamr@2: const BOOST_CSR_GRAPH_TYPE&) williamr@2: { williamr@2: return e.src; williamr@2: } williamr@2: williamr@2: template williamr@2: inline Vertex williamr@2: target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e, williamr@2: const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: return g.m_column[e.idx]; williamr@2: } williamr@2: williamr@2: template williamr@2: inline std::pair williamr@2: out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed; williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it; williamr@2: EdgeIndex v_row_start = g.m_rowstart[v]; williamr@2: EdgeIndex next_row_start = g.m_rowstart[v + 1]; williamr@2: return std::make_pair(it(ed(v, v_row_start)), williamr@2: it(ed(v, (std::max)(v_row_start, next_row_start)))); williamr@2: } williamr@2: williamr@2: template williamr@2: inline EdgeIndex williamr@2: out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: EdgeIndex v_row_start = g.m_rowstart[v]; williamr@2: EdgeIndex next_row_start = g.m_rowstart[v + 1]; williamr@2: return (std::max)(v_row_start, next_row_start) - v_row_start; williamr@2: } williamr@2: williamr@2: // From AdjacencyGraph williamr@2: template williamr@2: inline std::pair williamr@2: adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: EdgeIndex v_row_start = g.m_rowstart[v]; williamr@2: EdgeIndex next_row_start = g.m_rowstart[v + 1]; williamr@2: return std::make_pair(g.m_column.begin() + v_row_start, williamr@2: g.m_column.begin() + williamr@2: (std::max)(v_row_start, next_row_start)); williamr@2: } williamr@2: williamr@2: // Extra, common functions williamr@2: template williamr@2: inline typename graph_traits::vertex_descriptor williamr@2: vertex(typename graph_traits::vertex_descriptor i, williamr@2: const BOOST_CSR_GRAPH_TYPE&) williamr@2: { williamr@2: return i; williamr@2: } williamr@2: williamr@2: // Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i)) williamr@2: // time williamr@2: template williamr@2: inline std::pair williamr@2: edge_range(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: typedef typename std::vector::const_iterator adj_iter; williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter; williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edge_desc; williamr@2: std::pair raw_adjacencies = adjacent_vertices(i, g); williamr@2: std::pair adjacencies = williamr@2: std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j); williamr@2: EdgeIndex idx_begin = adjacencies.first - g.m_column.begin(); williamr@2: EdgeIndex idx_end = adjacencies.second - g.m_column.begin(); williamr@2: return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)), williamr@2: out_edge_iter(edge_desc(i, idx_end))); williamr@2: } williamr@2: williamr@2: template williamr@2: inline std::pair williamr@2: edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter; williamr@2: std::pair range = edge_range(i, j, g); williamr@2: if (range.first == range.second) williamr@2: return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(), williamr@2: false); williamr@2: else williamr@2: return std::make_pair(*range.first, true); williamr@2: } williamr@2: williamr@2: // Find an edge given its index in the graph williamr@2: template williamr@2: inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor williamr@2: edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: typedef typename std::vector::const_iterator row_start_iter; williamr@2: assert (idx < num_edges(g)); williamr@2: row_start_iter src_plus_1 = williamr@2: std::upper_bound(g.m_rowstart.begin(), williamr@2: g.m_rowstart.begin() + g.m_last_source + 1, williamr@2: idx); williamr@2: // Get last source whose rowstart is at most idx williamr@2: // upper_bound returns this position plus 1 williamr@2: Vertex src = (src_plus_1 - g.m_rowstart.begin()) - 1; williamr@2: return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx); williamr@2: } williamr@2: williamr@2: // From EdgeListGraph williamr@2: template williamr@2: class BOOST_CSR_GRAPH_TYPE::edge_iterator williamr@2: { williamr@2: public: williamr@2: typedef std::forward_iterator_tag iterator_category; williamr@2: typedef edge_descriptor value_type; williamr@2: williamr@2: typedef const edge_descriptor* pointer; williamr@2: williamr@2: typedef edge_descriptor reference; williamr@2: typedef typename int_t::fast difference_type; williamr@2: williamr@2: edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0) {} williamr@2: williamr@2: edge_iterator(const compressed_sparse_row_graph& graph, williamr@2: edge_descriptor current_edge, williamr@2: EdgeIndex end_of_this_vertex) williamr@2: : rowstart_array(&graph.m_rowstart[0]), current_edge(current_edge), williamr@2: end_of_this_vertex(end_of_this_vertex) {} williamr@2: williamr@2: // From InputIterator williamr@2: reference operator*() const { return current_edge; } williamr@2: pointer operator->() const { return ¤t_edge; } williamr@2: williamr@2: bool operator==(const edge_iterator& o) const { williamr@2: return current_edge == o.current_edge; williamr@2: } williamr@2: bool operator!=(const edge_iterator& o) const { williamr@2: return current_edge != o.current_edge; williamr@2: } williamr@2: williamr@2: edge_iterator& operator++() { williamr@2: ++current_edge.idx; williamr@2: while (current_edge.idx == end_of_this_vertex) { williamr@2: ++current_edge.src; williamr@2: end_of_this_vertex = rowstart_array[current_edge.src + 1]; williamr@2: } williamr@2: return *this; williamr@2: } williamr@2: williamr@2: edge_iterator operator++(int) { williamr@2: edge_iterator temp = *this; williamr@2: ++*this; williamr@2: return temp; williamr@2: } williamr@2: williamr@2: private: williamr@2: const EdgeIndex* rowstart_array; williamr@2: edge_descriptor current_edge; williamr@2: EdgeIndex end_of_this_vertex; williamr@2: }; williamr@2: williamr@2: template williamr@2: inline EdgeIndex williamr@2: num_edges(const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: return g.m_column.size(); williamr@2: } williamr@2: williamr@2: template williamr@2: std::pair williamr@2: edges(const BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei; williamr@2: typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc; williamr@2: if (g.m_rowstart.size() == 1 || g.m_column.empty()) { williamr@2: return std::make_pair(ei(), ei()); williamr@2: } else { williamr@2: // Find the first vertex that has outgoing edges williamr@2: Vertex src = 0; williamr@2: while (g.m_rowstart[src + 1] == 0) ++src; williamr@2: return std::make_pair(ei(g, edgedesc(src, 0), g.m_rowstart[src + 1]), williamr@2: ei(g, edgedesc(num_vertices(g), g.m_column.size()), 0)); williamr@2: } williamr@2: } williamr@2: williamr@2: // For Property Graph williamr@2: williamr@2: // Graph properties williamr@2: template williamr@2: inline void williamr@2: set_property(BOOST_CSR_GRAPH_TYPE& g, Tag, const Value& value) williamr@2: { williamr@2: get_property_value(g.m_property, Tag()) = value; williamr@2: } williamr@2: williamr@2: template williamr@2: inline williamr@2: typename graph_property::type& williamr@2: get_property(BOOST_CSR_GRAPH_TYPE& g, Tag) williamr@2: { williamr@2: return get_property_value(g.m_property, Tag()); williamr@2: } williamr@2: williamr@2: template williamr@2: inline williamr@2: const williamr@2: typename graph_property::type& williamr@2: get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag) williamr@2: { williamr@2: return get_property_value(g.m_property, Tag()); williamr@2: } williamr@2: williamr@2: // Add edge_index property map williamr@2: template williamr@2: struct csr_edge_index_map williamr@2: { williamr@2: typedef Index value_type; williamr@2: typedef Index reference; williamr@2: typedef Descriptor key_type; williamr@2: typedef readable_property_map_tag category; williamr@2: }; williamr@2: williamr@2: template williamr@2: inline Index williamr@2: get(const csr_edge_index_map&, williamr@2: const typename csr_edge_index_map::key_type& key) williamr@2: { williamr@2: return key.idx; williamr@2: } williamr@2: williamr@2: // Doing the right thing here (by unifying with vertex_index_t and williamr@2: // edge_index_t) breaks GCC. williamr@2: template williamr@2: struct property_map williamr@2: { williamr@2: private: williamr@2: typedef identity_property_map vertex_index_type; williamr@2: typedef typename graph_traits::edge_descriptor williamr@2: edge_descriptor; williamr@2: typedef csr_edge_index_map edge_index_type; williamr@2: williamr@2: typedef typename mpl::if_, williamr@2: edge_index_type, williamr@2: detail::error_property_not_found>::type williamr@2: edge_or_none; williamr@2: williamr@2: public: williamr@2: typedef typename mpl::if_, williamr@2: vertex_index_type, williamr@2: edge_or_none>::type type; williamr@2: williamr@2: typedef type const_type; williamr@2: }; williamr@2: williamr@2: template williamr@2: inline identity_property_map williamr@2: get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&) williamr@2: { williamr@2: return identity_property_map(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline Vertex williamr@2: get(vertex_index_t, williamr@2: const BOOST_CSR_GRAPH_TYPE&, Vertex v) williamr@2: { williamr@2: return v; williamr@2: } williamr@2: williamr@2: template williamr@2: inline typename property_map::const_type williamr@2: get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&) williamr@2: { williamr@2: typedef typename property_map::const_type williamr@2: result_type; williamr@2: return result_type(); williamr@2: } williamr@2: williamr@2: template williamr@2: inline EdgeIndex williamr@2: get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&, williamr@2: typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e) williamr@2: { williamr@2: return e.idx; williamr@2: } williamr@2: williamr@2: // Support for bundled properties williamr@2: template williamr@2: struct property_map williamr@2: { williamr@2: private: williamr@2: typedef graph_traits traits; williamr@2: typedef VertexProperty vertex_bundled; williamr@2: typedef EdgeProperty edge_bundled; williamr@2: typedef typename ct_if<(detail::is_vertex_bundle::value), williamr@2: typename traits::vertex_descriptor, williamr@2: typename traits::edge_descriptor>::type williamr@2: descriptor; williamr@2: williamr@2: public: williamr@2: typedef bundle_property_map williamr@2: type; williamr@2: typedef bundle_property_map const_type; williamr@2: }; williamr@2: williamr@2: template williamr@2: inline williamr@2: typename property_map::type williamr@2: get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g) williamr@2: { williamr@2: typedef typename property_map::type williamr@2: result_type; williamr@2: return result_type(&g, p); williamr@2: } williamr@2: williamr@2: template williamr@2: inline williamr@2: typename property_map::const_type williamr@2: get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g) williamr@2: { williamr@2: typedef typename property_map::const_type williamr@2: result_type; williamr@2: return result_type(&g, p); williamr@2: } williamr@2: williamr@2: template williamr@2: inline T williamr@2: get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g, williamr@2: const Key& key) williamr@2: { williamr@2: return get(get(p, g), key); williamr@2: } williamr@2: williamr@2: template williamr@2: inline void williamr@2: put(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g, williamr@2: const Key& key, const T& value) williamr@2: { williamr@2: put(get(p, g), key, value); williamr@2: } williamr@2: williamr@2: #undef BOOST_CSR_GRAPH_TYPE williamr@2: #undef BOOST_CSR_GRAPH_TEMPLATE_PARMS williamr@2: williamr@2: } // end namespace boost williamr@2: williamr@2: #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP