1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606 |
- // 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
- #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
- #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
- #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/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>
- #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/utility/enable_if.hpp>
- #include <boost/graph/graph_selectors.hpp>
- #include <boost/graph/detail/is_distributed_selector.hpp>
- #include <boost/graph/properties.hpp>
- #include <boost/static_assert.hpp>
- #include <boost/functional/hash.hpp>
- #include <boost/next_prior.hpp>
- #include <boost/property_map/transform_value_property_map.hpp>
- #include <boost/mpl/print.hpp>
- namespace boost {
- // A tag type indicating that the graph in question is a compressed
- // sparse row graph. This is an internal detail of the BGL.
- struct csr_graph_tag;
- // A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate
- // that the edge list passed into the CSR graph is already sorted by source
- // vertex.
- enum edges_are_sorted_t {edges_are_sorted};
- // A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global)
- // used to indicate that the edge list passed into the CSR graph is already
- // sorted by source vertex.
- enum edges_are_sorted_global_t {edges_are_sorted_global};
- // A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
- // indicate that the edge list passed into the CSR graph is not sorted by
- // source vertex. This version caches the edge information in memory, and thus
- // requires only a single pass over the input data.
- enum edges_are_unsorted_t {edges_are_unsorted};
- // A type (edges_are_unsorted_multi_pass_t) and a value
- // (edges_are_unsorted_multi_pass) used to indicate that the edge list passed
- // into the CSR graph is not sorted by source vertex. This version uses less
- // memory but requires multi-pass capability on the iterators.
- enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
- // A type (edges_are_unsorted_multi_pass_global_t) and a value
- // (edges_are_unsorted_multi_pass_global) used to indicate that the edge list
- // passed into the CSR graph is not sorted by source vertex. This version uses
- // less memory but requires multi-pass capability on the iterators. The
- // global mapping and filtering is done here because it is often faster and it
- // greatly simplifies handling of edge properties.
- enum edges_are_unsorted_multi_pass_global_t {edges_are_unsorted_multi_pass_global};
- // A type (construct_inplace_from_sources_and_targets_t) and a value
- // (construct_inplace_from_sources_and_targets) used to indicate that mutable
- // vectors of sources and targets (and possibly edge properties) are being used
- // to construct the CSR graph. These vectors are sorted in-place and then the
- // targets and properties are swapped into the graph data structure.
- enum construct_inplace_from_sources_and_targets_t {construct_inplace_from_sources_and_targets};
- // A type (construct_inplace_from_sources_and_targets_global_t) and a value
- // (construct_inplace_from_sources_and_targets_global) used to indicate that
- // mutable vectors of sources and targets (and possibly edge properties) are
- // being used to construct the CSR graph. These vectors are sorted in-place
- // and then the targets and properties are swapped into the graph data
- // structure. It is assumed that global indices (for distributed CSR) are
- // used, and a map is required to convert those to local indices. This
- // constructor is intended for internal use by the various CSR graphs
- // (sequential and distributed).
- enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
- // A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global)
- // used to indicate that the edge list passed into the CSR graph is not sorted
- // by source vertex. The data is also stored using global vertex indices, and
- // must be filtered to choose only local vertices. This constructor caches the
- // edge information in memory, and thus requires only a single pass over the
- // input data. This constructor is intended for internal use by the
- // distributed CSR constructors.
- enum edges_are_unsorted_global_t {edges_are_unsorted_global};
- /****************************************************************************
- * Local helper macros to reduce typing and clutter later on. *
- ****************************************************************************/
- #define BOOST_CSR_GRAPH_TEMPLATE_PARMS \
- typename Directed, typename VertexProperty, typename EdgeProperty, \
- typename GraphProperty, typename Vertex, typename EdgeIndex
- #define BOOST_CSR_GRAPH_TYPE \
- compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, \
- GraphProperty, Vertex, EdgeIndex>
- #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>
- 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;
- T saved_value;
- const T& dereference() const {return saved_value;}
- bool equal(default_construct_iterator /*i*/) const {return true;}
- void increment() {}
- void decrement() {}
- void advance(typename base_type::difference_type) {}
- typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
- };
- template <typename Less>
- struct compare_first {
- Less less;
- compare_first(Less less = Less()): less(less) {}
- template <typename Tuple>
- bool operator()(const Tuple& a, const Tuple& b) const {
- return less(a.template get<0>(), b.template get<0>());
- }
- };
- template <int N, typename Result>
- struct my_tuple_get_class {
- typedef const Result& result_type;
- template <typename Tuple>
- result_type operator()(const Tuple& t) const {
- return t.template get<N>();
- }
- };
- }
- /** Compressed sparse row graph.
- *
- * Vertex and EdgeIndex should be unsigned integral types and should
- * specialize numeric_limits.
- */
- template<typename Directed = directedS,
- typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property,
- typename Vertex = std::size_t,
- typename EdgeIndex = Vertex>
- 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, typed_identity_property_map<Vertex> >
- {
- public:
- typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
- VertexProperty, Vertex, typed_identity_property_map<Vertex> >
- inherited_vertex_properties;
- // Some tests to prevent use of "void" is a property type (as was done in some test cases):
- BOOST_STATIC_ASSERT((!is_same<VertexProperty, void>::value));
- BOOST_STATIC_ASSERT((!is_same<EdgeProperty, void>::value));
- BOOST_STATIC_ASSERT((!is_same<GraphProperty, void>::value));
- public:
- // For Property Graph
- typedef GraphProperty graph_property_type;
- typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
- 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 directed and bidirectional graphs. In the future,
- * undirected CSR graphs will also be supported.
- */
- // BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
- // Concept requirements:
- // For Graph
- typedef Vertex vertex_descriptor;
- typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
- typedef directed_tag directed_category;
- typedef allow_parallel_edge_tag edge_parallel_category;
- class traversal_category: public incidence_graph_tag,
- public adjacency_graph_tag,
- public vertex_list_graph_tag,
- public edge_list_graph_tag {};
- static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
- // 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;
- // 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 void 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) {}
- // 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)
- {
- m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<vertices_size_type>(), keep_all());
- }
- // 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, typed_identity_property_map<vertices_size_type>(), keep_all());
- }
- // 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);
- }
- // 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);
- }
- // From number of vertices and sorted list of edges (new interface)
- template<typename InputIterator>
- compressed_sparse_row_graph(edges_are_sorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- vertices_size_type numverts,
- edges_size_type numedges = 0,
- const GraphProperty& prop = GraphProperty())
- : m_property(prop)
- {
- m_forward.assign_from_sorted_edges(edge_begin, edge_end, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
- inherited_vertex_properties::resize(numverts);
- }
- // From number of vertices and sorted list of edges (new interface)
- template<typename InputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_sorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- edges_size_type numedges = 0,
- const GraphProperty& prop = GraphProperty())
- : m_property(prop)
- {
- m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
- inherited_vertex_properties::resize(numverts);
- }
- // From number of vertices and sorted list of edges, filtered and global (new interface)
- 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 SourcePred& source_pred,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty())
- : m_property(prop)
- {
- 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 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 SourcePred& source_pred,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty())
- : m_property(prop)
- {
- 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;
- // vectors are returned with unspecified contents but are guaranteed not to
- // share storage with the constructed graph.
- compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
- std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_property(prop)
- {
- m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
- }
- // From number of vertices and mutable vectors of sources and targets,
- // expressed with global vertex indices; vectors are returned with
- // unspecified contents but are guaranteed not to share storage with the
- // constructed graph. This constructor should only be used by the
- // distributed CSR graph.
- template <typename GlobalToLocal>
- compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
- std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- vertices_size_type numlocalverts,
- GlobalToLocal global_to_local,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_property(prop)
- {
- 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
- // properties; vectors are returned with unspecified contents but are
- // guaranteed not to share storage with the constructed graph.
- compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
- std::vector<vertex_descriptor>& sources,
- std::vector<vertex_descriptor>& targets,
- 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_property(prop)
- {
- m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
- }
- // From number of vertices and mutable vectors of sources and targets and
- // edge properties, expressed with global vertex indices; vectors are
- // returned with unspecified contents but are guaranteed not to share
- // storage with the constructed graph. This constructor should only be used
- // by the distributed CSR graph.
- template <typename GlobalToLocal>
- 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 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_property(prop)
- {
- 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
- // cached in coordinate form before creating the actual graph.
- template<typename InputIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_property(prop)
- {
- std::vector<vertex_descriptor> sources, targets;
- boost::graph::detail::split_into_separate_coords
- (edge_begin, edge_end, sources, targets);
- m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
- }
- // From number of vertices and single-pass range of unsorted edges and
- // single-pass range of edge properties. Data is cached in coordinate form
- // before creating the actual graph.
- template<typename InputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(edges_are_unsorted_t,
- InputIterator edge_begin, InputIterator edge_end,
- EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_property(prop)
- {
- std::vector<vertex_descriptor> sources, targets;
- 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++;
- }
- m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
- }
- // 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 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 SourcePred& source_pred,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_property(prop)
- {
- std::vector<vertex_descriptor> sources, targets;
- 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
- // single-pass range of edge properties. Data is cached in coordinate form
- // before creating the actual graph. Edges are filtered and transformed for
- // use in a distributed graph.
- template<typename InputIterator, typename EdgePropertyIterator,
- typename GlobalToLocal, typename 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 SourcePred& source_pred,
- const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_property(prop)
- {
- std::vector<vertex_descriptor> sources, targets;
- 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);
- }
- // 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)
- {
- 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, typed_identity_property_map<vertices_size_type>());
- }
- // 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 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, typed_identity_property_map<vertices_size_type>());
- }
- // 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 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, typed_identity_property_map<vertices_size_type>());
- }
- 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)]; }
- // Directly access a graph bundle
- graph_bundled& operator[](graph_bundle_t)
- { return get_property(*this); }
- const graph_bundled& operator[](graph_bundle_t) const
- { return get_property(*this); }
- // 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;
- GraphProperty m_property;
- };
- 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, typed_identity_property_map<Vertex> >
- {
- public:
- typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
- VertexProperty, Vertex, typed_identity_property_map<Vertex> >
- inherited_vertex_properties;
- public:
- // For Property Graph
- typedef GraphProperty graph_property_type;
- typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
- // 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 {};
- static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
- // 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;
- // 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,
- typed_identity_property_map<Vertex>(),
- 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)
- {
- m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<Vertex>(), keep_all());
- set_up_backward_property_links();
- }
- // 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, typed_identity_property_map<Vertex>(), 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);
- set_up_backward_property_links();
- }
- // Requires the above, plus VertexListGraph and EdgeListGraph
- template<typename Graph, typename VertexIndexMap>
- void assign(const Graph& g, const VertexIndexMap& vi)
- {
- 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);
- set_up_backward_property_links();
- }
- // 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);
- set_up_backward_property_links();
- }
- 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;
- };
- // Construction functions
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- add_vertex(BOOST_CSR_GRAPH_TYPE& 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_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- 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_DIR_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- 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.vertex_properties().resize(num_vertices(g));
- return old_num_verts_plus_one - 1;
- }
- // Add edges from a sorted (smallest sources first) range of pairs and edge
- // properties
- 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_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_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
- void
- add_edges_sorted(
- BidirectionalIteratorOrig first_sorted,
- BidirectionalIteratorOrig last_sorted,
- BOOST_DIR_CSR_GRAPH_TYPE& g) {
- g.add_edges_sorted_internal(first_sorted, last_sorted);
- }
- template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
- typename EPIterOrig, typename GlobalToLocal>
- void
- add_edges_sorted_global(
- BidirectionalIteratorOrig first_sorted,
- BidirectionalIteratorOrig last_sorted,
- EPIterOrig ep_iter_sorted,
- const GlobalToLocal& global_to_local,
- 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_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_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_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
- typename GlobalToLocal>
- inline void
- add_edges_global(InputIterator first, InputIterator last,
- 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_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
- inline void
- 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_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_DIR_CSR_GRAPH_TYPE& g) {
- g.add_edges_internal(first, last, ep_iter, ep_iter_end);
- }
- 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_DIR_CSR_GRAPH_TYPE& g) {
- g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
- }
- // From VertexListGraph
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
- return g.m_forward.m_rowstart.size() - 1;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- std::pair<counting_iterator<Vertex>, counting_iterator<Vertex> >
- inline vertices(const BOOST_CSR_GRAPH_TYPE& g) {
- return std::make_pair(counting_iterator<Vertex>(0),
- counting_iterator<Vertex>(num_vertices(g)));
- }
- // From IncidenceGraph
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
- const BOOST_CSR_GRAPH_TYPE&)
- {
- return e.src;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
- const BOOST_CSR_GRAPH_TYPE& g)
- {
- return g.m_forward.m_column[e.idx];
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
- typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
- out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
- {
- 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_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, 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_forward.m_rowstart[v];
- EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
- return next_row_start - v_row_start;
- }
- 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::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(g, v_row_start),
- it(g, 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;
- }
- // 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_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() + next_row_start);
- }
- // Extra, common functions
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor
- vertex(typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor i,
- const BOOST_CSR_GRAPH_TYPE&)
- {
- return i;
- }
- // 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, g) == j)
- return std::make_pair(*range.first, true);
- }
- return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
- false);
- }
- // Find an edge given its index in the graph
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
- edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g)
- {
- typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
- BOOST_ASSERT (idx < num_edges(g));
- row_start_iter src_plus_1 =
- std::upper_bound(g.m_forward.m_rowstart.begin(),
- g.m_forward.m_rowstart.end(),
- idx);
- // Get last source whose rowstart is at most idx
- // upper_bound returns this position plus 1
- Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1;
- return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline EdgeIndex
- num_edges(const BOOST_CSR_GRAPH_TYPE& g)
- {
- return g.m_forward.m_column.size();
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_iterator,
- typename BOOST_CSR_GRAPH_TYPE::edge_iterator>
- edges(const BOOST_CSR_GRAPH_TYPE& g)
- {
- typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
- typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
- 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_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));
- }
- }
- // For Property Graph
- // Graph properties
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value>
- inline void
- set_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag, const Value& value)
- {
- get_property_value(g.m_property, tag) = value;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
- inline
- typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
- get_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag)
- {
- return get_property_value(g.m_property, tag);
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
- inline
- const
- typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
- get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag tag)
- {
- return get_property_value(g.m_property, tag);
- }
- template <typename G, typename Tag, typename Kind>
- struct csr_property_map_helper {};
- // Kind == void for invalid property tags, so we can use that to SFINAE out
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, vertex_property_tag> {
- typedef vertex_all_t all_tag;
- typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type>::key_type key_type;
- typedef VertexProperty plist_type;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type all_type;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type all_const_type;
- typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
- typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
- };
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, edge_property_tag> {
- typedef edge_all_t all_tag;
- typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type>::key_type key_type;
- typedef EdgeProperty plist_type;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type all_type;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type all_const_type;
- typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
- typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
- };
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, graph_property_tag> {
- typedef graph_all_t all_tag;
- typedef BOOST_CSR_GRAPH_TYPE* key_type;
- typedef GraphProperty plist_type;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type all_type;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type all_const_type;
- typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
- typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
- };
- // disable_if isn't truly necessary but required to avoid ambiguity with specializations below
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- struct property_map<BOOST_CSR_GRAPH_TYPE, Tag, typename disable_if<detail::is_distributed_selector<Vertex> >::type>:
- csr_property_map_helper<
- BOOST_CSR_GRAPH_TYPE,
- Tag,
- typename detail::property_kind_from_graph<BOOST_CSR_GRAPH_TYPE, Tag>
- ::type> {};
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type
- get(Tag tag, BOOST_CSR_GRAPH_TYPE& g) {
- return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
- }
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type
- get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g) {
- return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
- }
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type>::reference
- get(Tag tag, BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::type outer_pm;
- return lookup_one_property<typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
- }
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type>::reference
- get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::const_type outer_pm;
- return lookup_one_property<const typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
- }
- template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
- void
- put(Tag tag,
- BOOST_CSR_GRAPH_TYPE& g,
- typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k,
- typename lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::type val) {
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
- lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::lookup(get(all_tag(), g, k), tag) = val;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
- {
- typedef typed_identity_property_map<Vertex> type;
- typedef type const_type;
- };
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
- {
- typedef detail::csr_edge_index_map<Vertex, EdgeIndex> type;
- typedef type const_type;
- };
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
- {
- typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::vertex_map_type type;
- typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::const_vertex_map_type const_type;
- };
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- struct property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
- {
- typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::edge_map_type type;
- typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::const_edge_map_type const_type;
- };
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- struct property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
- {
- typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, typename BOOST_CSR_GRAPH_TYPE::graph_property_type> type;
- typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, const typename BOOST_CSR_GRAPH_TYPE::graph_property_type> const_type;
- };
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typed_identity_property_map<Vertex>
- get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
- {
- return typed_identity_property_map<Vertex>();
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- get(vertex_index_t,
- const BOOST_CSR_GRAPH_TYPE&, Vertex v)
- {
- return v;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typed_identity_property_map<Vertex>
- get(vertex_index_t, BOOST_CSR_GRAPH_TYPE&)
- {
- return typed_identity_property_map<Vertex>();
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline Vertex
- get(vertex_index_t,
- BOOST_CSR_GRAPH_TYPE&, Vertex v)
- {
- return v;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
- get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&)
- {
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
- result_type;
- return result_type();
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline EdgeIndex
- get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&,
- typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
- {
- return e.idx;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
- get(edge_index_t, BOOST_CSR_GRAPH_TYPE&)
- {
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
- result_type;
- return result_type();
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline EdgeIndex
- get(edge_index_t, BOOST_CSR_GRAPH_TYPE&,
- typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
- {
- return e.idx;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type
- get(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g)
- {
- return g.get_vertex_bundle(get(vertex_index, g));
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type
- get(vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g)
- {
- return g.get_vertex_bundle(get(vertex_index, g));
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline VertexProperty&
- get(vertex_all_t,
- BOOST_CSR_GRAPH_TYPE& g, Vertex v)
- {
- return get(vertex_all, g)[v];
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline const VertexProperty&
- get(vertex_all_t,
- const BOOST_CSR_GRAPH_TYPE& g, Vertex v)
- {
- return get(vertex_all, g)[v];
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline void
- put(vertex_all_t,
- BOOST_CSR_GRAPH_TYPE& g,
- Vertex v,
- const VertexProperty& val)
- {
- put(get(vertex_all, g), v, val);
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type
- get(edge_all_t, BOOST_CSR_GRAPH_TYPE& g)
- {
- return g.m_forward.get_edge_bundle(get(edge_index, g));
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type
- get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g)
- {
- return g.m_forward.get_edge_bundle(get(edge_index, g));
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline EdgeProperty&
- get(edge_all_t,
- BOOST_CSR_GRAPH_TYPE& g,
- const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
- {
- return get(edge_all, g)[e];
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline const EdgeProperty&
- get(edge_all_t,
- const BOOST_CSR_GRAPH_TYPE& g,
- const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
- {
- return get(edge_all, g)[e];
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline void
- put(edge_all_t,
- BOOST_CSR_GRAPH_TYPE& g,
- const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e,
- const EdgeProperty& val)
- {
- put(get(edge_all, g), e, val);
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type
- get(graph_all_t, BOOST_CSR_GRAPH_TYPE& g)
- {
- return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type(g.m_property);
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type
- get(graph_all_t, const BOOST_CSR_GRAPH_TYPE& g)
- {
- return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type(g.m_property);
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline GraphProperty&
- get(graph_all_t,
- BOOST_CSR_GRAPH_TYPE& g,
- BOOST_CSR_GRAPH_TYPE*)
- {
- return g.m_property;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline const GraphProperty&
- get(graph_all_t,
- const BOOST_CSR_GRAPH_TYPE& g,
- BOOST_CSR_GRAPH_TYPE*)
- {
- return g.m_property;
- }
- template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
- inline void
- put(graph_all_t,
- BOOST_CSR_GRAPH_TYPE& g,
- BOOST_CSR_GRAPH_TYPE*,
- const GraphProperty& val)
- {
- g.m_property = val;
- }
- #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
- #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
|