From: asutton_at_[hidden]
Date: 2008-07-20 11:40:59
Author: asutton
Date: 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
New Revision: 47633
URL: http://svn.boost.org/trac/boost/changeset/47633
Log:
Imported and rewrote property map implementation. This includes the definition
and implementation of associative container adapters for vertices and edges,
and the implementation of interior/exterior property maps.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_property_map.hpp
- copied, changed from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_properties.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/container_property_map.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_property_container.hpp
- copied, changed from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_property_container.hpp
- copied, changed from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_property_map.hpp
- copied, changed from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_properties.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp (contents, props changed)
Removed:
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_properties.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_properties.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 16 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 7
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 9 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp | 3
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp | 3
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp | 5
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp | 203 ++++++++++++++-------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_property_map.hpp | 68 ++----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_property_container.hpp | 42 +-------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_property_container.hpp | 44 +-------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_property_map.hpp | 47 ++------
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 11 +
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 28 +---
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot | 39 +++++++
14 files changed, 207 insertions(+), 318 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -6,7 +6,9 @@
/**
* A directed edge represents an edge in a directed graph. A directed edge is
- * uniquely identified by its source and target vertices and edge property.
+ * uniquely identified by its source and target vertices the descriptor into
+ * the source vertex's out edge list, which also happens to uniquely describe
+ * the edge property, if applicable.
*
* @param VertexDesc A vertex descriptor
* @param OutDesc An out edge descriptor.
@@ -94,7 +96,6 @@
std::size_t hash_value(directed_edge<O,I> const& e)
{
using boost::hash;
- std::cout << e.out << std::endl;
return hash_value(e.out);
}
@@ -124,12 +125,14 @@
: store(0), vert(), edge()
{ }
+ directed_edge_iterator(vertex_store& s)
+ : store(&s), vert(store->end_vertices()), edge()
+ { }
+
directed_edge_iterator(vertex_store& s, vertex_iterator i)
: store(&s)
, vert(i)
- , edge(next(vert == store->end_vertices()
- ? edge_iterator()
- : vertex().begin_out(), true))
+ , edge(next(vertex().begin_out(), true))
{ }
/** Locate the next valid edge iterator, skipping the update on init. */
@@ -148,7 +151,8 @@
// If after incrementing, we reach the end of the vertices, then
// we have to skip to the next non-empty vertex or the end of the
// sequence, whichever comes first.
- while(e == vertex().end_out() && vert != store->end_vertices()) {
+ while(vert != store->end_vertices() && e == vertex().end_out())
+ {
++vert;
e = vertex().begin_out();
}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -800,7 +800,7 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_iterator
directed_graph<VP,EP,VS,ES>::end_edges() const
-{ return edge_iterator(_verts, _verts.end_vertices()); }
+{ return edge_iterator(_verts); }
/** Return an iterator range over the edges in the graph. */
template <BOOST_GRAPH_DG_PARAMS>
@@ -929,7 +929,10 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_properties&
directed_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
-{ return e.properties(); }
+{
+ vertex_type& vert = _verts.vertex(e.source());
+ return vert.get_edge_properties(e.out_edge());
+}
#undef BOOST_GRAPH_DG_PARAMS
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -66,13 +66,20 @@
{ return _out.find(v); }
//@}
- /** @name Property Accessors */
+ /** @name Vertex Property Accessors */
//@{
inline vertex_properties& properties()
{ return _props; }
inline vertex_properties const& properties() const
{ return _props; }
+
+ // Return the edge properties for the given out edge descriptor.
+ inline edge_properties& get_edge_properties(out_descriptor o)
+ { return _out.properties(o); }
+
+ inline edge_properties const& get_edge_properties(out_descriptor o) const
+ { return _out.properties(o); }
//@}
/** Return the reverse out descriptor for the given in edge. */
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -104,6 +104,9 @@
{ return make_iterator(_edges, o)->first; }
/** Return the properties stored with this edge. */
+ inline edge_properties& properties(out_descriptor o)
+ { return make_iterator(_edges, o)->second.first; }
+
inline edge_properties const& properties(out_descriptor o) const
{ return make_iterator(_edges, o)->second.first; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -99,6 +99,9 @@
{ return make_iterator(_edges, o)->first; }
/** Return the properties stored with this edge. */
+ inline edge_properties& properties(out_descriptor o)
+ { return make_iterator(_edges, o)->second.first; }
+
inline edge_properties const& properties(out_descriptor o) const
{ return make_iterator(_edges, o)->second.first; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -79,10 +79,15 @@
inline vertex_descriptor target(out_descriptor o) const
{ return make_iterator(_edges, o)->first; }
+
/** Return the properties stored with this edge. */
+ inline edge_properties& properties(out_descriptor o)
+ { return make_iterator(_edges, o)->second.first; }
+
inline edge_properties const& properties(out_descriptor o) const
{ return make_iterator(_edges, o)->second.first; }
+
/** Return the in edge descriptor bound to this edge. */
inline in_descriptor in_edge(out_descriptor o) const
{ return make_iterator(_edges, o)->second.second; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -2,51 +2,50 @@
#ifndef PROPERTIES_HPP
#define PROPERTIES_HPP
-#include <vector>
-#include <tr1/unordered_map>
+#include <boost/descriptors.hpp>
-#include <boost/type_traits.hpp>
-#include <boost/mpl/if.hpp>
+// Include associative adpaters for exterior properties.
+#include "property_map/hashed_property_container.hpp"
+#include "property_map/indexed_property_container.hpp"
+
+// Include property map implementations.
+#include "property_map/container_property_map.hpp"
+#include "property_map/simple_property_map.hpp"
+#include "property_map/bundled_property_map.hpp"
+
+// TODO: We currently distinguish between exterior and interior using the names
+// of the structures...
+
+// Define the mapping strategy based on the type of descriptor. By default,
+// we prefer to use hashing since the number of data structures that actually
+// index their vertices is... tiny.
+struct index_mapping { };
+struct hash_mapping { };
+
+template <typename Descriptor>
+struct descriptor_mapping
+{ typedef hash_mapping strategy; };
+
+template <typename Index>
+struct descriptor_mapping<index_descriptor<Index>>
+{ typedef index_mapping strategy;};
-#include "vertex_vector.hpp"
-#include "edge_vector.hpp"
-
-#include "property_map/hashed_properties.hpp"
-#include "property_map/indexed_properties.hpp"
-
-// All the fun of exterior properties... We need a mechanism that determines
-// the underlying mapping type of exterior properties. For vector-based stores
-// we can simply map each vertex to its corresponding element in another vector.
-// For non-vector-based stores, it's easier to use a hash of the descriptor.
-
-// We need a metafunction to determine whether or not a vertex set allows
-// indexed or hashed exterior properties. By default, we should assume that
-// we're using hash tables (they're more flexible).
-
-template <typename VertexStore>
-struct use_hashing
-{ BOOST_STATIC_CONSTANT(bool, value = true); };
-
-// Specialize over the basic vertex vector and edge vector.
-template <template <typename> class Alloc>
-struct use_hashing< vertex_vector<Alloc> >
-{ BOOST_STATIC_CONSTANT(bool, value = false); };
-
-template <template <typename> class Alloc>
-struct use_hashing< edge_vector<Alloc> >
-{ BOOST_STATIC_CONSTANT(bool, value = false); };
-
-// Select the type of container based on the underlying store selector
+// Select the type of container based on the underlying store selector.
template <typename Selector, typename Descriptor, typename Property>
struct choose_container
{
typedef typename boost::mpl::if_<
- use_hashing<Selector>,
+ boost::is_same<
+ typename descriptor_mapping<Descriptor>::strategy,
+ hash_mapping>,
hashed_property_container<Descriptor, Property>,
indexed_property_container<Descriptor, Property>
>::type type;
};
+/**
+ * Used to cotnain exterior vertex properties.
+ */
template <typename Graph, typename Property>
struct exterior_vertex_property
: choose_container<
@@ -57,122 +56,68 @@
typename Graph::vertex_store_selector, typename Graph::vertex_descriptor, Property
>::type base_type;
- exterior_vertex_property(Graph const& g)
- : base_type(g.num_vertices())
- { }
-
- exterior_vertex_property(Graph const& g, Property const& p)
+ exterior_vertex_property(Graph const& g, Property const& p = Property())
: base_type(g.begin_vertices(), g.end_vertices(), p)
{ }
};
+/**
+ * Used to contain exterior edge properties.
+ *
+ * @todo It turns out that undirected edge_vectors can use vectors to store
+ * properties. This is because the edge descriptor is basically just returning
+ * the index into the vector as a key.
+ */
template <typename Graph, typename Property>
struct exterior_edge_property
: hashed_property_container<typename Graph::edge_descriptor, Property>
{
typedef hashed_property_container<typename Graph::edge_descriptor, Property> base_type;
- exterior_edge_property(const Graph& g)
- : base_type(g.num_edges())
- { }
-
- exterior_edge_property(Graph const& g, Property const& p)
+ exterior_edge_property(Graph const& g, Property const& p = Property())
: base_type(g.begin_edges(), g.end_edges(), p)
{ }
};
-#if 0
-
-// For now, these tags are used to actually decide the underlying implementation
-// of the property map.
-struct indexed_property_map_tag { };
-struct hashed_property_map_tag { };
-
-template <typename Tag, typename Iterator, typename Property>
-struct exterior_property
-{
- typedef typename mpl::if_<
- is_same<Tag, hashed_property_map_tag>,
- hashed_property_container<Iterator, Property>,
- indexed_property_container<Iterator, Property>
- >::type container_type;
-
- typedef typename mpl::if_<
- is_same<Tag, hashed_property_map_tag>, // predicate
- hashed_property_map<Iterator, Property>, // on true
- indexed_property_map<Iterator, Property> // on false
- >::type map_type;
-};
-
-template <typename Graph, typename Property>
-struct exterior_vertex_property
-{
- typedef exterior_property<
- typename Graph::vertex_property_map_category,
- typename Graph::vertex_iterator,
- Property
- > base_type;
- typedef typename base_type::container_type container_type;
- typedef typename base_type::map_type map_type;};
-
-template <typename Graph, typename Property>
-struct exterior_edge_property
-{
- typedef exterior_property<
- typename Graph::edge_property_map_category,
- typename Graph::edge_iterator,
- Property
- > base_type;
- typedef typename base_type::container_type container_type;
- typedef typename base_type::map_type map_type;
-
-};
-
-
-// Interior properties aer also a great deal of fun.
-
-template <typename Graph, typename Property = typename Graph::vertex_properties>
-struct interior_vertex_property
+/**
+ * The property map structure provides a funtional abstraction over the
+ * associative mapping provided by some type (or set of types). The default
+ * implementation is constructed over an associative container.
+ *
+ * @requires AssociativeContainer<Container>
+ */
+template <typename Container>
+struct exterior_property_map
+ : container_property_map<Container>
{
- typedef simple_property_map<
- Graph,
- typename Graph::vertex_descriptor,
- typename Graph::vertex_properties
- > map_type;
-};
-
-template <typename Graph, typename Bundle, typename Property>
-struct interior_vertex_property<Graph, Property Bundle::*>
-{
- typedef bundled_property_map<
- Graph,
- typename Graph::vertex_descriptor,
- Bundle,
- Property
- > map_type;
+ exterior_property_map(Container& cont)
+ : container_property_map<Container>(cont)
+ { }
};
-template <typename Graph, typename Property = typename Graph::vertex_properties>
-struct interior_edge_property
+/**
+ * The interior property map defines a property map over the interior properties
+ * of a vertex. Although this takes 3 parameters, you should always use default
+ * value of the 3rd parameter. The Key parameter must either be the vertex
+ * or edge descriptor type of the graph.
+ */
+template <typename Graph, typename Key, typename Property = typename Graph::vertex_properties>
+struct interior_property_map
+ : simple_property_map<Graph, Key, Property>
{
- typedef simple_property_map<
- Graph,
- typename Graph::edge_descriptor,
- typename Graph::edge_properties
- > map_type;
+ interior_property_map(Graph& g)
+ : simple_property_map<Graph, Key, Property>(g)
+ { }
};
-template <typename Graph, typename Bundle, typename Property>
-struct interior_edge_property<Graph, Property Bundle::*>
+/** A specialization of the above for members of the vertex/edge label. */
+template <typename Graph, typename Key, typename Bundle, typename Property>
+struct interior_property_map<Graph, Key, Property Bundle::*>
+ : bundled_property_map<Graph, Key, Bundle, Property>
{
- typedef bundled_property_map<
- Graph,
- typename Graph::edge_descriptor,
- Bundle,
- Property
- > map_type;
+ interior_property_map(Graph& g, Property Bundle::* b)
+ : bundled_property_map<Graph, Key, Bundle, Property>(g, b)
+ { }
};
#endif
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_properties.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
+++ (empty file)
@@ -1,69 +0,0 @@
-
-#ifndef BOOST_GRAPHS_PROPERTY_MAP_BUNDLED_PROPERTIES_HPP
-#define BOOST_GRAPHS_PROPERTY_MAP_BUNDLED_PROPERTIES_HPP
-
-namespace boost {
-namespace graphs {
-
-/**
- * A simple property map provides get/put functions for non-bundled or simple
- * vertex and edge properties. This is not called "simple" because it is
- * trivially implemented but because it return the properties assigned to the
- * vertex or edge (depending on the descriptor) without any indirection. To
- * build property maps over members or a structured (or bundled) property,
- * use the bundled property map.
- */
-template <typename Graph, typename Descriptor, typename Bundle, typename Property>
-struct bundled_property_map
-{
- typedef Descriptor key_type;
- typedef Property property_type;
-
- inline bundled_property_map(Graph& g, Property Bundle::* mem)
- : graph(g)
- , member(mem)
- { }
-
- inline bundled_property_map(bundled_property_map const& x)
- : graph(x.g)
- , member(x.mem)
- { }
-
- inline Bundle const& bundle(key_type const& k) const
- { return graph.properties(k); }
-
- inline Bundle& bundle(key_type const& k)
- { return graph.properties(k); }
-
-
- inline Property const& get(key_type const& k) const
- { return bundle(k).*member; }
-
- inline void put(key_type const& k, Property const& v)
- { bundle(k).*member = v; }
-
- Graph& graph;
- Property Bundle::* member;
-};
-
-template <typename G, typename D, typename B, typename P>
-typename bundled_property_map<G,D,B,P>::property_type const&
-get(bundled_property_map<G,D,B,P> const& pm,
- typename bundled_property_map<G,D,B,P>::key_type const& k)
-{
- return pm.get(k);
-}
-
-template <typename G, typename D, typename B, typename P>
-void
-put(bundled_property_map<G,D,B,P>& pm,
- typename bundled_property_map<G,D,B,P>::key_type const& k,
- typename bundled_property_map<G,D,B,P>::property_type const& v)
-{
- pm.put(k, v);
-}
-
-} /* namesapce graphs */
-} /* namespace boost */
-
-#endif
Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_property_map.hpp (from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_properties.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/bundled_property_map.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -1,69 +1,29 @@
-#ifndef BOOST_GRAPHS_PROPERTY_MAP_BUNDLED_PROPERTIES_HPP
-#define BOOST_GRAPHS_PROPERTY_MAP_BUNDLED_PROPERTIES_HPP
-
-namespace boost {
-namespace graphs {
+#ifndef BUNDLED_PROPERTY_MAP_HPP
+#define BUNDLED_PROPERTY_MAP_HPP
/**
- * A simple property map provides get/put functions for non-bundled or simple
- * vertex and edge properties. This is not called "simple" because it is
- * trivially implemented but because it return the properties assigned to the
- * vertex or edge (depending on the descriptor) without any indirection. To
- * build property maps over members or a structured (or bundled) property,
- * use the bundled property map.
+ * The bundled property map provides a "slicing" property map for vertex or
+ * edge properties that are defined by compound types (structs or classes).
*/
-template <typename Graph, typename Descriptor, typename Bundle, typename Property>
+template <typename Graph, typename Key, typename Bundle, typename Property>
struct bundled_property_map
{
- typedef Descriptor key_type;
- typedef Property property_type;
-
- inline bundled_property_map(Graph& g, Property Bundle::* mem)
- : graph(g)
- , member(mem)
- { }
+ typedef Key key_type;
+ typedef Property value_type;
- inline bundled_property_map(bundled_property_map const& x)
- : graph(x.g)
- , member(x.mem)
+ inline bundled_property_map(Graph& g, Property Bundle::* b)
+ : graph(g), bundle(b)
{ }
- inline Bundle const& bundle(key_type const& k) const
- { return graph.properties(k); }
-
- inline Bundle& bundle(key_type const& k)
- { return graph.properties(k); }
-
-
- inline Property const& get(key_type const& k) const
- { return bundle(k).*member; }
+ inline value_type& operator()(key_type const& k)
+ { return graph[k].*bundle; }
- inline void put(key_type const& k, Property const& v)
- { bundle(k).*member = v; }
+ inline value_type const& operator()(key_type const& k) const
+ { return graph[k].*bundle; }
Graph& graph;
- Property Bundle::* member;
+ Property Bundle::* bundle;
};
-template <typename G, typename D, typename B, typename P>
-typename bundled_property_map<G,D,B,P>::property_type const&
-get(bundled_property_map<G,D,B,P> const& pm,
- typename bundled_property_map<G,D,B,P>::key_type const& k)
-{
- return pm.get(k);
-}
-
-template <typename G, typename D, typename B, typename P>
-void
-put(bundled_property_map<G,D,B,P>& pm,
- typename bundled_property_map<G,D,B,P>::key_type const& k,
- typename bundled_property_map<G,D,B,P>::property_type const& v)
-{
- pm.put(k, v);
-}
-
-} /* namesapce graphs */
-} /* namespace boost */
-
#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/container_property_map.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/container_property_map.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -0,0 +1,25 @@
+
+#ifndef CONTAINER_PROPERTY_MAP_HPP
+#define CONTAINER_PROPERTY_MAP_HPP
+
+template <typename Container>
+struct container_property_map
+{
+ typedef typename Container::key_type key_type;
+ typedef typename Container::value_type value_type;
+ typedef value_type& reference;
+
+ container_property_map(Container& cont)
+ : container(cont)
+ { }
+
+ value_type& operator()(key_type const& key)
+ { return container[key]; }
+
+ value_type const& operator()(key_type const& key) const
+ { return container[key]; }
+
+ Container& container;
+};
+
+#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
+++ (empty file)
@@ -1,126 +0,0 @@
-
-#ifndef HASHED_PROPERTIES_HPP
-#define HASHED_PROPERTIES_HPP
-
-#include <tr1/unordered_map>
-
-#include <boost/functional/hash.hpp>
-
-namespace detail {
-
-/**
- * Wrap an iterator with a default value so that it generates default values
- * over a range of keys.
- */
-template <typename Iter, typename Prop>
-struct key_value_iterator
-{
- typedef typename std::forward_iterator_tag iterator_category;
- typedef typename std::size_t difference_type;
-
- typedef std::pair<typename Iter::value_type, Prop> value_type;
- typedef value_type reference;
- typedef value_type pointer;
-
- key_value_iterator(Iter i)
- : iter(i)
- , value()
- { }
-
- key_value_iterator(Iter i, Prop const& p)
- : iter(i)
- , value(p)
- { }
-
- key_value_iterator& operator++()
- { ++iter; return *this; }
-
- reference operator*()
- { return make_pair(*iter, value); }
-
- bool operator==(key_value_iterator const& x) const
- { return iter == x.iter; }
-
- bool operator!=(key_value_iterator const& x) const
- { return iter != x.iter; }
-
- Iter iter;
- Prop value;
-};
-
-template <typename Iter, typename Prop>
-inline key_value_iterator<Iter, Prop>
-make_key_value_iterator(Iter i, Prop const& x)
-{ return key_value_iterator<Iter, Prop>(i, x); }
-
-} // namespace detail
-
-/**
- * A simple wrapper around an unordered map, this is used to map descriptors
- * to arbitrary property values. Note that the property type must be default
- * constructible.
- *
- * This may seem a little odd because we're passing an iterator and not the key
- * type. However, the key type is always the iterator's value type.
- */
-template <typename Descriptor, typename Property>
-class hashed_property_container
-{
-public:
- typedef Property value_type;
- typedef Descriptor key_type;
- typedef std::tr1::unordered_map<
- key_type, value_type, boost::hash<key_type>
- > container_type;
-
- /**
- * Construct the hashtable over n buckets. This may not actually allocate
- * n buckets, so we can't necessarily guarantee that memory will actually
- * be allocated for each element, much less what those default values would
- * actually be.
- */
- hashed_property_container(std::size_t n)
- : data(n)
- { }
-
- /**
- * Construct the hashtable over the keys in the iterator range [f, l) with
- * the default value x.
- */
- template <typename Iter>
- hashed_property_container(Iter f, Iter l, value_type const& x)
- : data(detail::make_key_value_iterator(f, x),
- detail::make_key_value_iterator(l, value_type()))
- { }
-
- // Get the property associated with the key k.
- inline value_type& operator[](key_type const& k)
- { return data[k]; }
-
- container_type data;
-};
-
-/**
- * The corresponding property map implements a lightweight, regular accessor
- * to a hashed property container.
- */
-template <typename Iterator, typename Property>
-class hashed_property_map
-{
- typedef hashed_property_container<Iterator, Property> container_type;
-public:
- typedef typename container_type::value_type property_type;
- typedef typename container_type::key_type key_type;
-
- hashed_property_map(container_type& cont)
- : data(cont)
- { }
-
- hashed_property_map(hashed_property_map const& x)
- : data(x.data)
- { }
-
- container_type& data;
-};
-
-#endif
Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_property_container.hpp (from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_property_container.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -22,14 +22,8 @@
typedef value_type reference;
typedef value_type pointer;
- key_value_iterator(Iter i)
- : iter(i)
- , value()
- { }
-
key_value_iterator(Iter i, Prop const& p)
- : iter(i)
- , value(p)
+ : iter(i), value(p)
{ }
key_value_iterator& operator++()
@@ -69,9 +63,7 @@
public:
typedef Property value_type;
typedef Descriptor key_type;
- typedef std::tr1::unordered_map<
- key_type, value_type, boost::hash<key_type>
- > container_type;
+ typedef std::tr1::unordered_map<key_type, value_type, boost::hash<key_type>> container_type;
/**
* Construct the hashtable over n buckets. This may not actually allocate
@@ -89,38 +81,16 @@
*/
template <typename Iter>
hashed_property_container(Iter f, Iter l, value_type const& x)
- : data(detail::make_key_value_iterator(f, x),
- detail::make_key_value_iterator(l, value_type()))
+ : data(detail::make_key_value_iterator(f, x), detail::make_key_value_iterator(l, value_type()))
{ }
- // Get the property associated with the key k.
inline value_type& operator[](key_type const& k)
{ return data[k]; }
- container_type data;
-};
-
-/**
- * The corresponding property map implements a lightweight, regular accessor
- * to a hashed property container.
- */
-template <typename Iterator, typename Property>
-class hashed_property_map
-{
- typedef hashed_property_container<Iterator, Property> container_type;
-public:
- typedef typename container_type::value_type property_type;
- typedef typename container_type::key_type key_type;
-
- hashed_property_map(container_type& cont)
- : data(cont)
- { }
-
- hashed_property_map(hashed_property_map const& x)
- : data(x.data)
- { }
+ inline value_type const& operator[](key_type const& k) const
+ { return data[k]; }
- container_type& data;
+ container_type data;
};
#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
+++ (empty file)
@@ -1,117 +0,0 @@
-
-#ifndef INDEXED_PROPERTIES_HPP
-#define INDEXED_PROPERTIES_HPP
-
-#include <iterator>
-#include <vector>
-
-namespace detail {
-
-/**
- * Wrap an iterator with a default value so that it generates default values
- * over a range of keys.
- */
-template <typename Iter, typename Prop>
-struct default_value_iterator
-{
- typedef typename std::forward_iterator_tag iterator_category;
- typedef std::size_t difference_type;
-
- typedef Prop value_type;
- typedef value_type const& reference;
- typedef value_type const* pointer;
-
- default_value_iterator(Iter i)
- : iter(i)
- , value()
- { }
-
- default_value_iterator(Iter i, Prop const& p)
- : iter(i)
- , value(p)
- { }
-
- default_value_iterator& operator++()
- { ++iter; return *this; }
-
- reference operator*()
- { return value; }
-
- bool operator==(default_value_iterator const& x) const
- { return iter == x.iter; }
-
- bool operator!=(default_value_iterator const& x) const
- { return iter != x.iter; }
-
- Iter iter;
- Prop value;
-};
-
-template <typename Iter, typename Prop>
-inline default_value_iterator<Iter, Prop>
-make_default_value_iterator(Iter i, Prop const&)
-{ return default_value_iterator<Iter, Prop>(i); }
-
-} // namespace detail
-
-
-/**
- * A simple wrapper around a vector. Because the "key" to this vector is
- * actually given as a descriptor, we have to get the underlying index that
- * allows us to map this value to a property.
- *
- * This definitely rquires that the descriptor values be continuous.
- */
-template <typename Descriptor, typename Property>
-struct indexed_property_container
-{
- typedef Property value_type;
- typedef Descriptor key_type;
- typedef std::vector<Property> container_type;
-
- inline indexed_property_container(std::size_t n)
- : data(n)
- { }
-
- /**
- * Construct the hashtable over the keys in the iterator range [f, l) with
- * the default value x.
- */
- template <typename Iter>
- inline indexed_property_container(Iter f, Iter l, value_type const& x)
- : data(detail::make_default_value_iterator(f, x),
- detail::make_default_value_iterator(l, value_type()))
- { }
-
- inline value_type& operator[](key_type const& k)
- { return data[k.get()]; }
-
- container_type data;
-};
-
-
-/**
- * The corresponding property map implements a lightweight, regular accessor
- * to a indexed property container.
- */
-template <typename Iterator, typename Property>
-struct indexed_property_map
-{
- typedef indexed_property_container<Iterator, Property> container_type;
-
- typedef typename container_type::value_type property_type;
- typedef typename container_type::key_type key_type;
-
- indexed_property_map(container_type& cont)
- : data(cont)
- { }
-
- indexed_property_map(indexed_property_map const& x)
- : data(x.data)
- { }
-
- container_type& data;
-};
-
-
-#endif
Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_property_container.hpp (from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_property_container.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -21,14 +21,8 @@
typedef value_type const& reference;
typedef value_type const* pointer;
- default_value_iterator(Iter i)
- : iter(i)
- , value()
- { }
-
default_value_iterator(Iter i, Prop const& p)
- : iter(i)
- , value(p)
+ : iter(i), value(p)
{ }
default_value_iterator& operator++()
@@ -49,8 +43,8 @@
template <typename Iter, typename Prop>
inline default_value_iterator<Iter, Prop>
-make_default_value_iterator(Iter i, Prop const&)
-{ return default_value_iterator<Iter, Prop>(i); }
+make_default_value_iterator(Iter i, Prop const& p)
+{ return default_value_iterator<Iter, Prop>(i, p); }
} // namespace detail
@@ -79,38 +73,16 @@
*/
template <typename Iter>
inline indexed_property_container(Iter f, Iter l, value_type const& x)
- : data(detail::make_default_value_iterator(f, x),
- detail::make_default_value_iterator(l, value_type()))
+ : data(detail::make_default_value_iterator(f, x), detail::make_default_value_iterator(l, value_type()))
{ }
inline value_type& operator[](key_type const& k)
- { return data[k.get()]; }
-
- container_type data;
-};
+ { return data[k.value]; }
+ inline value_type const& operator[](key_type const& k) const
+ { return data[k.value]; }
-/**
- * The corresponding property map implements a lightweight, regular accessor
- * to a indexed property container.
- */
-template <typename Iterator, typename Property>
-struct indexed_property_map
-{
- typedef indexed_property_container<Iterator, Property> container_type;
-
- typedef typename container_type::value_type property_type;
- typedef typename container_type::key_type key_type;
-
- indexed_property_map(container_type& cont)
- : data(cont)
- { }
-
- indexed_property_map(indexed_property_map const& x)
- : data(x.data)
- { }
-
- container_type& data;
+ container_type data;
};
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_properties.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
+++ (empty file)
@@ -1,53 +0,0 @@
-
-#ifndef BOOST_GRAPHS_PROPERTY_MAP_SIMPLE_PROPERTIES_HPP
-#define BOOST_GRAPHS_PROPERTY_MAP_SIMPLE_PROPERTIES_HPP
-
-namespace boost {
-namespace graphs {
-
-/**
- * A simple property map provides get/put functions for non-bundled or simple
- * vertex and edge properties. This is not called "simple" because it is
- * trivially implemented but because it return the properties assigned to the
- * vertex or edge (depending on the descriptor) without any indirection. To
- * build property maps over members or a structured (or bundled) property,
- * use the bundled property map.
- */
-template <typename Graph, typename Descriptor, typename Property>
-struct simple_property_map
-{
- typedef Descriptor key_type;
- typedef Property property_type;
-
- simple_property_map(Graph& g)
- : graph(g)
- { }
-
- simple_property_map(simple_property_map const& x)
- : graph(x.g)
- { }
-
- Graph& graph;
-};
-
-template <typename G, typename D, typename P>
-typename simple_property_map<G,D,P>::property_type const&
-get(simple_property_map<G,D,P> const& pm,
- typename simple_property_map<G,D,P>::key_type const& x)
-{
- return pm.graph.properties(x);
-}
-
-template <typename G, typename D, typename P>
-void
-put(simple_property_map<G,D,P>& pm,
- typename simple_property_map<G,D,P>::key_type const& x,
- typename simple_property_map<G,D,P>::property_type const& v)
-{
- pm.graph.properties(x) = v;
-}
-
-} /* namesapce graphs */
-} /* namespace boost */
-
-#endif
Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_property_map.hpp (from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_properties.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/simple_property_map.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -1,9 +1,6 @@
-#ifndef BOOST_GRAPHS_PROPERTY_MAP_SIMPLE_PROPERTIES_HPP
-#define BOOST_GRAPHS_PROPERTY_MAP_SIMPLE_PROPERTIES_HPP
-
-namespace boost {
-namespace graphs {
+#ifndef SIMPLE_PROPERTY_MAP_HPP
+#define SIMPLE_PROPERTY_MAP_HPP
/**
* A simple property map provides get/put functions for non-bundled or simple
@@ -12,42 +9,28 @@
* vertex or edge (depending on the descriptor) without any indirection. To
* build property maps over members or a structured (or bundled) property,
* use the bundled property map.
+ *
+ * Note that this works because all graph types overload the [] operators to
+ * return either vertex or edge properties depending on key type.
*/
-template <typename Graph, typename Descriptor, typename Property>
+template <typename Graph, typename Key, typename Property>
struct simple_property_map
{
- typedef Descriptor key_type;
- typedef Property property_type;
+ typedef Key key_type;
+ typedef Property value_type;
+ typedef value_type& reference;
- simple_property_map(Graph& g)
+ inline simple_property_map(Graph& g)
: graph(g)
{ }
- simple_property_map(simple_property_map const& x)
- : graph(x.g)
- { }
+ inline value_type& operator()(key_type const& key)
+ { return graph[key]; }
+
+ inline value_type const& operator()(key_type const& key) const
+ { return graph[key]; }
Graph& graph;
};
-template <typename G, typename D, typename P>
-typename simple_property_map<G,D,P>::property_type const&
-get(simple_property_map<G,D,P> const& pm,
- typename simple_property_map<G,D,P>::key_type const& x)
-{
- return pm.graph.properties(x);
-}
-
-template <typename G, typename D, typename P>
-void
-put(simple_property_map<G,D,P>& pm,
- typename simple_property_map<G,D,P>::key_type const& x,
- typename simple_property_map<G,D,P>::property_type const& v)
-{
- pm.graph.properties(x) = v;
-}
-
-} /* namesapce graphs */
-} /* namespace boost */
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -104,14 +104,17 @@
std::ostream& operator<<(std::ostream& os, undirected_edge<V,P> const& e)
{ return os << "{" << e.first() << " " << e.second() << "}"; }
+/**
+ * The hash value of edges can be computed over the hash value of the property
+ * descriptors. This is because the property descriptor provides a global
+ * context for the edge.
+ */
template <typename V, typename P>
inline std::size_t
hash_value(undirected_edge<V,P> const& e)
{
- std::size_t seed;
- boost::hash_combine(seed, e.ends);
- boost::hash_combine(seed, e.prop);
- return seed;
+ using boost::hash;
+ return hash_value(e.prop);
}
/**
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -1,26 +1,18 @@
-
-# Import a newer version of g++ and configure it for C++0x support.
-using gcc : 4.4 : g++-4.4 : <cxxflags>-std=c++0x ;
-
-# Build all subrojects using g++-4.4
-project graphs
- : requirements <toolset>gcc-4.4
- ;
-
-
# exe set : set.cpp : <include>../../ <include>/usr/local/include ;
# exe map : map.cpp : <include>../../ <include>/usr/local/include ;
# exe props : props.cpp : <include>../../ <include>/usr/local/include ;
# exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;
# exe desc : desc.cpp : <include>../../ <include>/usr/local/include ;
-exe test_verts : test_verts.cpp : <include>../../ ;
-exe test_props : test_props.cpp : <include>../../ ;
-exe test_incs : test_incs.cpp : <include>../../ ;
-exe test_outs : test_outs.cpp : <include>../../ ;
-exe test_ins : test_ins.cpp : <include>../../ ;
-exe test_es : test_es.cpp : <include>../../ ;
+exe test_verts : test_verts.cpp ;
+exe test_props : test_props.cpp ;
+exe test_incs : test_incs.cpp ;
+exe test_outs : test_outs.cpp ;
+exe test_ins : test_ins.cpp ;
+exe test_es : test_es.cpp ;
+
+exe un : un.cpp ;
+exe di : di.cpp ;
-exe un : un.cpp : <include>../../ ;
-exe di : di.cpp : <include>../../ ;
+exe propmaps : propmaps.cpp ;
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamroot 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -0,0 +1,39 @@
+
+import modules ;
+import path ;
+
+# Import a newer version of g++ and configure it for C++0x support.
+using gcc : 4.4 : g++-4.4 : <cxxflags>-std=c++0x ;
+
+# Define the boost root for this and nested projects. This shouold try to pull
+# a specification from the build.
+local boost-root = [ modules.peek : BOOST_ROOT ] ;
+if ! $(boost-root)
+{
+ local boost-search-dirs = [ modules.peek : BOOST_BUILD_PATH ] ;
+
+ for local dir in $(boost-search-dirs)
+ {
+ if [ path.glob $(dir)/../../../ : boost/version.hpp ]
+ {
+ boost-root += $(dir)/../../../ ;
+ }
+ }
+
+ if $(boost-root)
+ {
+ boost-root = [ path.make $(boost-root[1]) ] ;
+ }
+ else
+ {
+ ECHO "Warning: couldn't find BOOST_ROOT in" $(boost-root) ;
+ }
+}
+
+# Build all subrojects using g++-4.4
+project graphs
+ : requirements
+ <toolset>gcc-4.4
+ <include>$(boost-root)
+ <include>../..
+ ;
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp 2008-07-20 11:40:57 EDT (Sun, 20 Jul 2008)
@@ -0,0 +1,133 @@
+
+#include <iostream>
+#include <iterator>
+
+#include <boost/lexical_cast.hpp>
+#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/directed_graph.hpp>
+#include <boost/graphs/properties.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+template <typename Graph>
+void test_props()
+{
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::vertex_properties VertexProps;
+ typedef typename Graph::edge_descriptor Edge;
+ typedef typename Graph::edge_properties EdgeProps;
+
+ Graph g;
+ cout << "--- " << typestr(g) << " ---" << endl;
+
+ // Create a fully connected graph.
+ const int N = 5;
+ for(int i = 0; i < N; ++i) {
+ Vertex u = g.add_vertex(i);
+ }
+ int x = 0;
+ typename Graph::vertex_range rng = g.vertices();
+ for( ; rng.first != rng.second; ++rng.first) {
+ typename Graph::vertex_iterator i = g.begin_vertices();
+ for( ; i != rng.first; ++i) {
+ Edge e = g.add_edge(*i, *rng.first, x++);
+ }
+ }
+ cout << g.num_vertices() << " x " << g.num_edges() << endl;
+
+ typedef exterior_vertex_property<Graph, double> VertexWeightProp;
+ typedef exterior_property_map<VertexWeightProp> VertexWeightMap;
+ VertexWeightProp vertex_weights(g, 6.28);
+ VertexWeightMap vw(vertex_weights);
+
+ typedef exterior_edge_property<Graph, double> EdgeWeightProp;
+ typedef exterior_property_map<EdgeWeightProp> EdgeWeightMap;
+ EdgeWeightProp edge_weights(g, 3.14);
+ EdgeWeightMap ew(edge_weights);
+
+ // Set and print the values of an exterior vertex property.
+ typename Graph::vertex_range vr = g.vertices();
+ for( ; vr.first != vr.second; ++vr.first) {
+ vw(*vr.first) = distance(g.begin_vertices(), vr.first) * 2;
+ cout << "vertex weight: " << vw(*vr.first) << endl;
+ }
+
+ // Set and print the values of an exterior edge property.
+ typename Graph::edge_range er = g.edges();
+ for( ; er.first != er.second; ++er.first) {
+ ew(*er.first) = distance(g.begin_edges(), er.first) * 10;
+ cout << "edge weight: " << ew(*er.first) << endl;
+ }
+
+ // If bundled, constructed over the entire bundle.
+
+
+ {
+ typedef interior_property_map<Graph, Vertex> PropMap;
+ typedef interior_property_map<Graph, Vertex, string VertexProps::*> NameMap;
+ PropMap props(g);
+ NameMap names(g, &VertexProps::name);
+ for(vr.first = g.begin_vertices(); vr.first != vr.second; ++vr.first) {
+ Vertex v = *vr.first;
+ names(v) = "City " + lexical_cast<string>(props(v).id);
+ cout << names(v) << endl;
+ }
+ }
+
+ {
+ typedef interior_property_map<Graph, Edge> PropMap;
+ typedef interior_property_map<Graph, Edge, string EdgeProps::*> NameMap;
+ PropMap props(g);
+ NameMap names(g, &EdgeProps::name);
+ for(er.first = g.begin_edges(); er.first != er.second; ++er.first) {
+ Edge e = *er.first;
+ names(e) = "Road " + lexical_cast<string>(props(e).id);
+ cout << names(e) << endl;
+ }
+ }
+}
+
+
+struct Object
+{
+ Object(int id)
+ : id(id), name()
+ { }
+
+ int id;
+ string name;
+};
+
+typedef Object City;
+typedef Object Road;
+
+int main()
+{
+ /*
+ {
+ typedef undirected_graph<int, int, vertex_vector<>, edge_vector<>> G1;
+ typedef undirected_graph<int, int, vertex_list<>, edge_list<>> G2;
+ typedef undirected_graph<int, int, vertex_set<>, edge_set<>> G3;
+
+ test_props<G1>();
+ test_props<G2>();
+ test_props<G3>();
+ }
+ */
+
+ {
+ typedef directed_graph<City, Road, vertex_vector<>, edge_vector<>> G1;
+ typedef directed_graph<int, int, vertex_list<>, edge_list<>> G2;
+ typedef directed_graph<int, int, vertex_set<>, edge_set<>> G3;
+
+ test_props<G1>();
+ // test_props<G2>();
+ // test_props<G3>();
+ }
+
+
+ return 0;
+}
\ No newline at end of file