diff options
Diffstat (limited to 'boost/graph')
60 files changed, 2371 insertions, 1989 deletions
diff --git a/boost/graph/adj_list_serialize.hpp b/boost/graph/adj_list_serialize.hpp index c1ff4111d0..01db50282f 100644 --- a/boost/graph/adj_list_serialize.hpp +++ b/boost/graph/adj_list_serialize.hpp @@ -61,6 +61,8 @@ inline void save( ar << serialization::make_nvp("v" , indices[target(e,graph)]); ar << serialization::make_nvp("edge_property", get(edge_all_t(), graph, e) ); } + + ar << serialization::make_nvp("graph_property", get_property(graph, graph_all_t()) ); } @@ -95,6 +97,7 @@ inline void load( boost::tie(e,inserted) = add_edge(verts[u], verts[v], graph); ar >> serialization::make_nvp("edge_property", get(edge_all_t(), graph, e) ); } + ar >> serialization::make_nvp("graph_property", get_property(graph, graph_all_t()) ); } template<class Archive, class OEL, class VL, class D, class VP, class EP, class GP, class EL> diff --git a/boost/graph/adjacency_list.hpp b/boost/graph/adjacency_list.hpp index 5034fec5a5..21b7500d26 100644 --- a/boost/graph/adjacency_list.hpp +++ b/boost/graph/adjacency_list.hpp @@ -51,11 +51,6 @@ namespace boost { // adjacency_list, and the container_gen traits class which is used // to map the selectors to the container type used to implement the // graph. - // - // The main container_gen traits class uses partial specialization, - // so we also include a workaround. - -#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION #if !defined BOOST_NO_SLIST struct slistS {}; @@ -130,93 +125,6 @@ namespace boost { typedef boost::unordered_multiset<ValueType> type; }; -#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION - -#if !defined BOOST_NO_SLIST - struct slistS { - template <class T> - struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::slist<T> type; }; - }; -#endif - - struct vecS { - template <class T> - struct bind_ { typedef std::vector<T> type; }; - }; - - struct listS { - template <class T> - struct bind_ { typedef std::list<T> type; }; - }; - - struct setS { - template <class T> - struct bind_ { typedef std::set<T, std::less<T> > type; }; - }; - - - struct mapS { - template <class T> - struct bind_ { typedef std::set<T, std::less<T> > type; }; - }; - - struct multisetS { - template <class T> - struct bind_ { typedef std::multiset<T, std::less<T> > type; }; - }; - - struct multimapS { - template <class T> - struct bind_ { typedef std::multiset<T, std::less<T> > type; }; - }; - - struct hash_setS { - template <class T> - struct bind_ { typedef boost::unordered_set<T> type; }; - }; - - struct hash_mapS { - template <class T> - struct bind_ { typedef boost::unordered_set<T> type; }; - }; - - struct hash_multisetS { - template <class T> - struct bind_ { typedef boost::unordered_multiset<T> type; }; - }; - - struct hash_multimapS { - template <class T> - struct bind_ { typedef boost::unordered_multiset<T> type; }; - }; - - template <class Selector> struct container_selector { - typedef vecS type; - }; - -#define BOOST_CONTAINER_SELECTOR(NAME) \ - template <> struct container_selector<NAME> { \ - typedef NAME type; \ - } - - BOOST_CONTAINER_SELECTOR(vecS); - BOOST_CONTAINER_SELECTOR(listS); - BOOST_CONTAINER_SELECTOR(mapS); - BOOST_CONTAINER_SELECTOR(setS); - BOOST_CONTAINER_SELECTOR(multisetS); - BOOST_CONTAINER_SELECTOR(hash_mapS); -#if !defined BOOST_NO_SLIST - BOOST_CONTAINER_SELECTOR(slistS); -#endif - - template <class Selector, class ValueType> - struct container_gen { - typedef typename container_selector<Selector>::type Select; - typedef typename Select:: template bind_<ValueType>::type type; - }; - -#endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION - template <class StorageSelector> struct parallel_edge_traits { }; @@ -354,13 +262,7 @@ namespace boost { adjacency_list<OutEdgeListS,VertexListS,DirectedS, VertexProperty,EdgeProperty,GraphProperty,EdgeListS>, VertexListS, OutEdgeListS, DirectedS, -#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES) - typename detail::retag_property_list<vertex_bundle_t, - VertexProperty>::type, - typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type, -#else VertexProperty, EdgeProperty, -#endif GraphProperty, EdgeListS>::type, // Support for named vertices public graph::maybe_named_graph< @@ -371,25 +273,14 @@ namespace boost { VertexProperty> { public: -#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES) - typedef typename graph_detail::graph_prop<GraphProperty>::property graph_property_type; - typedef typename graph_detail::graph_prop<GraphProperty>::bundle graph_bundled; - - typedef typename graph_detail::vertex_prop<VertexProperty>::property vertex_property_type; - typedef typename graph_detail::vertex_prop<VertexProperty>::bundle vertex_bundled; - - typedef typename graph_detail::edge_prop<EdgeProperty>::property edge_property_type; - typedef typename graph_detail::edge_prop<EdgeProperty>::bundle edge_bundled; -#else typedef GraphProperty graph_property_type; - typedef no_graph_bundle graph_bundled; + typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled; typedef VertexProperty vertex_property_type; - typedef no_vertex_bundle vertex_bundled; + typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type vertex_bundled; typedef EdgeProperty edge_property_type; - typedef no_edge_bundle edge_bundled; -#endif + typedef typename lookup_one_property<EdgeProperty, edge_bundle_t>::type edge_bundled; private: typedef adjacency_list self; @@ -502,20 +393,20 @@ namespace boost { #define ADJLIST adjacency_list<OEL,VL,D,VP,EP,GP,EL> template<ADJLIST_PARAMS, typename Tag, typename Value> - inline void set_property(ADJLIST& g, Tag, Value const& value) { - get_property_value(*g.m_property, Tag()) = value; + inline void set_property(ADJLIST& g, Tag tag, Value const& value) { + get_property_value(*g.m_property, tag) = value; } template<ADJLIST_PARAMS, typename Tag> inline typename graph_property<ADJLIST, Tag>::type& - get_property(ADJLIST& g, Tag) { - return get_property_value(*g.m_property, Tag()); + get_property(ADJLIST& g, Tag tag) { + return get_property_value(*g.m_property, tag); } template<ADJLIST_PARAMS, typename Tag> inline typename graph_property<ADJLIST, Tag>::type const& - get_property(ADJLIST const& g, Tag) { - return get_property_value(*g.m_property, Tag()); + get_property(ADJLIST const& g, Tag tag) { + return get_property_value(*g.m_property, tag); } // dwa 09/25/00 - needed to be more explicit so reverse_graph would work. @@ -545,58 +436,6 @@ namespace boost { return e.m_target; } - // Support for bundled properties -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES - template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty, - typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle> - inline - typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, - GraphProperty, EdgeListS>, T Bundle::*>::type - get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, - GraphProperty, EdgeListS>& g) - { - typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, - EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::type - result_type; - return result_type(&g, p); - } - - template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty, - typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle> - inline - typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, - GraphProperty, EdgeListS>, T Bundle::*>::const_type - get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, - GraphProperty, EdgeListS> const & g) - { - typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, - EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::const_type - result_type; - return result_type(&g, p); - } - - template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty, - typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle, - typename Key> - inline T - get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, - GraphProperty, EdgeListS> const & g, const Key& key) - { - return get(get(p, g), key); - } - - template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty, - typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle, - typename Key> - inline void - put(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty, - GraphProperty, EdgeListS>& g, const Key& key, const T& value) - { - put(get(p, g), key, value); - } - -#endif - // Mutability Traits template <ADJLIST_PARAMS> struct graph_mutability_traits<ADJLIST> { diff --git a/boost/graph/adjacency_list_io.hpp b/boost/graph/adjacency_list_io.hpp index 91b0b465d7..aaba8a43c3 100644 --- a/boost/graph/adjacency_list_io.hpp +++ b/boost/graph/adjacency_list_io.hpp @@ -40,7 +40,7 @@ namespace boost { template<class Tag, class Value, class Next> std::istream& operator >> ( std::istream& in, property<Tag,Value,Next>& p ) { - in >> p.m_value >> *(static_cast<Next*>(&p)); // houpla !! + in >> p.m_value >> p.m_base; // houpla !! return in; } @@ -65,7 +65,7 @@ template<class Tag, class Value, class Next, class V, class Stag> void get ( property<Tag,Value,Next>& p, const V& v, Stag s ) { - get( *(static_cast<Next*>(&p)),v,s ); + get( p.m_base,v,s ); } template<class Value, class Next, class V, class Stag> @@ -82,7 +82,7 @@ void getSubset ( property<Tag,Value,Next>& p, const property<Stag,Svalue,Snext>& s ) { get( p, s.m_value, Stag() ); - getSubset( p, Snext(s) ); + getSubset( p, s.m_base ); } template<class Tag, class Value, class Next, @@ -215,7 +215,7 @@ struct PropertyPrinter template<class Val> PropertyPrinter& operator () ( std::ostream& out, const Val& v ) { - typename property_map<Graph,Tag>::type ps = get(Tag(), *graph); + typename property_map<Graph,Tag>::const_type ps = get(Tag(), *graph); out << ps[ v ] <<" "; PropertyPrinter<Graph,Next> print(*graph); print(out, v); @@ -248,7 +248,7 @@ struct PropertyPrinter<Graph, property<Tag, Value, Next> > template<class Val> PropertyPrinter& operator () ( std::ostream& out, const Val& v ) { - typename property_map<Graph,Tag>::type ps = get(Tag(), *graph); + typename property_map<Graph,Tag>::const_type ps = get(Tag(), *graph); out << ps[ v ] <<" "; PropertyPrinter<Graph,Next> print(*graph); print(out, v); diff --git a/boost/graph/adjacency_matrix.hpp b/boost/graph/adjacency_matrix.hpp index 47d8d5f28a..65cf27a57d 100644 --- a/boost/graph/adjacency_matrix.hpp +++ b/boost/graph/adjacency_matrix.hpp @@ -21,6 +21,7 @@ #include <boost/graph/graph_mutability_traits.hpp> #include <boost/graph/graph_selectors.hpp> #include <boost/mpl/if.hpp> +#include <boost/mpl/bool.hpp> #include <boost/graph/adjacency_iterator.hpp> #include <boost/graph/detail/edge.hpp> #include <boost/iterator/iterator_adaptor.hpp> @@ -29,7 +30,10 @@ #include <boost/graph/properties.hpp> #include <boost/tuple/tuple.hpp> #include <boost/static_assert.hpp> -#include <boost/type_traits/ice.hpp> +#include <boost/type_traits.hpp> +#include <boost/property_map/property_map.hpp> +#include <boost/property_map/transform_value_property_map.hpp> +#include <boost/property_map/function_property_map.hpp> namespace boost { @@ -484,25 +488,14 @@ namespace boost { BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value)); #endif -#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES) - typedef typename graph_detail::graph_prop<GraphProperty>::property graph_property_type; - typedef typename graph_detail::graph_prop<GraphProperty>::bundle graph_bundled; - - typedef typename graph_detail::vertex_prop<VertexProperty>::property vertex_property_type; - typedef typename graph_detail::vertex_prop<VertexProperty>::bundle vertex_bundled; - - typedef typename graph_detail::edge_prop<EdgeProperty>::property edge_property_type; - typedef typename graph_detail::edge_prop<EdgeProperty>::bundle edge_bundled; -#else typedef GraphProperty graph_property_type; - typedef no_graph_bundle graph_bundled; + typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled; typedef VertexProperty vertex_property_type; - typedef no_vertex_bundle vertex_bundled; + typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type vertex_bundled; typedef EdgeProperty edge_property_type; - typedef no_edge_bundle edge_bundled; -#endif + typedef typename lookup_one_property<EdgeProperty, edge_bundle_t>::type edge_bundled; public: // should be private typedef typename mpl::if_<typename has_property<edge_property_type>::type, @@ -640,16 +633,16 @@ namespace boost { #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES // Directly access a vertex or edge bundle vertex_bundled& operator[](vertex_descriptor v) - { return get(vertex_bundle, *this)[v]; } + { return get(vertex_bundle, *this, v); } const vertex_bundled& operator[](vertex_descriptor v) const - { return get(vertex_bundle, *this)[v]; } + { return get(vertex_bundle, *this, v); } edge_bundled& operator[](edge_descriptor e) - { return get(edge_bundle, *this)[e]; } + { return get(edge_bundle, *this, e); } const edge_bundled& operator[](edge_descriptor e) const - { return get(edge_bundle, *this)[e]; } + { return get(edge_bundle, *this, e); } graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } @@ -1035,326 +1028,211 @@ namespace boost { //========================================================================= // Functions required by the PropertyGraph concept - // O(1) - template <typename D, typename VP, typename EP, typename GP, typename A, - typename Tag, typename Value> - inline void - set_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag, const Value& value) - { - get_property_value(g.m_property, Tag()) = value; - } - template <typename D, typename VP, typename EP, typename GP, typename A, - typename Tag> - inline typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& - get_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag) - { - return get_property_value(g.m_property, Tag()); - } + typename Prop, typename Kind> + struct adj_mat_pm_helper; template <typename D, typename VP, typename EP, typename GP, typename A, - typename Tag> - inline const typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& - get_property(const adjacency_matrix<D,VP,EP,GP,A>& g, Tag) - { - return get_property_value(g.m_property, Tag()); - } + typename Prop> + struct adj_mat_pm_helper<D, VP, EP, GP, A, Prop, vertex_property_tag> { + typedef typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::vertex_descriptor arg_type; + typedef typed_identity_property_map<arg_type> vi_map_type; + typedef iterator_property_map<typename std::vector<VP>::iterator, vi_map_type> all_map_type; + typedef iterator_property_map<typename std::vector<VP>::const_iterator, vi_map_type> all_map_const_type; + typedef transform_value_property_map< + detail::lookup_one_property_f<VP, Prop>, + all_map_type> + type; + typedef transform_value_property_map< + detail::lookup_one_property_f<const VP, Prop>, + all_map_const_type> + const_type; + typedef typename property_traits<type>::reference single_nonconst_type; + typedef typename property_traits<const_type>::reference single_const_type; + + static type get_nonconst(adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop) { + return type(prop, all_map_type(g.m_vertex_properties.begin(), vi_map_type())); + } - //========================================================================= - // Vertex Property Map + static const_type get_const(const adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop) { + return const_type(prop, all_map_const_type(g.m_vertex_properties.begin(), vi_map_type())); + } - template <typename GraphPtr, typename Vertex, typename T, typename R, - typename Tag> - class adj_matrix_vertex_property_map - : public put_get_helper<R, - adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> > - { - public: - typedef T value_type; - typedef R reference; - typedef Vertex key_type; - typedef boost::lvalue_property_map_tag category; - adj_matrix_vertex_property_map() { } - adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { } - inline reference operator[](key_type v) const { - return get_property_value(m_g->m_vertex_properties[v], Tag()); + static single_nonconst_type get_nonconst_one(adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop, arg_type v) { + return lookup_one_property<VP, Prop>::lookup(g.m_vertex_properties[v], prop); } - GraphPtr m_g; - }; - template <class Property, class Vertex> - struct adj_matrix_vertex_id_map - : public boost::put_get_helper<Vertex, - adj_matrix_vertex_id_map<Property, Vertex> > - { - typedef Vertex value_type; - typedef Vertex reference; - typedef Vertex key_type; - typedef boost::readable_property_map_tag category; - adj_matrix_vertex_id_map() { } - template <class Graph> - inline adj_matrix_vertex_id_map(const Graph&) { } - inline value_type operator[](key_type v) const { return v; } + static single_const_type get_const_one(const adjacency_matrix<D, VP, EP, GP, A>& g, Prop prop, arg_type v) { + return lookup_one_property<const VP, Prop>::lookup(g.m_vertex_properties[v], prop); + } }; - namespace detail { - - struct adj_matrix_any_vertex_pa { - template <class Tag, class Graph, class Property> - struct bind_ { - typedef typename property_value<Property,Tag>::type Value; - typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; - - typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&, - Tag> type; - typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value, - const Value&, Tag> const_type; - }; - }; - struct adj_matrix_id_vertex_pa { - template <class Tag, class Graph, class Property> - struct bind_ { - typedef typename Graph::vertex_descriptor Vertex; - typedef adj_matrix_vertex_id_map<Property, Vertex> type; - typedef adj_matrix_vertex_id_map<Property, Vertex> const_type; - }; - }; - - template <class Tag> - struct adj_matrix_choose_vertex_pa_helper { - typedef adj_matrix_any_vertex_pa type; - }; - template <> - struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> { - typedef adj_matrix_id_vertex_pa type; - }; - - template <class Tag, class Graph, class Property> - struct adj_matrix_choose_vertex_pa { - typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper; - typedef typename Helper::template bind_<Tag,Graph,Property> Bind; - typedef typename Bind::type type; - typedef typename Bind::const_type const_type; - }; - - struct adj_matrix_vertex_property_selector { - template <class Graph, class Property, class Tag> - struct bind_ { - typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice; - typedef typename Choice::type type; - typedef typename Choice::const_type const_type; - }; + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + struct adj_mat_pm_helper<D, VP, EP, GP, A, Tag, edge_property_tag> { + typedef typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor edge_descriptor; + + template <typename IsConst> + struct lookup_property_from_edge { + Tag tag; + lookup_property_from_edge(Tag tag): tag(tag) {} + typedef typename boost::mpl::if_<IsConst, const EP, EP>::type ep_type_nonref; + typedef ep_type_nonref& ep_type; + typedef typename lookup_one_property<ep_type_nonref, Tag>::type& result_type; + result_type operator()(edge_descriptor e) const { + return lookup_one_property<ep_type_nonref, Tag>::lookup(*static_cast<ep_type_nonref*>(e.get_property()), tag); + } }; - } // namespace detail - - template <> - struct vertex_property_selector<adjacency_matrix_class_tag> { - typedef detail::adj_matrix_vertex_property_selector type; - }; + typedef function_property_map< + lookup_property_from_edge<boost::mpl::false_>, + typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor> type; + typedef function_property_map< + lookup_property_from_edge<boost::mpl::true_>, + typename graph_traits<adjacency_matrix<D, VP, EP, GP, A> >::edge_descriptor> const_type; + typedef edge_descriptor arg_type; + typedef typename lookup_property_from_edge<boost::mpl::false_>::result_type single_nonconst_type; + typedef typename lookup_property_from_edge<boost::mpl::true_>::result_type single_const_type; + + static type get_nonconst(adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag) { + return type(tag); + } - //========================================================================= - // Edge Property Map + static const_type get_const(const adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag) { + return const_type(tag); + } + static single_nonconst_type get_nonconst_one(adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag, edge_descriptor e) { + return lookup_one_property<EP, Tag>::lookup(*static_cast<EP*>(e.get_property()), tag); + } - template <typename Directed, typename Property, typename Vertex, - typename T, typename R, typename Tag> - class adj_matrix_edge_property_map - : public put_get_helper<R, - adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> > - { - public: - typedef T value_type; - typedef R reference; - typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type; - typedef boost::lvalue_property_map_tag category; - inline reference operator[](key_type e) const { - Property& p = *(Property*)e.get_property(); - return get_property_value(p, Tag()); + static single_const_type get_const_one(const adjacency_matrix<D, VP, EP, GP, A>& g, Tag tag, edge_descriptor e) { + return lookup_one_property<const EP, Tag>::lookup(*static_cast<const EP*>(e.get_property()), tag); } }; - struct adj_matrix_edge_property_selector { - template <class Graph, class Property, class Tag> - struct bind_ { - typedef typename property_value<Property,Tag>::type T; - typedef typename Graph::vertex_descriptor Vertex; - typedef adj_matrix_edge_property_map<typename Graph::directed_category, - Property, Vertex, T, T&, Tag> type; - typedef adj_matrix_edge_property_map<typename Graph::directed_category, - Property, Vertex, T, const T&, Tag> const_type; - }; - }; - template <> - struct edge_property_selector<adjacency_matrix_class_tag> { - typedef adj_matrix_edge_property_selector type; - }; - //========================================================================= - // Functions required by PropertyGraph + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + struct property_map<adjacency_matrix<D,VP,EP,GP,A>, Tag> + : adj_mat_pm_helper<D, VP, EP, GP, A, Tag, + typename detail::property_kind_from_graph<adjacency_matrix<D, VP, EP, GP, A>, Tag>::type> {}; - namespace detail { + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::type + get(Tag tag, adjacency_matrix<D, VP, EP, GP, A>& g) { + return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst(g, tag); + } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A> - typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::type - get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property, - vertex_property_tag) - { - typedef adjacency_matrix<D,VP,EP,GP,A> Graph; - typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::type PA; - return PA(&g); - } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A> - typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::type - get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property, - edge_property_tag) - { - typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::type PA; - return PA(); - } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A> - typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::const_type - get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property, - vertex_property_tag) - { - typedef adjacency_matrix<D,VP,EP,GP,A> Graph; - typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::const_type PA; - return PA(&g); - } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A> - typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::const_type - get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property, - edge_property_tag) - { - typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>, - Property>::const_type PA; - return PA(); - } + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::const_type + get(Tag tag, const adjacency_matrix<D, VP, EP, GP, A>& g) { + return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_const(g, tag); + } - } // namespace detail + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::single_nonconst_type + get(Tag tag, adjacency_matrix<D, VP, EP, GP, A>& g, typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::arg_type a) { + return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst_one(g, tag, a); + } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A> - inline - typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type - get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g) - { - typedef typename property_kind<Property>::type Kind; - return detail::get_dispatch(g, p, Kind()); + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::single_const_type + get(Tag tag, const adjacency_matrix<D, VP, EP, GP, A>& g, typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::arg_type a) { + return property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_const_one(g, tag, a); + } + + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + void + put(Tag tag, + adjacency_matrix<D, VP, EP, GP, A>& g, + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::arg_type a, + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::single_const_type val) { + property_map<adjacency_matrix<D, VP, EP, GP, A>, Tag>::get_nonconst_one(g, tag, a) = val; } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A> - inline - typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type - get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g) + // O(1) + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag, typename Value> + inline void + set_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag, const Value& value) { - typedef typename property_kind<Property>::type Kind; - return detail::get_dispatch(g, p, Kind()); + get_property_value(g.m_property, tag) = value; } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A, typename Key> - inline - typename property_traits< - typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type - >::value_type - get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g, - const Key& key) + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + inline typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& + get_property(adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag) { - return get(get(p, g), key); + return get_property_value(g.m_property, tag); } - template <typename Property, typename D, typename VP, typename EP, - typename GP, typename A, typename Key, typename Value> - inline void - put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g, - const Key& key, const Value& value) + template <typename D, typename VP, typename EP, typename GP, typename A, + typename Tag> + inline const typename graph_property<adjacency_matrix<D,VP,EP,GP,A>, Tag>::type& + get_property(const adjacency_matrix<D,VP,EP,GP,A>& g, Tag tag) { - typedef adjacency_matrix<D,VP,EP,GP,A> Graph; - typedef typename boost::property_map<Graph, Property>::type Map; - Map pmap = get(p, g); - put(pmap, key, value); + return get_property_value(g.m_property, tag); } //========================================================================= - // Other Functions + // Vertex Property Map template <typename D, typename VP, typename EP, typename GP, typename A> - typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor - vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n, - const adjacency_matrix<D,VP,EP,GP,A>&) - { - return n; + struct property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t> { + typedef typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor Vertex; + typedef typed_identity_property_map<Vertex> type; + typedef type const_type; + }; + + template <typename D, typename VP, typename EP, typename GP, typename A> + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type + get(vertex_index_t, adjacency_matrix<D, VP, EP, GP, A>&) { + return typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type(); } - // Support for bundled properties -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES - template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, - typename Allocator, typename T, typename Bundle> - inline - typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, - T Bundle::*>::type - get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g) - { - typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, - T Bundle::*>::type - result_type; - return result_type(&g, p); + template <typename D, typename VP, typename EP, typename GP, typename A> + typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor + get(vertex_index_t, + adjacency_matrix<D, VP, EP, GP, A>&, + typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor v) { + return v; } - template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, - typename Allocator, typename T, typename Bundle> - inline - typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, - T Bundle::*>::const_type - get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g) - { - typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>, - T Bundle::*>::const_type - result_type; - return result_type(&g, p); + template <typename D, typename VP, typename EP, typename GP, typename A> + typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type + get(vertex_index_t, const adjacency_matrix<D, VP, EP, GP, A>&) { + return typename property_map<adjacency_matrix<D, VP, EP, GP, A>, vertex_index_t>::const_type(); } - template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, - typename Allocator, typename T, typename Bundle, typename Key> - inline T - get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g, - const Key& key) - { - return get(get(p, g), key); + template <typename D, typename VP, typename EP, typename GP, typename A> + typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor + get(vertex_index_t, + const adjacency_matrix<D, VP, EP, GP, A>&, + typename adjacency_matrix<D, VP, EP, GP, A>::vertex_descriptor v) { + return v; } - template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty, - typename Allocator, typename T, typename Bundle, typename Key> - inline void - put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g, - const Key& key, const T& value) + //========================================================================= + // Other Functions + + template <typename D, typename VP, typename EP, typename GP, typename A> + typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor + vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n, + const adjacency_matrix<D,VP,EP,GP,A>&) { - put(get(p, g), key, value); + return n; } -#endif - -#define ADJMAT_PARAMS \ - typename D, typename VP, typename EP, typename GP, typename A -#define ADJMAT adjacency_matrix<D,VP,EP,GP,A> -template <ADJMAT_PARAMS> -struct graph_mutability_traits<ADJMAT> { - typedef mutable_edge_property_graph_tag category; +template <typename D, typename VP, typename EP, typename GP, typename A> +struct graph_mutability_traits<adjacency_matrix<D, VP, EP, GP, A> > { + typedef mutable_edge_property_graph_tag category; }; -#undef ADJMAT_PARAMS -#undef ADJMAT } // namespace boost diff --git a/boost/graph/astar_search.hpp b/boost/graph/astar_search.hpp index 316e706390..132dca021c 100644 --- a/boost/graph/astar_search.hpp +++ b/boost/graph/astar_search.hpp @@ -158,6 +158,7 @@ namespace boost { template <class Edge, class Graph> void tree_edge(Edge e, const Graph& g) { + using boost::get; m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, m_combine, m_compare); @@ -173,6 +174,7 @@ namespace boost { template <class Edge, class Graph> void gray_target(Edge e, const Graph& g) { + using boost::get; m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, m_combine, m_compare); @@ -189,6 +191,7 @@ namespace boost { template <class Edge, class Graph> void black_target(Edge e, const Graph& g) { + using boost::get; m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, m_combine, m_compare); diff --git a/boost/graph/bellman_ford_shortest_paths.hpp b/boost/graph/bellman_ford_shortest_paths.hpp index c80ebe7c7d..e102d92209 100644 --- a/boost/graph/bellman_ford_shortest_paths.hpp +++ b/boost/graph/bellman_ford_shortest_paths.hpp @@ -171,7 +171,7 @@ namespace boost { bool bellman_dispatch2 (VertexAndEdgeListGraph& g, - detail::error_property_not_found, + param_not_found, Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance, const bgl_named_params<P, T, R>& params) { diff --git a/boost/graph/betweenness_centrality.hpp b/boost/graph/betweenness_centrality.hpp index 052f0633c1..a4de175330 100644 --- a/boost/graph/betweenness_centrality.hpp +++ b/boost/graph/betweenness_centrality.hpp @@ -498,14 +498,14 @@ namespace detail { namespace graph { }; template<> - struct brandes_betweenness_centrality_dispatch1<error_property_not_found> + struct brandes_betweenness_centrality_dispatch1<param_not_found> { template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, typename VertexIndexMap> static void run(const Graph& g, CentralityMap centrality, EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, - error_property_not_found) + param_not_found) { brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map, vertex_index); @@ -532,7 +532,7 @@ brandes_betweenness_centrality(const Graph& g, { typedef bgl_named_params<Param,Tag,Rest> named_params; - typedef typename property_value<named_params, edge_weight_t>::type ew; + typedef typename get_param_type<edge_weight_t, named_params>::type ew; detail::graph::brandes_betweenness_centrality_dispatch1<ew>::run( g, choose_param(get_param(params, vertex_centrality), diff --git a/boost/graph/biconnected_components.hpp b/boost/graph/biconnected_components.hpp index 9586f9a211..1669f69522 100644 --- a/boost/graph/biconnected_components.hpp +++ b/boost/graph/biconnected_components.hpp @@ -21,6 +21,7 @@ #include <boost/graph/depth_first_search.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/concept/assert.hpp> +#include <boost/assert.hpp> namespace boost { @@ -28,17 +29,23 @@ namespace boost { template<typename ComponentMap, typename DiscoverTimeMap, typename LowPointMap, typename PredecessorMap, - typename OutputIterator, typename Stack, + typename OutputIterator, typename Stack, + typename ArticulationVector, typename IndexMap, typename DFSVisitor> struct biconnected_components_visitor : public dfs_visitor<> { biconnected_components_visitor - (ComponentMap comp, std::size_t& c, DiscoverTimeMap dtm, + (ComponentMap comp, std::size_t& c, + std::size_t& children_of_root, DiscoverTimeMap dtm, std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred, - OutputIterator out, Stack& S, DFSVisitor vis) - : comp(comp), c(c), children_of_root(0), dtm(dtm), - dfs_time(dfs_time), lowpt(lowpt), - pred(pred), out(out), S(S), vis(vis) { } + OutputIterator out, Stack& S, + ArticulationVector& is_articulation_point, IndexMap index_map, + DFSVisitor vis) + : comp(comp), c(c), children_of_root(children_of_root), + dtm(dtm), dfs_time(dfs_time), lowpt(lowpt), + pred(pred), out(out), S(S), + is_articulation_point(is_articulation_point), + index_map(index_map), vis(vis) { } template <typename Vertex, typename Graph> void initialize_vertex(const Vertex& u, Graph& g) @@ -89,8 +96,7 @@ namespace boost typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g); typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g); - if ( ( tgt != get(pred, src) || get(pred, src) == src ) && - get(dtm, tgt) < get(dtm, src) ) { + if ( tgt != get(pred, src) ) { S.push(e); put(lowpt, src, min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, src), @@ -111,40 +117,41 @@ namespace boost BOOST_USING_STD_MIN(); Vertex parent = get(pred, u); if (parent == u) { // Root of tree is special - if (children_of_root >= 2) { - *out++ = u; - } - return; - } - put(lowpt, parent, - min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent), + is_articulation_point[get(index_map, u)] = (children_of_root > 1); + } else { + put(lowpt, parent, + min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent), get(lowpt, u))); - if ( get(lowpt, u) >= get(dtm, parent) ) { - if ( get(pred, parent) != parent ) { - *out++ = parent; - } - while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) { + if ( get(lowpt, u) >= get(dtm, parent) ) { + is_articulation_point[get(index_map, parent)] = true; + while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) { + put(comp, S.top(), c); + S.pop(); + } + BOOST_ASSERT (source(S.top(), g) == parent); + BOOST_ASSERT (target(S.top(), g) == u); put(comp, S.top(), c); S.pop(); + ++c; } - assert (source(S.top(), g) == parent); - assert (target(S.top(), g) == u); - put(comp, S.top(), c); - S.pop(); - ++c; + } + if ( is_articulation_point[get(index_map, u)] ) { + *out++ = u; } vis.finish_vertex(u, g); } ComponentMap comp; std::size_t& c; - std::size_t children_of_root; + std::size_t& children_of_root; DiscoverTimeMap dtm; std::size_t& dfs_time; LowPointMap lowpt; PredecessorMap pred; OutputIterator out; Stack& S; + ArticulationVector& is_articulation_point; + IndexMap index_map; DFSVisitor vis; }; @@ -168,14 +175,16 @@ namespace boost vertex_t> )); std::size_t num_components = 0; + std::size_t children_of_root; std::size_t dfs_time = 0; - std::stack<edge_t> S; + std::stack<edge_t> S; + std::vector<char> is_articulation_point(num_vertices(g)); - biconnected_components_visitor<ComponentMap, DiscoverTimeMap, - LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, - DFSVisitor> - vis(comp, num_components, dtm, dfs_time, lowpt, pred, out, - S, dfs_vis); + biconnected_components_visitor<ComponentMap, DiscoverTimeMap, + LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, + std::vector<char>, VertexIndexMap, DFSVisitor> + vis(comp, num_components, children_of_root, dtm, dfs_time, + lowpt, pred, out, S, is_articulation_point, index_map, dfs_vis); depth_first_search(g, visitor(vis).vertex_index_map(index_map)); @@ -201,7 +210,7 @@ namespace boost }; template <> - struct bicomp_dispatch3<error_property_not_found> + struct bicomp_dispatch3<param_not_found> { template<typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, @@ -210,7 +219,7 @@ namespace boost ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, LowPointMap lowpt, const bgl_named_params<P, T, R>& params, - error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; std::vector<vertex_t> pred(num_vertices(g)); @@ -235,8 +244,7 @@ namespace boost DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, LowPointMap lowpt) { - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_predecessor_t>::type dispatch_type; + typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch3<dispatch_type>::apply (g, comp, out, index_map, dtm, lowpt, params, @@ -246,7 +254,7 @@ namespace boost template <> - struct bicomp_dispatch2<error_property_not_found> + struct bicomp_dispatch2<param_not_found> { template<typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, @@ -254,15 +262,14 @@ namespace boost static std::pair<std::size_t, OutputIterator> apply (const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, - error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; std::vector<vertices_size_type> lowpt(num_vertices(g)); vertices_size_type vst(0); - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_predecessor_t>::type dispatch_type; + typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch3<dispatch_type>::apply (g, comp, out, index_map, dtm, @@ -280,8 +287,7 @@ namespace boost ComponentMap comp, OutputIterator out, VertexIndexMap index_map, const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm) { - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_lowpoint_t>::type dispatch_type; + typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch2<dispatch_type>::apply (g, comp, out, index_map, dtm, params, @@ -290,21 +296,20 @@ namespace boost }; template <> - struct bicomp_dispatch1<error_property_not_found> + struct bicomp_dispatch1<param_not_found> { template<typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, class P, class T, class R> static std::pair<std::size_t, OutputIterator> apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, - const bgl_named_params<P, T, R>& params, error_property_not_found) + const bgl_named_params<P, T, R>& params, param_not_found) { typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; std::vector<vertices_size_type> discover_time(num_vertices(g)); vertices_size_type vst(0); - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_lowpoint_t>::type dispatch_type; + typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params<P,T,R> >::type dispatch_type; return bicomp_dispatch2<dispatch_type>::apply (g, comp, out, index_map, @@ -321,14 +326,14 @@ namespace boost biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt) { - typedef detail::error_property_not_found dispatch_type; + typedef param_not_found dispatch_type; return detail::bicomp_dispatch3<dispatch_type>::apply (g, comp, out, get(vertex_index, g), dtm, lowpt, bgl_named_params<int, buffer_param_t>(0), - detail::error_property_not_found()); + param_not_found()); } template <typename Graph, typename ComponentMap, typename OutputIterator, @@ -337,8 +342,7 @@ namespace boost biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, const bgl_named_params<P, T, R>& params) { - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_discover_time_t>::type dispatch_type; + typedef typename get_param_type< vertex_discover_time_t, bgl_named_params<P,T,R> >::type dispatch_type; return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, choose_const_pmap(get_param(params, vertex_index), g, vertex_index), diff --git a/boost/graph/breadth_first_search.hpp b/boost/graph/breadth_first_search.hpp index f65e47572a..18bc24f5cf 100644 --- a/boost/graph/breadth_first_search.hpp +++ b/boost/graph/breadth_first_search.hpp @@ -53,11 +53,12 @@ namespace boost { }; + // Multiple-source version template <class IncidenceGraph, class Buffer, class BFSVisitor, - class ColorMap> + class ColorMap, class SourceIterator> void breadth_first_visit (const IncidenceGraph& g, - typename graph_traits<IncidenceGraph>::vertex_descriptor s, + SourceIterator sources_begin, SourceIterator sources_end, Buffer& Q, BFSVisitor vis, ColorMap color) { BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> )); @@ -70,8 +71,11 @@ namespace boost { typedef color_traits<ColorValue> Color; typename GTraits::out_edge_iterator ei, ei_end; - put(color, s, Color::gray()); vis.discover_vertex(s, g); - Q.push(s); + for (; sources_begin != sources_end; ++sources_begin) { + Vertex s = *sources_begin; + put(color, s, Color::gray()); vis.discover_vertex(s, g); + Q.push(s); + } while (! Q.empty()) { Vertex u = Q.top(); Q.pop(); vis.examine_vertex(u, g); for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { @@ -89,12 +93,25 @@ namespace boost { } // end while } // breadth_first_visit + // Single-source version + template <class IncidenceGraph, class Buffer, class BFSVisitor, + class ColorMap> + void breadth_first_visit + (const IncidenceGraph& g, + typename graph_traits<IncidenceGraph>::vertex_descriptor s, + Buffer& Q, BFSVisitor vis, ColorMap color) + { + typename graph_traits<IncidenceGraph>::vertex_descriptor sources[1] = {s}; + breadth_first_visit(g, sources, sources + 1, Q, vis, color); + } + - template <class VertexListGraph, class Buffer, class BFSVisitor, + template <class VertexListGraph, class SourceIterator, + class Buffer, class BFSVisitor, class ColorMap> void breadth_first_search (const VertexListGraph& g, - typename graph_traits<VertexListGraph>::vertex_descriptor s, + SourceIterator sources_begin, SourceIterator sources_end, Buffer& Q, BFSVisitor vis, ColorMap color) { // Initialization @@ -105,7 +122,18 @@ namespace boost { vis.initialize_vertex(*i, g); put(color, *i, Color::white()); } - breadth_first_visit(g, s, Q, vis, color); + breadth_first_visit(g, sources_begin, sources_end, Q, vis, color); + } + + template <class VertexListGraph, class Buffer, class BFSVisitor, + class ColorMap> + void breadth_first_search + (const VertexListGraph& g, + typename graph_traits<VertexListGraph>::vertex_descriptor s, + Buffer& Q, BFSVisitor vis, ColorMap color) + { + typename graph_traits<VertexListGraph>::vertex_descriptor sources[1] = {s}; + breadth_first_search(g, sources, sources + 1, Q, vis, color); } namespace graph { struct bfs_visitor_event_not_overridden {}; } @@ -270,13 +298,13 @@ namespace boost { }; template <> - struct bfs_dispatch<detail::error_property_not_found> { + struct bfs_dispatch<param_not_found> { template <class VertexListGraph, class P, class T, class R> static void apply (VertexListGraph& g, typename graph_traits<VertexListGraph>::vertex_descriptor s, const bgl_named_params<P, T, R>& params, - detail::error_property_not_found) + param_not_found) { null_visitor null_vis; @@ -294,7 +322,7 @@ namespace boost { } // namespace detail - +#if 1 // Named Parameter Variant template <class VertexListGraph, class P, class T, class R> void breadth_first_search @@ -307,11 +335,11 @@ namespace boost { // graph is not really const since we may write to property maps // of the graph. VertexListGraph& ng = const_cast<VertexListGraph&>(g); - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_color_t>::type C; + typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C; detail::bfs_dispatch<C>::apply(ng, s, params, get_param(params, vertex_color)); } +#endif // This version does not initialize colors, user has to. @@ -343,6 +371,33 @@ namespace boost { ); } + namespace graph { + namespace detail { + template <typename Graph, typename Source> + struct breadth_first_search_impl { + typedef void result_type; + template <typename ArgPack> + void operator()(const Graph& g, const Source& source, const ArgPack& arg_pack) { + using namespace boost::graph::keywords; + typename boost::graph_traits<Graph>::vertex_descriptor sources[1] = {source}; + boost::queue<typename boost::graph_traits<Graph>::vertex_descriptor> Q; + boost::breadth_first_search(g, + &sources[0], + &sources[1], + boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]), + arg_pack[_visitor | make_bfs_visitor(null_visitor())], + boost::detail::make_color_map_from_arg_pack(g, arg_pack)); + } + }; + } + BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4) + } + +#if 0 + // Named Parameter Variant + BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2) +#endif + } // namespace boost #ifdef BOOST_GRAPH_USE_MPI diff --git a/boost/graph/bron_kerbosch_all_cliques.hpp b/boost/graph/bron_kerbosch_all_cliques.hpp index 1466dfe5f0..b663cf95f0 100644 --- a/boost/graph/bron_kerbosch_all_cliques.hpp +++ b/boost/graph/bron_kerbosch_all_cliques.hpp @@ -224,7 +224,7 @@ namespace detail // otherwise, iterate over candidates and and test // for maxmimal cliquiness. - typename Container::iterator i, j, end = cands.end(); + typename Container::iterator i, j; for(i = cands.begin(); i != cands.end(); ) { Vertex candidate = *i; @@ -270,7 +270,6 @@ bron_kerbosch_all_cliques(const Graph& g, Visitor vis, std::size_t min) { BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); - BOOST_CONCEPT_ASSERT(( VertexIndexGraphConcept<Graph> )); BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> )); // Structural requirement only typedef typename graph_traits<Graph>::vertex_descriptor Vertex; typedef typename graph_traits<Graph>::vertex_iterator VertexIterator; diff --git a/boost/graph/chrobak_payne_drawing.hpp b/boost/graph/chrobak_payne_drawing.hpp index ef6ae5c9c6..4d026986c2 100644 --- a/boost/graph/chrobak_payne_drawing.hpp +++ b/boost/graph/chrobak_payne_drawing.hpp @@ -13,7 +13,6 @@ #include <list> #include <stack> #include <boost/config.hpp> -#include <boost/utility.hpp> //for next and prior #include <boost/graph/graph_traits.hpp> #include <boost/property_map/property_map.hpp> diff --git a/boost/graph/clustering_coefficient.hpp b/boost/graph/clustering_coefficient.hpp index dad4695a77..5345ed999a 100644 --- a/boost/graph/clustering_coefficient.hpp +++ b/boost/graph/clustering_coefficient.hpp @@ -7,7 +7,7 @@ #ifndef BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP #define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP -#include <boost/utility.hpp> +#include <boost/next_prior.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/lookup_edge.hpp> diff --git a/boost/graph/compressed_sparse_row_graph.hpp b/boost/graph/compressed_sparse_row_graph.hpp index caa27a9060..59e8bb4aba 100644 --- a/boost/graph/compressed_sparse_row_graph.hpp +++ b/boost/graph/compressed_sparse_row_graph.hpp @@ -41,12 +41,9 @@ #include <boost/graph/properties.hpp> #include <boost/static_assert.hpp> #include <boost/functional/hash.hpp> -#include <boost/utility.hpp> - -#ifdef BOOST_GRAPH_NO_BUNDLED_PROPERTIES -# error The Compressed Sparse Row graph only supports bundled properties. -# error You will need a compiler that conforms better to the C++ standard. -#endif +#include <boost/next_prior.hpp> +#include <boost/property_map/transform_value_property_map.hpp> +#include <boost/mpl/print.hpp> namespace boost { @@ -195,8 +192,8 @@ class compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, Graph public: // For Property Graph - typedef typename graph_detail::graph_prop<GraphProperty>::property graph_property_type; - typedef typename graph_detail::graph_prop<GraphProperty>::bundle graph_bundled; + 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; @@ -746,8 +743,8 @@ class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, public: // For Property Graph - typedef typename graph_detail::graph_prop<GraphProperty>::property graph_property_type; - typedef typename graph_detail::graph_prop<GraphProperty>::bundle graph_bundled; + 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; @@ -933,6 +930,7 @@ class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, { m_forward.assign(g, vi, numverts, numedges); inherited_vertex_properties::resize(numverts); + set_up_backward_property_links(); } // Requires the above, plus VertexListGraph and EdgeListGraph @@ -946,6 +944,7 @@ class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, 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. @@ -959,125 +958,7 @@ class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, 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<Vertex>()); - } - - // Add edges from a sorted (smallest sources first) range of pairs - template <typename BidirectionalIteratorOrig> - void - add_edges_sorted_internal( - BidirectionalIteratorOrig first_sorted, - BidirectionalIteratorOrig last_sorted) { - m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>()); - } - - template <typename BidirectionalIteratorOrig, typename GlobalToLocal> - void - add_edges_sorted_internal_global( - BidirectionalIteratorOrig first_sorted, - BidirectionalIteratorOrig last_sorted, - const GlobalToLocal& global_to_local) { - m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local); - } - - template <typename BidirectionalIteratorOrig, typename EPIterOrig, - typename GlobalToLocal> - void - add_edges_sorted_internal_global( - BidirectionalIteratorOrig first_sorted, - BidirectionalIteratorOrig last_sorted, - EPIterOrig ep_iter_sorted, - const GlobalToLocal& global_to_local) { - m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local); - } - - // Add edges from a range of (source, target) pairs that are unsorted - template <typename InputIterator, typename GlobalToLocal> - inline void - add_edges_internal(InputIterator first, InputIterator last, - const GlobalToLocal& global_to_local) { - typedef compressed_sparse_row_graph Graph; - typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; - typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num; - typedef typename boost::graph_traits<Graph>::edges_size_type edge_num; - typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t; - edge_vector_t new_edges(first, last); - if (new_edges.empty()) return; - std::sort(new_edges.begin(), new_edges.end()); - this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local); - } - - template <typename InputIterator> - inline void - add_edges_internal(InputIterator first, InputIterator last) { - this->add_edges_internal(first, last, typed_identity_property_map<Vertex>()); - } - - // Add edges from a range of (source, target) pairs and edge properties that - // are unsorted - template <typename InputIterator, typename EPIterator, typename GlobalToLocal> - inline void - add_edges_internal(InputIterator first, InputIterator last, - EPIterator ep_iter, EPIterator ep_iter_end, - const GlobalToLocal& global_to_local) { - typedef compressed_sparse_row_graph Graph; - typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; - typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num; - typedef typename boost::graph_traits<Graph>::edges_size_type edge_num; - typedef std::pair<vertex_t, vertex_t> vertex_pair; - typedef std::vector< - boost::tuple<vertex_pair, - edge_bundled> > - edge_vector_t; - edge_vector_t new_edges - (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)), - boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end))); - if (new_edges.empty()) return; - std::sort(new_edges.begin(), new_edges.end(), - boost::detail::compare_first< - std::less<vertex_pair> >()); - m_forward.add_edges_sorted_internal - (boost::make_transform_iterator( - new_edges.begin(), - boost::detail::my_tuple_get_class<0, vertex_pair>()), - boost::make_transform_iterator( - new_edges.end(), - boost::detail::my_tuple_get_class<0, vertex_pair>()), - boost::make_transform_iterator( - new_edges.begin(), - boost::detail::my_tuple_get_class - <1, edge_bundled>()), - global_to_local); - } - - // Add edges from a range of (source, target) pairs and edge properties that - // are unsorted - template <typename InputIterator, typename EPIterator> - inline void - add_edges_internal(InputIterator first, InputIterator last, - EPIterator ep_iter, EPIterator ep_iter_end) { - this->add_edges_internal(first, last, ep_iter, ep_iter_end, typed_identity_property_map<Vertex>()); + set_up_backward_property_links(); } using inherited_vertex_properties::operator[]; @@ -1134,7 +1015,6 @@ add_vertices(typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size(); EdgeIndex numedges = g.m_forward.m_rowstart.back(); g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges); - g.m_backward.m_rowstart.resize(old_num_verts_plus_one + count, numedges); g.vertex_properties().resize(num_vertices(g)); return old_num_verts_plus_one - 1; } @@ -1383,26 +1263,110 @@ edges(const BOOST_CSR_GRAPH_TYPE& g) // Graph properties template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value> inline void -set_property(BOOST_CSR_GRAPH_TYPE& g, Tag, const Value& value) +set_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag, const Value& value) { - get_property_value(g.m_property, Tag()) = 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) +get_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag) { - return get_property_value(g.m_property, 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) +get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag tag) { - return get_property_value(g.m_property, 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; +}; + +template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag> +struct property_map<BOOST_CSR_GRAPH_TYPE, Tag>: + 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; + typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::type outer_pm; + 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> @@ -1420,20 +1384,27 @@ struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t> }; template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> -struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t> +struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t> { 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_bundle_t> +struct property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t> { 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> +{ + 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&) { @@ -1449,6 +1420,21 @@ get(vertex_index_t, } 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&) { @@ -1466,125 +1452,144 @@ get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&, } template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> -inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t>::type -get(vertex_bundle_t, BOOST_CSR_GRAPH_TYPE& g) +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_bundle_t>::const_type -get(vertex_bundle_t, const BOOST_CSR_GRAPH_TYPE& g) +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_bundle_t, +get(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g, Vertex v) { - return get(vertex_bundle, g)[v]; + return get(vertex_all, g)[v]; } template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> inline const VertexProperty& -get(vertex_bundle_t, +get(vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g, Vertex v) { - return get(vertex_bundle, g)[v]; + return get(vertex_all, g)[v]; } template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> inline void -put(vertex_bundle_t, +put(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g, Vertex v, const VertexProperty& val) { - put(get(vertex_bundle, g), v, val); + put(get(vertex_all, g), v, val); } template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> -inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_bundle_t>::type -get(edge_bundle_t, BOOST_CSR_GRAPH_TYPE& g) +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_bundle_t>::const_type -get(edge_bundle_t, const BOOST_CSR_GRAPH_TYPE& g) +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_bundle_t, +get(edge_all_t, BOOST_CSR_GRAPH_TYPE& g, const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e) { - return get(edge_bundle, g)[e]; + return get(edge_all, g)[e]; } template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> inline const EdgeProperty& -get(edge_bundle_t, +get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g, const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e) { - return get(edge_bundle, g)[e]; + return get(edge_all, g)[e]; } template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> inline void -put(edge_bundle_t, +put(edge_all_t, BOOST_CSR_GRAPH_TYPE& g, const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e, const EdgeProperty& val) { - put(get(edge_bundle, g), e, val); + put(get(edge_all, g), e, val); } -template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle> -inline -typename property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>::type -get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g) +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) { - typedef typename property_map<BOOST_CSR_GRAPH_TYPE, - T Bundle::*>::type - result_type; - return result_type(&g, p); + return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type(g.m_property); } -template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle> -inline -typename property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>::const_type -get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g) +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) { - typedef typename property_map<BOOST_CSR_GRAPH_TYPE, - T Bundle::*>::const_type - result_type; - return result_type(&g, p); + return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type(g.m_property); } -template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle, - typename Key> -inline T -get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g, - const Key& key) +template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> +inline GraphProperty& +get(graph_all_t, + BOOST_CSR_GRAPH_TYPE& g, + BOOST_CSR_GRAPH_TYPE*) { - return get(get(p, g), key); + return g.m_property; } -template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle, - typename Key> +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(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g, - const Key& key, const T& value) +put(graph_all_t, + BOOST_CSR_GRAPH_TYPE& g, + BOOST_CSR_GRAPH_TYPE*, + const GraphProperty& val) { - put(get(p, g), key, value); + g.m_property = val; } #undef BOOST_CSR_GRAPH_TYPE diff --git a/boost/graph/copy.hpp b/boost/graph/copy.hpp index 0dc6c664a2..21bb0fb01e 100644 --- a/boost/graph/copy.hpp +++ b/boost/graph/copy.hpp @@ -280,7 +280,7 @@ namespace boost { typedef choose_copier_parameter type; }; template <> - struct choose_edge_copy<detail::error_property_not_found> { + struct choose_edge_copy<param_not_found> { typedef choose_default_edge_copier type; }; template <class Param, class G1, class G2> @@ -314,7 +314,7 @@ namespace boost { typedef choose_copier_parameter type; }; template <> - struct choose_vertex_copy<detail::error_property_not_found> { + struct choose_vertex_copy<param_not_found> { typedef choose_default_vertex_copier type; }; template <class Param, class G1, class G2> diff --git a/boost/graph/depth_first_search.hpp b/boost/graph/depth_first_search.hpp index d38ad603d0..34d73a2fdd 100644 --- a/boost/graph/depth_first_search.hpp +++ b/boost/graph/depth_first_search.hpp @@ -21,6 +21,7 @@ #include <boost/graph/named_function_params.hpp> #include <boost/ref.hpp> #include <boost/implicit_cast.hpp> +#include <boost/parameter.hpp> #include <boost/concept/assert.hpp> #include <vector> @@ -198,7 +199,7 @@ namespace boost { put(color, u, Color::white()); vis.initialize_vertex(u, g); } - if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g); + if (start_vertex != detail::get_default_starting_vertex(g)){ vis.start_vertex(start_vertex, g); detail::depth_first_visit_impl(g, start_vertex, vis, color, detail::nontruth2()); } @@ -221,7 +222,7 @@ namespace boost { if (verts.first == verts.second) return; - depth_first_search(g, vis, color, *verts.first); + depth_first_search(g, vis, color, detail::get_default_starting_vertex(g)); } template <class Visitors = null_visitor> @@ -282,27 +283,27 @@ namespace boost { } typedef dfs_visitor<> default_dfs_visitor; - // Named Parameter Variant - template <class VertexListGraph, class P, class T, class R> - void - depth_first_search(const VertexListGraph& g, - const bgl_named_params<P, T, R>& params) - { - typedef typename boost::graph_traits<VertexListGraph>::vertex_iterator vi; - std::pair<vi, vi> verts = vertices(g); - if (verts.first == verts.second) - return; - using namespace boost::graph::keywords; - typedef bgl_named_params<P, T, R> params_type; - BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) - depth_first_search - (g, - arg_pack[_visitor | make_dfs_visitor(null_visitor())], - boost::detail::make_color_map_from_arg_pack(g, arg_pack), - arg_pack[_root_vertex | *vertices(g).first] - ); + // Boost.Parameter named parameter variant + namespace graph { + namespace detail { + template <typename Graph> + struct depth_first_search_impl { + typedef void result_type; + template <typename ArgPack> + void operator()(const Graph& g, const ArgPack& arg_pack) const { + using namespace boost::graph::keywords; + boost::depth_first_search(g, + arg_pack[_visitor | make_dfs_visitor(null_visitor())], + boost::detail::make_color_map_from_arg_pack(g, arg_pack), + arg_pack[_root_vertex || boost::detail::get_default_starting_vertex_t<Graph>(g)]); + } + }; + } + BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(depth_first_search, 1, 4) } + BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(depth_first_search, 1) + template <class IncidenceGraph, class DFSVisitor, class ColorMap> void depth_first_visit (const IncidenceGraph& g, diff --git a/boost/graph/detail/adjacency_list.hpp b/boost/graph/detail/adjacency_list.hpp index 100c44ba7f..fa39898907 100644 --- a/boost/graph/detail/adjacency_list.hpp +++ b/boost/graph/detail/adjacency_list.hpp @@ -37,11 +37,6 @@ #include <boost/static_assert.hpp> #include <boost/assert.hpp> -// Symbol truncation problems with MSVC, trying to shorten names. -#define stored_edge se_ -#define stored_edge_property sep_ -#define stored_edge_iter sei_ - /* Outline for this file: @@ -67,11 +62,6 @@ */ -#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) -// Stay out of the way of the concept checking class -# define Graph Graph_ -#endif - namespace boost { namespace detail { @@ -727,8 +717,10 @@ namespace boost { typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); typename Config::OutEdgeList::iterator out_i = out_el.begin(); + typename Config::EdgeIter edge_iter_to_erase; for (; out_i != out_el.end(); ++out_i) if (&(*out_i).get_property() == &p) { + edge_iter_to_erase = (*out_i).get_iter(); out_el.erase(out_i); break; } @@ -736,10 +728,10 @@ namespace boost { typename Config::OutEdgeList::iterator in_i = in_el.begin(); for (; in_i != in_el.end(); ++in_i) if (&(*in_i).get_property() == &p) { - g.m_edges.erase((*in_i).get_iter()); in_el.erase(in_i); - return; + break; } + g.m_edges.erase(edge_iter_to_erase); } }; @@ -760,8 +752,10 @@ namespace boost { no_property* p = (no_property*)e.get_property(); typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); typename Config::OutEdgeList::iterator out_i = out_el.begin(); + typename Config::EdgeIter edge_iter_to_erase; for (; out_i != out_el.end(); ++out_i) if (&(*out_i).get_property() == p) { + edge_iter_to_erase = (*out_i).get_iter(); out_el.erase(out_i); break; } @@ -769,10 +763,10 @@ namespace boost { typename Config::OutEdgeList::iterator in_i = in_el.begin(); for (; in_i != in_el.end(); ++in_i) if (&(*in_i).get_property() == p) { - g.m_edges.erase((*in_i).get_iter()); in_el.erase(in_i); - return; + break; } + g.m_edges.erase(edge_iter_to_erase); } }; @@ -811,6 +805,7 @@ namespace boost { typedef typename EdgeList::value_type StoredEdge; typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end(); + BOOST_ASSERT ((i != end)); if (i != end) { g.m_edges.erase((*i).get_iter()); el.erase(i); @@ -991,24 +986,12 @@ namespace boost { typedef typename Config::graph_type graph_type; typedef typename Config::edge_parallel_category Cat; graph_type& g = static_cast<graph_type&>(g_); - typename Config::OutEdgeList& el = g.out_edge_list(u); - typename Config::OutEdgeList::iterator - ei = el.begin(), ei_end = el.end(); - for (; ei != ei_end; /* Increment below */ ) { - bool is_self_loop = (*ei).get_target() == u; - // Don't erase from our own incidence list in the case of a self-loop - // since we're clearing it anyway. - if (!is_self_loop) { - detail::erase_from_incidence_list - (g.out_edge_list((*ei).get_target()), u, Cat()); - typename Config::OutEdgeList::iterator ei_copy = ei; - ++ei; - if (!is_self_loop) g.m_edges.erase((*ei_copy).get_iter()); - } else { - ++ei; - } + while (true) { + typename Config::out_edge_iterator ei, ei_end; + boost::tie(ei, ei_end) = out_edges(u, g); + if (ei == ei_end) break; + remove_edge(*ei, g); } - g.out_edge_list(u).clear(); } // O(1) for allow_parallel_edge_tag // O(log(E/V)) for disallow_parallel_edge_tag @@ -1511,10 +1494,16 @@ namespace boost { typedef typename Config::edges_size_type edges_size_type; typedef typename Config::degree_size_type degree_size_type; typedef typename Config::StoredEdge StoredEdge; + typedef typename Config::vertex_property_type vertex_property_type; typedef typename Config::edge_property_type edge_property_type; + typedef typename Config::graph_property_type graph_property_type; typedef typename Config::global_edgelist_selector global_edgelist_selector; + + typedef typename lookup_one_property<vertex_property_type, vertex_bundle_t>::type vertex_bundled; + typedef typename lookup_one_property<edge_property_type, edge_bundle_t>::type edge_bundled; + typedef typename lookup_one_property<graph_property_type, graph_bundle_t>::type graph_bundled; }; template <class Config, class Base> @@ -1645,43 +1634,43 @@ namespace boost { inline typename boost::property_map<typename Config::graph_type, Property>::type - get_dispatch(adj_list_helper<Config,Base>&, Property, + get_dispatch(adj_list_helper<Config,Base>&, Property p, boost::edge_property_tag) { typedef typename Config::graph_type Graph; typedef typename boost::property_map<Graph, Property>::type PA; - return PA(); + return PA(p); } template <class Config, class Base, class Property> inline typename boost::property_map<typename Config::graph_type, Property>::const_type - get_dispatch(const adj_list_helper<Config,Base>&, Property, + get_dispatch(const adj_list_helper<Config,Base>&, Property p, boost::edge_property_tag) { typedef typename Config::graph_type Graph; typedef typename boost::property_map<Graph, Property>::const_type PA; - return PA(); + return PA(p); } template <class Config, class Base, class Property> inline typename boost::property_map<typename Config::graph_type, Property>::type - get_dispatch(adj_list_helper<Config,Base>& g, Property, + get_dispatch(adj_list_helper<Config,Base>& g, Property p, boost::vertex_property_tag) { typedef typename Config::graph_type Graph; typedef typename boost::property_map<Graph, Property>::type PA; - return PA(&static_cast<Graph&>(g)); + return PA(&static_cast<Graph&>(g), p); } template <class Config, class Base, class Property> inline typename boost::property_map<typename Config::graph_type, Property>::const_type - get_dispatch(const adj_list_helper<Config, Base>& g, Property, + get_dispatch(const adj_list_helper<Config, Base>& g, Property p, boost::vertex_property_tag) { typedef typename Config::graph_type Graph; typedef typename boost::property_map<Graph, Property>::const_type PA; const Graph& cg = static_cast<const Graph&>(g); - return PA(&cg); + return PA(&cg, p); } } // namespace detail @@ -1691,7 +1680,7 @@ namespace boost { inline typename boost::property_map<typename Config::graph_type, Property>::type get(Property p, adj_list_helper<Config, Base>& g) { - typedef typename property_kind<Property>::type Kind; + typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind; return detail::get_dispatch(g, p, Kind()); } template <class Config, class Base, class Property> @@ -1699,7 +1688,7 @@ namespace boost { typename boost::property_map<typename Config::graph_type, Property>::const_type get(Property p, const adj_list_helper<Config, Base>& g) { - typedef typename property_kind<Property>::type Kind; + typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind; return detail::get_dispatch(g, p, Kind()); } @@ -2427,15 +2416,15 @@ namespace boost { typedef Reference reference; typedef typename Graph::vertex_descriptor key_type; typedef boost::lvalue_property_map_tag category; - inline adj_list_vertex_property_map() { } - inline adj_list_vertex_property_map(const Graph*) { } + inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { } inline Reference operator[](key_type v) const { StoredVertex* sv = (StoredVertex*)v; - return get_property_value(sv->m_property, Tag()); + return get_property_value(sv->m_property, m_tag); } inline Reference operator()(key_type v) const { return this->operator[](v); } + Tag m_tag; }; template <class Graph, class Property, class PropRef> @@ -2449,8 +2438,7 @@ namespace boost { typedef PropRef reference; typedef typename Graph::vertex_descriptor key_type; typedef boost::lvalue_property_map_tag category; - inline adj_list_vertex_all_properties_map() { } - inline adj_list_vertex_all_properties_map(const Graph*) { } + inline adj_list_vertex_all_properties_map(const Graph* = 0, vertex_all_t = vertex_all_t()) { } inline PropRef operator[](key_type v) const { StoredVertex* sv = (StoredVertex*)v; return sv->m_property; @@ -2473,15 +2461,15 @@ namespace boost { typedef Reference reference; typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type; typedef boost::lvalue_property_map_tag category; - vec_adj_list_vertex_property_map() { } - vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { } + vec_adj_list_vertex_property_map(GraphPtr g = 0, Tag tag = Tag()) : m_g(g), m_tag(tag) { } inline Reference operator[](key_type v) const { - return get_property_value(m_g->m_vertices[v].m_property, Tag()); + return get_property_value(m_g->m_vertices[v].m_property, m_tag); } inline Reference operator()(key_type v) const { return this->operator[](v); } GraphPtr m_g; + Tag m_tag; }; template <class Graph, class GraphPtr, class Property, class PropertyRef> @@ -2495,8 +2483,7 @@ namespace boost { typedef PropertyRef reference; typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type; typedef boost::lvalue_property_map_tag category; - vec_adj_list_vertex_all_properties_map() { } - vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { } + vec_adj_list_vertex_all_properties_map(GraphPtr g = 0, vertex_all_t = vertex_all_t()) : m_g(g) { } inline PropertyRef operator[](key_type v) const { return m_g->m_vertices[v].m_property; } @@ -2542,7 +2529,7 @@ namespace boost { typedef boost::readable_property_map_tag category; inline vec_adj_list_vertex_id_map() { } template <class Graph> - inline vec_adj_list_vertex_id_map(const Graph&) { } + inline vec_adj_list_vertex_id_map(const Graph&, vertex_index_t) { } inline value_type operator[](key_type v) const { return v; } inline value_type operator()(key_type v) const { return v; } }; @@ -2579,21 +2566,14 @@ namespace boost { }; }; namespace detail { - template <class Tag> - struct adj_list_choose_vertex_pa_helper { - typedef adj_list_any_vertex_pa type; - }; - template <> - struct adj_list_choose_vertex_pa_helper<vertex_all_t> { - typedef adj_list_all_vertex_pa type; - }; template <class Tag, class Graph, class Property> - struct adj_list_choose_vertex_pa { - typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper; - typedef typename Helper::template bind_<Tag,Graph,Property> Bind; - typedef typename Bind::type type; - typedef typename Bind::const_type const_type; - }; + struct adj_list_choose_vertex_pa + : boost::mpl::if_< + boost::is_same<Tag, vertex_all_t>, + adj_list_all_vertex_pa, + adj_list_any_vertex_pa>::type + ::template bind_<Tag, Graph, Property> + {}; template <class Tag> @@ -2609,12 +2589,9 @@ namespace boost { typedef vec_adj_list_all_vertex_pa type; }; template <class Tag, class Graph, class Property> - struct vec_adj_list_choose_vertex_pa { - typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper; - typedef typename Helper::template bind_<Tag,Graph,Property> Bind; - typedef typename Bind::type type; - typedef typename Bind::const_type const_type; - }; + struct vec_adj_list_choose_vertex_pa + : vec_adj_list_choose_vertex_pa_helper<Tag>::type::template bind_<Tag,Graph,Property> + {}; } // namespace detail //========================================================================= @@ -2629,13 +2606,16 @@ namespace boost { Tag> > { + Tag tag; + explicit adj_list_edge_property_map(Tag tag = Tag()): tag(tag) {} + typedef Value value_type; typedef Ref reference; typedef detail::edge_desc_impl<Directed, Vertex> key_type; typedef boost::lvalue_property_map_tag category; inline Ref operator[](key_type e) const { Property& p = *(Property*)e.get_property(); - return get_property_value(p, Tag()); + return get_property_value(p, tag); } inline Ref operator()(key_type e) const { return this->operator[](e); @@ -2650,6 +2630,7 @@ namespace boost { PropPtr, Vertex> > { + explicit adj_list_edge_all_properties_map(edge_all_t = edge_all_t()) {} typedef Property value_type; typedef PropRef reference; typedef detail::edge_desc_impl<Directed, Vertex> key_type; @@ -2701,19 +2682,12 @@ namespace boost { typedef adj_list_all_edge_pmap type; }; template <class Tag, class Graph, class Property> - struct adj_list_choose_edge_pmap { - typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper; - typedef typename Helper::template bind_<Graph,Property,Tag> Bind; - typedef typename Bind::type type; - typedef typename Bind::const_type const_type; - }; + struct adj_list_choose_edge_pmap + : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag> + {}; struct adj_list_edge_property_selector { template <class Graph, class Property, class Tag> - struct bind_ { - typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice; - typedef typename Choice::type type; - typedef typename Choice::const_type const_type; - }; + struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {}; }; } // namespace detail @@ -2730,11 +2704,9 @@ namespace boost { struct adj_list_vertex_property_selector { template <class Graph, class Property, class Tag> - struct bind_ { - typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice; - typedef typename Choice::type type; - typedef typename Choice::const_type const_type; - }; + struct bind_ + : detail::adj_list_choose_vertex_pa<Tag,Graph,Property> + {}; }; template <> struct vertex_property_selector<adj_list_tag> { @@ -2743,11 +2715,7 @@ namespace boost { struct vec_adj_list_vertex_property_selector { template <class Graph, class Property, class Tag> - struct bind_ { - typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice; - typedef typename Choice::type type; - typedef typename Choice::const_type const_type; - }; + struct bind_: detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> {}; }; template <> struct vertex_property_selector<vec_adj_list_tag> { @@ -2793,15 +2761,6 @@ namespace boost { #endif -#undef stored_edge -#undef stored_edge_property -#undef stored_edge_iter - -#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) -// Stay out of the way of the concept checking class -#undef Graph -#endif - #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT /* diff --git a/boost/graph/detail/compressed_sparse_row_struct.hpp b/boost/graph/detail/compressed_sparse_row_struct.hpp index 75ac96204d..56495f3436 100644 --- a/boost/graph/detail/compressed_sparse_row_struct.hpp +++ b/boost/graph/detail/compressed_sparse_row_struct.hpp @@ -44,7 +44,6 @@ #include <boost/graph/graph_selectors.hpp> #include <boost/static_assert.hpp> #include <boost/functional/hash.hpp> -#include <boost/utility.hpp> namespace boost { diff --git a/boost/graph/detail/histogram_sort.hpp b/boost/graph/detail/histogram_sort.hpp index b359a73ded..ca6266a528 100644 --- a/boost/graph/detail/histogram_sort.hpp +++ b/boost/graph/detail/histogram_sort.hpp @@ -60,6 +60,7 @@ count_starts // Put the degree of each vertex v into m_rowstart[v + 1] for (KeyIterator i = begin; i != end; ++i) { if (key_filter(*i)) { + BOOST_ASSERT (key_transform(*i) < numkeys); ++starts[key_transform(*i) + 1]; } } @@ -99,6 +100,7 @@ histogram_sort(KeyIterator key_begin, KeyIterator key_end, for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i) { if (key_filter(*i)) { vertices_size_type source = key_transform(*i); + BOOST_ASSERT (source < numkeys); EdgeIndex insert_pos = current_insert_positions[source]; ++current_insert_positions[source]; values1_out[insert_pos] = *v1i; @@ -137,6 +139,7 @@ histogram_sort(KeyIterator key_begin, KeyIterator key_end, for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i) { if (key_filter(*i)) { vertices_size_type source = key_transform(*i); + BOOST_ASSERT (source < numkeys); EdgeIndex insert_pos = current_insert_positions[source]; ++current_insert_positions[source]; values1_out[insert_pos] = *v1i; @@ -163,6 +166,7 @@ histogram_sort_inplace(KeyIterator key_begin, std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys); // 2. Swap the sources and targets into place for (size_t i = 0; i < rowstart[numkeys]; ++i) { + BOOST_ASSERT (key_transform(key_begin[i]) < numkeys); // While edge i is not in the right bucket: while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) { // Add a slot in the right bucket @@ -197,6 +201,7 @@ histogram_sort_inplace(KeyIterator key_begin, std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys); // 2. Swap the sources and targets into place for (size_t i = 0; i < rowstart[numkeys]; ++i) { + BOOST_ASSERT (key_transform(key_begin[i]) < numkeys); // While edge i is not in the right bucket: while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) { // Add a slot in the right bucket diff --git a/boost/graph/detail/read_graphviz_spirit.hpp b/boost/graph/detail/read_graphviz_spirit.hpp index 4e8b22e5eb..9946469883 100644 --- a/boost/graph/detail/read_graphviz_spirit.hpp +++ b/boost/graph/detail/read_graphviz_spirit.hpp @@ -604,7 +604,9 @@ bool read_graphviz_spirit(MultiPassIterator begin, MultiPassIterator end, scanner_t scan(begin, end, policies); - return p.parse(scan); + bool ok = p.parse(scan); + m_graph.finish_building_graph(); + return ok; } } // namespace boost diff --git a/boost/graph/directed_graph.hpp b/boost/graph/directed_graph.hpp index 0bf0251905..250d0b63d7 100644 --- a/boost/graph/directed_graph.hpp +++ b/boost/graph/directed_graph.hpp @@ -7,7 +7,6 @@ #ifndef BOOST_GRAPH_DIRECTED_GRAPH_HPP #define BOOST_GRAPH_DIRECTED_GRAPH_HPP -#include <boost/utility.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> @@ -33,14 +32,12 @@ template < class directed_graph { public: - typedef typename graph_detail::graph_prop<GraphProp>::property graph_property_type; - typedef typename graph_detail::graph_prop<GraphProp>::bundle graph_bundled; - - typedef typename graph_detail::vertex_prop<VertexProp>::property vertex_property_type; - typedef typename graph_detail::vertex_prop<VertexProp>::bundle vertex_bundled; - - typedef typename graph_detail::edge_prop<EdgeProp>::property edge_property_type; - typedef typename graph_detail::edge_prop<EdgeProp>::bundle edge_bundled; + typedef GraphProp graph_property_type; + typedef VertexProp vertex_property_type; + typedef EdgeProp edge_property_type; + typedef typename lookup_one_property<GraphProp, graph_bundle_t>::type graph_bundled; + typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled; + typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled; private: // Wrap the user-specified properties with an index. @@ -590,35 +587,6 @@ void set_property(DIRECTED_GRAPH& g, Property p, Value v) { return set_property(g.impl(), p, v); } -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES - -template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle> -inline typename property_map<DIRECTED_GRAPH, Type Bundle::*>::type -get(Type Bundle::* p, DIRECTED_GRAPH& g) { - typedef typename property_map< - DIRECTED_GRAPH, Type Bundle::* - >::type return_type; - return return_type(&g, p); -} - -template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle> -inline typename property_map<DIRECTED_GRAPH, Type Bundle::*>::const_type -get(Type Bundle::* p, DIRECTED_GRAPH const& g) { - typedef typename property_map< - DIRECTED_GRAPH, Type Bundle::* - >::const_type return_type; - return return_type(&g, p); -} - -template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key> -inline Type get(Type Bundle::* p, DIRECTED_GRAPH const& g, Key const& k) -{ return get(p, g.impl(), k); } - -template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key, typename Value> -inline void put(Type Bundle::* p, DIRECTED_GRAPH& g, Key const& k, Value const& v) -{ put(p, g.impl(), k, v); } -#endif - // Vertex index management template <DIRECTED_GRAPH_PARAMS> diff --git a/boost/graph/distributed/adjacency_list.hpp b/boost/graph/distributed/adjacency_list.hpp index d0bbbfe55f..264ede512e 100644 --- a/boost/graph/distributed/adjacency_list.hpp +++ b/boost/graph/distributed/adjacency_list.hpp @@ -1882,6 +1882,30 @@ namespace boost { } //--------------------------------------------------------------------- + //--------------------------------------------------------------------- + // Opposite of above. + edge_property_type split_edge_property(const base_edge_property_type& p) + { return split_edge_property(p, directed_selector()); } + + edge_property_type + split_edge_property(const base_edge_property_type& p, directedS) + { + return p.m_base; + } + + edge_property_type + split_edge_property(const base_edge_property_type& p, bidirectionalS) + { + return p.m_base; + } + + edge_property_type + split_edge_property(const base_edge_property_type& p, undirectedS) + { + return p.m_base.m_base; + } + //--------------------------------------------------------------------- + /** The set of messages that can be transmitted and received by * a distributed adjacency list. This list will eventually be * exhaustive, but is currently quite limited. diff --git a/boost/graph/distributed/adjlist/redistribute.hpp b/boost/graph/distributed/adjlist/redistribute.hpp index 064aaba191..5401f1240a 100644 --- a/boost/graph/distributed/adjlist/redistribute.hpp +++ b/boost/graph/distributed/adjlist/redistribute.hpp @@ -237,8 +237,8 @@ PBGL_DISTRIB_ADJLIST_TYPE || get(vertex_to_processor, src) != src.owner || get(vertex_to_processor, tgt) != tgt.owner) redistributed_edges[get(vertex_to_processor, source(*ei, *this))] - .push_back(redistributed_edge(*ei, get(edge_all_t(), base(), - ei->local))); + .push_back(redistributed_edge(*ei, split_edge_property(get(edge_all_t(), base(), + ei->local)))); } inplace_all_to_all(pg, redistributed_edges); diff --git a/boost/graph/distributed/betweenness_centrality.hpp b/boost/graph/distributed/betweenness_centrality.hpp index b6ca7d06ef..04d249a5b8 100644 --- a/boost/graph/distributed/betweenness_centrality.hpp +++ b/boost/graph/distributed/betweenness_centrality.hpp @@ -1389,7 +1389,7 @@ namespace graph { namespace parallel { namespace detail { }; template<> - struct brandes_betweenness_centrality_dispatch1<boost::detail::error_property_not_found> + struct brandes_betweenness_centrality_dispatch1<boost::param_not_found> { template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, typename VertexIndexMap, typename Buffer> @@ -1397,7 +1397,7 @@ namespace graph { namespace parallel { namespace detail { run(const Graph& g, CentralityMap centrality, EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, Buffer sources, typename graph_traits<Graph>::edges_size_type delta, - boost::detail::error_property_not_found) + boost::param_not_found) { boost::graph::parallel::detail::brandes_betweenness_centrality_dispatch2( g, centrality, edge_centrality_map, vertex_index, sources, delta); @@ -1417,7 +1417,8 @@ brandes_betweenness_centrality(const Graph& g, typedef queue<typename graph_traits<Graph>::vertex_descriptor> queue_t; queue_t q; - typedef typename property_value<named_params, edge_weight_t>::type ew; + typedef typename get_param_type<edge_weight_t, named_params>::type ew_param; + typedef typename detail::choose_impl_result<mpl::true_, Graph, ew_param, edge_weight_t>::type ew; graph::parallel::detail::brandes_betweenness_centrality_dispatch1<ew>::run( g, choose_param(get_param(params, vertex_centrality), @@ -1427,7 +1428,7 @@ brandes_betweenness_centrality(const Graph& g, choose_const_pmap(get_param(params, vertex_index), g, vertex_index), choose_param(get_param(params, buffer_param_t()), boost::ref(q)), choose_param(get_param(params, lookahead_t()), 0), - get_param(params, edge_weight)); + choose_const_pmap(get_param(params, edge_weight), g, edge_weight)); } template<typename Graph, typename CentralityMap> @@ -1605,14 +1606,14 @@ namespace detail { namespace graph { }; template<> - struct non_distributed_brandes_betweenness_centrality_dispatch1<detail::error_property_not_found> + struct non_distributed_brandes_betweenness_centrality_dispatch1<param_not_found> { template<typename ProcessGroup, typename Graph, typename CentralityMap, typename EdgeCentralityMap, typename VertexIndexMap, typename Buffer> static void run(const ProcessGroup& pg, const Graph& g, CentralityMap centrality, EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, - Buffer sources, detail::error_property_not_found) + Buffer sources, param_not_found) { non_distributed_brandes_betweenness_centrality_dispatch2(pg, g, centrality, edge_centrality_map, vertex_index, sources); @@ -1631,7 +1632,8 @@ non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Gra typedef queue<int> queue_t; queue_t q; - typedef typename property_value<named_params, edge_weight_t>::type ew; + typedef typename get_param_type<edge_weight_t, named_params>::type ew_param; + typedef typename detail::choose_impl_result<mpl::true_, Graph, ew_param, edge_weight_t>::type ew; detail::graph::non_distributed_brandes_betweenness_centrality_dispatch1<ew>::run( pg, g, choose_param(get_param(params, vertex_centrality), @@ -1640,7 +1642,7 @@ non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Gra dummy_property_map()), choose_const_pmap(get_param(params, vertex_index), g, vertex_index), choose_param(get_param(params, buffer_param_t()), boost::ref(q)), - get_param(params, edge_weight)); + choose_const_pmap(get_param(params, edge_weight), g, edge_weight)); } template<typename ProcessGroup, typename Graph, typename CentralityMap> diff --git a/boost/graph/distributed/breadth_first_search.hpp b/boost/graph/distributed/breadth_first_search.hpp index c987585f5f..36e2df8bb7 100644 --- a/boost/graph/distributed/breadth_first_search.hpp +++ b/boost/graph/distributed/breadth_first_search.hpp @@ -118,7 +118,7 @@ namespace boost { typename graph_traits<DistributedGraph>::vertex_descriptor s, ColorMap color, BFSVisitor vis, - error_property_not_found, + boost::param_not_found, VertexIndexMap vertex_index) { using boost::graph::parallel::process_group; diff --git a/boost/graph/distributed/compressed_sparse_row_graph.hpp b/boost/graph/distributed/compressed_sparse_row_graph.hpp index 01d32cfb88..33861c47b4 100644 --- a/boost/graph/distributed/compressed_sparse_row_graph.hpp +++ b/boost/graph/distributed/compressed_sparse_row_graph.hpp @@ -365,30 +365,22 @@ class compressed_sparse_row_graph< // Directly access a vertex or edge bundle vertex_bundled& operator[](vertex_descriptor v) { - std::pair<process_id_type, vertex_descriptor> locator - = get(vertex_global, *this, v); - BOOST_ASSERT(locator.first == process_id(m_process_group)); - return base().m_vertex_properties[locator.second]; + return get(vertex_bundle, *this, v); } const vertex_bundled& operator[](vertex_descriptor v) const { - std::pair<process_id_type, vertex_descriptor> locator - = get(vertex_global, *this, v); - BOOST_ASSERT(locator.first == process_id(m_process_group)); - return base().m_process_group[locator.second]; + return get(vertex_bundle, *this, v); } edge_bundled& operator[](edge_descriptor e) { - BOOST_ASSERT(get(vertex_owner, *this, e.src) == process_id(m_process_group)); - return base().m_edge_properties[e.idx]; + return get(edge_bundle, *this, e); } const edge_bundled& operator[](edge_descriptor e) const { - BOOST_ASSERT(get(vertex_owner, *this, e.src) == process_id(m_process_group)); - return base().m_edge_properties[e.idx]; + return get(edge_bundle, *this, e); } // Create a vertex descriptor from a process ID and a local index. @@ -1757,19 +1749,22 @@ class csr_edge_global_map public: // ----------------------------------------------------------------- // Readable Property Map concept requirements - typedef std::pair<ProcessID, EdgeIndex> value_type; - typedef value_type reference; typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> key_type; + typedef std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > value_type; + typedef value_type reference; typedef readable_property_map_tag category; }; template<typename ProcessID, typename Vertex, typename EdgeIndex> -inline std::pair<ProcessID, EdgeIndex> +inline std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > get(csr_edge_global_map<ProcessID, Vertex, EdgeIndex> pm, typename csr_edge_global_map<ProcessID, Vertex, EdgeIndex>::key_type k) { const int local_index_bits = sizeof(Vertex) * CHAR_BIT - processor_bits; - return std::pair<ProcessID, EdgeIndex>(k.src >> local_index_bits, k.idx); + const Vertex local_index_mask = Vertex(-1) >> processor_bits; + return std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > + ((k.src >> local_index_bits), + detail::csr_edge_descriptor<Vertex, EdgeIndex>(k.src & local_index_mask, k.idx)); } template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> @@ -1796,7 +1791,7 @@ get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> inline std::pair<typename ProcessGroup::process_id_type, - typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type> + typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor> get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k) { @@ -1818,7 +1813,7 @@ get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> inline std::pair<typename ProcessGroup::process_id_type, - typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type> + typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor> get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k) { @@ -1827,12 +1822,16 @@ get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, const int local_index_bits = sizeof(vertex_descriptor) * CHAR_BIT - processor_bits; + const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type local_index_mask = + typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type(-1) >> processor_bits; typedef std::pair<typename ProcessGroup::process_id_type, - typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type> + typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor> result_type; - return result_type(k.src >> local_index_bits, k.idx); + return result_type(k.src >> local_index_bits, + typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor + (k.src & local_index_mask, k.idx)); } // ----------------------------------------------------------------- @@ -1847,7 +1846,8 @@ class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t> typedef local_property_map< typename BOOST_DISTRIB_CSR_GRAPH_TYPE::process_group_type, global_map, - identity_property_map> type; + typename property_map<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type, edge_index_t>::type + > type; typedef type const_type; }; @@ -1859,7 +1859,7 @@ get(edge_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t> ::type result_type; return result_type(g.process_group(), get(edge_global, g), - identity_property_map()); + get(edge_index, g.base())); } template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> @@ -1878,7 +1878,7 @@ get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t> ::const_type result_type; return result_type(g.process_group(), get(edge_global, g), - identity_property_map()); + get(edge_index, g.base())); } template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> @@ -1889,229 +1889,67 @@ get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, return k.idx; } -/* Common traits for getting vertex_bundle and edge_bundle maps */ - -namespace detail { - template <typename Graph, typename T> struct get_bundles; - - template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename T> - class get_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE, T> { - typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph; - typedef typename Graph::process_group_type process_group_type; - - // Extract the global property map for our key type. - typedef typename property_map<Graph, vertex_global_t>::const_type vertex_global_map; - typedef typename property_traits<vertex_global_map>::value_type vertex_locator; - typedef typename property_map<Graph, edge_global_t>::const_type edge_global_map; - typedef typename property_traits<edge_global_map>::value_type edge_locator; - - // Build the local property map - typedef bundle_property_map<std::vector<VertexProperty>, - typename vertex_locator::second_type, - VertexProperty, - T> vertex_local_pmap; - - // Build the local const property map - typedef bundle_property_map<const std::vector<VertexProperty>, - typename vertex_locator::second_type, - VertexProperty, - const T> vertex_local_const_pmap; - - // Build the local property map - typedef bundle_property_map<std::vector<EdgeProperty>, - typename edge_locator::second_type, - EdgeProperty, - T> edge_local_pmap; - - // Build the local const property map - typedef bundle_property_map<const std::vector<EdgeProperty>, - typename edge_locator::second_type, - EdgeProperty, - const T> edge_local_const_pmap; - - public: - typedef ::boost::parallel::distributed_property_map< - process_group_type, vertex_global_map, vertex_local_pmap> vertex_map_type; - - typedef ::boost::parallel::distributed_property_map< - process_group_type, vertex_global_map, vertex_local_const_pmap> vertex_map_const_type; - - typedef ::boost::parallel::distributed_property_map< - process_group_type, edge_global_map, edge_local_pmap> edge_map_type; - - typedef ::boost::parallel::distributed_property_map< - process_group_type, edge_global_map, edge_local_const_pmap> edge_map_const_type; - - }; - - template <typename Graph> struct get_full_bundles; - - template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> - class get_full_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE> { // For vertex_bundle_t and edge_bundle_t - typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph; - typedef typename Graph::process_group_type process_group_type; - - // Extract the global property map for our key type. - typedef typename property_map<Graph, vertex_global_t>::const_type vertex_global_map; - typedef typename property_traits<vertex_global_map>::value_type vertex_locator; - typedef typename property_map<Graph, edge_global_t>::const_type edge_global_map; - typedef typename property_traits<edge_global_map>::value_type edge_locator; - - // Build the local property maps - typedef typename property_map<typename Graph::base_type, vertex_bundle_t>::type vertex_local_pmap; - typedef typename property_map<typename Graph::base_type, vertex_bundle_t>::const_type vertex_local_const_pmap; - typedef typename property_map<typename Graph::base_type, edge_bundle_t>::type edge_local_pmap; - typedef typename property_map<typename Graph::base_type, edge_bundle_t>::const_type edge_local_const_pmap; - - public: - typedef ::boost::parallel::distributed_property_map< - process_group_type, vertex_global_map, vertex_local_pmap> vertex_map_type; - - typedef ::boost::parallel::distributed_property_map< - process_group_type, vertex_global_map, vertex_local_const_pmap> vertex_map_const_type; - - typedef ::boost::parallel::distributed_property_map< - process_group_type, edge_global_map, edge_local_pmap> edge_map_type; - - typedef ::boost::parallel::distributed_property_map< - process_group_type, edge_global_map, edge_local_const_pmap> edge_map_const_type; - - }; -} - -template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> -struct property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_bundle_t> -{ - typedef typename detail::get_full_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE>::vertex_map_type type; - typedef typename detail::get_full_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE>::vertex_map_const_type const_type; -}; - -template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> -struct property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_bundle_t> -{ - typedef typename detail::get_full_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE>::edge_map_type type; - typedef typename detail::get_full_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE>::edge_map_const_type const_type; -}; - -// ----------------------------------------------------------------- -// Bundled Properties -template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle> -class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, T Bundle::*> -{ - typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph; - typedef typename Graph::process_group_type process_group_type; +template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag> +class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag> { + typedef BOOST_DISTRIB_CSR_GRAPH_TYPE graph_type; + typedef typename graph_type::process_group_type process_group_type; + typedef typename graph_type::base_type base_graph_type; + typedef typename property_map<base_graph_type, Tag>::type + local_pmap; + typedef typename property_map<base_graph_type, Tag>::const_type + local_const_pmap; + + typedef graph_traits<graph_type> traits; + typedef typename graph_traits<base_graph_type>::vertex_descriptor local_vertex; + typedef typename property_traits<local_pmap>::key_type local_key_type; + + typedef typename property_traits<local_pmap>::value_type value_type; + + typedef typename property_map<graph_type, vertex_global_t>::const_type + vertex_global_map; + typedef typename property_map<graph_type, edge_global_t>::const_type + edge_global_map; + + typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<base_graph_type, Tag>::type, + vertex_property_tag>, + vertex_global_map, edge_global_map>::type + global_map; public: - typedef typename mpl::if_<detail::is_vertex_bundle<VertexProperty, - EdgeProperty, - Bundle>, - typename detail::get_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE, T>::vertex_map_type, - typename detail::get_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE, T>::edge_map_type> - ::type type; - - typedef typename mpl::if_<detail::is_vertex_bundle<VertexProperty, - EdgeProperty, - Bundle>, - typename detail::get_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE, T>::vertex_map_const_type, - typename detail::get_bundles<BOOST_DISTRIB_CSR_GRAPH_TYPE, T>::edge_map_const_type> - ::type const_type; -}; - -namespace detail { - // Retrieve the local bundle_property_map corresponding to a - // non-const vertex property. - template<typename Graph, typename T, typename Bundle> - inline bundle_property_map<std::vector<typename Graph::vertex_bundled>, - typename Graph::vertex_descriptor, - typename Graph::vertex_bundled, T> - get_distrib_csr_bundle(T Bundle::* p, Graph& g, mpl::true_) - { - typedef bundle_property_map<std::vector<typename Graph::vertex_bundled>, - typename Graph::vertex_descriptor, - typename Graph::vertex_bundled, T> result_type; - return result_type(&g.base().vertex_properties().m_vertex_properties, p); - } - - // Retrieve the local bundle_property_map corresponding to a - // const vertex property. - template<typename Graph, typename T, typename Bundle> - inline bundle_property_map<const std::vector<typename Graph::vertex_bundled>, - typename Graph::vertex_descriptor, - typename Graph::vertex_bundled, const T> - get_distrib_csr_bundle(T Bundle::* p, const Graph& g, mpl::true_) - { - typedef bundle_property_map< - const std::vector<typename Graph::vertex_bundled>, - typename Graph::vertex_descriptor, - typename Graph::vertex_bundled, const T> result_type; - return result_type(&g.base().vertex_properties().m_vertex_properties, p); - } + typedef ::boost::parallel::distributed_property_map< + process_group_type, global_map, local_pmap> type; - // Retrieve the local bundle_property_map corresponding to a - // non-const edge property. - template<typename Graph, typename T, typename Bundle> - inline bundle_property_map<std::vector<typename Graph::edge_bundled>, - typename Graph::edges_size_type, - typename Graph::edge_bundled, T> - get_distrib_csr_bundle(T Bundle::* p, Graph& g, mpl::false_) - { - typedef bundle_property_map<std::vector<typename Graph::edge_bundled>, - typename Graph::edges_size_type, - typename Graph::edge_bundled, T> result_type; - return result_type(&g.base().edge_properties().m_edge_properties, p); - } - - // Retrieve the local bundle_property_map corresponding to a - // const edge property. - template<typename Graph, typename T, typename Bundle> - inline bundle_property_map<const std::vector<typename Graph::edge_bundled>, - typename Graph::edges_size_type, - typename Graph::edge_bundled, const T> - get_distrib_csr_bundle(T Bundle::* p, const Graph& g, mpl::false_) - { - typedef bundle_property_map< - const std::vector<typename Graph::edge_bundled>, - typename Graph::edges_size_type, - typename Graph::edge_bundled, const T> result_type; - return result_type(&g.base().edge_properties().m_edge_properties, p); - } -} + typedef ::boost::parallel::distributed_property_map< + process_group_type, global_map, local_const_pmap> const_type; +}; -template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle> -typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, T Bundle::*>::type -get(T Bundle::* p, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) +template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag> +typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::type +get(Tag tag, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) { typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph; - typedef typename property_map<Graph, T Bundle::*>::type result_type; - - // Resolver + typedef typename property_map<Graph, Tag>::type result_type; typedef typename property_traits<result_type>::value_type value_type; - typedef typename property_reduce<T Bundle::*>::template apply<value_type> + typedef typename property_reduce<Tag>::template apply<value_type> reduce; - typedef typename property_traits<result_type>::key_type descriptor; - typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; - typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, + typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<Graph, Tag>::type, + vertex_property_tag>, vertex_global_t, edge_global_t>::type global_map_t; return result_type(g.process_group(), get(global_map_t(), g), - detail::get_distrib_csr_bundle - (p, g, mpl::bool_<is_same<descriptor, - vertex_descriptor>::value>()), - reduce()); + get(tag, g.base()), reduce()); } -template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle> -typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, T Bundle::*>::const_type -get(T Bundle::* p, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) +template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag> +typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::const_type +get(Tag tag, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) { typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph; - typedef typename property_map<Graph, T Bundle::*>::const_type result_type; - - // Resolver + typedef typename property_map<Graph, Tag>::const_type result_type; typedef typename property_traits<result_type>::value_type value_type; - typedef typename property_reduce<T Bundle::*>::template apply<value_type> + typedef typename property_reduce<Tag>::template apply<value_type> reduce; typedef typename property_traits<result_type>::key_type descriptor; @@ -2121,10 +1959,7 @@ get(T Bundle::* p, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) global_map_t; return result_type(g.process_group(), get(global_map_t(), g), - detail::get_distrib_csr_bundle - (p, g, mpl::bool_<is_same<descriptor, - vertex_descriptor>::value>()), - reduce()); + get(tag, g.base()), reduce()); } namespace mpi { diff --git a/boost/graph/distributed/dijkstra_shortest_paths.hpp b/boost/graph/distributed/dijkstra_shortest_paths.hpp index f72fa11a50..acfd194400 100644 --- a/boost/graph/distributed/dijkstra_shortest_paths.hpp +++ b/boost/graph/distributed/dijkstra_shortest_paths.hpp @@ -49,7 +49,7 @@ namespace boost { }; template<> - struct parallel_dijkstra_impl2< ::boost::detail::error_property_not_found > + struct parallel_dijkstra_impl2< ::boost::param_not_found > { template<typename DistributedGraph, typename DijkstraVisitor, typename PredecessorMap, typename DistanceMap, @@ -60,7 +60,7 @@ namespace boost { run(const DistributedGraph& g, typename graph_traits<DistributedGraph>::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, - ::boost::detail::error_property_not_found, + ::boost::param_not_found, WeightMap weight, IndexMap index_map, ColorMap color_map, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) @@ -95,7 +95,7 @@ namespace boost { }; template<> - struct parallel_dijkstra_impl< ::boost::detail::error_property_not_found > + struct parallel_dijkstra_impl< ::boost::param_not_found > { private: template<typename DistributedGraph, typename DijkstraVisitor, @@ -131,7 +131,7 @@ namespace boost { typename graph_traits<DistributedGraph>::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, Lookahead lookahead, WeightMap weight, IndexMap index_map, - ::boost::detail::error_property_not_found, + ::boost::param_not_found, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) { @@ -190,8 +190,7 @@ namespace boost { IndexMap> DefColorMap; DefColorMap color_map(color.begin(), index_map); - typedef typename property_value< bgl_named_params<T, Tag, Base>, - vertex_color_t>::type color_map_type; + typedef typename get_param_type< vertex_color_t, bgl_named_params<T, Tag, Base> >::type color_map_type; graph::detail::parallel_dijkstra_impl<color_map_type> ::run(g, s, predecessor, distance, diff --git a/boost/graph/distributed/page_rank.hpp b/boost/graph/distributed/page_rank.hpp index c2c230d387..1fc43ed683 100644 --- a/boost/graph/distributed/page_rank.hpp +++ b/boost/graph/distributed/page_rank.hpp @@ -93,6 +93,7 @@ page_rank_impl(const Graph& g, RankMap rank_map, Done done, ::const_type vertex_owner_map; typename property_map<Graph, vertex_owner_t>::const_type owner = get(vertex_owner, g); + (void)owner; typedef typename boost::graph::parallel::process_group_type<Graph> ::type process_group_type; diff --git a/boost/graph/eccentricity.hpp b/boost/graph/eccentricity.hpp index a8b3e48547..63797a8309 100644 --- a/boost/graph/eccentricity.hpp +++ b/boost/graph/eccentricity.hpp @@ -7,7 +7,7 @@ #ifndef BOOST_GRAPH_ECCENTRICITY_HPP #define BOOST_GRAPH_ECCENTRICITY_HPP -#include <boost/utility.hpp> +#include <boost/next_prior.hpp> #include <boost/config.hpp> #include <boost/graph/detail/geodesic.hpp> #include <boost/concept/assert.hpp> diff --git a/boost/graph/edmonds_karp_max_flow.hpp b/boost/graph/edmonds_karp_max_flow.hpp index 43cc592d2e..8f86fb2026 100644 --- a/boost/graph/edmonds_karp_max_flow.hpp +++ b/boost/graph/edmonds_karp_max_flow.hpp @@ -52,21 +52,21 @@ namespace boost { // find minimum residual capacity along the augmenting path FlowValue delta = (std::numeric_limits<FlowValue>::max)(); - e = p[sink]; + e = get(p, sink); do { BOOST_USING_STD_MIN(); - delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[e]); + delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e)); u = source(e, g); - e = p[u]; + e = get(p, u); } while (u != src); // push delta units of flow along the augmenting path - e = p[sink]; + e = get(p, sink); do { - residual_capacity[e] -= delta; - residual_capacity[reverse_edge[e]] += delta; + put(residual_capacity, e, get(residual_capacity, e) - delta); + put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta); u = source(e, g); - e = p[u]; + e = get(p, u); } while (u != src); } @@ -94,22 +94,22 @@ namespace boost { typename graph_traits<Graph>::out_edge_iterator ei, e_end; for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) - res[*ei] = cap[*ei]; + put(res, *ei, get(cap, *ei)); - color[sink] = Color::gray(); - while (color[sink] != Color::white()) { + put(color, sink, Color::gray()); + while (get(color, sink) != Color::white()) { boost::queue<vertex_t> Q; breadth_first_search (detail::residual_graph(g, res), src, Q, make_bfs_visitor(record_edge_predecessors(pred, on_tree_edge())), color); - if (color[sink] != Color::white()) + if (get(color, sink) != Color::white()) detail::augment(g, src, sink, pred, res, rev); } // while typename property_traits<CapacityEdgeMap>::value_type flow = 0; for (boost::tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei) - flow += (cap[*ei] - res[*ei]); + flow += (get(cap, *ei) - get(res, *ei)); return flow; } // edmonds_karp_max_flow() @@ -140,7 +140,7 @@ namespace boost { } }; template<> - struct edmonds_karp_dispatch2<detail::error_property_not_found> { + struct edmonds_karp_dispatch2<param_not_found> { template <class Graph, class PredMap, class P, class T, class R> static typename edge_capacity_value<Graph, P, T, R>::type apply @@ -149,7 +149,7 @@ namespace boost { typename graph_traits<Graph>::vertex_descriptor sink, PredMap pred, const bgl_named_params<P, T, R>& params, - detail::error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; typedef typename graph_traits<Graph>::vertices_size_type size_type; @@ -183,13 +183,13 @@ namespace boost { const bgl_named_params<P, T, R>& params, PredMap pred) { - typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C; + typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C; return edmonds_karp_dispatch2<C>::apply (g, src, sink, pred, params, get_param(params, vertex_color)); } }; template<> - struct edmonds_karp_dispatch1<detail::error_property_not_found> { + struct edmonds_karp_dispatch1<param_not_found> { template <class Graph, class P, class T, class R> static typename edge_capacity_value<Graph, P, T, R>::type @@ -198,7 +198,7 @@ namespace boost { typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, const bgl_named_params<P, T, R>& params, - detail::error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; typedef typename graph_traits<Graph>::vertices_size_type size_type; @@ -206,7 +206,7 @@ namespace boost { num_vertices(g) : 1; std::vector<edge_descriptor> pred_vec(n); - typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C; + typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C; return edmonds_karp_dispatch2<C>::apply (g, src, sink, make_iterator_property_map(pred_vec.begin(), choose_const_pmap @@ -227,7 +227,7 @@ namespace boost { typename graph_traits<Graph>::vertex_descriptor sink, const bgl_named_params<P, T, R>& params) { - typedef typename property_value< bgl_named_params<P,T,R>, vertex_predecessor_t>::type Pred; + typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type Pred; return detail::edmonds_karp_dispatch1<Pred>::apply (g, src, sink, params, get_param(params, vertex_predecessor)); } diff --git a/boost/graph/fruchterman_reingold.hpp b/boost/graph/fruchterman_reingold.hpp index 4ce502e83b..bab353f334 100644 --- a/boost/graph/fruchterman_reingold.hpp +++ b/boost/graph/fruchterman_reingold.hpp @@ -363,7 +363,7 @@ namespace detail { }; template<> - struct fr_force_directed_layout<error_property_not_found> + struct fr_force_directed_layout<param_not_found> { template<typename Topology, typename Graph, typename PositionMap, typename AttractiveForce, typename RepulsiveForce, @@ -377,7 +377,7 @@ namespace detail { RepulsiveForce repulsive_force, ForcePairs force_pairs, Cooling cool, - error_property_not_found, + param_not_found, const bgl_named_params<Param, Tag, Rest>& params) { typedef typename Topology::point_difference_type PointDiff; @@ -404,8 +404,7 @@ fruchterman_reingold_force_directed_layout const Topology& topology, const bgl_named_params<Param, Tag, Rest>& params) { - typedef typename property_value<bgl_named_params<Param,Tag,Rest>, - vertex_displacement_t>::type D; + typedef typename get_param_type<vertex_displacement_t, bgl_named_params<Param,Tag,Rest> >::type D; detail::fr_force_directed_layout<D>::run (g, position, topology, diff --git a/boost/graph/graph_archetypes.hpp b/boost/graph/graph_archetypes.hpp index 9b364bb814..81f9c2c8a8 100644 --- a/boost/graph/graph_archetypes.hpp +++ b/boost/graph/graph_archetypes.hpp @@ -53,6 +53,8 @@ namespace boost { // should use a different namespace for this typedef void in_edge_iterator; typedef void vertex_iterator; typedef void edge_iterator; + + static vertex_descriptor null_vertex() {return vertex_descriptor();} }; template <typename V, typename D, typename P, typename B> V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&, @@ -105,6 +107,8 @@ namespace boost { // should use a different namespace for this typedef void out_edge_iterator; typedef void vertex_iterator; typedef void edge_iterator; + + static vertex_descriptor null_vertex() {return vertex_descriptor();} }; template <typename V, typename D, typename P, typename B> @@ -154,6 +158,8 @@ namespace boost { // should use a different namespace for this typedef void in_edge_iterator; typedef void edge_iterator; + + static vertex_descriptor null_vertex() {return vertex_descriptor();} }; template <typename V, typename D, typename P, typename B> diff --git a/boost/graph/graph_test.hpp b/boost/graph/graph_test.hpp index 7b3a5402bd..69d89f34f2 100644 --- a/boost/graph/graph_test.hpp +++ b/boost/graph/graph_test.hpp @@ -325,10 +325,10 @@ namespace boost { template <typename PropVal, typename PropertyTag> void test_readable_vertex_property_graph - (const std::vector<PropVal>& vertex_prop, PropertyTag, const Graph& g) + (const std::vector<PropVal>& vertex_prop, PropertyTag tag, const Graph& g) { typedef typename property_map<Graph, PropertyTag>::const_type const_Map; - const_Map pmap = get(PropertyTag(), g); + const_Map pmap = get(tag, g); typename std::vector<PropVal>::const_iterator i = vertex_prop.begin(); for (typename boost::graph_traits<Graph>::vertex_iterator @@ -339,7 +339,7 @@ namespace boost { ++bgl_first_9) { //BGL_FORALL_VERTICES_T(v, g, Graph) { typename property_traits<const_Map>::value_type - pval1 = get(pmap, v), pval2 = get(PropertyTag(), g, v); + pval1 = get(pmap, v), pval2 = get(tag, g, v); BOOST_CHECK(pval1 == pval2); BOOST_CHECK(pval1 == *i++); } @@ -350,7 +350,7 @@ namespace boost { (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g) { typedef typename property_map<Graph, PropertyTag>::type PMap; - PMap pmap = get(PropertyTag(), g); + PMap pmap = get(tag, g); typename std::vector<PropVal>::const_iterator i = vertex_prop.begin(); for (typename boost::graph_traits<Graph>::vertex_iterator bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; @@ -368,7 +368,7 @@ namespace boost { typename std::vector<PropVal>::const_iterator j = vertex_prop.begin(); BGL_FORALL_VERTICES_T(v, g, Graph) - put(PropertyTag(), g, v, *j++); + put(tag, g, v, *j++); test_readable_vertex_property_graph(vertex_prop, tag, g); } diff --git a/boost/graph/graph_traits.hpp b/boost/graph/graph_traits.hpp index fad82f9d2f..625429e611 100644 --- a/boost/graph/graph_traits.hpp +++ b/boost/graph/graph_traits.hpp @@ -15,8 +15,11 @@ #include <utility> /* Primarily for std::pair */ #include <boost/tuple/tuple.hpp> #include <boost/mpl/if.hpp> +#include <boost/mpl/eval_if.hpp> #include <boost/mpl/bool.hpp> #include <boost/mpl/not.hpp> +#include <boost/mpl/has_xxx.hpp> +#include <boost/mpl/void.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/iterator/iterator_categories.hpp> #include <boost/iterator/iterator_adaptor.hpp> @@ -218,28 +221,31 @@ namespace boost { //?? not the right place ?? Lee typedef boost::forward_traversal_tag multi_pass_input_iterator_tag; - // Forward declare graph_bundle_t property name (from - // boost/graph/properties.hpp, which includes this file) for - // bundled_result. - enum graph_bundle_t {graph_bundle}; + namespace detail { + BOOST_MPL_HAS_XXX_TRAIT_DEF(graph_property_type) + BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_property_type) + BOOST_MPL_HAS_XXX_TRAIT_DEF(vertex_property_type) + + template <typename G> struct get_graph_property_type {typedef typename G::graph_property_type type;}; + template <typename G> struct get_edge_property_type {typedef typename G::edge_property_type type;}; + template <typename G> struct get_vertex_property_type {typedef typename G::vertex_property_type type;}; + } template <typename G> - struct graph_property_type { - typedef typename G::graph_property_type type; - }; + struct graph_property_type + : boost::mpl::eval_if<detail::has_graph_property_type<G>, + detail::get_graph_property_type<G>, + no_property> {}; template <typename G> - struct edge_property_type { - typedef typename G::edge_property_type type; - }; + struct edge_property_type + : boost::mpl::eval_if<detail::has_edge_property_type<G>, + detail::get_edge_property_type<G>, + no_property> {}; template <typename G> - struct vertex_property_type { - typedef typename G::vertex_property_type type; - }; - - struct no_bundle { }; - struct no_graph_bundle : no_bundle { }; - struct no_vertex_bundle : no_bundle { }; - struct no_edge_bundle : no_bundle { }; + struct vertex_property_type + : boost::mpl::eval_if<detail::has_vertex_property_type<G>, + detail::get_vertex_property_type<G>, + no_property> {}; template<typename G> struct graph_bundle_type { @@ -281,7 +287,7 @@ namespace boost { // A helper metafunction for determining whether or not a type is // bundled. template <typename T> - struct is_no_bundle : mpl::bool_<is_convertible<T, no_bundle>::value> + struct is_no_bundle : mpl::bool_<is_same<T, no_property>::value> { }; } // namespace graph_detail diff --git a/boost/graph/graphml.hpp b/boost/graph/graphml.hpp index 2239d96661..028cdc26ca 100644 --- a/boost/graph/graphml.hpp +++ b/boost/graph/graphml.hpp @@ -262,7 +262,7 @@ write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index, for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) { std::string key_id = "key" + lexical_cast<std::string>(key_count++); - if (i->second->key() == typeid(Graph)) + if (i->second->key() == typeid(Graph*)) graph_key_ids[i->first] = key_id; else if (i->second->key() == typeid(vertex_descriptor)) vertex_key_ids[i->first] = key_id; @@ -273,7 +273,7 @@ write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index, std::string type_name = "string"; mpl::for_each<value_types>(get_type_name<value_types>(i->second->value(), type_names, type_name)); out << " <key id=\"" << encode_char_entities(key_id) << "\" for=\"" - << (i->second->key() == typeid(Graph) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\"" + << (i->second->key() == typeid(Graph*) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\"" << " attr.name=\"" << i->first << "\"" << " attr.type=\"" << type_name << "\"" << " />\n"; @@ -287,10 +287,12 @@ write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index, // Output graph data for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) { - if (i->second->key() == typeid(Graph)) + if (i->second->key() == typeid(Graph*)) { + // The const_cast here is just to get typeid correct for property + // map key; the graph should not be mutated using it. out << " <data key=\"" << graph_key_ids[i->first] << "\">" - << encode_char_entities(i->second->get_string(g)) << "</data>\n"; + << encode_char_entities(i->second->get_string(const_cast<Graph*>(&g))) << "</data>\n"; } } diff --git a/boost/graph/graphviz.hpp b/boost/graph/graphviz.hpp index 718220ffec..aedce5553c 100644 --- a/boost/graph/graphviz.hpp +++ b/boost/graph/graphviz.hpp @@ -25,10 +25,14 @@ #include <boost/property_map/dynamic_property_map.hpp> #include <boost/graph/overloading.hpp> #include <boost/graph/dll_import_export.hpp> +#include <boost/graph/compressed_sparse_row_graph.hpp> +#include <boost/graph/iteration_macros.hpp> #include <boost/spirit/include/classic_multi_pass.hpp> #include <boost/lexical_cast.hpp> +#include <boost/static_assert.hpp> #include <boost/algorithm/string/replace.hpp> #include <boost/xpressive/xpressive_static.hpp> +#include <boost/foreach.hpp> namespace boost { @@ -713,6 +717,9 @@ class mutate_graph virtual void // RG: need new second parameter to support BGL subgraphs set_graph_property(const id_t& key, const id_t& value) = 0; + + virtual void + finish_building_graph() = 0; }; template<typename MutableGraph> @@ -781,6 +788,8 @@ class mutate_graph_impl : public mutate_graph put(key, dp_, &graph_, value); } + void finish_building_graph() {} + protected: MutableGraph& graph_; @@ -790,6 +799,109 @@ class mutate_graph_impl : public mutate_graph std::map<edge_t, bgl_edge_t> bgl_edges; }; +template<typename Directed, + typename VertexProperty, + typename EdgeProperty, + typename GraphProperty, + typename Vertex, + typename EdgeIndex> +class mutate_graph_impl<compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> > + : public mutate_graph +{ + typedef compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> CSRGraph; + typedef typename graph_traits<CSRGraph>::vertices_size_type bgl_vertex_t; + typedef typename graph_traits<CSRGraph>::edges_size_type bgl_edge_t; + typedef typename graph_traits<CSRGraph>::edge_descriptor edge_descriptor; + + public: + mutate_graph_impl(CSRGraph& graph, dynamic_properties& dp, + std::string node_id_prop) + : graph_(graph), dp_(dp), vertex_count(0), node_id_prop_(node_id_prop) { } + + ~mutate_graph_impl() {} + + void finish_building_graph() { + typedef compressed_sparse_row_graph<directedS, no_property, bgl_edge_t, GraphProperty, Vertex, EdgeIndex> TempCSRGraph; + TempCSRGraph temp(edges_are_unsorted_multi_pass, + edges_to_add.begin(), edges_to_add.end(), + counting_iterator<bgl_edge_t>(0), + vertex_count); + set_property(temp, graph_all, get_property(graph_, graph_all)); + graph_.assign(temp); // Copies structure, not properties + std::vector<edge_descriptor> edge_permutation_from_sorting(num_edges(temp)); + BGL_FORALL_EDGES_T(e, temp, TempCSRGraph) { + edge_permutation_from_sorting[temp[e]] = e; + } + typedef boost::tuple<id_t, bgl_vertex_t, id_t> v_prop; + BOOST_FOREACH(const v_prop& t, vertex_props) { + put(boost::get<0>(t), dp_, boost::get<1>(t), boost::get<2>(t)); + } + typedef boost::tuple<id_t, bgl_edge_t, id_t> e_prop; + BOOST_FOREACH(const e_prop& t, edge_props) { + put(boost::get<0>(t), dp_, edge_permutation_from_sorting[boost::get<1>(t)], boost::get<2>(t)); + } + } + + bool is_directed() const + { + return + boost::is_convertible< + typename boost::graph_traits<CSRGraph>::directed_category, + boost::directed_tag>::value; + } + + virtual void do_add_vertex(const node_t& node) + { + // Add the node to the graph. + bgl_vertex_t v = vertex_count++; + + // Set up a mapping from name to BGL vertex. + bgl_nodes.insert(std::make_pair(node, v)); + + // node_id_prop_ allows the caller to see the real id names for nodes. + vertex_props.push_back(boost::make_tuple(node_id_prop_, v, node)); + } + + void + do_add_edge(const edge_t& edge, const node_t& source, const node_t& target) + { + bgl_edge_t result = edges_to_add.size(); + edges_to_add.push_back(std::make_pair(bgl_nodes[source], bgl_nodes[target])); + bgl_edges.insert(std::make_pair(edge, result)); + } + + void + set_node_property(const id_t& key, const node_t& node, const id_t& value) + { + vertex_props.push_back(boost::make_tuple(key, bgl_nodes[node], value)); + } + + void + set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) + { + edge_props.push_back(boost::make_tuple(key, bgl_edges[edge], value)); + } + + void + set_graph_property(const id_t& key, const id_t& value) + { + /* RG: pointer to graph prevents copying */ + put(key, dp_, &graph_, value); + } + + + protected: + CSRGraph& graph_; + dynamic_properties& dp_; + bgl_vertex_t vertex_count; + std::string node_id_prop_; + std::vector<boost::tuple<id_t, bgl_vertex_t, id_t> > vertex_props; + std::vector<boost::tuple<id_t, bgl_edge_t, id_t> > edge_props; + std::vector<std::pair<bgl_vertex_t, bgl_vertex_t> > edges_to_add; + std::map<node_t, bgl_vertex_t> bgl_nodes; + std::map<edge_t, bgl_edge_t> bgl_edges; +}; + } } } // end namespace boost::detail::graph #ifdef BOOST_GRAPH_USE_SPIRIT_PARSER diff --git a/boost/graph/grid_graph.hpp b/boost/graph/grid_graph.hpp index f63f3d01e6..7bb3732422 100644 --- a/boost/graph/grid_graph.hpp +++ b/boost/graph/grid_graph.hpp @@ -17,7 +17,6 @@ #include <boost/array.hpp> #include <boost/bind.hpp> #include <boost/limits.hpp> -#include <boost/make_shared.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/properties.hpp> #include <boost/iterator/counting_iterator.hpp> @@ -63,14 +62,14 @@ namespace boost { grid_graph_index_map() { } grid_graph_index_map(const Graph& graph) : - m_graph(make_shared<Graph>(graph)) { } + m_graph(&graph) { } value_type operator[](key_type key) const { return (m_graph->index_of(key)); } protected: - shared_ptr<Graph> m_graph; + const Graph* m_graph; }; template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> diff --git a/boost/graph/is_kuratowski_subgraph.hpp b/boost/graph/is_kuratowski_subgraph.hpp index 8791b4cf18..1dd314d317 100644 --- a/boost/graph/is_kuratowski_subgraph.hpp +++ b/boost/graph/is_kuratowski_subgraph.hpp @@ -9,7 +9,6 @@ #define __IS_KURATOWSKI_SUBGRAPH_HPP__ #include <boost/config.hpp> -#include <boost/utility.hpp> //for next/prior #include <boost/tuple/tuple.hpp> //for tie #include <boost/property_map/property_map.hpp> #include <boost/graph/properties.hpp> @@ -301,11 +300,11 @@ namespace boost if (target_graph == detail::tg_k_5) { - return isomorphism(K_5,contracted_graph); + return boost::isomorphism(K_5,contracted_graph); } else //target_graph == tg_k_3_3 { - return isomorphism(K_3_3,contracted_graph); + return boost::isomorphism(K_3_3,contracted_graph); } diff --git a/boost/graph/is_straight_line_drawing.hpp b/boost/graph/is_straight_line_drawing.hpp index 74775b44f5..c471cde8be 100644 --- a/boost/graph/is_straight_line_drawing.hpp +++ b/boost/graph/is_straight_line_drawing.hpp @@ -9,7 +9,7 @@ #define __IS_STRAIGHT_LINE_DRAWING_HPP__ #include <boost/config.hpp> -#include <boost/utility.hpp> //for next and prior +#include <boost/next_prior.hpp> #include <boost/tuple/tuple.hpp> #include <boost/tuple/tuple_comparison.hpp> #include <boost/property_map/property_map.hpp> @@ -19,6 +19,7 @@ #include <algorithm> #include <vector> #include <set> +#include <map> @@ -34,12 +35,12 @@ namespace boost // defines how far away from the endpoints of s1 and s2 we want to consider // an intersection. - bool intersects(double x1, double y1, - double x2, double y2, - double a1, double b1, - double a2, double b2, - double epsilon = 0.000001 - ) + inline bool intersects(double x1, double y1, + double x2, double y2, + double a1, double b1, + double a2, double b2, + double epsilon = 0.000001 + ) { if (x1 - x2 == 0) diff --git a/boost/graph/isomorphism.hpp b/boost/graph/isomorphism.hpp index bbdd1f7b41..99055f35c8 100644 --- a/boost/graph/isomorphism.hpp +++ b/boost/graph/isomorphism.hpp @@ -11,8 +11,9 @@ #include <iterator> #include <algorithm> #include <boost/config.hpp> +#include <boost/assert.hpp> +#include <boost/smart_ptr.hpp> #include <boost/graph/depth_first_search.hpp> -#include <boost/utility.hpp> #include <boost/detail/algorithm.hpp> #include <boost/pending/indirect_cmp.hpp> // for make_indirect_pmap #include <boost/concept/assert.hpp> @@ -134,6 +135,10 @@ namespace boost { bool test_isomorphism() { + // reset isomapping + BGL_FORALL_VERTICES_T(v, G1, Graph1) + f[v] = graph_traits<Graph2>::null_vertex(); + { std::vector<invar1_value> invar1_array; BGL_FORALL_VERTICES_T(v, G1, Graph1) @@ -195,69 +200,130 @@ namespace boost { } private: + struct match_continuation { + enum {pos_G2_vertex_loop, pos_fi_adj_loop, pos_dfs_num} position; + typedef typename graph_traits<Graph2>::vertex_iterator vertex_iterator; + std::pair<vertex_iterator, vertex_iterator> G2_verts; + typedef typename graph_traits<Graph2>::adjacency_iterator adjacency_iterator; + std::pair<adjacency_iterator, adjacency_iterator> fi_adj; + edge_iter iter; + int dfs_num_k; + }; + bool match(edge_iter iter, int dfs_num_k) { + std::vector<match_continuation> k; + typedef typename graph_traits<Graph2>::vertex_iterator vertex_iterator; + std::pair<vertex_iterator, vertex_iterator> G2_verts(vertices(G2)); + typedef typename graph_traits<Graph2>::adjacency_iterator adjacency_iterator; + std::pair<adjacency_iterator, adjacency_iterator> fi_adj; + vertex1_t i, j; + + recur: if (iter != ordered_edges.end()) { - vertex1_t i = source(*iter, G1), j = target(*iter, G2); + i = source(*iter, G1); + j = target(*iter, G2); if (dfs_num[i] > dfs_num_k) { - vertex1_t kp1 = dfs_vertices[dfs_num_k + 1]; - BGL_FORALL_VERTICES_T(u, G2, Graph2) { - if (invariant1(kp1) == invariant2(u) && in_S[u] == false) { - f[kp1] = u; - in_S[u] = true; - num_edges_on_k = 0; - - if (match(iter, dfs_num_k + 1)) -#if 0 - // dwa 2003/7/11 -- this *HAS* to be a bug! - ; -#endif - return true; + G2_verts = vertices(G2); + while (G2_verts.first != G2_verts.second) { + { + vertex2_t u = *G2_verts.first; + vertex1_t kp1 = dfs_vertices[dfs_num_k + 1]; + if (invariant1(kp1) == invariant2(u) && in_S[u] == false) { + { + f[kp1] = u; + in_S[u] = true; + num_edges_on_k = 0; - in_S[u] = false; + match_continuation new_k; + new_k.position = match_continuation::pos_G2_vertex_loop; + new_k.G2_verts = G2_verts; + new_k.iter = iter; + new_k.dfs_num_k = dfs_num_k; + k.push_back(new_k); + ++dfs_num_k; + goto recur; + } + } } +G2_loop_k: ++G2_verts.first; } } else if (dfs_num[j] > dfs_num_k) { - vertex1_t k = dfs_vertices[dfs_num_k]; - num_edges_on_k -= - count_if(adjacent_vertices(f[k], G2), make_indirect_pmap(in_S)); - - for (int jj = 0; jj < dfs_num_k; ++jj) { - vertex1_t j = dfs_vertices[jj]; - num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[k]); + { + vertex1_t vk = dfs_vertices[dfs_num_k]; + num_edges_on_k -= + count_if(adjacent_vertices(f[vk], G2), make_indirect_pmap(in_S)); + + for (int jj = 0; jj < dfs_num_k; ++jj) { + vertex1_t j = dfs_vertices[jj]; + num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[vk]); + } } if (num_edges_on_k != 0) - return false; - BGL_FORALL_ADJ_T(f[i], v, G2, Graph2) - if (invariant2(v) == invariant1(j) && in_S[v] == false) { - f[j] = v; - in_S[v] = true; - num_edges_on_k = 1; - BOOST_USING_STD_MAX(); - int next_k = max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num_k, max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num[i], dfs_num[j])); - if (match(boost::next(iter), next_k)) - return true; - in_S[v] = false; + goto return_point_false; + fi_adj = adjacent_vertices(f[i], G2); + while (fi_adj.first != fi_adj.second) { + { + vertex2_t v = *fi_adj.first; + if (invariant2(v) == invariant1(j) && in_S[v] == false) { + f[j] = v; + in_S[v] = true; + num_edges_on_k = 1; + BOOST_USING_STD_MAX(); + int next_k = max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num_k, max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num[i], dfs_num[j])); + match_continuation new_k; + new_k.position = match_continuation::pos_fi_adj_loop; + new_k.fi_adj = fi_adj; + new_k.iter = iter; + new_k.dfs_num_k = dfs_num_k; + ++iter; + dfs_num_k = next_k; + k.push_back(new_k); + goto recur; + } } - - +fi_adj_loop_k:++fi_adj.first; + } } else { if (container_contains(adjacent_vertices(f[i], G2), f[j])) { ++num_edges_on_k; - if (match(boost::next(iter), dfs_num_k)) - return true; + match_continuation new_k; + new_k.position = match_continuation::pos_dfs_num; + k.push_back(new_k); + ++iter; + goto recur; } } } else - return true; - return false; - } + goto return_point_true; + goto return_point_false; + { + return_point_true: return true; + + return_point_false: + if (k.empty()) return false; + const match_continuation& this_k = k.back(); + switch (this_k.position) { + case match_continuation::pos_G2_vertex_loop: {G2_verts = this_k.G2_verts; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*G2_verts.first] = false; i = source(*iter, G1); j = target(*iter, G2); goto G2_loop_k;} + case match_continuation::pos_fi_adj_loop: {fi_adj = this_k.fi_adj; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*fi_adj.first] = false; i = source(*iter, G1); j = target(*iter, G2); goto fi_adj_loop_k;} + case match_continuation::pos_dfs_num: {k.pop_back(); goto return_point_false;} + default: { + BOOST_ASSERT(!"Bad position"); +#ifdef UNDER_CE + exit(-1); +#else + abort(); +#endif + } + } + } + } }; @@ -404,39 +470,68 @@ namespace boost { index_map1, index_map2 ); } + + template <typename G, typename Index> + struct make_degree_invariant { + const G& g; + const Index& index; + make_degree_invariant(const G& g, const Index& index): g(g), index(index) {} + typedef typename boost::graph_traits<G>::degree_size_type degree_size_type; + typedef shared_array_property_map<degree_size_type, Index> prop_map_type; + typedef degree_vertex_invariant<prop_map_type, G> result_type; + result_type operator()() const { + prop_map_type pm = make_shared_array_property_map(num_vertices(g), degree_size_type(), index); + compute_in_degree(g, pm); + return result_type(pm, g); + } + }; } // namespace detail - - // Named parameter interface - template <typename Graph1, typename Graph2, class P, class T, class R> - bool isomorphism(const Graph1& g1, - const Graph2& g2, - const bgl_named_params<P,T,R>& params) - { - typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; - typename std::vector<vertex2_t>::size_type n = num_vertices(g1); - std::vector<vertex2_t> f(n); - return detail::isomorphism_impl - (g1, g2, - choose_param(get_param(params, vertex_isomorphism_t()), - make_safe_iterator_property_map(f.begin(), f.size(), - choose_const_pmap(get_param(params, vertex_index1), - g1, vertex_index), vertex2_t())), - choose_const_pmap(get_param(params, vertex_index1), g1, vertex_index), - choose_const_pmap(get_param(params, vertex_index2), g2, vertex_index), - params - ); - } - - // All defaults interface - template <typename Graph1, typename Graph2> - bool isomorphism(const Graph1& g1, const Graph2& g2) - { - return isomorphism(g1, g2, - bgl_named_params<int, buffer_param_t>(0));// bogus named param + namespace graph { + namespace detail { + template <typename Graph1, typename Graph2> + struct isomorphism_impl { + typedef bool result_type; + template <typename ArgPack> + bool operator()(const Graph1& g1, const Graph2& g2, const ArgPack& arg_pack) const { + using namespace boost::graph::keywords; + typedef typename boost::detail::override_const_property_result<ArgPack, tag::vertex_index1_map, boost::vertex_index_t, Graph1>::type index1_map_type; + typedef typename boost::detail::override_const_property_result<ArgPack, tag::vertex_index2_map, boost::vertex_index_t, Graph2>::type index2_map_type; + index1_map_type index1_map = boost::detail::override_const_property(arg_pack, _vertex_index1_map, g1, boost::vertex_index); + index2_map_type index2_map = boost::detail::override_const_property(arg_pack, _vertex_index2_map, g2, boost::vertex_index); + typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; + typename std::vector<vertex2_t>::size_type n = (typename std::vector<vertex2_t>::size_type)num_vertices(g1); + std::vector<vertex2_t> f(n); + typename boost::parameter::lazy_binding< + ArgPack, + tag::vertex_invariant1, + boost::detail::make_degree_invariant<Graph1, index1_map_type> >::type + invariant1 = + arg_pack[_vertex_invariant1 || boost::detail::make_degree_invariant<Graph1, index1_map_type>(g1, index1_map)]; + typename boost::parameter::lazy_binding< + ArgPack, + tag::vertex_invariant2, + boost::detail::make_degree_invariant<Graph2, index2_map_type> >::type + invariant2 = + arg_pack[_vertex_invariant2 || boost::detail::make_degree_invariant<Graph2, index2_map_type>(g2, index2_map)]; + return boost::isomorphism + (g1, g2, + choose_param(arg_pack[_isomorphism_map | boost::param_not_found()], + make_shared_array_property_map(num_vertices(g1), vertex2_t(), index1_map)), + invariant1, + invariant2, + arg_pack[_vertex_max_invariant | (invariant2.max)()], + index1_map, + index2_map); + } + }; + } + BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(isomorphism, 2, 6) } + // Named parameter interface + BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(isomorphism, 2) // Verify that the given mapping iso_map from the vertices of g1 to the // vertices of g2 describes an isomorphism. diff --git a/boost/graph/johnson_all_pairs_shortest.hpp b/boost/graph/johnson_all_pairs_shortest.hpp index 32e2b5cdcd..b8da0fe19a 100644 --- a/boost/graph/johnson_all_pairs_shortest.hpp +++ b/boost/graph/johnson_all_pairs_shortest.hpp @@ -121,8 +121,6 @@ namespace boost { (g2, *u, pred, d, w_hat, id2, compare, combine, inf, zero,dvis); for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) { if (*u != s && *v != s) { - typename Traits1::vertex_descriptor u1, v1; - u1 = verts1[get(id2, *u)]; v1 = verts1[get(id2, *v)]; D[get(id2, *u)-1][get(id2, *v)-1] = combine(get(d, *v), (get(h, *v) - get(h, *u))); } } diff --git a/boost/graph/make_connected.hpp b/boost/graph/make_connected.hpp index de6c861ddd..a2f8b1ee48 100644 --- a/boost/graph/make_connected.hpp +++ b/boost/graph/make_connected.hpp @@ -9,7 +9,7 @@ #define __MAKE_CONNECTED_HPP__ #include <boost/config.hpp> -#include <boost/utility.hpp> //for next +#include <boost/next_prior.hpp> #include <boost/tuple/tuple.hpp> //for tie #include <boost/graph/connected_components.hpp> #include <boost/property_map/property_map.hpp> diff --git a/boost/graph/matrix_as_graph.hpp b/boost/graph/matrix_as_graph.hpp index b39d126a23..fb727940d7 100644 --- a/boost/graph/matrix_as_graph.hpp +++ b/boost/graph/matrix_as_graph.hpp @@ -14,7 +14,7 @@ #include <utility> #include <boost/config.hpp> #include <boost/operators.hpp> -#include <boost/int_iterator.hpp> +#include <boost/pending/detail/int_iterator.hpp> #include <boost/graph/graph_traits.hpp> namespace boost { diff --git a/boost/graph/max_cardinality_matching.hpp b/boost/graph/max_cardinality_matching.hpp index 043f701478..5516bebc47 100644 --- a/boost/graph/max_cardinality_matching.hpp +++ b/boost/graph/max_cardinality_matching.hpp @@ -16,7 +16,6 @@ #include <algorithm> // for std::sort and std::stable_sort #include <utility> // for std::pair #include <boost/property_map/property_map.hpp> -#include <boost/utility.hpp> // for boost::tie #include <boost/graph/graph_traits.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/depth_first_search.hpp> diff --git a/boost/graph/named_function_params.hpp b/boost/graph/named_function_params.hpp index c5e35fa54e..32dd580232 100644 --- a/boost/graph/named_function_params.hpp +++ b/boost/graph/named_function_params.hpp @@ -13,11 +13,12 @@ #include <functional> #include <vector> #include <boost/ref.hpp> +#include <boost/utility/result_of.hpp> +#include <boost/preprocessor.hpp> #include <boost/parameter/name.hpp> #include <boost/parameter/binding.hpp> -#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits.hpp> #include <boost/mpl/not.hpp> -#include <boost/type_traits/add_reference.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/property_map/property_map.hpp> @@ -111,15 +112,16 @@ namespace boost { BOOST_BGL_ONE_PARAM_REF(max_priority_queue, max_priority_queue) template <typename T, typename Tag, typename Base = no_property> - struct bgl_named_params : public Base + struct bgl_named_params { typedef bgl_named_params self; typedef Base next_type; typedef Tag tag_type; typedef T value_type; bgl_named_params(T v = T()) : m_value(v) { } - bgl_named_params(T v, const Base& b) : Base(b), m_value(v) { } + bgl_named_params(T v, const Base& b) : m_value(v), m_base(b) { } T m_value; + Base m_base; #define BOOST_BGL_ONE_PARAM_REF(name, key) \ template <typename PType> \ @@ -182,145 +184,147 @@ BOOST_BGL_DECLARE_NAMED_PARAMS //=========================================================================== // Functions for extracting parameters from bgl_named_params - template <class Tag1, class Tag2, class T1, class Base> - inline - typename property_value< bgl_named_params<T1,Tag1,Base>, Tag2>::type - get_param(const bgl_named_params<T1,Tag1,Base>& p, Tag2 tag2) - { - enum { match = detail::same_property<Tag1,Tag2>::value }; - typedef typename - property_value< bgl_named_params<T1,Tag1,Base>, Tag2>::type T2; - T2* t2 = 0; - typedef detail::property_value_dispatch<match> Dispatcher; - return Dispatcher::const_get_value(p, t2, tag2); - } + template <typename Tag, typename Args> + struct lookup_named_param {}; + template <typename T, typename Tag, typename Base> + struct lookup_named_param<Tag, bgl_named_params<T, Tag, Base> > { + typedef T type; + static const T& get(const bgl_named_params<T, Tag, Base>& p) { + return p.m_value; + } + }; - namespace detail { - // MSVC++ workaround - template <class Param> - struct choose_param_helper { - template <class Default> struct result { typedef Param type; }; - template <typename Default> - static const Param& apply(const Param& p, const Default&) { return p; } - }; - template <> - struct choose_param_helper<error_property_not_found> { - template <class Default> struct result { typedef Default type; }; - template <typename Default> - static const Default& apply(const error_property_not_found&, const Default& d) - { return d; } - }; - } // namespace detail + template <typename Tag1, typename T, typename Tag, typename Base> + struct lookup_named_param<Tag1, bgl_named_params<T, Tag, Base> > { + typedef typename lookup_named_param<Tag1, Base>::type type; + static const type& get(const bgl_named_params<T, Tag, Base>& p) { + return lookup_named_param<Tag1, Base>::get(p.m_base); + } + }; + + template <typename Tag, typename Args, typename Def> + struct lookup_named_param_def { + typedef Def type; + static const Def& get(const Args&, const Def& def) {return def;} + }; + + template <typename T, typename Tag, typename Base, typename Def> + struct lookup_named_param_def<Tag, bgl_named_params<T, Tag, Base>, Def> { + typedef T type; + static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def&) { + return p.m_value; + } + }; + + template <typename Tag1, typename T, typename Tag, typename Base, typename Def> + struct lookup_named_param_def<Tag1, bgl_named_params<T, Tag, Base>, Def> { + typedef typename lookup_named_param_def<Tag1, Base, Def>::type type; + static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def& def) { + return lookup_named_param_def<Tag1, Base, Def>::get(p.m_base, def); + } + }; + + struct param_not_found {}; + + template <typename Tag, typename Args> + struct get_param_type: + lookup_named_param_def<Tag, Args, param_not_found> {}; + + template <class Tag, typename Args> + inline + const typename lookup_named_param_def<Tag, Args, param_not_found>::type& + get_param(const Args& p, Tag) { + return lookup_named_param_def<Tag, Args, param_not_found>::get(p, param_not_found()); + } template <class P, class Default> - const typename detail::choose_param_helper<P>::template result<Default>::type& - choose_param(const P& param, const Default& d) { - return detail::choose_param_helper<P>::apply(param, d); + const P& choose_param(const P& param, const Default&) { + return param; + } + + template <class Default> + Default choose_param(const param_not_found&, const Default& d) { + return d; } template <typename T> inline bool is_default_param(const T&) { return false; } - inline bool is_default_param(const detail::error_property_not_found&) + inline bool is_default_param(const param_not_found&) { return true; } namespace detail { + template <typename T> + struct const_type_as_type {typedef typename T::const_type type;}; + } // namespace detail + - struct choose_parameter { - template <class P, class Graph, class Tag> - struct bind_ { - typedef const P& const_result_type; - typedef const P& result_type; - typedef P type; - }; - - template <class P, class Graph, class Tag> - static typename bind_<P, Graph, Tag>::const_result_type - const_apply(const P& p, const Graph&, Tag&) - { return p; } + // Use this function instead of choose_param() when you want + // to avoid requiring get(tag, g) when it is not used. + namespace detail { + template <typename GraphIsConst, typename Graph, typename Param, typename Tag> + struct choose_impl_result: + boost::mpl::eval_if< + boost::is_same<Param, param_not_found>, + boost::mpl::eval_if< + GraphIsConst, + detail::const_type_as_type<property_map<Graph, Tag> >, + property_map<Graph, Tag> >, + boost::mpl::identity<Param> > {}; + + // Parameters of f are (GraphIsConst, Graph, Param, Tag) + template <bool Found> struct choose_impl_helper; + + template <> struct choose_impl_helper<false> { + template <typename Param, typename Graph, typename PropertyTag> + static typename property_map<Graph, PropertyTag>::const_type + f(boost::mpl::true_, const Graph& g, const Param&, PropertyTag tag) { + return get(tag, g); + } - template <class P, class Graph, class Tag> - static typename bind_<P, Graph, Tag>::result_type - apply(const P& p, Graph&, Tag&) - { return p; } + template <typename Param, typename Graph, typename PropertyTag> + static typename property_map<Graph, PropertyTag>::type + f(boost::mpl::false_, Graph& g, const Param&, PropertyTag tag) { + return get(tag, g); + } }; - struct choose_default_param { - template <class P, class Graph, class Tag> - struct bind_ { - typedef typename property_map<Graph, Tag>::type - result_type; - typedef typename property_map<Graph, Tag>::const_type - const_result_type; - typedef typename property_map<Graph, Tag>::const_type - type; - }; - - template <class P, class Graph, class Tag> - static typename bind_<P, Graph, Tag>::const_result_type - const_apply(const P&, const Graph& g, Tag tag) { - return get(tag, g); - } - template <class P, class Graph, class Tag> - static typename bind_<P, Graph, Tag>::result_type - apply(const P&, Graph& g, Tag tag) { - return get(tag, g); + template <> struct choose_impl_helper<true> { + template <typename GraphIsConst, typename Param, typename Graph, typename PropertyTag> + static Param f(GraphIsConst, const Graph&, const Param& p, PropertyTag) { + return p; } }; + } - template <class Param> - struct choose_property_map { - typedef choose_parameter type; - }; - template <> - struct choose_property_map<detail::error_property_not_found> { - typedef choose_default_param type; - }; + template <typename Param, typename Graph, typename PropertyTag> + typename detail::choose_impl_result<boost::mpl::true_, Graph, Param, PropertyTag>::type + choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag) + { + return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value> + ::f(boost::mpl::true_(), g, p, tag); + } - template <class Param, class Graph, class Tag> - struct choose_pmap_helper { - typedef typename choose_property_map<Param>::type Selector; - typedef typename Selector:: template bind_<Param, Graph, Tag> Bind; - typedef Bind type; - typedef typename Bind::result_type result_type; - typedef typename Bind::const_result_type const_result_type; - typedef typename Bind::type result; - }; + template <typename Param, typename Graph, typename PropertyTag> + typename detail::choose_impl_result<boost::mpl::false_, Graph, Param, PropertyTag>::type + choose_pmap(const Param& p, Graph& g, PropertyTag tag) + { + return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value> + ::f(boost::mpl::false_(), g, p, tag); + } + + namespace detail { // used in the max-flow algorithms template <class Graph, class P, class T, class R> struct edge_capacity_value { typedef bgl_named_params<P, T, R> Params; - typedef typename property_value< Params, edge_capacity_t>::type Param; - typedef typename detail::choose_pmap_helper<Param, Graph, - edge_capacity_t>::result CapacityEdgeMap; + typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<Params, edge_capacity_t>::type, edge_capacity_t>::type CapacityEdgeMap; typedef typename property_traits<CapacityEdgeMap>::value_type type; }; - } // namespace detail - - - // Use this function instead of choose_param() when you want - // to avoid requiring get(tag, g) when it is not used. - template <typename Param, typename Graph, typename PropertyTag> - typename - detail::choose_pmap_helper<Param,Graph,PropertyTag>::const_result_type - choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag) - { - typedef typename - detail::choose_pmap_helper<Param,Graph,PropertyTag>::Selector Choice; - return Choice::const_apply(p, g, tag); - } - - template <typename Param, typename Graph, typename PropertyTag> - typename detail::choose_pmap_helper<Param,Graph,PropertyTag>::result_type - choose_pmap(const Param& p, Graph& g, PropertyTag tag) - { - typedef typename - detail::choose_pmap_helper<Param,Graph,PropertyTag>::Selector Choice; - return Choice::apply(p, g, tag); } // Declare all new tags @@ -353,7 +357,7 @@ BOOST_BGL_DECLARE_NAMED_PARAMS typedef convert_bgl_params_to_boost_parameter<typename T::next_type> rest_conv; typedef boost::parameter::aux::arg_list<tagged_arg_type, typename rest_conv::type> type; static type conv(const T& x) { - return type(tagged_arg_type(x.m_value), rest_conv::conv(x)); + return type(tagged_arg_type(x.m_value), rest_conv::conv(x.m_base)); } }; @@ -362,7 +366,7 @@ BOOST_BGL_DECLARE_NAMED_PARAMS typedef convert_bgl_params_to_boost_parameter<R> rest_conv; typedef typename rest_conv::type type; static type conv(const bgl_named_params<P, int, R>& x) { - return rest_conv::conv(x); + return rest_conv::conv(x.m_base); } }; @@ -375,7 +379,7 @@ BOOST_BGL_DECLARE_NAMED_PARAMS template <> struct convert_bgl_params_to_boost_parameter<boost::no_named_parameters> { typedef boost::parameter::aux::empty_arg_list type; - static type conv(const boost::no_property&) {return type();} + static type conv(const boost::no_named_parameters&) {return type();} }; struct bgl_parameter_not_found_type {}; @@ -460,6 +464,78 @@ BOOST_BGL_DECLARE_NAMED_PARAMS >()(g, ap[t | 0]); } + template <typename F> struct make_arg_pack_type; + template <> struct make_arg_pack_type<void()> {typedef boost::parameter::aux::empty_arg_list type;}; + template <typename K, typename A> + struct make_arg_pack_type<void(K, A)> { + typedef boost::parameter::aux::tagged_argument<K, A> type; + }; + +#define BOOST_GRAPH_OPENING_PART_OF_PAIR(z, i, n) boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, BOOST_PP_SUB(n, i)), BOOST_PP_CAT(Arg, BOOST_PP_SUB(n, i))>, +#define BOOST_GRAPH_MAKE_PAIR_PARAM(z, i, _) const boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, i), BOOST_PP_CAT(Arg, i)>& BOOST_PP_CAT(kw, i) + +#define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _) \ + template <BOOST_PP_ENUM_PARAMS(i, typename Keyword), BOOST_PP_ENUM_PARAMS(i, typename Arg)> \ + struct make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(i, Keyword), BOOST_PP_ENUM_PARAMS(i, Arg))> { \ + typedef \ + BOOST_PP_REPEAT(i, BOOST_GRAPH_OPENING_PART_OF_PAIR, BOOST_PP_DEC(i)) boost::parameter::aux::empty_arg_list BOOST_PP_REPEAT(i, > BOOST_PP_TUPLE_EAT(3), ~) \ + type; \ + }; + BOOST_PP_REPEAT_FROM_TO(2, 11, BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION, ~) +#undef BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION + +#define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(name, nfixed, nnamed_max) \ + /* Entry point for conversion from BGL-style named parameters */ \ + template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) typename ArgPack> \ + typename boost::result_of< \ + detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>(BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const ArgPack&) \ + >::type \ + BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) BOOST_PP_COMMA_IF(nfixed) const ArgPack& arg_pack) { \ + return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>()(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ + } \ + /* Individual functions taking Boost.Parameter-style keyword arguments */ \ + BOOST_PP_REPEAT(BOOST_PP_INC(nnamed_max), BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE, (name)(nfixed)) + +#define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE(z, nnamed, seq) \ + BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq)) + +#define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed) \ + template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Keyword) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Arg)> \ + typename boost::result_of< \ + detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)> \ + (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \ + const typename boost::detail::make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(nnamed, Keyword) BOOST_PP_COMMA_IF(nnamed) BOOST_PP_ENUM_PARAMS(nnamed, Arg))>::type&) \ + >::type \ + name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) \ + BOOST_PP_ENUM_TRAILING(nnamed, BOOST_GRAPH_MAKE_PAIR_PARAM, ~)) { \ + return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>() \ + (BOOST_PP_ENUM_PARAMS(nfixed, param), \ + (boost::parameter::aux::empty_arg_list() BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, kw))); \ + } + +#define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed) \ + template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) class P, class T, class R> \ + typename boost::result_of< \ + ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \ + (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \ + const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<P, T, R> >::type &) \ + >::type \ + name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) BOOST_PP_COMMA_IF(nfixed) const boost::bgl_named_params<P, T, R>& old_style_params) { \ + typedef boost::bgl_named_params<P, T, R> old_style_params_type; \ + BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_style_params_type, old_style_params) \ + return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ + } \ + \ + BOOST_PP_EXPR_IF(nfixed, template <) BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_EXPR_IF(nfixed, >) \ + BOOST_PP_EXPR_IF(nfixed, typename) boost::result_of< \ + ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \ + (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const boost::parameter::aux::empty_arg_list &) \ + >::type \ + name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)) { \ + BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(boost::no_named_parameters, boost::no_named_parameters()) \ + return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ + } + } namespace detail { @@ -609,6 +685,13 @@ BOOST_BGL_DECLARE_NAMED_PARAMS make_priority_queue_from_arg_pack_gen(KeyT defaultKey_) : defaultKey(defaultKey_) { } + template <class F> + struct result { + typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg1_type>::type>::type graph_type; + typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg2_type>::type>::type arg_pack_type; + typedef typename priority_queue_maker<graph_type, arg_pack_type, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type type; + }; + template <class Graph, class ArgPack> typename priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type operator()(const Graph& g, const ArgPack& ap) const { @@ -616,6 +699,25 @@ BOOST_BGL_DECLARE_NAMED_PARAMS } }; + template <typename G> + typename boost::graph_traits<G>::vertex_descriptor + get_null_vertex(const G&) {return boost::graph_traits<G>::null_vertex();} + + template <typename G> + typename boost::graph_traits<G>::vertex_descriptor + get_default_starting_vertex(const G& g) { + std::pair<typename boost::graph_traits<G>::vertex_iterator, typename boost::graph_traits<G>::vertex_iterator> iters = vertices(g); + return (iters.first == iters.second) ? boost::graph_traits<G>::null_vertex() : *iters.first; + } + + template <typename G> + struct get_default_starting_vertex_t { + typedef typename boost::graph_traits<G>::vertex_descriptor result_type; + const G& g; + get_default_starting_vertex_t(const G& g): g(g) {} + result_type operator()() const {return get_default_starting_vertex(g);} + }; + } // namespace detail } // namespace boost diff --git a/boost/graph/named_graph.hpp b/boost/graph/named_graph.hpp index 38f4ca0e1e..f49c09707d 100644 --- a/boost/graph/named_graph.hpp +++ b/boost/graph/named_graph.hpp @@ -156,51 +156,6 @@ struct internal_vertex_constructor<property<Tag, T, Base> > #endif /******************************************************************* - * Named graph-specific metafunctions * - *******************************************************************/ -namespace detail { - /** @internal - * Extracts the type of a bundled vertex property from a vertex - * property. The primary template matches when we have hit the end - * of the @c property<> list. - */ - template<typename VertexProperty> - struct extract_bundled_vertex - { - typedef VertexProperty type; - }; - - /** @internal - * Recursively extract the bundled vertex property from a vertex - * property. - */ - template<typename Tag, typename T, typename Base> - struct extract_bundled_vertex<property<Tag, T, Base> > - : extract_bundled_vertex<Base> - { }; - - /** - * We have found the bundled vertex property type, marked with - * vertex_bundle_t. - */ - template<typename T, typename Base> - struct extract_bundled_vertex<property<vertex_bundle_t, T, Base> > - { - typedef T type; - }; - - /** - * Translate @c no_property into @c error_property_not_found when we - * have failed to extract a bundled vertex property type. - */ - template<> - struct extract_bundled_vertex<no_property> - { - typedef boost::detail::error_property_not_found type; - }; -} - -/******************************************************************* * Named graph mixin * *******************************************************************/ @@ -228,7 +183,7 @@ public: typedef typename internal_vertex_name<VertexProperty>::type extract_name_type; /// The type of the "bundled" property, from which the name can be /// extracted. - typedef typename detail::extract_bundled_vertex<VertexProperty>::type + typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type bundled_vertex_property_type; /// The type of the function object that generates vertex properties @@ -477,7 +432,7 @@ struct maybe_named_graph<Graph, Vertex, VertexProperty, void> { /// The type of the "bundled" property, from which the name can be /// extracted. - typedef typename detail::extract_bundled_vertex<VertexProperty>::type + typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type bundled_vertex_property_type; /// Notify the named_graph that we have added the given vertex. This diff --git a/boost/graph/neighbor_bfs.hpp b/boost/graph/neighbor_bfs.hpp index 4585f2e298..4830dcc4ed 100644 --- a/boost/graph/neighbor_bfs.hpp +++ b/boost/graph/neighbor_bfs.hpp @@ -250,13 +250,13 @@ namespace boost { }; template <> - struct neighbor_bfs_dispatch<detail::error_property_not_found> { + struct neighbor_bfs_dispatch<param_not_found> { template <class VertexListGraph, class P, class T, class R> static void apply (VertexListGraph& g, typename graph_traits<VertexListGraph>::vertex_descriptor s, const bgl_named_params<P, T, R>& params, - detail::error_property_not_found) + param_not_found) { std::vector<default_color_type> color_vec(num_vertices(g)); null_visitor null_vis; @@ -288,8 +288,7 @@ namespace boost { // graph is not really const since we may write to property maps // of the graph. VertexListGraph& ng = const_cast<VertexListGraph&>(g); - typedef typename property_value< bgl_named_params<P,T,R>, - vertex_color_t>::type C; + typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C; detail::neighbor_bfs_dispatch<C>::apply(ng, s, params, get_param(params, vertex_color)); } diff --git a/boost/graph/planar_canonical_ordering.hpp b/boost/graph/planar_canonical_ordering.hpp index 6cb7bdb824..86203aaf38 100644 --- a/boost/graph/planar_canonical_ordering.hpp +++ b/boost/graph/planar_canonical_ordering.hpp @@ -12,7 +12,7 @@ #include <vector> #include <list> #include <boost/config.hpp> -#include <boost/utility.hpp> //for next and prior +#include <boost/next_prior.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/property_map/property_map.hpp> diff --git a/boost/graph/planar_detail/boyer_myrvold_impl.hpp b/boost/graph/planar_detail/boyer_myrvold_impl.hpp index 71607fcbc2..41ba2bc575 100644 --- a/boost/graph/planar_detail/boyer_myrvold_impl.hpp +++ b/boost/graph/planar_detail/boyer_myrvold_impl.hpp @@ -10,7 +10,7 @@ #include <vector> #include <list> -#include <boost/utility.hpp> //for boost::next +#include <boost/next_prior.hpp> #include <boost/config.hpp> //for std::min macros #include <boost/shared_ptr.hpp> #include <boost/tuple/tuple.hpp> diff --git a/boost/graph/planar_face_traversal.hpp b/boost/graph/planar_face_traversal.hpp index bcd565528d..6befa43bac 100644 --- a/boost/graph/planar_face_traversal.hpp +++ b/boost/graph/planar_face_traversal.hpp @@ -10,8 +10,11 @@ #define __PLANAR_FACE_TRAVERSAL_HPP__ #include <vector> -#include <boost/utility.hpp> //for next and prior +#include <set> +#include <map> +#include <boost/next_prior.hpp> #include <boost/graph/graph_traits.hpp> +#include <boost/graph/properties.hpp> namespace boost diff --git a/boost/graph/properties.hpp b/boost/graph/properties.hpp index bc498bbf9c..6b5ade974a 100644 --- a/boost/graph/properties.hpp +++ b/boost/graph/properties.hpp @@ -68,26 +68,20 @@ namespace boost { struct vertex_property_tag { }; struct edge_property_tag { }; -#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION // See examples/edge_property.cpp for how to use this. #define BOOST_INSTALL_PROPERTY(KIND, NAME) \ template <> struct property_kind<KIND##_##NAME##_t> { \ typedef KIND##_property_tag type; \ } -#else -#define BOOST_INSTALL_PROPERTY(KIND, NAME) \ - template <> struct property_kind<KIND##_##NAME##_t> { \ - typedef KIND##_property_tag type; \ - } -#endif #define BOOST_DEF_PROPERTY(KIND, NAME) \ enum KIND##_##NAME##_t { KIND##_##NAME }; \ BOOST_INSTALL_PROPERTY(KIND, NAME) - BOOST_DEF_PROPERTY(vertex, all); - BOOST_DEF_PROPERTY(edge, all); - BOOST_DEF_PROPERTY(graph, all); + // These three are defined in boost/pending/property.hpp + BOOST_INSTALL_PROPERTY(vertex, all); + BOOST_INSTALL_PROPERTY(edge, all); + BOOST_INSTALL_PROPERTY(graph, all); BOOST_DEF_PROPERTY(vertex, index); BOOST_DEF_PROPERTY(vertex, index1); BOOST_DEF_PROPERTY(vertex, index2); @@ -128,10 +122,10 @@ namespace boost { BOOST_DEF_PROPERTY(graph, visitor); // These tags are used for property bundles - // BOOST_DEF_PROPERTY(graph, bundle); -- needed in graph_traits.hpp, so enum is defined there + // These three are defined in boost/pending/property.hpp BOOST_INSTALL_PROPERTY(graph, bundle); - BOOST_DEF_PROPERTY(vertex, bundle); - BOOST_DEF_PROPERTY(edge, bundle); + BOOST_INSTALL_PROPERTY(vertex, bundle); + BOOST_INSTALL_PROPERTY(edge, bundle); // These tags are used to denote the owners and local descriptors // for the vertices and edges of a distributed graph. @@ -148,6 +142,25 @@ namespace boost { namespace detail { + template <typename G, typename Tag> + struct property_kind_from_graph: property_kind<Tag> {}; + +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES + template <typename G, typename R, typename T> + struct property_kind_from_graph<G, R T::*> { + typedef typename boost::mpl::if_< + boost::is_same<T, typename vertex_bundle_type<G>::type>, + vertex_property_tag, + typename boost::mpl::if_< + boost::is_same<T, typename edge_bundle_type<G>::type>, + edge_property_tag, + typename boost::mpl::if_< + boost::is_same<T, typename graph_bundle_type<G>::type>, + graph_property_tag, + void>::type>::type>::type type; + }; +#endif + struct dummy_edge_property_selector { template <class Graph, class Property, class Tag> struct bind_ { @@ -192,70 +205,32 @@ namespace boost { }; template <class Graph, class PropertyTag> - struct edge_property_map { - typedef typename edge_property_type<Graph>::type Property; - typedef typename graph_tag_or_void<Graph>::type graph_tag; - typedef typename edge_property_selector<graph_tag>::type Selector; - typedef typename Selector::template bind_<Graph,Property,PropertyTag> - Bind; - typedef typename Bind::type type; - typedef typename Bind::const_type const_type; - }; + struct edge_property_map + : edge_property_selector< + typename graph_tag_or_void<Graph>::type + >::type::template bind_< + Graph, + typename edge_property_type<Graph>::type, + PropertyTag> + {}; template <class Graph, class PropertyTag> - class vertex_property_map { - public: - typedef typename vertex_property_type<Graph>::type Property; - typedef typename graph_tag_or_void<Graph>::type graph_tag; - typedef typename vertex_property_selector<graph_tag>::type Selector; - typedef typename Selector::template bind_<Graph,Property,PropertyTag> - Bind; - public: - typedef typename Bind::type type; - typedef typename Bind::const_type const_type; - }; - - // This selects the kind of property map, whether is maps from - // edges or from vertices. - // - // It is overly complicated because it's a workaround for - // partial specialization. - struct choose_vertex_property_map { - template <class Graph, class Property> - struct bind_ { - typedef vertex_property_map<Graph, Property> type; - }; - }; - struct choose_edge_property_map { - template <class Graph, class Property> - struct bind_ { - typedef edge_property_map<Graph, Property> type; - }; - }; - template <class Kind> - struct property_map_kind_selector { - // VC++ gets confused if this isn't defined, even though - // this never gets used. - typedef choose_vertex_property_map type; - }; - template <> struct property_map_kind_selector<vertex_property_tag> { - typedef choose_vertex_property_map type; - }; - template <> struct property_map_kind_selector<edge_property_tag> { - typedef choose_edge_property_map type; - }; + struct vertex_property_map + : vertex_property_selector< + typename graph_tag_or_void<Graph>::type + >::type::template bind_< + Graph, + typename vertex_property_type<Graph>::type, + PropertyTag> + {}; } // namespace detail template <class Graph, class Property> - struct property_map { - // private: - typedef typename property_kind<Property>::type Kind; - typedef typename detail::property_map_kind_selector<Kind>::type Selector; - typedef typename Selector::template bind_<Graph, Property> Bind; - typedef typename Bind::type Map; - public: - typedef typename Map::type type; - typedef typename Map::const_type const_type; - }; + struct property_map: + mpl::if_< + is_same<typename detail::property_kind_from_graph<Graph, Property>::type, edge_property_tag>, + detail::edge_property_map<Graph, Property>, + detail::vertex_property_map<Graph, Property> >::type + {}; // shortcut for accessing the value type of the property map template <class Graph, class Property> @@ -273,16 +248,8 @@ namespace boost { >::type type; }; - template <class Graph> - class vertex_property { - public: - typedef typename Graph::vertex_property_type type; - }; - template <class Graph> - class edge_property { - public: - typedef typename Graph::edge_property_type type; - }; + template <class Graph> class vertex_property: vertex_property_type<Graph> {}; + template <class Graph> class edge_property: edge_property_type<Graph> {}; template <typename Graph> class degree_property_map @@ -383,99 +350,6 @@ namespace boost { # define BOOST_GRAPH_NO_BUNDLED_PROPERTIES #endif -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES - template<typename Graph, typename Descriptor, typename Bundle, typename T> - struct bundle_property_map - : put_get_helper<T&, bundle_property_map<Graph, Descriptor, Bundle, T> > - { - typedef Descriptor key_type; - typedef typename remove_const<T>::type value_type; - typedef T& reference; - typedef lvalue_property_map_tag category; - - bundle_property_map() { } - bundle_property_map(Graph* g_, T Bundle::* pm_) : g(g_), pm(pm_) {} - - reference operator[](key_type k) const { return (*g)[k].*pm; } - private: - Graph* g; - T Bundle::* pm; - }; - - namespace detail { - template<typename VertexBundle, typename EdgeBundle, typename Bundle> - struct is_vertex_bundle - : mpl::and_<is_convertible<VertexBundle*, Bundle*>, - mpl::and_<mpl::not_<is_void<VertexBundle> >, - mpl::not_<is_same<VertexBundle, no_property> > > > - { }; - } - - // Specialize the property map template to generate bundled property maps. - template <typename Graph, typename T, typename Bundle> - struct property_map<Graph, T Bundle::*> - { - private: - typedef graph_traits<Graph> traits; - typedef typename Graph::vertex_bundled vertex_bundled; - typedef typename Graph::edge_bundled edge_bundled; - typedef typename mpl::if_c<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value), - typename traits::vertex_descriptor, - typename traits::edge_descriptor>::type - descriptor; - typedef typename mpl::if_c<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value), - vertex_bundled, - edge_bundled>::type - actual_bundle; - - public: - typedef bundle_property_map<Graph, descriptor, actual_bundle, T> type; - typedef bundle_property_map<const Graph, descriptor, actual_bundle, const T> - const_type; - }; -#endif - -// These metafunctions help implement the process of determining the vertex -// and edge properties of a graph. -namespace graph_detail { - template<typename Retag> - struct retagged_property { - typedef typename Retag::type type; - }; - - // Search the normalized PropList (as returned by retagged<>::type) for - // the given bundle. Return the type error if no such bundle can be found. - template <typename PropList, typename Bundle> - struct retagged_bundle { - typedef typename property_value<PropList, Bundle>::type Value; - typedef typename mpl::if_< - is_same<Value, detail::error_property_not_found>, no_bundle, Value - >::type type; - }; - - template<typename Prop, typename Bundle> - class normal_property { - // Normalize the property into a property list. - typedef detail::retag_property_list<Bundle, Prop> List; - public: - // Extract the normalized property and bundle types. - typedef typename retagged_property<List>::type property; - typedef typename retagged_bundle<property, Bundle>::type bundle; - }; - - template<typename Prop> - struct graph_prop : normal_property<Prop, graph_bundle_t> - { }; - - template<typename Prop> - struct vertex_prop : normal_property<Prop, vertex_bundle_t> - { }; - - template<typename Prop> - struct edge_prop : normal_property<Prop, edge_bundle_t> - { }; -} // namespace graph_detail - // NOTE: These functions are declared, but never defined since they need to // be overloaded by graph implementations. However, we need them to be // declared for the functions below. @@ -498,17 +372,11 @@ get_property(Graph& g) { template<typename Graph> inline typename graph_property<Graph, graph_bundle_t>::type const& -get_property(Graph const& g) { +get_property(const Graph& g) { return get_property(g, graph_bundle); } #endif } // namespace boost -#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) -// Stay out of the way of the concept checking class -# undef Graph -# undef RandomAccessIterator -#endif - -#endif /* BOOST_GRAPH_PROPERTIES_HPPA */ +#endif /* BOOST_GRAPH_PROPERTIES_HPP */ diff --git a/boost/graph/property_maps/null_property_map.hpp b/boost/graph/property_maps/null_property_map.hpp index f6273481b0..09ff55e348 100644 --- a/boost/graph/property_maps/null_property_map.hpp +++ b/boost/graph/property_maps/null_property_map.hpp @@ -29,7 +29,7 @@ namespace boost // The null_property_map<K,V> only has a put() function. template <typename K, typename V> - void put(null_property_map<K,V>& pm, const K& key, const V& value) + void put(null_property_map<K,V>& /*pm*/, const K& /*key*/, const V& /*value*/) { } // A helper function for intantiating null property maps. diff --git a/boost/graph/reverse_graph.hpp b/boost/graph/reverse_graph.hpp index 48c4e0576e..96fc32d3ae 100644 --- a/boost/graph/reverse_graph.hpp +++ b/boost/graph/reverse_graph.hpp @@ -105,6 +105,7 @@ class reverse_graph { typedef graph_traits<BidirectionalGraph> Traits; public: typedef BidirectionalGraph base_type; + typedef GraphRef base_ref_type; // Constructor reverse_graph(GraphRef g) : m_g(g) {} @@ -358,47 +359,38 @@ namespace detail { } }; - struct reverse_graph_vertex_property_selector { - template <class ReverseGraph, class Property, class Tag> - struct bind_ { - typedef typename ReverseGraph::base_type Graph; - typedef property_map<Graph, Tag> PMap; - typedef typename PMap::type type; - typedef typename PMap::const_type const_type; - }; - }; - - struct reverse_graph_edge_property_selector { - template <class ReverseGraph, class Property, class Tag> - struct bind_ { - typedef typename ReverseGraph::base_type Graph; - typedef property_map<Graph, Tag> PMap; - typedef reverse_graph_edge_property_map<typename PMap::type> type; - typedef reverse_graph_edge_property_map<typename PMap::const_type> const_type; - }; - }; - } // namespace detail -template <> -struct vertex_property_selector<reverse_graph_tag> { - typedef detail::reverse_graph_vertex_property_selector type; +template <class BidirGraph, class GRef, class Property> +struct property_map<reverse_graph<BidirGraph, GRef>, Property> { + typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop; + typedef typename property_map<BidirGraph, Property>::type orig_type; + typedef typename property_map<BidirGraph, Property>::const_type orig_const_type; + typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_type>, orig_type>::type type; + typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type; }; -template <> -struct edge_property_selector<reverse_graph_tag> { - typedef detail::reverse_graph_edge_property_selector type; +template <class BidirGraph, class GRef, class Property> +struct property_map<const reverse_graph<BidirGraph, GRef>, Property> { + typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop; + typedef typename property_map<BidirGraph, Property>::const_type orig_const_type; + typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type; + typedef const_type type; }; template <class BidirGraph, class GRef, class Property> -typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type +typename disable_if< + is_same<Property, edge_underlying_t>, + typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type>::type get(Property p, reverse_graph<BidirGraph,GRef>& g) { return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type(get(p, g.m_g)); } template <class BidirGraph, class GRef, class Property> -typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type +typename disable_if< + is_same<Property, edge_underlying_t>, + typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type>::type get(Property p, const reverse_graph<BidirGraph,GRef>& g) { const BidirGraph& gref = g.m_g; // in case GRef is non-const @@ -406,9 +398,11 @@ get(Property p, const reverse_graph<BidirGraph,GRef>& g) } template <class BidirectionalGraph, class GRef, class Property, class Key> -typename property_traits< - typename property_map<BidirectionalGraph, Property>::const_type ->::value_type +typename disable_if< + is_same<Property, edge_underlying_t>, + typename property_traits< + typename property_map<reverse_graph<BidirectionalGraph, GRef>, Property>::const_type + >::value_type>::type get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k) { return get(get(p, g), k); @@ -459,19 +453,40 @@ struct property_map<reverse_graph<Graph, GRef>, edge_underlying_t> { typedef detail::underlying_edge_desc_map_type<ed> const_type; }; -template <class Graph, class GRef> -detail::underlying_edge_desc_map_type<typename graph_traits<Graph>::edge_descriptor> +template <typename T> struct is_reverse_graph: boost::mpl::false_ {}; +template <typename G, typename R> struct is_reverse_graph<reverse_graph<G, R> >: boost::mpl::true_ {}; + +template <class G> +typename enable_if<is_reverse_graph<G>, + detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type get(edge_underlying_t, - const reverse_graph<Graph,GRef>& g) + G& g) { - return detail::underlying_edge_desc_map_type<typename graph_traits<Graph>::edge_descriptor>(); + return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>(); } -template <class Graph, class GRef> -typename graph_traits<Graph>::edge_descriptor +template <class G> +typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type +get(edge_underlying_t, + G& g, + const typename graph_traits<G>::edge_descriptor& k) +{ + return k.underlying_descx; +} + +template <class G> +typename enable_if<is_reverse_graph<G>, detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type +get(edge_underlying_t, + const G& g) +{ + return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>(); +} + +template <class G> +typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type get(edge_underlying_t, - const reverse_graph<Graph,GRef>& g, - const typename graph_traits<reverse_graph<Graph, GRef> >::edge_descriptor& k) + const G& g, + const typename graph_traits<G>::edge_descriptor& k) { return k.underlying_descx; } diff --git a/boost/graph/stanford_graph.hpp b/boost/graph/stanford_graph.hpp index 0bb798c0f3..89f5e34b29 100644 --- a/boost/graph/stanford_graph.hpp +++ b/boost/graph/stanford_graph.hpp @@ -318,13 +318,15 @@ namespace boost { class sgb_vertex_util_map : public boost::put_get_helper<Ref, sgb_vertex_util_map<Tag, Ref> > { + Tag tag; public: + explicit sgb_vertex_util_map(Tag tag = Tag()): tag(tag) {} typedef boost::lvalue_property_map_tag category; typedef typename Tag::type value_type; typedef Vertex* key_type; typedef Ref reference; reference operator[](Vertex* v) const { - return get_util_field(v, Tag()); + return get_util_field(v, tag); } }; @@ -333,13 +335,15 @@ namespace boost { class sgb_edge_util_map : public boost::put_get_helper<Ref, sgb_edge_util_map<Tag, Ref> > { + Tag tag; public: + explicit sgb_edge_util_map(Tag tag = Tag()): tag(tag) {} typedef boost::lvalue_property_map_tag category; typedef typename Tag::type value_type; typedef Vertex* key_type; typedef Ref reference; reference operator[](const sgb_edge& e) const { - return get_util_field(e._arc, Tag()); + return get_util_field(e._arc, tag); } }; diff --git a/boost/graph/stoer_wagner_min_cut.hpp b/boost/graph/stoer_wagner_min_cut.hpp index 814eae0ce8..060f51b4a6 100644 --- a/boost/graph/stoer_wagner_min_cut.hpp +++ b/boost/graph/stoer_wagner_min_cut.hpp @@ -20,7 +20,7 @@ #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/property_map/property_map.hpp> #include <boost/tuple/tuple.hpp> -#include <boost/typeof/typeof.hpp> +#include <boost/utility/result_of.hpp> namespace boost { @@ -218,7 +218,9 @@ namespace boost { typedef boost::bgl_named_params<P, T, R> params_type; BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) - BOOST_AUTO(pq, (boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> >(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)))(g, arg_pack))); + typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type; + gen_type gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0))); + typename boost::result_of<gen_type(const UndirectedGraph&, const arg_pack_type&)>::type pq = gen(g, arg_pack); return boost::detail::stoer_wagner_min_cut(g, weights, diff --git a/boost/graph/strong_components.hpp b/boost/graph/strong_components.hpp index ba5d45907a..61345bdcb8 100644 --- a/boost/graph/strong_components.hpp +++ b/boost/graph/strong_components.hpp @@ -131,7 +131,7 @@ namespace boost { template <> - struct strong_comp_dispatch2<detail::error_property_not_found> { + struct strong_comp_dispatch2<param_not_found> { template <class Graph, class ComponentMap, class RootMap, class P, class T, class R> inline static typename property_traits<ComponentMap>::value_type @@ -139,7 +139,7 @@ namespace boost { ComponentMap comp, RootMap r_map, const bgl_named_params<P, T, R>& params, - detail::error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::vertices_size_type size_type; size_type n = num_vertices(g) > 0 ? num_vertices(g) : 1; @@ -179,7 +179,7 @@ namespace boost { } }; template <> - struct strong_comp_dispatch1<detail::error_property_not_found> { + struct strong_comp_dispatch1<param_not_found> { template <class Graph, class ComponentMap, class P, class T, class R> @@ -187,7 +187,7 @@ namespace boost { apply(const Graph& g, ComponentMap comp, const bgl_named_params<P, T, R>& params, - detail::error_property_not_found) + param_not_found) { typedef typename graph_traits<Graph>::vertex_descriptor Vertex; typename std::vector<Vertex>::size_type diff --git a/boost/graph/subgraph.hpp b/boost/graph/subgraph.hpp index b98c390267..22706bc617 100644 --- a/boost/graph/subgraph.hpp +++ b/boost/graph/subgraph.hpp @@ -24,7 +24,9 @@ #include <boost/static_assert.hpp> #include <boost/assert.hpp> -#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits.hpp> +#include <boost/mpl/if.hpp> +#include <boost/mpl/or.hpp> namespace boost { @@ -103,13 +105,11 @@ public: typedef typename Traits::in_edge_iterator in_edge_iterator; - typedef typename Graph::edge_property_type edge_property_type; - typedef typename Graph::vertex_property_type vertex_property_type; - typedef typename Graph::vertex_bundled vertex_bundled; - typedef typename Graph::edge_bundled edge_bundled; + typedef typename edge_property_type<Graph>::type edge_property_type; + typedef typename vertex_property_type<Graph>::type vertex_property_type; typedef subgraph_tag graph_tag; typedef Graph graph_type; - typedef typename Graph::graph_property_type graph_property_type; + typedef typename graph_property_type<Graph>::type graph_property_type; // Create the main graph, the root of the subgraph tree subgraph() @@ -131,15 +131,29 @@ public: // copy constructor subgraph(const subgraph& x) - : m_graph(x.m_graph), m_parent(x.m_parent), m_edge_counter(x.m_edge_counter) + : m_parent(x.m_parent), m_edge_counter(x.m_edge_counter) , m_global_vertex(x.m_global_vertex), m_global_edge(x.m_global_edge) { - // Do a deep copy (recursive). - for(typename ChildrenList::const_iterator i = x.m_children.begin(); - i != x.m_children.end(); ++i) + if(x.is_root()) { - m_children.push_back(new subgraph<Graph>( **i )); + m_graph = x.m_graph; } + // Do a deep copy (recursive). + // Only the root graph is copied, the subgraphs contain + // only references to the global vertices they own. + typename subgraph<Graph>::children_iterator i,i_end; + boost::tie(i,i_end) = x.children(); + for(; i != i_end; ++i) + { + subgraph<Graph> child = this->create_subgraph(); + child = *i; + vertex_iterator vi,vi_end; + boost::tie(vi,vi_end) = vertices(*i); + for (;vi!=vi_end;++vi) + { + add_vertex(*vi,child); + } + } } @@ -334,9 +348,6 @@ public: // Probably shouldn't be public.... } }; -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES -// TODO: I don't think these are required since the default metafunction -// returns Graph::vertex_bundled. template <typename Graph> struct vertex_bundle_type<subgraph<Graph> > : vertex_bundle_type<Graph> @@ -346,7 +357,11 @@ template<typename Graph> struct edge_bundle_type<subgraph<Graph> > : edge_bundle_type<Graph> { }; -#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES + +template<typename Graph> +struct graph_bundle_type<subgraph<Graph> > + : graph_bundle_type<Graph> +{ }; //=========================================================================== // Functions special to the Subgraph Class @@ -764,7 +779,10 @@ class subgraph_global_property_map { typedef property_traits<PropertyMap> Traits; public: - typedef typename Traits::category category; + typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>, + readable_property_map_tag, + typename Traits::category>::type + category; typedef typename Traits::value_type value_type; typedef typename Traits::key_type key_type; typedef typename Traits::reference reference; @@ -772,18 +790,19 @@ public: subgraph_global_property_map() { } - subgraph_global_property_map(GraphPtr g) - : m_g(g) + subgraph_global_property_map(GraphPtr g, Tag tag) + : m_g(g), m_tag(tag) { } reference operator[](key_type e) const { - PropertyMap pmap = get(Tag(), m_g->root().m_graph); + PropertyMap pmap = get(m_tag, m_g->root().m_graph); return m_g->is_root() ? pmap[e] : pmap[m_g->local_to_global(e)]; } GraphPtr m_g; + Tag m_tag; }; /** @@ -799,7 +818,10 @@ class subgraph_local_property_map { typedef property_traits<PropertyMap> Traits; public: - typedef typename Traits::category category; + typedef typename mpl::if_<is_const<typename remove_pointer<GraphPtr>::type>, + readable_property_map_tag, + typename Traits::category>::type + category; typedef typename Traits::value_type value_type; typedef typename Traits::key_type key_type; typedef typename Traits::reference reference; @@ -810,17 +832,18 @@ public: subgraph_local_property_map() { } - subgraph_local_property_map(GraphPtr g) - : m_g(g) + subgraph_local_property_map(GraphPtr g, Tag tag) + : m_g(g), m_tag(tag) { } reference operator[](key_type e) const { // Get property map on the underlying graph. - PropertyMap pmap = get(Tag(), m_g->m_graph); + PropertyMap pmap = get(m_tag, m_g->m_graph); return pmap[e]; } GraphPtr m_g; + Tag m_tag; }; namespace detail { @@ -935,139 +958,37 @@ struct edge_property_selector<subgraph_tag> { typedef detail::subgraph_property_generator type; }; -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES -/** @internal - * This property map implements local or global bundled property access on - * an underlying graph. The LocalGlobal template template parameter must be - * one of the local_property or global_property templates. - */ -template < - typename Graph, typename Descriptor, typename Bundle, typename T, - template <typename> class LocalGlobal> -struct subgraph_lg_bundle_property_map - : put_get_helper< - T&, - subgraph_lg_bundle_property_map<Graph, Descriptor, Bundle, T, LocalGlobal> - > -{ -private: - typedef LocalGlobal<Descriptor> Wrap; -public: - typedef Descriptor key_type; - typedef typename remove_const<T>::type value_type; - typedef T& reference; - typedef lvalue_property_map_tag category; - - subgraph_lg_bundle_property_map() - { } - - subgraph_lg_bundle_property_map(Graph* g, T Bundle::* p) - : m_g(g), m_prop(p) - { } - - reference operator[](key_type k) const - { return (*m_g)[Wrap(k)].*m_prop; } - -private: - Graph* m_g; - T Bundle::* m_prop; -}; - -// Specialize the property map template to generate bundled property maps. -// NOTE: I'm cheating (actually double-dipping) with the local/global subgraph -// property templates. I'm not using them store descriptors, just specialize -// the property map template for specific lookups. -namespace graph_detail { - // Help decoding some of the types required for property map definitions. - template <typename Graph, typename T, typename Bundle> - struct bundled_subgraph_pmap_helper { - typedef subgraph<Graph> Subgraph; - typedef graph_traits<Subgraph> Traits; - typedef typename Subgraph::vertex_bundled VertBundled; - typedef typename Subgraph::edge_bundled EdgeBundled; - - // Deduce the descriptor from the template params - typedef typename mpl::if_< - detail::is_vertex_bundle<VertBundled, EdgeBundled, Bundle>, - typename Traits::vertex_descriptor, typename Traits::edge_descriptor - >::type Desc; - - // Deduce the bundled property type - typedef typename mpl::if_< - detail::is_vertex_bundle<VertBundled, EdgeBundled, Bundle>, - VertBundled, EdgeBundled - >::type Prop; - }; -} // namespace graph_detail - -template <typename Graph, typename T, typename Bundle> -struct property_map<subgraph<Graph>, local_property<T Bundle::*> > - : graph_detail::bundled_subgraph_pmap_helper<Graph, T, Bundle> -{ -private: - typedef graph_detail::bundled_subgraph_pmap_helper<Graph, T, Bundle> Base; - typedef typename Base::Subgraph Subgraph; - typedef typename Base::Desc Desc; - typedef typename Base::Prop Prop; -public: - typedef subgraph_lg_bundle_property_map< - Subgraph, Desc, Prop, T, local_property - > type; - typedef subgraph_lg_bundle_property_map< - Subgraph const, Desc, Prop, T const, local_property - > const_type; -}; - -template <typename Graph, typename T, typename Bundle> -struct property_map<subgraph<Graph>, global_property<T Bundle::*> > - : graph_detail::bundled_subgraph_pmap_helper<Graph, T, Bundle> -{ -private: - typedef graph_detail::bundled_subgraph_pmap_helper<Graph, T, Bundle> Base; - typedef typename Base::Subgraph Subgraph; - typedef typename Base::Desc Desc; - typedef typename Base::Prop Prop; -public: - typedef subgraph_lg_bundle_property_map< - Subgraph, Desc, Prop, T, global_property - > type; - typedef subgraph_lg_bundle_property_map< - Subgraph const, Desc, Prop, T const, global_property - > const_type; -}; -#endif - // ================================================== // get(p, g), get(p, g, k), and put(p, g, k, v) // ================================================== template <typename G, typename Property> typename property_map<subgraph<G>, Property>::type -get(Property, subgraph<G>& g) { +get(Property p, subgraph<G>& g) { typedef typename property_map< subgraph<G>, Property>::type PMap; - return PMap(&g); + return PMap(&g, p); } template <typename G, typename Property> typename property_map<subgraph<G>, Property>::const_type -get(Property, const subgraph<G>& g) { +get(Property p, const subgraph<G>& g) { typedef typename property_map< subgraph<G>, Property>::const_type PMap; - return PMap(&g); + return PMap(&g, p); } template <typename G, typename Property, typename Key> typename property_traits< typename property_map<subgraph<G>, Property>::const_type >::value_type -get(Property, const subgraph<G>& g, const Key& k) { +get(Property p, const subgraph<G>& g, const Key& k) { typedef typename property_map< subgraph<G>, Property>::const_type PMap; - PMap pmap(&g); + PMap pmap(&g, p); return pmap[k]; } template <typename G, typename Property, typename Key, typename Value> -void put(Property, subgraph<G>& g, const Key& k, const Value& val) { +void put(Property p, subgraph<G>& g, const Key& k, const Value& val) { typedef typename property_map< subgraph<G>, Property>::type PMap; - PMap pmap(&g); + PMap pmap(&g, p); pmap[k] = val; } @@ -1077,20 +998,20 @@ void put(Property, subgraph<G>& g, const Key& k, const Value& val) { // ================================================== template <typename G, typename Property> typename property_map<subgraph<G>, global_property<Property> >::type -get(global_property<Property>, subgraph<G>& g) { +get(global_property<Property> p, subgraph<G>& g) { typedef typename property_map< subgraph<G>, global_property<Property> >::type Map; - return Map(&g); + return Map(&g, p.value); } template <typename G, typename Property> typename property_map<subgraph<G>, global_property<Property> >::const_type -get(global_property<Property>, const subgraph<G>& g) { +get(global_property<Property> p, const subgraph<G>& g) { typedef typename property_map< subgraph<G>, global_property<Property> >::const_type Map; - return Map(&g); + return Map(&g, p.value); } // ================================================== @@ -1099,112 +1020,22 @@ get(global_property<Property>, const subgraph<G>& g) { // ================================================== template <typename G, typename Property> typename property_map<subgraph<G>, local_property<Property> >::type -get(local_property<Property>, subgraph<G>& g) { +get(local_property<Property> p, subgraph<G>& g) { typedef typename property_map< subgraph<G>, local_property<Property> >::type Map; - return Map(&g); + return Map(&g, p.value); } template <typename G, typename Property> typename property_map<subgraph<G>, local_property<Property> >::const_type -get(local_property<Property>, const subgraph<G>& g) { +get(local_property<Property> p, const subgraph<G>& g) { typedef typename property_map< subgraph<G>, local_property<Property> >::const_type Map; - return Map(&g); -} - -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES -// ================================================== -// get(bundle(p), g) -// ================================================== - -template<typename G, typename T, typename Bundle> -inline typename property_map<subgraph<G>, T Bundle::*>::type -get(T Bundle::* p, subgraph<G>& g) { - typedef typename property_map<subgraph<G>, T Bundle::*>::type Map; - return Map(&g, p); -} - -template<typename G, typename T, typename Bundle> -inline typename property_map<subgraph<G>, T Bundle::*>::const_type -get(T Bundle::* p, subgraph<G> const& g) { - typedef typename property_map<subgraph<G>, T Bundle::*>::const_type Map; - return Map(&g, p); -} - -template <typename Graph, typename Type, typename Bundle, typename Key> -inline Type get(Type Bundle::* p, subgraph<Graph> const& g, Key const& k) -{ return get(get(p, g), k); } - -template <typename Graph, typename Type, typename Bundle, typename Key, - typename Value> -inline void put(Type Bundle::* p, Graph& g, Key const& k, Value const& v) -{ put(get(p, g), k, v); } - -// ========================================================= -// Local bundled, get - -template<typename G, typename T, typename Bundle> -inline typename property_map< - subgraph<G>, local_property<T Bundle::*> ->::type -get(local_property<T Bundle::*> p, subgraph<G>& g) { - typedef typename property_map< - subgraph<G>, local_property<T Bundle::*> - >::type Map; - return Map(&g, p.value); -} - -template<typename G, typename T, typename Bundle> -inline typename property_map< - subgraph<G>, local_property<T Bundle::*> ->::const_type -get(local_property<T Bundle::*> p, subgraph<G> const& g) { - typedef typename property_map< - subgraph<G>, local_property<T Bundle::*> - >::const_type Map; - return Map(&g, p.value); -} - -template <typename Graph, typename Type, typename Bundle, typename Key> -inline Type get(local_property<Type Bundle::*> p, subgraph<Graph> const& g, - Key const& k) -{ return get(get(p, g), k); } - -// ========================================================= -// Global bundled, get - -template<typename G, typename T, typename Bundle> -inline typename property_map< - subgraph<G>, global_property<T Bundle::*> ->::type -get(global_property<T Bundle::*> p, subgraph<G>& g) { - typedef typename property_map< - subgraph<G>, global_property<T Bundle::*> - >::type Map; - return Map(&g, p.value); -} - -template<typename G, typename T, typename Bundle> -inline typename property_map< - subgraph<G>, global_property<T Bundle::*> ->::const_type -get(global_property<T Bundle::*> p, subgraph<G> const& g) { - typedef typename property_map< - subgraph<G>, global_property<T Bundle::*> - >::const_type Map; return Map(&g, p.value); } -template <typename Graph, typename Type, typename Bundle, typename Key> -inline Type get(global_property<Type Bundle::*> p, subgraph<Graph> const& g, - Key const& k) -{ return get(get(p, g), k); } - -#endif - template <typename G, typename Tag> inline typename graph_property<G, Tag>::type& get_property(subgraph<G>& g, Tag tag) { diff --git a/boost/graph/two_graphs_common_spanning_trees.hpp b/boost/graph/two_graphs_common_spanning_trees.hpp new file mode 100644 index 0000000000..86d57ece07 --- /dev/null +++ b/boost/graph/two_graphs_common_spanning_trees.hpp @@ -0,0 +1,870 @@ +// Copyright (C) 2012, Michele Caini. +// 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) + +// Two Graphs Common Spanning Trees Algorithm +// Based on academic article of Mint, Read and Tarjan +// Efficient Algorithm for Common Spanning Tree Problem +// Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347 + + +#ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP +#define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP + + +#include <boost/config.hpp> + +#include <boost/bimap.hpp> +#include <boost/type_traits.hpp> +#include <boost/concept/requires.hpp> +#include <boost/graph/graph_traits.hpp> +#include <boost/graph/undirected_dfs.hpp> +#include <boost/graph/connected_components.hpp> +#include <boost/graph/filtered_graph.hpp> +#include <vector> +#include <stack> +#include <map> + + +namespace boost +{ + + +namespace detail { + + + template + < + typename TreeMap, + typename PredMap, + typename DistMap, + typename LowMap, + typename Buffer + > + struct bridges_visitor: public default_dfs_visitor + { + bridges_visitor( + TreeMap tree, + PredMap pred, + DistMap dist, + LowMap low, + Buffer& buffer + ): mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer) + { mNum = -1; } + + template <typename Vertex, typename Graph> + void initialize_vertex(const Vertex& u, const Graph& g) + { + put(mPred, u, u); + put(mDist, u, -1); + } + + template <typename Vertex, typename Graph> + void discover_vertex(const Vertex& u, const Graph& g) + { + put(mDist, u, ++mNum); + put(mLow, u, get(mDist, u)); + } + + template <typename Edge, typename Graph> + void tree_edge(const Edge& e, const Graph& g) + { + put(mPred, target(e, g), source(e, g)); + put(mTree, target(e, g), e); + } + + template <typename Edge, typename Graph> + void back_edge(const Edge& e, const Graph& g) + { + put(mLow, source(e, g), + (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g)))); + } + + template <typename Vertex, typename Graph> + void finish_vertex(const Vertex& u, const Graph& g) + { + Vertex parent = get(mPred, u); + if(get(mLow, u) > get(mDist, parent)) + mBuffer.push(get(mTree, u)); + put(mLow, parent, + (std::min)(get(mLow, parent), get(mLow, u))); + } + + TreeMap mTree; + PredMap mPred; + DistMap mDist; + LowMap mLow; + Buffer& mBuffer; + int mNum; + }; + + + template <typename Buffer> + struct cycle_finder: public base_visitor< cycle_finder<Buffer> > + { + typedef on_back_edge event_filter; + cycle_finder(): mBuffer(0) { } + cycle_finder(Buffer* buffer) + : mBuffer(buffer) { } + template <typename Edge, typename Graph> + void operator()(const Edge& e, const Graph& g) + { + if(mBuffer) + mBuffer->push(e); + } + Buffer* mBuffer; + }; + + + template <typename DeletedMap> + struct deleted_edge_status + { + deleted_edge_status() { } + deleted_edge_status(DeletedMap map): mMap(map) { } + template <typename Edge> + bool operator()(const Edge& e) const + { return (!get(mMap, e)); } + DeletedMap mMap; + }; + + + template <typename InLMap> + struct inL_edge_status + { + inL_edge_status() { } + inL_edge_status(InLMap map): mMap(map) { } + template <typename Edge> + bool operator()(const Edge& e) const + { return get(mMap, e); } + InLMap mMap; + }; + + + template < + typename Graph, + typename Func, + typename Seq, + typename Map + > + void rec_two_graphs_common_spanning_trees + ( + const Graph& iG, + bimap< + bimaps::set_of<int>, + bimaps::set_of< typename graph_traits<Graph>::edge_descriptor > + > iG_bimap, + Map aiG_inL, + Map diG, + const Graph& vG, + bimap< + bimaps::set_of<int>, + bimaps::set_of< typename graph_traits<Graph>::edge_descriptor > + > vG_bimap, + Map avG_inL, + Map dvG, + Func func, + Seq inL + ) + { + typedef graph_traits<Graph> GraphTraits; + + typedef typename GraphTraits::vertex_descriptor vertex_descriptor; + typedef typename GraphTraits::edge_descriptor edge_descriptor; + + typedef typename Seq::size_type seq_size_type; + + int edges = num_vertices(iG) - 1; +// +// [ Michele Caini ] +// +// Using the condition (edges != 0) leads to the accidental submission of +// sub-graphs ((V-1+1)-fake-tree, named here fat-tree). +// Remove this condition is a workaround for the problem of fat-trees. +// Please do not add that condition, even if it improves performance. +// +// Here is proposed the previous guard (that was wrong): +// for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i) +// + { + for(seq_size_type i = 0; i < inL.size(); ++i) + if(inL[i]) + --edges; + + if(edges < 0) + return; + } + + bool is_tree = (edges == 0); + if(is_tree) { + func(inL); + } else { + std::map<vertex_descriptor, default_color_type> vertex_color; + std::map<edge_descriptor, default_color_type> edge_color; + + std::stack<edge_descriptor> iG_buf, vG_buf; + bool found = false; + + seq_size_type m; + for(seq_size_type j = 0; j < inL.size() && !found; ++j) { + if(!inL[j] + && !get(diG, iG_bimap.left.at(j)) + && !get(dvG, vG_bimap.left.at(j))) + { + put(aiG_inL, iG_bimap.left.at(j), true); + put(avG_inL, vG_bimap.left.at(j), true); + + undirected_dfs( + make_filtered_graph(iG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(aiG_inL)), + make_dfs_visitor( + detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs( + make_filtered_graph(vG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(avG_inL)), + make_dfs_visitor( + detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + if(iG_buf.empty() && vG_buf.empty()) { + inL[j] = true; + found = true; + m = j; + } else { + while(!iG_buf.empty()) iG_buf.pop(); + while(!vG_buf.empty()) vG_buf.pop(); + put(aiG_inL, iG_bimap.left.at(j), false); + put(avG_inL, vG_bimap.left.at(j), false); + } + } + } + + if(found) { + + std::stack<edge_descriptor> iG_buf_copy, vG_buf_copy; + for(seq_size_type j = 0; j < inL.size(); ++j) { + if(!inL[j] + && !get(diG, iG_bimap.left.at(j)) + && !get(dvG, vG_bimap.left.at(j))) + { + + put(aiG_inL, iG_bimap.left.at(j), true); + put(avG_inL, vG_bimap.left.at(j), true); + + undirected_dfs( + make_filtered_graph(iG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(aiG_inL)), + make_dfs_visitor( + detail::cycle_finder< + std::stack<edge_descriptor> > (&iG_buf)), + associative_property_map< std::map< + vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs( + make_filtered_graph(vG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(avG_inL)), + make_dfs_visitor( + detail::cycle_finder< + std::stack<edge_descriptor> > (&vG_buf)), + associative_property_map< std::map< + vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + if(!iG_buf.empty() || !vG_buf.empty()) { + while(!iG_buf.empty()) iG_buf.pop(); + while(!vG_buf.empty()) vG_buf.pop(); + put(diG, iG_bimap.left.at(j), true); + put(dvG, vG_bimap.left.at(j), true); + iG_buf_copy.push(iG_bimap.left.at(j)); + vG_buf_copy.push(vG_bimap.left.at(j)); + } + + put(aiG_inL, iG_bimap.left.at(j), false); + put(avG_inL, vG_bimap.left.at(j), false); + } + } + + // REC + detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, Map> + (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); + + while(!iG_buf_copy.empty()) { + put(diG, iG_buf_copy.top(), false); + put(dvG, vG_bimap.left.at( + iG_bimap.right.at(iG_buf_copy.top())), false); + iG_buf_copy.pop(); + } + while(!vG_buf_copy.empty()) { + put(dvG, vG_buf_copy.top(), false); + put(diG, iG_bimap.left.at( + vG_bimap.right.at(vG_buf_copy.top())), false); + vG_buf_copy.pop(); + } + + inL[m] = false; + put(aiG_inL, iG_bimap.left.at(m), false); + put(avG_inL, vG_bimap.left.at(m), false); + + put(diG, iG_bimap.left.at(m), true); + put(dvG, vG_bimap.left.at(m), true); + + std::map<vertex_descriptor, edge_descriptor> tree_map; + std::map<vertex_descriptor, vertex_descriptor> pred_map; + std::map<vertex_descriptor, int> dist_map, low_map; + + detail::bridges_visitor< + associative_property_map< + std::map<vertex_descriptor, edge_descriptor> + >, + associative_property_map< + std::map<vertex_descriptor, vertex_descriptor> + >, + associative_property_map< std::map<vertex_descriptor, int> >, + associative_property_map< std::map<vertex_descriptor, int> >, + std::stack<edge_descriptor> + > + iG_vis( + associative_property_map< + std::map< vertex_descriptor, edge_descriptor> >(tree_map), + associative_property_map< + std::map< vertex_descriptor, vertex_descriptor> >(pred_map), + associative_property_map< + std::map< vertex_descriptor, int> >(dist_map), + associative_property_map< + std::map< vertex_descriptor, int> >(low_map), + iG_buf + ), + vG_vis( + associative_property_map< + std::map< vertex_descriptor, edge_descriptor> >(tree_map), + associative_property_map< + std::map< vertex_descriptor, vertex_descriptor> >(pred_map), + associative_property_map< + std::map< vertex_descriptor, int> >(dist_map), + associative_property_map< + std::map< vertex_descriptor, int> >(low_map), + vG_buf + ); + + undirected_dfs(make_filtered_graph(iG, + detail::deleted_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(diG)), + iG_vis, + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs(make_filtered_graph(vG, + detail::deleted_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(dvG)), + vG_vis, + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + found = false; + std::stack<edge_descriptor> iG_buf_tmp, vG_buf_tmp; + while(!iG_buf.empty() && !found) { + if(!inL[iG_bimap.right.at(iG_buf.top())]) { + put(aiG_inL, iG_buf.top(), true); + put(avG_inL, vG_bimap.left.at( + iG_bimap.right.at(iG_buf.top())), true); + + undirected_dfs( + make_filtered_graph(iG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(aiG_inL)), + make_dfs_visitor( + detail::cycle_finder< + std::stack<edge_descriptor> > (&iG_buf_tmp)), + associative_property_map< + std::map< + vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs( + make_filtered_graph(vG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(avG_inL)), + make_dfs_visitor( + detail::cycle_finder< + std::stack<edge_descriptor> > (&vG_buf_tmp)), + associative_property_map< + std::map< + vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { + found = true; + } else { + while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); + while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); + iG_buf_copy.push(iG_buf.top()); + } + + put(aiG_inL, iG_buf.top(), false); + put(avG_inL, vG_bimap.left.at( + iG_bimap.right.at(iG_buf.top())), false); + } + iG_buf.pop(); + } + while(!vG_buf.empty() && !found) { + if(!inL[vG_bimap.right.at(vG_buf.top())]) { + put(avG_inL, vG_buf.top(), true); + put(aiG_inL, iG_bimap.left.at( + vG_bimap.right.at(vG_buf.top())), true); + + undirected_dfs( + make_filtered_graph(iG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(aiG_inL)), + make_dfs_visitor( + detail::cycle_finder< + std::stack<edge_descriptor> > (&iG_buf_tmp)), + associative_property_map< + std::map< + vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs( + make_filtered_graph(vG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(avG_inL)), + make_dfs_visitor( + detail::cycle_finder< + std::stack<edge_descriptor> > (&vG_buf_tmp)), + associative_property_map< + std::map< + vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { + found = true; + } else { + while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); + while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); + vG_buf_copy.push(vG_buf.top()); + } + + put(avG_inL, vG_buf.top(), false); + put(aiG_inL, iG_bimap.left.at( + vG_bimap.right.at(vG_buf.top())), false); + } + vG_buf.pop(); + } + + if(!found) { + + while(!iG_buf_copy.empty()) { + inL[iG_bimap.right.at(iG_buf_copy.top())] = true; + put(aiG_inL, iG_buf_copy.top(), true); + put(avG_inL, vG_bimap.left.at( + iG_bimap.right.at(iG_buf_copy.top())), true); + iG_buf.push(iG_buf_copy.top()); + iG_buf_copy.pop(); + } + while(!vG_buf_copy.empty()) { + inL[vG_bimap.right.at(vG_buf_copy.top())] = true; + put(avG_inL, vG_buf_copy.top(), true); + put(aiG_inL, iG_bimap.left.at( + vG_bimap.right.at(vG_buf_copy.top())), true); + vG_buf.push(vG_buf_copy.top()); + vG_buf_copy.pop(); + } + + // REC + detail::rec_two_graphs_common_spanning_trees< + Graph, Func, Seq, Map> + (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); + + while(!iG_buf.empty()) { + inL[iG_bimap.right.at(iG_buf.top())] = false; + put(aiG_inL, iG_buf.top(), false); + put(avG_inL, vG_bimap.left.at( + iG_bimap.right.at(iG_buf.top())), false); + iG_buf.pop(); + } + while(!vG_buf.empty()) { + inL[vG_bimap.right.at(vG_buf.top())] = false; + put(avG_inL, vG_buf.top(), false); + put(aiG_inL, iG_bimap.left.at( + vG_bimap.right.at(vG_buf.top())), false); + vG_buf.pop(); + } + + } + + put(diG, iG_bimap.left.at(m), false); + put(dvG, vG_bimap.left.at(m), false); + + } + } + } + +} // namespace detail + + + +template <typename Coll, typename Seq> +struct tree_collector +{ + +public: + BOOST_CONCEPT_ASSERT((BackInsertionSequence<Coll>)); + BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>)); + BOOST_CONCEPT_ASSERT((CopyConstructible<Seq>)); + + typedef typename Coll::value_type coll_value_type; + typedef typename Seq::value_type seq_value_type; + + BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value)); + BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); + + tree_collector(Coll& seqs): mSeqs(seqs) { } + + inline void operator()(Seq seq) + { mSeqs.push_back(seq); } + +private: + Coll& mSeqs; + +}; + + + +template < + typename Graph, + typename Order, + typename Func, + typename Seq +> +BOOST_CONCEPT_REQUIRES( + ((RandomAccessContainer<Order>)) + ((IncidenceGraphConcept<Graph>)) + ((UnaryFunction<Func, void, Seq>)) + ((Mutable_RandomAccessContainer<Seq>)) + ((VertexAndEdgeListGraphConcept<Graph>)), + (void) +) +two_graphs_common_spanning_trees + ( + const Graph& iG, + Order iG_map, + const Graph& vG, + Order vG_map, + Func func, + Seq inL + ) +{ + typedef graph_traits<Graph> GraphTraits; + + typedef typename GraphTraits::directed_category directed_category; + typedef typename GraphTraits::vertex_descriptor vertex_descriptor; + typedef typename GraphTraits::edge_descriptor edge_descriptor; + + typedef typename GraphTraits::edges_size_type edges_size_type; + typedef typename GraphTraits::edge_iterator edge_iterator; + + typedef typename Seq::const_iterator seq_const_iterator; + typedef typename Seq::difference_type seq_diff_type; + typedef typename Seq::value_type seq_value_type; + typedef typename Seq::size_type seq_size_type; + typedef typename Seq::iterator seq_iterator; + + typedef typename Order::const_iterator order_const_iterator; + typedef typename Order::difference_type order_diff_type; + typedef typename Order::value_type order_value_type; + typedef typename Order::size_type order_size_type; + typedef typename Order::iterator order_iterator; + + BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value)); + BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>)); + + BOOST_CONCEPT_ASSERT((Convertible<seq_size_type, edges_size_type>)); + BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); + + BOOST_STATIC_ASSERT((is_same<directed_category, undirected_tag>::value)); + + if(num_vertices(iG) != num_vertices(vG)) + return; + + if(inL.size() != num_edges(iG) + || inL.size() != num_edges(vG)) + return; + + if(iG_map.size() != num_edges(iG) + || vG_map.size() != num_edges(vG)) + return; + + typedef bimaps::bimap< + bimaps::set_of< int >, + bimaps::set_of< order_value_type > + > bimap_type; + typedef typename bimap_type::value_type bimap_value; + + bimap_type iG_bimap, vG_bimap; + for(order_size_type i = 0; i < iG_map.size(); ++i) + iG_bimap.insert(bimap_value(i, iG_map[i])); + for(order_size_type i = 0; i < vG_map.size(); ++i) + vG_bimap.insert(bimap_value(i, vG_map[i])); + + edge_iterator current, last; + boost::tuples::tie(current, last) = edges(iG); + for(; current != last; ++current) + if(iG_bimap.right.find(*current) == iG_bimap.right.end()) + return; + boost::tuples::tie(current, last) = edges(vG); + for(; current != last; ++current) + if(vG_bimap.right.find(*current) == vG_bimap.right.end()) + return; + + std::stack<edge_descriptor> iG_buf, vG_buf; + + std::map<vertex_descriptor, edge_descriptor> tree_map; + std::map<vertex_descriptor, vertex_descriptor> pred_map; + std::map<vertex_descriptor, int> dist_map, low_map; + + detail::bridges_visitor< + associative_property_map< + std::map<vertex_descriptor, edge_descriptor> + >, + associative_property_map< + std::map<vertex_descriptor, vertex_descriptor> + >, + associative_property_map< std::map<vertex_descriptor, int> >, + associative_property_map< std::map<vertex_descriptor, int> >, + std::stack<edge_descriptor> + > + iG_vis( + associative_property_map< + std::map< vertex_descriptor, edge_descriptor> >(tree_map), + associative_property_map< + std::map< vertex_descriptor, vertex_descriptor> >(pred_map), + associative_property_map<std::map< vertex_descriptor, int> >(dist_map), + associative_property_map<std::map< vertex_descriptor, int> >(low_map), + iG_buf + ), + vG_vis( + associative_property_map< + std::map< vertex_descriptor, edge_descriptor> >(tree_map), + associative_property_map< + std::map< vertex_descriptor, vertex_descriptor> >(pred_map), + associative_property_map<std::map< vertex_descriptor, int> >(dist_map), + associative_property_map<std::map< vertex_descriptor, int> >(low_map), + vG_buf + ); + + std::map<vertex_descriptor, default_color_type> vertex_color; + std::map<edge_descriptor, default_color_type> edge_color; + + undirected_dfs(iG, iG_vis, + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs(vG, vG_vis, + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + while(!iG_buf.empty()) { + inL[iG_bimap.right.at(iG_buf.top())] = true; + iG_buf.pop(); + } + while(!vG_buf.empty()) { + inL[vG_bimap.right.at(vG_buf.top())] = true; + vG_buf.pop(); + } + + std::map<edge_descriptor, bool> iG_inL, vG_inL; + associative_property_map< std::map<edge_descriptor, bool> > + aiG_inL(iG_inL), avG_inL(vG_inL); + + for(seq_size_type i = 0; i < inL.size(); ++i) + { + if(inL[i]) { + put(aiG_inL, iG_bimap.left.at(i), true); + put(avG_inL, vG_bimap.left.at(i), true); + } else { + put(aiG_inL, iG_bimap.left.at(i), false); + put(avG_inL, vG_bimap.left.at(i), false); + } + } + + undirected_dfs( + make_filtered_graph(iG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(aiG_inL)), + make_dfs_visitor( + detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs( + make_filtered_graph(vG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(avG_inL)), + make_dfs_visitor( + detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + if(iG_buf.empty() && vG_buf.empty()) { + + std::map<edge_descriptor, bool> iG_deleted, vG_deleted; + associative_property_map< std::map<edge_descriptor, bool> > diG(iG_deleted); + associative_property_map< std::map<edge_descriptor, bool> > dvG(vG_deleted); + + boost::tuples::tie(current, last) = edges(iG); + for(; current != last; ++current) + put(diG, *current, false); + boost::tuples::tie(current, last) = edges(vG); + for(; current != last; ++current) + put(dvG, *current, false); + + for(seq_size_type j = 0; j < inL.size(); ++j) { + if(!inL[j]) { + put(aiG_inL, iG_bimap.left.at(j), true); + put(avG_inL, vG_bimap.left.at(j), true); + + undirected_dfs( + make_filtered_graph(iG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(aiG_inL)), + make_dfs_visitor( + detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + undirected_dfs( + make_filtered_graph(vG, + detail::inL_edge_status< associative_property_map< + std::map<edge_descriptor, bool> > >(avG_inL)), + make_dfs_visitor( + detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), + associative_property_map< + std::map<vertex_descriptor, default_color_type> >(vertex_color), + associative_property_map< + std::map<edge_descriptor, default_color_type> >(edge_color) + ); + + if(!iG_buf.empty() || !vG_buf.empty()) { + while(!iG_buf.empty()) iG_buf.pop(); + while(!vG_buf.empty()) vG_buf.pop(); + put(diG, iG_bimap.left.at(j), true); + put(dvG, vG_bimap.left.at(j), true); + } + + put(aiG_inL, iG_bimap.left.at(j), false); + put(avG_inL, vG_bimap.left.at(j), false); + } + } + + int cc = 0; + + std::map<vertex_descriptor, int> com_map; + cc += connected_components( + make_filtered_graph(iG, + detail::deleted_edge_status<associative_property_map< + std::map<edge_descriptor, bool> > >(diG)), + associative_property_map<std::map<vertex_descriptor, int> >(com_map) + ); + cc += connected_components( + make_filtered_graph(vG, + detail::deleted_edge_status<associative_property_map< + std::map<edge_descriptor, bool> > >(dvG)), + associative_property_map< std::map<vertex_descriptor, int> >(com_map) + ); + + if(cc != 2) + return; + + // REC + detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, + associative_property_map< std::map<edge_descriptor, bool> > > + (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); + + } + +} + + +template < + typename Graph, + typename Func, + typename Seq +> +BOOST_CONCEPT_REQUIRES( + ((IncidenceGraphConcept<Graph>)) + ((EdgeListGraphConcept<Graph>)), + (void) +) +two_graphs_common_spanning_trees + ( + const Graph& iG, + const Graph& vG, + Func func, + Seq inL + ) +{ + typedef graph_traits<Graph> GraphTraits; + + typedef typename GraphTraits::edge_descriptor edge_descriptor; + typedef typename GraphTraits::edges_size_type edges_size_type; + typedef typename GraphTraits::edge_iterator edge_iterator; + + std::vector<edge_descriptor> iGO, vGO; + edge_iterator curr, last; + + boost::tuples::tie(curr, last) = edges(iG); + for(; curr != last; ++curr) + iGO.push_back(*curr); + + boost::tuples::tie(curr, last) = edges(vG); + for(; curr != last; ++curr) + vGO.push_back(*curr); + + two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL); +} + + +} // namespace boost + + +#endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP diff --git a/boost/graph/undirected_dfs.hpp b/boost/graph/undirected_dfs.hpp index df31d22b2b..a3e1c038fd 100644 --- a/boost/graph/undirected_dfs.hpp +++ b/boost/graph/undirected_dfs.hpp @@ -188,7 +188,7 @@ namespace boost { }; template <> - struct udfs_dispatch<detail::error_property_not_found> { + struct udfs_dispatch<param_not_found> { template <typename Graph, typename Vertex, typename DFSVisitor, typename EdgeColorMap, typename P, typename T, typename R> @@ -196,7 +196,7 @@ namespace boost { apply(const Graph& g, DFSVisitor vis, Vertex start_vertex, const bgl_named_params<P, T, R>& params, EdgeColorMap edge_color, - detail::error_property_not_found) + param_not_found) { std::vector<default_color_type> color_vec(num_vertices(g)); default_color_type c = white_color; // avoid warning about un-init @@ -219,8 +219,7 @@ namespace boost { undirected_dfs(const Graph& g, const bgl_named_params<P, T, R>& params) { - typedef typename property_value< bgl_named_params<P, T, R>, - vertex_color_t>::type C; + typedef typename get_param_type< vertex_color_t, bgl_named_params<P, T, R> >::type C; detail::udfs_dispatch<C>::apply (g, choose_param(get_param(params, graph_visitor), diff --git a/boost/graph/undirected_graph.hpp b/boost/graph/undirected_graph.hpp index 3178b42afd..adcc86e515 100644 --- a/boost/graph/undirected_graph.hpp +++ b/boost/graph/undirected_graph.hpp @@ -7,7 +7,6 @@ #ifndef BOOST_GRAPH_UNDIRECTED_GRAPH_HPP #define BOOST_GRAPH_UNDIRECTED_GRAPH_HPP -#include <boost/utility.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> @@ -38,14 +37,12 @@ template < class undirected_graph { public: - typedef typename graph_detail::graph_prop<GraphProp>::property graph_property_type; - typedef typename graph_detail::graph_prop<GraphProp>::bundle graph_bundled; - - typedef typename graph_detail::vertex_prop<VertexProp>::property vertex_property_type; - typedef typename graph_detail::vertex_prop<VertexProp>::bundle vertex_bundled; - - typedef typename graph_detail::edge_prop<EdgeProp>::property edge_property_type; - typedef typename graph_detail::edge_prop<EdgeProp>::bundle edge_bundled; + typedef GraphProp graph_property_type; + typedef VertexProp vertex_property_type; + typedef EdgeProp edge_property_type; + typedef typename lookup_one_property<GraphProp, graph_bundle_t>::type graph_bundled; + typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled; + typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled; private: // Embed indices into the vertex type. @@ -530,36 +527,8 @@ remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) { return remove_in_edge_if(v, pred, g.impl()); } -// Helper code for working with property maps -namespace detail { - struct undirected_graph_vertex_property_selector { - template <class UndirectedGraph, class Property, class Tag> - struct bind_ { - typedef typename UndirectedGraph::graph_type Graph; - typedef property_map<Graph, Tag> PropertyMap; - typedef typename PropertyMap::type type; - typedef typename PropertyMap::const_type const_type; - }; - }; - - struct undirected_graph_edge_property_selector { - template <class UndirectedGraph, class Property, class Tag> - struct bind_ { - typedef typename UndirectedGraph::graph_type Graph; - typedef property_map<Graph, Tag> PropertyMap; - typedef typename PropertyMap::type type; - typedef typename PropertyMap::const_type const_type; - }; - }; -} // namespace detail - -template <> -struct vertex_property_selector<undirected_graph_tag> -{ typedef detail::undirected_graph_vertex_property_selector type; }; - -template <> -struct edge_property_selector<undirected_graph_tag> -{ typedef detail::undirected_graph_edge_property_selector type; }; +template <UNDIRECTED_GRAPH_PARAMS, typename Property> +struct property_map<UNDIRECTED_GRAPH, Property>: property_map<typename UNDIRECTED_GRAPH::graph_type, Property> {}; // PropertyGraph concepts template <UNDIRECTED_GRAPH_PARAMS, typename Property> @@ -599,36 +568,6 @@ template <UNDIRECTED_GRAPH_PARAMS, class Property, class Value> inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v) { return set_property(g.impl(), p, v); } -#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES -template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle> -inline typename property_map<UNDIRECTED_GRAPH, Type Bundle::*>::type -get(Type Bundle::* p, UNDIRECTED_GRAPH& g) { - typedef typename property_map< - UNDIRECTED_GRAPH, Type Bundle::* - >::type return_type; - return return_type(&g, p); -} - -template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle> -inline typename property_map<UNDIRECTED_GRAPH, Type Bundle::*>::const_type -get(Type Bundle::* p, UNDIRECTED_GRAPH const& g) { - typedef typename property_map< - UNDIRECTED_GRAPH, Type Bundle::* - >::const_type return_type; - return return_type(&g, p); -} - -template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key> -inline Type -get(Type Bundle::* p, UNDIRECTED_GRAPH const& g, Key const& k) -{ return get(p, g.impl(), k); } - -template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key, typename Value> -inline void -put(Type Bundle::* p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) -{ put(p, g.impl(), k, v); } -#endif - // Indexed Vertex graph template <UNDIRECTED_GRAPH_PARAMS> diff --git a/boost/graph/vector_as_graph.hpp b/boost/graph/vector_as_graph.hpp index ee0df4bc90..7bc8ac3802 100644 --- a/boost/graph/vector_as_graph.hpp +++ b/boost/graph/vector_as_graph.hpp @@ -19,6 +19,7 @@ #include <vector> #include <cstddef> #include <boost/iterator.hpp> +#include <boost/iterator/counting_iterator.hpp> #include <boost/range/irange.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/property_map/property_map.hpp> @@ -71,13 +72,14 @@ namespace boost { out_edge_iterator; typedef void in_edge_iterator; typedef void edge_iterator; - typedef typename integer_range<V>::iterator vertex_iterator; + typedef counting_iterator<V> vertex_iterator; typedef directed_tag directed_category; typedef allow_parallel_edge_tag edge_parallel_category; typedef vector_as_graph_traversal_tag traversal_category; typedef typename std::vector<EdgeList>::size_type vertices_size_type; typedef void edges_size_type; typedef typename EdgeList::size_type degree_size_type; + static V null_vertex() {return V(-1);} }; template <class EdgeList> struct edge_property_type< std::vector<EdgeList> > @@ -178,14 +180,11 @@ namespace boost { // source() and target() already provided for pairs in graph_traits.hpp template <class EdgeList, class Alloc> - std::pair<typename boost::integer_range<typename EdgeList::value_type> - ::iterator, - typename boost::integer_range<typename EdgeList::value_type> - ::iterator > + std::pair<boost::counting_iterator<typename EdgeList::value_type>, + boost::counting_iterator<typename EdgeList::value_type> > vertices(const std::vector<EdgeList, Alloc>& v) { - typedef typename boost::integer_range<typename EdgeList::value_type> - ::iterator Iter; + typedef boost::counting_iterator<typename EdgeList::value_type> Iter; return std::make_pair(Iter(0), Iter(v.size())); } |