|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49178 - in trunk: boost/graph boost/graph/detail libs/graph/build libs/graph/test
From: dgregor_at_[hidden]
Date: 2008-10-08 10:51:13
Author: dgregor
Date: 2008-10-08 10:51:11 EDT (Wed, 08 Oct 2008)
New Revision: 49178
URL: http://svn.boost.org/trac/boost/changeset/49178
Log:
Add support for named vertices in adjacency_list
Added:
trunk/boost/graph/named_graph.hpp (contents, props changed)
trunk/libs/graph/test/named_vertices_test.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/adjacency_list.hpp | 16 +++++++++++++++-
trunk/boost/graph/detail/adjacency_list.hpp | 15 +++++++++++++++
trunk/libs/graph/build/Jamfile.v2 | 25 ++++++++++++++++++++++++-
trunk/libs/graph/test/Jamfile.v2 | 2 ++
4 files changed, 56 insertions(+), 2 deletions(-)
Modified: trunk/boost/graph/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/adjacency_list.hpp (original)
+++ trunk/boost/graph/adjacency_list.hpp 2008-10-08 10:51:11 EDT (Wed, 08 Oct 2008)
@@ -44,6 +44,7 @@
#include <boost/type_traits/is_same.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/graph/named_graph.hpp>
namespace boost {
@@ -333,7 +334,14 @@
#else
VertexProperty, EdgeProperty,
#endif
- GraphProperty, EdgeListS>::type
+ GraphProperty, EdgeListS>::type,
+ // Support for named vertices
+ public graph::maybe_named_graph<
+ adjacency_list<OutEdgeListS,VertexListS,DirectedS,
+ VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
+ typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS,
+ EdgeListS>::vertex_descriptor,
+ VertexProperty>
{
#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
typedef typename detail::retag_property_list<vertex_bundle_t,
@@ -434,6 +442,12 @@
*this = tmp;
}
+ void clear()
+ {
+ this->clearing_graph();
+ Base::clear();
+ }
+
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
// Directly access a vertex or edge bundle
vertex_bundled& operator[](vertex_descriptor v)
Modified: trunk/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/detail/adjacency_list.hpp (original)
+++ trunk/boost/graph/detail/adjacency_list.hpp 2008-10-08 10:51:11 EDT (Wed, 08 Oct 2008)
@@ -1902,6 +1902,7 @@
bool inserted;
boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
v->m_position = pos;
+ g.added_vertex(v);
return v;
}
// O(1)
@@ -1910,13 +1911,19 @@
add_vertex(const typename Config::vertex_property_type& p,
adj_list_impl<Derived, Config, Base>& g_)
{
+ typedef typename Config::vertex_descriptor vertex_descriptor;
Derived& g = static_cast<Derived&>(g_);
+ if (optional<vertex_descriptor> v
+ = g.vertex_by_property(get_property_value(p, vertex_bundle)))
+ return *v;
+
typedef typename Config::stored_vertex stored_vertex;
stored_vertex* v = new stored_vertex(p);
typename Config::StoredVertexList::iterator pos;
bool inserted;
boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
v->m_position = pos;
+ g.added_vertex(v);
return v;
}
// O(1)
@@ -1926,6 +1933,7 @@
{
typedef typename Config::stored_vertex stored_vertex;
Derived& g = static_cast<Derived&>(g_);
+ g.removing_vertex(u);
stored_vertex* su = (stored_vertex*)u;
g.m_vertices.erase(su->m_position);
delete su;
@@ -2171,6 +2179,7 @@
add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
Graph& g = static_cast<Graph&>(g_);
g.m_vertices.resize(g.m_vertices.size() + 1);
+ g.added_vertex(g.m_vertices.size() - 1);
return g.m_vertices.size() - 1;
}
@@ -2178,9 +2187,14 @@
inline typename Config::vertex_descriptor
add_vertex(const typename Config::vertex_property_type& p,
vec_adj_list_impl<Graph, Config, Base>& g_) {
+ typedef typename Config::vertex_descriptor vertex_descriptor;
Graph& g = static_cast<Graph&>(g_);
+ if (optional<vertex_descriptor> v
+ = g.vertex_by_property(get_property_value(p, vertex_bundle)))
+ return *v;
typedef typename Config::stored_vertex stored_vertex;
g.m_vertices.push_back(stored_vertex(p));
+ g.added_vertex(g.m_vertices.size() - 1);
return g.m_vertices.size() - 1;
}
@@ -2219,6 +2233,7 @@
{
typedef typename Config::directed_category Cat;
Graph& g = static_cast<Graph&>(g_);
+ g.removing_vertex(v);
detail::remove_vertex_dispatch(g, v, Cat());
}
// O(1)
Added: trunk/boost/graph/named_graph.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/named_graph.hpp 2008-10-08 10:51:11 EDT (Wed, 08 Oct 2008)
@@ -0,0 +1,541 @@
+// 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>
+
+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 ONLY
+ *
+ * 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 ONLY
+ *
+ * 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
Modified: trunk/libs/graph/build/Jamfile.v2
==============================================================================
--- trunk/libs/graph/build/Jamfile.v2 (original)
+++ trunk/libs/graph/build/Jamfile.v2 2008-10-08 10:51:11 EDT (Wed, 08 Oct 2008)
@@ -57,4 +57,27 @@
<toolset>msvc-8.0:<cxxflags>-GR-
;
-boost-install boost_graph ;
\ No newline at end of file
+boost-install boost_graph ;
+
+############################################################
+# Distributed-memory parallel graph library (Parallel BGL) #
+############################################################
+use-project /boost/mpi : ../../mpi/build ;
+import mpi ;
+if [ mpi.configured ]
+{
+ lib boost_graph_mpi
+ : distributed/tag_allocator.cpp
+ distributed/mpi_process_group.cpp
+ : # Requirements
+ <library>../../mpi/build//boost_mpi
+ <library>/mpi//mpi [ mpi.extra-requirements ]
+ <library>../../serialization/build//boost_serialization
+ : # Default build
+ <link>shared
+ : # Usage requirements
+ <library>../../mpi/build//boost_mpi
+ <library>/mpi//mpi [ mpi.extra-requirements ]
+ <library>../../serialization/build//boost_serialization
+ ;
+}
\ No newline at end of file
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2008-10-08 10:51:11 EDT (Wed, 08 Oct 2008)
@@ -123,6 +123,8 @@
[ run make_maximal_planar_test.cpp ]
+ [ run named_vertices_test.cpp ]
+
[ run all_planar_input_files_test.cpp
../../filesystem/build
../../system/build
Added: trunk/libs/graph/test/named_vertices_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/named_vertices_test.cpp 2008-10-08 10:51:11 EDT (Wed, 08 Oct 2008)
@@ -0,0 +1,91 @@
+// Copyright (C) 2007-2008 The Trustees of Indiana University.
+
+// 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)
+
+// Test support for named vertices in adjacency_list.
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <string>
+#include <iostream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+
+/// City structure to be attached to each vertex
+struct City {
+ City() {}
+
+ City(const std::string& name, int population = -1)
+ : name(name), population(population) { }
+
+ std::string name;
+ int population;
+};
+
+namespace boost { namespace graph {
+
+/// Use the City name as a key for indexing cities in a graph
+template<>
+struct internal_vertex_name<City>
+{
+ typedef multi_index::member<City, std::string, &City::name> type;
+};
+
+/// Allow the graph to build cities given only their names (filling in
+/// the defaults for fields).
+template<>
+struct internal_vertex_constructor<City>
+{
+ typedef vertex_from_name<City> type;
+};
+
+} } // end namespace boost::graph
+
+/// Our road map, where each of the vertices are cities
+typedef adjacency_list<vecS, vecS, directedS, City> RoadMap;
+typedef graph_traits<RoadMap>::vertex_descriptor Vertex;
+
+int test_main(int argc, char* argv[])
+{
+ RoadMap map;
+
+ /// Create vertices for Bloomington, Indianapolis, Chicago
+ Vertex bloomington = add_vertex(City("Bloomington", 69291), map);
+ Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map);
+ Vertex chicago = add_vertex(City("Chicago", 9500000), map);
+
+ BOOST_CHECK(add_vertex(City("Bloomington", 69291), map) == bloomington);
+
+ BGL_FORALL_VERTICES(city, map, RoadMap)
+ std::cout << map[city].name << ", population " << map[city].population
+ << std::endl;
+
+ BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington);
+ BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis);
+ BOOST_CHECK(*find_vertex("Chicago", map) == chicago);
+
+ add_edge(bloomington, "Indianapolis", map);
+ add_edge("Indianapolis", chicago, map);
+ add_edge("Indianapolis", "Cincinnatti", map);
+
+ BGL_FORALL_EDGES(road, map, RoadMap)
+ std::cout << map[source(road, map)].name << " -> "
+ << map[target(road, map)].name << std::endl;
+
+ BOOST_CHECK(map[*find_vertex("Cincinnatti", map)].population == -1);
+
+ return 0;
+}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk