diff options
Diffstat (limited to 'boost/graph/detail/adjacency_list.hpp')
| -rw-r--r-- | boost/graph/detail/adjacency_list.hpp | 165 |
1 files changed, 62 insertions, 103 deletions
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 /* |