// This file implements a utility for creating mappings from arbitrary
// identifiers to the vertices of a graph.
-namespace boost {
+namespace boost
+{
// A type selector that denotes the use of some default value.
-struct defaultS { };
+struct defaultS
+{
+};
/** @internal */
-namespace graph_detail {
+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>
- { };
+ 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;
+ 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;
};
/**
* Label is an integral type.
*/
//@{
- template <typename Selector, typename Label, typename Vertex>
- struct generate_label_map { };
+ 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< 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< 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< 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_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 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;
+ 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;
+ 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 */
// basically requires a) that Container is vector<Label> and that Label
// is an unsigned integral value. Note that this will resize the vector
// to accommodate indices.
- template <typename Container, typename Graph, typename Label, typename Prop>
- std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
+ 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)
+ random_access_container_tag)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
// If the label is out of bounds, resize the vector to accommodate.
// Resize by 2x the index so we don't cause quadratic insertions over
// time.
- if(l >= c.size()) {
+ if (l >= c.size())
+ {
c.resize((l + 1) * 2);
}
Vertex v = add_vertex(p, g);
}
// 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>
+ 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&)
+ 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;
+ typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
Vertex v = add_vertex(p, 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>
+ 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,
- unique_associative_container_tag)
+ 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 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) {
+ std::pair< Iterator, bool > x = c.insert(std::make_pair(l, Vertex()));
+ if (x.second)
+ {
x.first->second = add_vertex(g);
put(boost::vertex_all, g, x.first->second, p);
}
}
// Dispatcher
- template <typename Container, typename Graph, typename Label, typename Prop>
- std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
+ 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)); }
+ {
+ 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(); }
+ 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)
+ 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();
+ 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)); }
+ 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>
+ 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)
+ random_access_container_tag)
{
// If the element is already occupied, then we probably don't want to
// overwrite it.
- if(c[l] == graph_traits<Graph>::null_vertex()) return false;
+ if (c[l] == graph_traits< 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>
+ 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; }
+ 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>
+ 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)
+ 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)); }
+ 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 { };
+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 {
+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;
+ typedef typename graph_detail::choose_map< Selector, Label,
+ typename graph_traits< Graph >::vertex_descriptor >::type map_type;
};
/**
* @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>
+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;
+ 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_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;
public:
labeled_graph(graph_property_type const& gp = graph_property_type())
- : _graph(gp), _map()
- { }
+ : _graph(gp), _map()
+ {
+ }
- labeled_graph(labeled_graph const& x)
- : _graph(x._graph), _map(x._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()
+ graph_property_type const& gp = graph_property_type())
+ : _graph(n, gp), _map()
{
- std::pair<vertex_iterator, vertex_iterator> rng = vertices(_graph);
+ std::pair< vertex_iterator, vertex_iterator > rng = vertices(_graph);
_map.insert(_map.end(), rng.first, rng.second);
}
// 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>
+ 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++); }
+ 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>
+ template < typename LabelIter, typename PropIter >
labeled_graph(vertices_size_type n, LabelIter l, PropIter p,
- graph_property_type const& gp = graph_property_type())
- : _graph(gp)
- { while(n-- > 0) add_vertex(*l++, *p++); }
+ graph_property_type const& gp = graph_property_type())
+ : _graph(gp)
+ {
+ while (n-- > 0)
+ add_vertex(*l++, *p++);
+ }
- labeled_graph& operator=(labeled_graph const& x) {
+ labeled_graph& operator=(labeled_graph const& x)
+ {
_graph = x._graph;
_map = x._map;
return *this;
* cannot be created.
*/
bool label_vertex(vertex_descriptor v, Label const& l)
- { return graph_detail::put_vertex_label(_map, _graph, l, v); }
+ {
+ 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
* needed.
*/
//@{
- vertex_descriptor add_vertex(Label const& l) {
+ vertex_descriptor add_vertex(Label const& l)
+ {
return graph_detail::insert_labeled_vertex(
- _map, _graph, l, vertex_property_type()
- ).first;
+ _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; }
+ {
+ return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first;
+ }
//@}
/** @name Insert Vertex
* insertion will always succeed.
*/
//@{
- std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
+ std::pair< vertex_descriptor, bool > insert_vertex(Label const& l)
+ {
return graph_detail::insert_labeled_vertex(
- _map, _graph, l, vertex_property_type()
- );
+ _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); }
+ 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 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); }
+ {
+ 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& operator[](Label const& l) { return _graph[vertex(l)]; }
vertex_bundled const& operator[](Label const& l) const
- { return _graph[vertex(l)]; }
+ {
+ return _graph[vertex(l)];
+ }
// Delegate edge lookup to the underlying graph.
- edge_bundled& operator[](edge_descriptor e)
- { return _graph[e]; }
+ edge_bundled& operator[](edge_descriptor e) { return _graph[e]; }
edge_bundled const& operator[](edge_descriptor e) const
- { return _graph[e]; }
+ {
+ return _graph[e];
+ }
//@}
#endif
/** Return a null descriptor */
static vertex_descriptor null_vertex()
- { return graph_traits<graph_type>::null_vertex(); }
+ {
+ return graph_traits< graph_type >::null_vertex();
+ }
private:
graph_type _graph;
* 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>
+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;
+ 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_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 Base::label_type label_type;
typedef typename Base::map_type map_type;
- labeled_graph(graph_type* g)
- : _graph(g)
- { }
+ labeled_graph(graph_type* g) : _graph(g) {}
/** @name Graph Access */
//@{
* cannot be created.
*/
bool label_vertex(vertex_descriptor v, Label const& l)
- { return graph_detail::put_vertex_label(_map, *_graph, l, v); }
+ {
+ return graph_detail::put_vertex_label(_map, *_graph, l, v);
+ }
/** @name Add Vertex */
//@{
- vertex_descriptor add_vertex(Label const& l) {
+ vertex_descriptor add_vertex(Label const& l)
+ {
return graph_detail::insert_labeled_vertex(
- _map, *_graph, l, vertex_property_type()
- ).first;
+ _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; }
+ {
+ return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first;
+ }
- std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
+ std::pair< vertex_descriptor, bool > insert_vertex(Label const& l)
+ {
return graph_detail::insert_labeled_vertex(
- _map, *_graph, l, vertex_property_type()
- );
+ _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); }
+ 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 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); }
+ {
+ 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& operator[](Label const& l) { return (*_graph)[vertex(l)]; }
vertex_bundled const& operator[](Label const& l) const
- { return (*_graph)[vertex(l)]; }
+ {
+ return (*_graph)[vertex(l)];
+ }
// Delegate edge lookup to the underlying graph.
- edge_bundled& operator[](edge_descriptor e)
- { return (*_graph)[e]; }
+ edge_bundled& operator[](edge_descriptor e) { return (*_graph)[e]; }
edge_bundled const& operator[](edge_descriptor e) const
- { return (*_graph)[e]; }
+ {
+ return (*_graph)[e];
+ }
//@}
#endif
static vertex_descriptor null_vertex()
- { return graph_traits<graph_type>::null_vertex(); }
+ {
+ return graph_traits< graph_type >::null_vertex();
+ }
private:
graph_type* _graph;
};
#define LABELED_GRAPH_PARAMS typename G, typename L, typename S
-#define LABELED_GRAPH labeled_graph<G,L,S>
+#define LABELED_GRAPH labeled_graph< G, L, S >
/** @name Labeled Graph */
//@{
-template <LABELED_GRAPH_PARAMS>
+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 typename LABELED_GRAPH::vertex_descriptor
-vertex_by_label(typename LABELED_GRAPH::label_type const l,
- LABELED_GRAPH& g)
-{ return g.vertex(l); }
+ typename LABELED_GRAPH::label_type const l, LABELED_GRAPH& g)
+{
+ return g.label_vertex(v, l);
+}
+
+template < LABELED_GRAPH_PARAMS >
+inline typename LABELED_GRAPH::vertex_descriptor 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()); }
+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); }
+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>
+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()); }
+{
+ 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>
+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()); }
+{
+ 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 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()); }
+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()); }
+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>
+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()); }
+{
+ 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()); }
+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>
+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()); }
+{
+ 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()); }
+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_ {
+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 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_ {
+ 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 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> {
+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> {
+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
+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); }
+{
+ 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); }
+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()); }
+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>
+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); }
+ 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>
+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()); }
+ 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 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); }
+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); }
+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