// Copyright (C) 2007 Douglas Gregor | |
// 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) | |
// Provides support for named vertices in graphs, allowing one to more | |
// easily associate unique external names (URLs, city names, employee | |
// ID numbers, etc.) with the vertices of a graph. | |
#ifndef BOOST_GRAPH_NAMED_GRAPH_HPP | |
#define BOOST_GRAPH_NAMED_GRAPH_HPP | |
#include <boost/config.hpp> | |
#include <boost/type_traits/remove_cv.hpp> | |
#include <boost/type_traits/remove_reference.hpp> | |
#include <boost/multi_index_container.hpp> | |
#include <boost/multi_index/hashed_index.hpp> | |
#include <boost/multi_index/member.hpp> | |
#include <boost/optional.hpp> | |
#include <boost/throw_exception.hpp> | |
#include <stdexcept> // for std::runtime_error | |
namespace boost { namespace graph { | |
/******************************************************************* | |
* User-customized traits * | |
*******************************************************************/ | |
/** | |
* @brief Trait used to extract the internal vertex name from a vertex | |
* property. | |
* | |
* To enable the use of internal vertex names in a graph type, | |
* specialize the @c internal_vertex_name trait for your graph | |
* property (e.g., @c a City class, which stores information about the | |
* vertices in a road map). | |
*/ | |
template<typename VertexProperty> | |
struct internal_vertex_name | |
{ | |
/** | |
* The @c type field provides a function object that extracts a key | |
* from the @c VertexProperty. The function object type must have a | |
* nested @c result_type that provides the type of the key. For | |
* more information, see the @c KeyExtractor concept in the | |
* Boost.MultiIndex documentation: @c type must either be @c void | |
* (if @c VertexProperty does not have an internal vertex name) or | |
* a model of @c KeyExtractor. | |
*/ | |
typedef void type; | |
}; | |
#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION | |
/** | |
* Extract the internal vertex name from a @c property structure by | |
* looking at its base. | |
*/ | |
template<typename Tag, typename T, typename Base> | |
struct internal_vertex_name<property<Tag, T, Base> > | |
: internal_vertex_name<Base> { }; | |
#endif | |
/** | |
* Construct an instance of @c VertexProperty directly from its | |
* name. This function object should be used within the @c | |
* internal_vertex_constructor trait. | |
*/ | |
template<typename VertexProperty> | |
struct vertex_from_name | |
{ | |
private: | |
typedef typename internal_vertex_name<VertexProperty>::type extract_name_type; | |
typedef typename remove_cv< | |
typename remove_reference< | |
typename extract_name_type::result_type>::type>::type | |
vertex_name_type; | |
public: | |
typedef vertex_name_type argument_type; | |
typedef VertexProperty result_type; | |
VertexProperty operator()(const vertex_name_type& name) | |
{ | |
return VertexProperty(name); | |
} | |
}; | |
/** | |
* Throw an exception whenever one tries to construct a @c | |
* VertexProperty instance from its name. | |
*/ | |
template<typename VertexProperty> | |
struct cannot_add_vertex | |
{ | |
private: | |
typedef typename internal_vertex_name<VertexProperty>::type extract_name_type; | |
typedef typename remove_cv< | |
typename remove_reference< | |
typename extract_name_type::result_type>::type>::type | |
vertex_name_type; | |
public: | |
typedef vertex_name_type argument_type; | |
typedef VertexProperty result_type; | |
VertexProperty operator()(const vertex_name_type& name) | |
{ | |
boost::throw_exception(std::runtime_error("add_vertex: " | |
"unable to create a vertex from its name")); | |
} | |
}; | |
/** | |
* @brief Trait used to construct an instance of a @c VertexProperty, | |
* which is a class type that stores the properties associated with a | |
* vertex in a graph, from just the name of that vertex property. This | |
* operation is used when an operation is required to map from a | |
* vertex name to a vertex descriptor (e.g., to add an edge outgoing | |
* from that vertex), but no vertex by the name exists. The function | |
* object provided by this trait will be used to add new vertices | |
* based only on their names. Since this cannot be done for arbitrary | |
* types, the default behavior is to throw an exception when this | |
* routine is called, which requires that all named vertices be added | |
* before adding any edges by name. | |
*/ | |
template<typename VertexProperty> | |
struct internal_vertex_constructor | |
{ | |
/** | |
* The @c type field provides a function object that constructs a | |
* new instance of @c VertexProperty from the name of the vertex (as | |
* determined by @c internal_vertex_name). The function object shall | |
* accept a vertex name and return a @c VertexProperty. Predefined | |
* options include: | |
* | |
* @c vertex_from_name<VertexProperty>: construct an instance of | |
* @c VertexProperty directly from the name. | |
* | |
* @c cannot_add_vertex<VertexProperty>: the default value, which | |
* throws an @c std::runtime_error if one attempts to add a vertex | |
* given just the name. | |
*/ | |
typedef cannot_add_vertex<VertexProperty> type; | |
}; | |
#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION | |
/** | |
* Extract the internal vertex constructor from a @c property structure by | |
* looking at its base. | |
*/ | |
template<typename Tag, typename T, typename Base> | |
struct internal_vertex_constructor<property<Tag, T, Base> > | |
: internal_vertex_constructor<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 * | |
*******************************************************************/ | |
/** | |
* named_graph is a mixin that provides names for the vertices of a | |
* graph, including a mapping from names to vertices. Graph types that | |
* may or may not be have vertex names (depending on the properties | |
* supplied by the user) should use maybe_named_graph. | |
* | |
* Template parameters: | |
* | |
* Graph: the graph type that derives from named_graph | |
* | |
* Vertex: the type of a vertex descriptor in Graph. Note: we cannot | |
* use graph_traits here, because the Graph is not yet defined. | |
* | |
* VertexProperty: the type stored with each vertex in the Graph. | |
*/ | |
template<typename Graph, typename Vertex, typename VertexProperty> | |
class named_graph | |
{ | |
public: | |
/// The type of the function object that extracts names from vertex | |
/// properties. | |
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 | |
bundled_vertex_property_type; | |
/// The type of the function object that generates vertex properties | |
/// from names, for the implicit addition of vertices. | |
typedef typename internal_vertex_constructor<VertexProperty>::type | |
vertex_constructor_type; | |
/// The type used to name vertices in the graph | |
typedef typename remove_cv< | |
typename remove_reference< | |
typename extract_name_type::result_type>::type>::type | |
vertex_name_type; | |
/// The type of vertex descriptors in the graph | |
typedef Vertex vertex_descriptor; | |
private: | |
/// Key extractor for use with the multi_index_container | |
struct extract_name_from_vertex | |
{ | |
typedef vertex_name_type result_type; | |
extract_name_from_vertex(Graph& graph, const extract_name_type& extract) | |
: graph(graph), extract(extract) { } | |
const result_type& operator()(Vertex vertex) const | |
{ | |
return extract(graph[vertex]); | |
} | |
Graph& graph; | |
extract_name_type extract; | |
}; | |
public: | |
/// The type that maps names to vertices | |
typedef multi_index::multi_index_container< | |
Vertex, | |
multi_index::indexed_by< | |
multi_index::hashed_unique<multi_index::tag<vertex_name_t>, | |
extract_name_from_vertex> > | |
> named_vertices_type; | |
/// The set of vertices, indexed by name | |
typedef typename named_vertices_type::template index<vertex_name_t>::type | |
vertices_by_name_type; | |
/// Construct an instance of the named graph mixin, using the given | |
/// function object to extract a name from the bundled property | |
/// associated with a vertex. | |
named_graph(const extract_name_type& extract = extract_name_type(), | |
const vertex_constructor_type& vertex_constructor | |
= vertex_constructor_type()); | |
/// Notify the named_graph that we have added the given vertex. The | |
/// name of the vertex will be added to the mapping. | |
void added_vertex(Vertex vertex); | |
/// Notify the named_graph that we are removing the given | |
/// vertex. The name of the vertex will be removed from the mapping. | |
void removing_vertex(Vertex vertex); | |
/// Notify the named_graph that we are clearing the graph. | |
/// This will clear out all of the name->vertex mappings | |
void clearing_graph(); | |
/// Retrieve the derived instance | |
Graph& derived() { return static_cast<Graph&>(*this); } | |
const Graph& derived() const { return static_cast<const Graph&>(*this); } | |
/// Extract the name from a vertex property instance | |
typename extract_name_type::result_type | |
extract_name(const bundled_vertex_property_type& property); | |
/// Search for a vertex that has the given property (based on its | |
/// name) | |
optional<vertex_descriptor> | |
vertex_by_property(const bundled_vertex_property_type& property); | |
/// Mapping from names to vertices | |
named_vertices_type named_vertices; | |
/// Constructs a vertex from the name of that vertex | |
vertex_constructor_type vertex_constructor; | |
}; | |
/// Helper macro containing the template parameters of named_graph | |
#define BGL_NAMED_GRAPH_PARAMS \ | |
typename Graph, typename Vertex, typename VertexProperty | |
/// Helper macro containing the named_graph<...> instantiation | |
#define BGL_NAMED_GRAPH \ | |
named_graph<Graph, Vertex, VertexProperty> | |
template<BGL_NAMED_GRAPH_PARAMS> | |
BGL_NAMED_GRAPH::named_graph(const extract_name_type& extract, | |
const vertex_constructor_type& vertex_constructor) | |
: named_vertices( | |
typename named_vertices_type::ctor_args_list( | |
boost::make_tuple( | |
boost::make_tuple( | |
0, // initial number of buckets | |
extract_name_from_vertex(derived(), extract), | |
boost::hash<vertex_name_type>(), | |
std::equal_to<vertex_name_type>())))), | |
vertex_constructor(vertex_constructor) | |
{ | |
} | |
template<BGL_NAMED_GRAPH_PARAMS> | |
inline void BGL_NAMED_GRAPH::added_vertex(Vertex vertex) | |
{ | |
named_vertices.insert(vertex); | |
} | |
template<BGL_NAMED_GRAPH_PARAMS> | |
inline void BGL_NAMED_GRAPH::removing_vertex(Vertex vertex) | |
{ | |
named_vertices.erase(vertex); | |
} | |
template<BGL_NAMED_GRAPH_PARAMS> | |
inline void BGL_NAMED_GRAPH::clearing_graph() | |
{ | |
named_vertices.clear(); | |
} | |
template<BGL_NAMED_GRAPH_PARAMS> | |
typename BGL_NAMED_GRAPH::extract_name_type::result_type | |
BGL_NAMED_GRAPH::extract_name(const bundled_vertex_property_type& property) | |
{ | |
return named_vertices.key_extractor().extract(property); | |
} | |
template<BGL_NAMED_GRAPH_PARAMS> | |
optional<typename BGL_NAMED_GRAPH::vertex_descriptor> | |
BGL_NAMED_GRAPH:: | |
vertex_by_property(const bundled_vertex_property_type& property) | |
{ | |
return find_vertex(extract_name(property), *this); | |
} | |
/// Retrieve the vertex associated with the given name | |
template<BGL_NAMED_GRAPH_PARAMS> | |
optional<Vertex> | |
find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name, | |
const BGL_NAMED_GRAPH& g) | |
{ | |
typedef typename BGL_NAMED_GRAPH::vertices_by_name_type | |
vertices_by_name_type; | |
// Retrieve the set of vertices indexed by name | |
vertices_by_name_type const& vertices_by_name | |
= g.named_vertices.template get<vertex_name_t>(); | |
/// Look for a vertex with the given name | |
typename vertices_by_name_type::const_iterator iter | |
= vertices_by_name.find(name); | |
if (iter == vertices_by_name.end()) | |
return optional<Vertex>(); // vertex not found | |
else | |
return *iter; | |
} | |
/// Retrieve the vertex associated with the given name, or add a new | |
/// vertex with that name if no such vertex is available. | |
template<BGL_NAMED_GRAPH_PARAMS> | |
Vertex | |
add_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name, | |
BGL_NAMED_GRAPH& g) | |
{ | |
if (optional<Vertex> vertex = find_vertex(name, g)) | |
/// We found the vertex, so return it | |
return *vertex; | |
else | |
/// There is no vertex with the given name, so create one | |
return add_vertex(g.vertex_constructor(name), g.derived()); | |
} | |
/// Add an edge using vertex names to refer to the vertices | |
template<BGL_NAMED_GRAPH_PARAMS> | |
std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name, | |
typename BGL_NAMED_GRAPH::vertex_name_type const& v_name, | |
BGL_NAMED_GRAPH& g) | |
{ | |
return add_edge(add_vertex(u_name, g.derived()), | |
add_vertex(v_name, g.derived()), | |
g.derived()); | |
} | |
/// Add an edge using vertex descriptors or names to refer to the vertices | |
template<BGL_NAMED_GRAPH_PARAMS> | |
std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u, | |
typename BGL_NAMED_GRAPH::vertex_name_type const& v_name, | |
BGL_NAMED_GRAPH& g) | |
{ | |
return add_edge(u, | |
add_vertex(v_name, g.derived()), | |
g.derived()); | |
} | |
/// Add an edge using vertex descriptors or names to refer to the vertices | |
template<BGL_NAMED_GRAPH_PARAMS> | |
std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name, | |
typename BGL_NAMED_GRAPH::vertex_descriptor const& v, | |
BGL_NAMED_GRAPH& g) | |
{ | |
return add_edge(add_vertex(u_name, g.derived()), | |
v, | |
g.derived()); | |
} | |
#undef BGL_NAMED_GRAPH | |
#undef BGL_NAMED_GRAPH_PARAMS | |
/******************************************************************* | |
* Maybe named graph mixin * | |
*******************************************************************/ | |
#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION | |
/** | |
* A graph mixin that can provide a mapping from names to vertices, | |
* and use that mapping to simplify creation and manipulation of | |
* graphs. | |
*/ | |
template<typename Graph, typename Vertex, typename VertexProperty, | |
typename ExtractName | |
= typename internal_vertex_name<VertexProperty>::type> | |
struct maybe_named_graph : public named_graph<Graph, Vertex, VertexProperty> | |
{ | |
}; | |
/** | |
* A graph mixin that can provide a mapping from names to vertices, | |
* and use that mapping to simplify creation and manipulation of | |
* graphs. This partial specialization turns off this functionality | |
* when the @c VertexProperty does not have an internal vertex name. | |
*/ | |
template<typename Graph, typename Vertex, typename VertexProperty> | |
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 | |
bundled_vertex_property_type; | |
/// Notify the named_graph that we have added the given vertex. This | |
/// is a no-op. | |
void added_vertex(Vertex) { } | |
/// Notify the named_graph that we are removing the given | |
/// vertex. This is a no-op. | |
void removing_vertex(Vertex) { } | |
/// Notify the named_graph that we are clearing the graph. This is a | |
/// no-op. | |
void clearing_graph() { } | |
/// Search for a vertex that has the given property (based on its | |
/// name). This always returns an empty optional<> | |
optional<Vertex> | |
vertex_by_property(const bundled_vertex_property_type&) | |
{ | |
return optional<Vertex>(); | |
} | |
}; | |
#else | |
template<typename Graph, typename Vertex, typename VertexProperty, | |
typename ExtractName | |
= typename internal_vertex_name<VertexProperty>::type> | |
struct maybe_named_graph | |
{ | |
/// The type of the "bundled" property, from which the name can be | |
/// extracted. | |
typedef typename detail::extract_bundled_vertex<VertexProperty>::type | |
bundled_vertex_property_type; | |
/// Notify the named_graph that we have added the given vertex. This | |
/// is a no-op. | |
void added_vertex(Vertex) { } | |
/// Notify the named_graph that we are removing the given | |
/// vertex. This is a no-op. | |
void removing_vertex(Vertex) { } | |
/// Notify the named_graph that we are clearing the graph. This is a | |
/// no-op. | |
void clearing_graph() { } | |
/// Search for a vertex that has the given property (based on its | |
/// name). This always returns an empty optional<> | |
template<typename Property> | |
optional<Vertex> | |
vertex_by_property(const bundled_vertex_property_type&) | |
{ | |
return optional<Vertex>(); | |
} | |
}; | |
#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION | |
} } // end namespace boost::graph | |
#endif // BOOST_GRAPH_NAMED_GRAPH_HPP |