| // Copyright (C) 2009 Andrew Sutton |
| |
| // Use, modification and distribution is subject to 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) |
| |
| #ifndef BOOST_GRAPH_LABELED_GRAPH_HPP |
| #define BOOST_GRAPH_LABELED_GRAPH_HPP |
| |
| #include <boost/config.hpp> |
| #include <vector> |
| #include <map> |
| |
| #include <boost/static_assert.hpp> |
| #include <boost/mpl/if.hpp> |
| #include <boost/mpl/bool.hpp> |
| #include <boost/unordered_map.hpp> |
| #include <boost/type_traits/is_same.hpp> |
| #include <boost/type_traits/is_unsigned.hpp> |
| #include <boost/pending/container_traits.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| |
| // This file implements a utility for creating mappings from arbitrary |
| // identifers to the vertices of a graph. |
| |
| namespace boost { |
| |
| // A type selector that denotes the use of some default value. |
| struct defaultS { }; |
| |
| /** @internal */ |
| namespace graph_detail { |
| /** Returns true if the selector is the default selector. */ |
| template <typename Selector> |
| struct is_default |
| : mpl::bool_<is_same<Selector, defaultS>::value> |
| { }; |
| |
| /** |
| * Choose the default map instance. If Label is an unsigned integral type |
| * the we can use a vector to store the information. |
| */ |
| template <typename Label, typename Vertex> |
| struct choose_default_map { |
| typedef typename mpl::if_< |
| is_unsigned<Label>, |
| std::vector<Vertex>, |
| std::map<Label, Vertex> // TODO: Should use unordered_map? |
| >::type type; |
| }; |
| |
| /** |
| * @name Generate Label Map |
| * These type generators are responsible for instantiating an associative |
| * container for the the labeled graph. Note that the Selector must be |
| * select a pair associative container or a vecS, which is only valid if |
| * Label is an integral type. |
| */ |
| //@{ |
| template <typename Selector, typename Label, typename Vertex> |
| struct generate_label_map { }; |
| |
| template <typename Label, typename Vertex> |
| struct generate_label_map<vecS, Label, Vertex> |
| { typedef std::vector<Vertex> type; }; |
| |
| template <typename Label, typename Vertex> |
| struct generate_label_map<mapS, Label, Vertex> |
| { typedef std::map<Label, Vertex> type; }; |
| |
| template <typename Label, typename Vertex> |
| struct generate_label_map<multimapS, Label, Vertex> |
| { typedef std::multimap<Label, Vertex> type; }; |
| |
| template <typename Label, typename Vertex> |
| struct generate_label_map<hash_mapS, Label, Vertex> |
| { typedef boost::unordered_map<Label, Vertex> type; }; |
| |
| template <typename Label, typename Vertex> |
| struct generate_label_map<hash_multimapS, Label, Vertex> |
| { typedef boost::unordered_multimap<Label, Vertex> type; }; |
| |
| template <typename Selector, typename Label, typename Vertex> |
| struct choose_custom_map { |
| typedef typename generate_label_map<Selector, Label, Vertex>::type type; |
| }; |
| //@} |
| |
| /** |
| * Choose and instantiate an "associative" container. Note that this can |
| * also choose vector. |
| */ |
| template <typename Selector, typename Label, typename Vertex> |
| struct choose_map { |
| typedef typename mpl::eval_if< |
| is_default<Selector>, |
| choose_default_map<Label, Vertex>, |
| choose_custom_map<Selector, Label, Vertex> |
| >::type type; |
| }; |
| |
| /** @name Insert Labeled Vertex */ |
| //@{ |
| // Tag dispatch on random access containers (i.e., vectors). This function |
| // basically requires a) that Container is vector<Label> and that Label |
| // is an unsigned integral value. Note that this will resize the vector |
| // to accomodate indices. |
| template <typename Container, typename Graph, typename Label, typename Prop> |
| std::pair<typename graph_traits<Graph>::vertex_descriptor, bool> |
| insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p, |
| random_access_container_tag) |
| { |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| |
| // If the label is out of bounds, resize the vector to accomodate. |
| // Resize by 2x the index so we don't cause quadratic insertions over |
| // time. |
| if(l >= c.size()) { |
| c.resize((l + 1) * 2); |
| } |
| Vertex v = add_vertex(p, g); |
| c[l] = v; |
| return std::make_pair(c[l], true); |
| } |
| |
| // Tag dispatch on multi associative containers (i.e. multimaps). |
| template <typename Container, typename Graph, typename Label, typename Prop> |
| std::pair<typename graph_traits<Graph>::vertex_descriptor, bool> |
| insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p, |
| multiple_associative_container_tag const&) |
| { |
| // Note that insertion always succeeds so we can add the vertex first |
| // and then the mapping to the label. |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| Vertex v = add_vertex(g); |
| c.insert(std::make_pair(l, v)); |
| return std::make_pair(v, true); |
| } |
| |
| // Tag dispatch on unique associative containers (i.e. maps). |
| template <typename Container, typename Graph, typename Label, typename Prop> |
| std::pair<typename graph_traits<Graph>::vertex_descriptor, bool> |
| insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const&, |
| unique_associative_container_tag) |
| { |
| // Here, we actually have to try the insertion first, and only add |
| // the vertex if we get a new element. |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| typedef typename Container::iterator Iterator; |
| std::pair<Iterator, bool> x = c.insert(std::make_pair(l, Vertex())); |
| if(x.second) { |
| x.first->second = add_vertex(g); |
| } |
| return std::make_pair(x.first->second, x.second); |
| } |
| |
| // Dispatcher |
| template <typename Container, typename Graph, typename Label, typename Prop> |
| std::pair<typename graph_traits<Graph>::vertex_descriptor, bool> |
| insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p) |
| { return insert_labeled_vertex(c, g, l, p, container_category(c)); } |
| //@} |
| |
| /** @name Find Labeled Vertex */ |
| //@{ |
| // Tag dispatch for sequential maps (i.e., vectors). |
| template <typename Container, typename Graph, typename Label> |
| typename graph_traits<Graph>::vertex_descriptor |
| find_labeled_vertex(Container const& c, Graph const&, Label const& l, |
| random_access_container_tag) |
| { return l < c.size() ? c[l] : graph_traits<Graph>::null_vertex(); } |
| |
| // Tag dispatch for pair associative maps (more or less). |
| template <typename Container, typename Graph, typename Label> |
| typename graph_traits<Graph>::vertex_descriptor |
| find_labeled_vertex(Container const& c, Graph const&, Label const& l, |
| associative_container_tag) |
| { |
| typename Container::const_iterator i = c.find(l); |
| return i != c.end() ? i->second : graph_traits<Graph>::null_vertex(); |
| } |
| |
| // Dispatcher |
| template <typename Container, typename Graph, typename Label> |
| typename graph_traits<Graph>::vertex_descriptor |
| find_labeled_vertex(Container const& c, Graph const& g, Label const& l) |
| { return find_labeled_vertex(c, g, l, container_category(c)); } |
| //@} |
| |
| /** @name Put Vertex Label */ |
| //@{ |
| // Tag dispatch on vectors. |
| template <typename Container, typename Label, typename Graph, typename Vertex> |
| bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v, |
| random_access_container_tag) |
| { |
| // If the element is already occupied, then we probably don't want to |
| // overwrite it. |
| if(c[l] == Graph::null_vertex()) return false; |
| c[l] = v; |
| return true; |
| } |
| |
| // Attempt the insertion and return its result. |
| template <typename Container, typename Label, typename Graph, typename Vertex> |
| bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v, |
| unique_associative_container_tag) |
| { return c.insert(std::make_pair(l, v)).second; } |
| |
| // Insert the pair and return true. |
| template <typename Container, typename Label, typename Graph, typename Vertex> |
| bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v, |
| multiple_associative_container_tag) |
| { |
| c.insert(std::make_pair(l, v)); |
| return true; |
| } |
| |
| // Dispatcher |
| template <typename Container, typename Label, typename Graph, typename Vertex> |
| bool put_vertex_label(Container& c, Graph const& g, Label const& l, Vertex v) |
| { return put_vertex_label(c, g, l, v, container_category(c)); } |
| //@} |
| |
| } // namespace detail |
| |
| struct labeled_graph_class_tag { }; |
| |
| /** @internal |
| * This class is responsible for the deduction and declaration of type names |
| * for the labeled_graph class template. |
| */ |
| template <typename Graph, typename Label, typename Selector> |
| struct labeled_graph_types { |
| typedef Graph graph_type; |
| |
| // Label and maps |
| typedef Label label_type; |
| typedef typename graph_detail::choose_map< |
| Selector, Label, typename graph_traits<Graph>::vertex_descriptor |
| >::type map_type; |
| }; |
| |
| /** |
| * The labeled_graph class is a graph adaptor that maintains a mapping between |
| * vertex labels and vertex descriptors. |
| * |
| * @todo This class is somewhat redundant for adjacency_list<*, vecS> if |
| * the intended label is an unsigned int (and perhpahs some other cases), but |
| * it does avoid some weird ambiguities (i.e. adding a vertex with a label that |
| * does not match its target index). |
| * |
| * @todo This needs to be reconciled with the named_graph, but since there is |
| * no documentation or examples, its not going to happen. |
| */ |
| template <typename Graph, typename Label, typename Selector = defaultS> |
| class labeled_graph |
| : protected labeled_graph_types<Graph, Label, Selector> |
| { |
| typedef labeled_graph_types<Graph, Label, Selector> Base; |
| public: |
| typedef labeled_graph_class_tag graph_tag; |
| |
| typedef typename Base::graph_type graph_type; |
| typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor; |
| typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor; |
| typedef typename graph_traits<graph_type>::directed_category directed_category; |
| typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category; |
| typedef typename graph_traits<graph_type>::traversal_category traversal_category; |
| |
| typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
| typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; |
| typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator; |
| typedef typename graph_traits<graph_type>::degree_size_type degree_size_type; |
| |
| typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator; |
| typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type; |
| typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
| typedef typename graph_traits<graph_type>::edges_size_type edges_size_type; |
| |
| typedef typename graph_type::graph_property_type graph_property_type; |
| typedef typename graph_type::graph_bundled graph_bundled; |
| |
| typedef typename graph_type::vertex_property_type vertex_property_type; |
| typedef typename graph_type::vertex_bundled vertex_bundled; |
| |
| typedef typename graph_type::edge_property_type edge_property_type; |
| typedef typename graph_type::edge_bundled edge_bundled; |
| |
| typedef typename Base::label_type label_type; |
| typedef typename Base::map_type map_type; |
| |
| public: |
| labeled_graph(graph_property_type const& gp = graph_property_type()) |
| : _graph(gp), _map() |
| { } |
| |
| labeled_graph(labeled_graph const& x) |
| : _graph(x._graph), _map(x._map) |
| { } |
| |
| // This constructor can only be used if map_type supports positional |
| // range insertion (i.e. its a vector). This is the only case where we can |
| // try to guess the intended labels for graph. |
| labeled_graph(vertices_size_type n, |
| graph_property_type const& gp = graph_property_type()) |
| : _graph(n, gp), _map() |
| { |
| std::pair<vertex_iterator, vertex_iterator> rng = vertices(_graph); |
| _map.insert(_map.end(), rng.first, rng.second); |
| } |
| |
| // Construct a grpah over n vertices, each of which receives a label from |
| // the range [l, l + n). Note that the graph is not directly constructed |
| // over the n vertices, but added sequentially. This constructor is |
| // necessarily slower than the underlying counterpart. |
| template <typename LabelIter> |
| labeled_graph(vertices_size_type n, LabelIter l, |
| graph_property_type const& gp = graph_property_type()) |
| : _graph(gp) |
| { while(n-- >= 0) add_vertex(*l++); } |
| |
| // Construct the graph over n vertices each of which has a label in the |
| // range [l, l + n) and a property in the range [p, p + n). |
| template <typename LabelIter, typename PropIter> |
| labeled_graph(vertices_size_type n, LabelIter l, PropIter p, |
| graph_property_type const& gp = graph_property_type()) |
| { while(n-- >= 0) add_vertex(*l++, *p++); } |
| |
| labeled_graph& operator=(labeled_graph const& x) { |
| _graph = x._graph; |
| _map = x._map; |
| return *this; |
| } |
| |
| /** @name Graph Accessors */ |
| //@{ |
| graph_type& graph() { return _graph; } |
| graph_type const& graph() const { return _graph; } |
| //@} |
| |
| /** |
| * Create a new label for the given vertex, returning false, if the label |
| * cannot be created. |
| */ |
| bool label_vertex(vertex_descriptor v, Label const& l) |
| { return graph_detail::put_vertex_label(_map, _graph, l, v); } |
| |
| /** @name Add Vertex |
| * Add a vertex to the graph, returning the descriptor. If the vertices |
| * are uniquely labeled and the label already exists within the graph, |
| * then no vertex is added, and the returned descriptor refers to the |
| * existing vertex. A vertex property can be given as a parameter, if |
| * needed. |
| */ |
| //@{ |
| vertex_descriptor add_vertex(Label const& l) { |
| return graph_detail::insert_labeled_vertex( |
| _map, _graph, l, vertex_property_type() |
| ).first; |
| } |
| |
| vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p) |
| { return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first; } |
| //@} |
| |
| /** @name Insert Vertex |
| * Insert a vertex into the graph, returning a pair containing the |
| * descriptor of a vertex and a boolean value that describes whether or not |
| * a new vertex was inserted. If vertices are not uniquely labeled, then |
| * insertion will always succeed. |
| */ |
| //@{ |
| std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) { |
| return graph_detail::insert_labeled_vertex( |
| _map, _graph, l, vertex_property_type() |
| ); |
| } |
| |
| std::pair<vertex_descriptor, bool> |
| insert_vertex(Label const& l, vertex_property_type const& p) |
| { return graph_detail::insert_labeled_vertex(_map, _graph, l, p); } |
| //@} |
| |
| /** Remove the vertex with the given label. */ |
| void remove_vertex(Label const& l) |
| { return boost::remove_vertex(vertex(l), _graph); } |
| |
| /** Return a descriptor for the given label. */ |
| vertex_descriptor vertex(Label const& l) const |
| { return graph_detail::find_labeled_vertex(_map, _graph, l); } |
| |
| #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
| /** @name Bundled Properties */ |
| //@{ |
| // Lookup the requested vertex and return the bundle. |
| vertex_bundled& operator[](Label const& l) |
| { return _graph[vertex(l)]; } |
| |
| vertex_bundled const& operator[](Label const& l) const |
| { return _graph[vertex(l)]; } |
| |
| // Delegate edge lookup to the underlying graph. |
| edge_bundled& operator[](edge_descriptor e) |
| { return _graph[e]; } |
| |
| edge_bundled const& operator[](edge_descriptor e) const |
| { return _graph[e]; } |
| //@} |
| #endif |
| |
| /** Return a null descriptor */ |
| static vertex_descriptor null_vertex() |
| { return graph_type::null_vertex(); } |
| |
| private: |
| graph_type _graph; |
| map_type _map; |
| }; |
| |
| /** |
| * The partial specialization over graph pointers allows the construction |
| * of temporary labeled graph objects. In this case, the labels are destructed |
| * when the wrapper goes out of scope. |
| */ |
| template <typename Graph, typename Label, typename Selector> |
| class labeled_graph<Graph*, Label, Selector> |
| : protected labeled_graph_types<Graph, Label, Selector> |
| { |
| typedef labeled_graph_types<Graph, Label, Selector> Base; |
| public: |
| typedef labeled_graph_class_tag graph_tag; |
| |
| typedef typename Base::graph_type graph_type; |
| typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor; |
| typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor; |
| typedef typename graph_traits<graph_type>::directed_category directed_category; |
| typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category; |
| typedef typename graph_traits<graph_type>::traversal_category traversal_category; |
| |
| typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
| typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; |
| typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator; |
| typedef typename graph_traits<graph_type>::degree_size_type degree_size_type; |
| |
| typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator; |
| typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type; |
| typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
| typedef typename graph_traits<graph_type>::edges_size_type edges_size_type; |
| |
| typedef typename graph_type::vertex_property_type vertex_property_type; |
| typedef typename graph_type::edge_property_type edge_property_type; |
| typedef typename graph_type::graph_property_type graph_property_type; |
| typedef typename graph_type::vertex_bundled vertex_bundled; |
| typedef typename graph_type::edge_bundled edge_bundled; |
| |
| typedef typename Base::label_type label_type; |
| typedef typename Base::map_type map_type; |
| |
| labeled_graph(graph_type* g) |
| : _graph(g) |
| { } |
| |
| /** @name Graph Access */ |
| //@{ |
| graph_type& graph() { return *_graph; } |
| graph_type const& graph() const { return *_graph; } |
| //@} |
| |
| /** |
| * Create a new label for the given vertex, returning false, if the label |
| * cannot be created. |
| */ |
| bool label_vertex(vertex_descriptor v, Label const& l) |
| { return graph_detail::put_vertex_label(_map, *_graph, l, v); } |
| |
| /** @name Add Vertex */ |
| //@{ |
| vertex_descriptor add_vertex(Label const& l) { |
| return graph_detail::insert_labeled_vertex( |
| _map, *_graph, l, vertex_property_type() |
| ).first; |
| } |
| |
| vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p) |
| { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first; } |
| |
| std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) { |
| return graph_detail::insert_labeled_vertex( |
| _map, *_graph, l, vertex_property_type() |
| ); |
| } |
| //@} |
| |
| /** Try to insert a vertex with the given label. */ |
| std::pair<vertex_descriptor, bool> |
| insert_vertex(Label const& l, vertex_property_type const& p) |
| { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p); } |
| |
| /** Remove the vertex with the given label. */ |
| void remove_vertex(Label const& l) |
| { return boost::remove_vertex(vertex(l), *_graph); } |
| |
| /** Return a descriptor for the given label. */ |
| vertex_descriptor vertex(Label const& l) const |
| { return graph_detail::find_labeled_vertex(_map, *_graph, l); } |
| |
| #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
| /** @name Bundled Properties */ |
| //@{ |
| // Lookup the requested vertex and return the bundle. |
| vertex_bundled& operator[](Label const& l) |
| { return (*_graph)[vertex(l)]; } |
| |
| vertex_bundled const& operator[](Label const& l) const |
| { return (*_graph)[vertex(l)]; } |
| |
| // Delegate edge lookup to the underlying graph. |
| edge_bundled& operator[](edge_descriptor e) |
| { return (*_graph)[e]; } |
| |
| edge_bundled const& operator[](edge_descriptor e) const |
| { return (*_graph)[e]; } |
| //@} |
| #endif |
| |
| static vertex_descriptor null_vertex() |
| { return graph_type::null_vertex(); } |
| |
| private: |
| graph_type* _graph; |
| map_type _map; |
| }; |
| |
| #define LABELED_GRAPH_PARAMS typename G, typename L, typename S |
| #define LABELED_GRAPH labeled_graph<G,L,S> |
| |
| /** @name Labeled Graph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline bool label_vertex(typename LABELED_GRAPH::vertex_descriptor v, |
| typename LABELED_GRAPH::label_type const l, |
| LABELED_GRAPH& g) |
| { return g.label_vertex(v, l); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline bool vertex_by_label(typename LABELED_GRAPH::label_type const l, |
| LABELED_GRAPH& g) |
| { return g.vertex(l); } |
| //@} |
| |
| /** @name Graph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
| edge(typename LABELED_GRAPH::vertex_descriptor const& u, |
| typename LABELED_GRAPH::vertex_descriptor const& v, |
| LABELED_GRAPH const& g) |
| { return edge(u, v, g.graph()); } |
| |
| // Labeled Extensions |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
| edge_by_label(typename LABELED_GRAPH::label_type const& u, |
| typename LABELED_GRAPH::label_type const& v, |
| LABELED_GRAPH const& g) |
| { return edge(g.vertex(u), g.vertex(v), g); } |
| //@} |
| |
| /** @name Incidence Graph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair< |
| typename LABELED_GRAPH::out_edge_iterator, |
| typename LABELED_GRAPH::out_edge_iterator> |
| out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
| { return out_edges(v, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::degree_size_type |
| out_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
| { return out_degree(v, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::vertex_descriptor |
| source(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g) |
| { return source(e, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::vertex_descriptor |
| target(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g) |
| { return target(e, g.graph()); } |
| //@} |
| |
| /** @name Bidirectional Graph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair< |
| typename LABELED_GRAPH::in_edge_iterator, |
| typename LABELED_GRAPH::in_edge_iterator> |
| in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
| { return in_edges(v, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::degree_size_type |
| in_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
| { return in_degree(v, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::degree_size_type |
| degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
| { return degree(v, g.graph()); } |
| //@} |
| |
| /** @name Adjacency Graph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair< |
| typename LABELED_GRAPH::adjacency_iterator, |
| typename LABELED_GRAPH::adjacency_iterator> |
| adjacenct_vertices(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
| { return adjacent_vertices(v, g.graph()); } |
| //@} |
| |
| /** @name VertexListGraph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair< |
| typename LABELED_GRAPH::vertex_iterator, |
| typename LABELED_GRAPH::vertex_iterator> |
| vertices(LABELED_GRAPH const& g) |
| { return vertices(g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::vertices_size_type |
| num_vertices(LABELED_GRAPH const& g) |
| { return num_vertices(g.graph()); } |
| //@} |
| |
| /** @name EdgeListGraph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair< |
| typename LABELED_GRAPH::edge_iterator, |
| typename LABELED_GRAPH::edge_iterator> |
| edges(LABELED_GRAPH const& g) |
| { return edges(g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::edges_size_type |
| num_edges(LABELED_GRAPH const& g) |
| { return num_edges(g.graph()); } |
| //@} |
| |
| /** @internal @name Property Lookup */ |
| //@{ |
| namespace graph_detail { |
| struct labeled_graph_vertex_property_selector { |
| template <class LabeledGraph, class Property, class Tag> |
| struct bind_ { |
| typedef typename LabeledGraph::graph_type Graph; |
| typedef property_map<Graph, Tag> PropertyMap; |
| typedef typename PropertyMap::type type; |
| typedef typename PropertyMap::const_type const_type; |
| }; |
| }; |
| |
| struct labeled_graph_edge_property_selector { |
| template <class LabeledGraph, class Property, class Tag> |
| struct bind_ { |
| typedef typename LabeledGraph::graph_type Graph; |
| typedef property_map<Graph, Tag> PropertyMap; |
| typedef typename PropertyMap::type type; |
| typedef typename PropertyMap::const_type const_type; |
| }; |
| }; |
| } |
| |
| template <> |
| struct vertex_property_selector<labeled_graph_class_tag> { |
| typedef graph_detail::labeled_graph_vertex_property_selector type; |
| }; |
| |
| template <> |
| struct edge_property_selector<labeled_graph_class_tag> { |
| typedef graph_detail::labeled_graph_edge_property_selector type; |
| }; |
| //@} |
| |
| /** @name Property Graph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS, typename Prop> |
| inline typename property_map<LABELED_GRAPH, Prop>::type |
| get(Prop p, LABELED_GRAPH& g) |
| { return get(p, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS, typename Prop> |
| inline typename property_map<LABELED_GRAPH, Prop>::const_type |
| get(Prop p, LABELED_GRAPH const& g) |
| { return get(p, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS, typename Prop, typename Key> |
| inline typename property_traits< |
| typename property_map<typename LABELED_GRAPH::graph_type, Prop>::const_type |
| >::value_type |
| get(Prop p, LABELED_GRAPH const& g, const Key& k) |
| { return get(p, g.graph(), k); } |
| |
| template <LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value> |
| inline void |
| put(Prop p, LABELED_GRAPH& g, Key const& k, Value const& v) |
| { put(p, g.graph(), k, v); } |
| //@} |
| |
| /** @name Mutable Graph */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
| add_edge(typename LABELED_GRAPH::vertex_descriptor const& u, |
| typename LABELED_GRAPH::vertex_descriptor const& v, |
| LABELED_GRAPH& g) |
| { return add_edge(u, v, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
| add_edge(typename LABELED_GRAPH::vertex_descriptor const& u, |
| typename LABELED_GRAPH::vertex_descriptor const& v, |
| typename LABELED_GRAPH::edge_property_type const& p, |
| LABELED_GRAPH& g) |
| { return add_edge(u, v, p, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline void |
| clear_vertex(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g) |
| { return clear_vertex(v, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline void |
| remove_edge(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g) |
| { return remove_edge(e, g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline void |
| remove_edge(typename LABELED_GRAPH::vertex_descriptor u, |
| typename LABELED_GRAPH::vertex_descriptor v, |
| LABELED_GRAPH& g) |
| { return remove_edge(u, v, g.graph()); } |
| |
| // Labeled extensions |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
| add_edge_by_label(typename LABELED_GRAPH::label_type const& u, |
| typename LABELED_GRAPH::label_type const& v, |
| LABELED_GRAPH& g) |
| { return add_edge(g.vertex(u), g.vertex(v), g); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
| add_edge_by_label(typename LABELED_GRAPH::label_type const& u, |
| typename LABELED_GRAPH::label_type const& v, |
| typename LABELED_GRAPH::edge_property_type const& p, |
| LABELED_GRAPH& g) |
| { return add_edge(g.vertex(u), g.vertex(v), p, g); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline void |
| clear_vertex_by_label(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g) |
| { clear_vertex(g.vertex(l), g.graph()); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline void |
| remove_edge_by_label(typename LABELED_GRAPH::label_type const& u, |
| typename LABELED_GRAPH::label_type const& v, |
| LABELED_GRAPH& g) |
| { remove_edge(g.vertex(u), g.vertex(v), g.graph()); } |
| //@} |
| |
| /** @name Labeled Mutable Graph |
| * The labeled mutable graph hides the add_ and remove_ vertex functions from |
| * the mutable graph concept. Note that the remove_vertex is hidden because |
| * removing the vertex without its key could leave a dangling reference in |
| * the map. |
| */ |
| //@{ |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::vertex_descriptor |
| add_vertex(typename LABELED_GRAPH::label_type const& l, |
| LABELED_GRAPH& g) |
| { return g.add_vertex(l); } |
| |
| // MutableLabeledPropertyGraph::add_vertex(l, vp, g) |
| template <LABELED_GRAPH_PARAMS> |
| inline typename LABELED_GRAPH::vertex_descriptor |
| add_vertex(typename LABELED_GRAPH::label_type const& l, |
| typename LABELED_GRAPH::vertex_property_type const& p, |
| LABELED_GRAPH& g) |
| { return g.add_vertex(l, p); } |
| |
| template <LABELED_GRAPH_PARAMS> |
| inline void |
| remove_vertex(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g) |
| { g.remove_vertex(l); } |
| //@} |
| |
| #undef LABELED_GRAPH_PARAMS |
| #undef LABELED_GRAPH |
| |
| } // namespace boost |
| |
| // Pull the labeled graph traits |
| #include <boost/graph/detail/labeled_graph_traits.hpp> |
| |
| #endif // BOOST_GRAPH_LABELED_GRAPH_HPP |