// Copyright 2005-2009 The Trustees of Indiana University. | |
// 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) | |
// Authors: Jeremiah Willcock | |
// Douglas Gregor | |
// Andrew Lumsdaine | |
// Compressed sparse row graph type internal structure | |
#ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP | |
#define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP | |
#ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP | |
#error This file should only be included from boost/graph/compressed_sparse_row_graph.hpp | |
#endif | |
#include <vector> | |
#include <utility> | |
#include <algorithm> | |
#include <climits> | |
#include <boost/assert.hpp> | |
#include <iterator> | |
#if 0 | |
#include <iostream> // For some debugging code below | |
#endif | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/graph/properties.hpp> | |
#include <boost/graph/filtered_graph.hpp> // For keep_all | |
#include <boost/graph/detail/indexed_properties.hpp> | |
#include <boost/graph/detail/histogram_sort.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> | |
#include <boost/iterator/transform_iterator.hpp> | |
#include <boost/tuple/tuple.hpp> | |
#include <boost/property_map/property_map.hpp> | |
#include <boost/integer.hpp> | |
#include <boost/iterator/iterator_facade.hpp> | |
#include <boost/mpl/if.hpp> | |
#include <boost/graph/graph_selectors.hpp> | |
#include <boost/static_assert.hpp> | |
#include <boost/functional/hash.hpp> | |
#include <boost/utility.hpp> | |
namespace boost { | |
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; | |
// Add edge_index property map | |
template<typename Vertex, typename EdgeIndex> | |
struct csr_edge_index_map | |
{ | |
typedef EdgeIndex value_type; | |
typedef EdgeIndex reference; | |
typedef csr_edge_descriptor<Vertex, EdgeIndex> key_type; | |
typedef readable_property_map_tag category; | |
}; | |
template<typename Vertex, typename EdgeIndex> | |
inline EdgeIndex | |
get(const csr_edge_index_map<Vertex, EdgeIndex>&, | |
const csr_edge_descriptor<Vertex, EdgeIndex>& key) | |
{ | |
return key.idx; | |
} | |
/** Compressed sparse row graph internal structure. | |
* | |
* Vertex and EdgeIndex should be unsigned integral types and should | |
* specialize numeric_limits. | |
*/ | |
template <typename EdgeProperty, | |
typename Vertex = std::size_t, typename EdgeIndex = Vertex> | |
class compressed_sparse_row_structure : | |
public detail::indexed_edge_properties< | |
compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>, | |
EdgeProperty, | |
csr_edge_descriptor<Vertex, EdgeIndex>, | |
csr_edge_index_map<Vertex, EdgeIndex> > { | |
public: | |
typedef detail::indexed_edge_properties< | |
compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>, | |
EdgeProperty, | |
csr_edge_descriptor<Vertex, EdgeIndex>, | |
csr_edge_index_map<Vertex, EdgeIndex> > | |
inherited_edge_properties; | |
typedef Vertex vertices_size_type; | |
typedef Vertex vertex_descriptor; | |
typedef EdgeIndex edges_size_type; | |
static vertex_descriptor null_vertex() { return vertex_descriptor(-1); } | |
std::vector<EdgeIndex> m_rowstart; | |
std::vector<Vertex> m_column; | |
compressed_sparse_row_structure(Vertex numverts = 0) | |
: m_rowstart(numverts + 1, EdgeIndex(0)), m_column() | |
{} | |
// Rebuild graph from number of vertices and multi-pass unsorted list of | |
// edges (filtered using source_pred and mapped using global_to_local) | |
template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred> | |
void | |
assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin, | |
MultiPassInputIterator edge_end, | |
vertices_size_type numlocalverts, | |
const GlobalToLocal& global_to_local, | |
const SourcePred& source_pred) { | |
m_rowstart.clear(); | |
m_rowstart.resize(numlocalverts + 1, 0); | |
typedef std::pair<vertices_size_type, vertices_size_type> edge_type; | |
typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator; | |
typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator; | |
source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>()); | |
source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>()); | |
target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>()); | |
target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>()); | |
boost::graph::detail::count_starts | |
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts, | |
source_pred, boost::make_property_map_function(global_to_local)); | |
m_column.resize(m_rowstart.back()); | |
inherited_edge_properties::resize(m_rowstart.back()); | |
boost::graph::detail::histogram_sort | |
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts, | |
targets_begin, m_column.begin(), | |
source_pred, boost::make_property_map_function(global_to_local)); | |
} | |
// Rebuild graph from number of vertices and multi-pass unsorted list of | |
// edges and their properties (filtered using source_pred and mapped using | |
// global_to_local) | |
template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred> | |
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 SourcePred& source_pred) { | |
m_rowstart.clear(); | |
m_rowstart.resize(numlocalverts + 1, 0); | |
typedef std::pair<vertices_size_type, vertices_size_type> edge_type; | |
typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator; | |
typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator; | |
source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>()); | |
source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>()); | |
target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>()); | |
target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>()); | |
boost::graph::detail::count_starts | |
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts, | |
source_pred, boost::make_property_map_function(global_to_local)); | |
m_column.resize(m_rowstart.back()); | |
inherited_edge_properties::resize(m_rowstart.back()); | |
boost::graph::detail::histogram_sort | |
(sources_begin, sources_end, m_rowstart.begin(), numlocalverts, | |
targets_begin, m_column.begin(), | |
ep_iter, inherited_edge_properties::begin(), | |
source_pred, boost::make_property_map_function(global_to_local)); | |
} | |
// Assign from number of vertices and sorted list of edges | |
template<typename InputIterator, typename GlobalToLocal, typename SourcePred> | |
void assign_from_sorted_edges( | |
InputIterator edge_begin, InputIterator edge_end, | |
const GlobalToLocal& global_to_local, | |
const SourcePred& source_pred, | |
vertices_size_type numlocalverts, | |
edges_size_type numedges_or_zero) { | |
m_column.clear(); | |
m_column.reserve(numedges_or_zero); | |
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 (!source_pred(ei->first)) 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 SourcePred> | |
void assign_from_sorted_edges( | |
InputIterator edge_begin, InputIterator edge_end, | |
EdgePropertyIterator ep_iter, | |
const GlobalToLocal& global_to_local, | |
const SourcePred& source_pred, | |
vertices_size_type numlocalverts, | |
edges_size_type numedges_or_zero) { | |
// 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. | |
edges_size_type numedges = numedges_or_zero; | |
if (numedges == 0) { | |
typedef typename std::iterator_traits<InputIterator>::iterator_category | |
category; | |
numedges = boost::graph::detail::reserve_count_for_single_pass(edge_begin, edge_end); | |
} | |
m_column.clear(); | |
m_column.reserve(numedges_or_zero); | |
inherited_edge_properties::clear(); | |
inherited_edge_properties::reserve(numedges_or_zero); | |
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 (!source_pred(ei->first)) 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; | |
} | |
// 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) { | |
BOOST_ASSERT (sources.size() == targets.size()); | |
// Do an in-place histogram sort (at least that's what I think it is) to | |
// sort sources and targets | |
m_rowstart.clear(); | |
m_rowstart.resize(numverts + 1); | |
boost::graph::detail::count_starts | |
(sources.begin(), sources.end(), m_rowstart.begin(), numverts, | |
keep_all(), boost::make_property_map_function(global_to_local)); | |
boost::graph::detail::histogram_sort_inplace | |
(sources.begin(), m_rowstart.begin(), numverts, | |
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); | |
inherited_edge_properties::resize(m_rowstart.back()); | |
} | |
// 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) { | |
BOOST_ASSERT (sources.size() == targets.size()); | |
BOOST_ASSERT (sources.size() == edge_props.size()); | |
// Do an in-place histogram sort (at least that's what I think it is) to | |
// sort sources and targets | |
m_rowstart.clear(); | |
m_rowstart.resize(numverts + 1); | |
boost::graph::detail::count_starts | |
(sources.begin(), sources.end(), m_rowstart.begin(), numverts, | |
keep_all(), boost::make_property_map_function(global_to_local)); | |
boost::graph::detail::histogram_sort_inplace | |
(sources.begin(), m_rowstart.begin(), numverts, | |
targets.begin(), edge_props.begin(), | |
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); | |
this->m_edge_properties.swap(edge_props); | |
} | |
// 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_rowstart.resize(numverts + 1); | |
m_column.resize(numedges); | |
inherited_edge_properties::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; | |
std::vector<g_vertex> ordered_verts_of_g(numverts); | |
BGL_FORALL_VERTICES_T(v, g, Graph) { | |
ordered_verts_of_g[get(vertex_index, g, v)] = v; | |
} | |
for (Vertex i = 0; i != numverts; ++i) { | |
m_rowstart[i] = current_edge; | |
g_vertex v = ordered_verts_of_g[i]; | |
g_out_edge_iter ei, ei_end; | |
for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) { | |
m_column[current_edge++] = get(vi, target(*ei, g)); | |
} | |
} | |
m_rowstart[numverts] = current_edge; | |
} | |
// 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) { | |
typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator; | |
typedef boost::reverse_iterator<EPIterOrig> EPIter; | |
// Flip sequence | |
BidirectionalIterator first(last_sorted); | |
BidirectionalIterator last(first_sorted); | |
typedef Vertex vertex_t; | |
typedef Vertex vertex_num; | |
typedef EdgeIndex 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 = m_rowstart.size() - 1; 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) | |
} | |
} | |
}; | |
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(): m_graph(0) {} | |
// Implicit copy constructor OK | |
csr_in_edge_iterator(const CSRGraph& graph, | |
EdgeIndex index_in_backward_graph) | |
: m_index_in_backward_graph(index_in_backward_graph), m_graph(&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 |