|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-06-25 10:24:48
Author: asutton
Date: 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
New Revision: 46679
URL: http://svn.boost.org/trac/boost/changeset/46679
Log:
Rewrote a number of classes to use a new triple<> type instead of tuple<>. I
did this to reduce the length of error messages and get rid of some of the
uglier syntax.
Copied the older property code out of branches and started rewriting it along
the lines of discussion of IU. Still no property maps.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp
- copied, changed from r46472, /sandbox/SOC/2008/graphs/branches/first/boost/graphs/properties.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/
- copied from r46472, /sandbox/SOC/2008/graphs/branches/first/boost/graphs/property_map/
sandbox/SOC/2008/graphs/trunk/boost/graphs/triple.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp | 8 -
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 45 +++++++-------
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp | 14 ++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp | 16 +---
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 19 +----
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp | 6
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp | 9 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp | 10 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp | 122 +++++++++++++++++++++++++--------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp | 108 +++++++++++++++++-----------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp | 103 ++++++++++++++++++++++-----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 8 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp | 7 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp | 9 --
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 14 +---
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 1
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 4
sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp | 4
23 files changed, 285 insertions(+), 236 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -55,14 +55,10 @@
}
inline bool operator==(adjacency_iterator const& x) const
- {
- return _iter == x._iter;
- }
+ { return _iter == x._iter; }
inline bool operator!=(adjacency_iterator const& x) const
- {
- return _iter != x._iter;
- }
+ { return _iter != x._iter; }
reference operator*() const
{
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-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -4,8 +4,6 @@
#include <iosfwd>
-#include <boost/tuple/tuple.hpp>
-
/**
* 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.
@@ -16,12 +14,14 @@
template <typename OutIter, typename InIter>
class directed_edge
{
+ template <typename O, typename I> friend bool operator==(directed_edge<O,I> const&, directed_edge<O,I> const&);
+ template <typename O, typename I> friend bool operator<(directed_edge<O,I> const&, directed_edge<O,I> const&);
public:
typedef OutIter out_iterator;
typedef InIter in_iterator;
typedef typename OutIter::value_type out_tuple;
- typedef typename boost::tuples::element<0, out_tuple>::type vertex_descriptor;
- typedef typename boost::tuples::element<1, out_tuple>::type edge_properties;
+ typedef typename out_tuple::first_type vertex_descriptor;
+ typedef typename out_tuple::second_type edge_properties;
/** @name Constructors */
//@{
@@ -42,38 +42,24 @@
/** Return the target of the edge. */
inline vertex_descriptor target() const
- { return _out->template get<0>(); }
+ { return _out->first; }
/** Return the iterator to the out edge. */
inline OutIter out_edge() const
{ return _out; }
inline InIter in_edge() const
- { return _out->template get<2>().template get<InIter>(); }
+ { return _out->third.template get<InIter>(); }
/** @name Property Accessors
* Return the properties associated with the edge.
*/
//@{
inline edge_properties& properties()
- { return _out->template get<1>(); }
+ { return _out->second; }
inline edge_properties const& properties() const
- { return _out->template get<1>(); }
- //@}
-
- /** @name Operators
- * @todo Consider externalizing these.
- */
- //@{
- inline bool operator==(directed_edge const& x)
- { return _src == x._src && _out == x._out; }
-
- inline bool operator!=(directed_edge const& x)
- { return !operator==(x); }
-
- inline bool operator<(directed_edge const& x)
- { return std::make_pair(_src, _out) < std::make_pair(x._src, x._out); }
+ { return _out->second; }
//@}
private:
@@ -82,6 +68,21 @@
};
template <typename O, typename I>
+inline bool
+operator==(directed_edge<O,I> const& x, directed_edge<O,I> const& y)
+{ return (x._src == y._src) && (x._out == y._out); }
+
+template <typename O, typename I>
+inline bool
+operator!=(directed_edge<O,I> const& x, directed_edge<O,I> const& y)
+{ return !(x == y); }
+
+template <typename O, typename I>
+inline bool
+operator<(directed_edge<O,I> const& x, directed_edge<O,I> const& y)
+{ return std::make_pair(x._src, x._out) < std::make_pair(y._src, y._out); }
+
+template <typename O, typename I>
std::ostream& operator<<(std::ostream& os, const directed_edge<O,I>& e)
{ return os << "(" << e.source() << " " << e.target() << ")"; }
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-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -59,6 +59,8 @@
public:
typedef VertexProps vertex_properties;
typedef EdgeProps edge_properties;
+ typedef VertexStore vertex_store_selector;
+ typedef EdgeStore edge_store_selector;
// In order to create the vertex store, we have to create the vertex type.
// In order to create the vertex type we need to create the edge store
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-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -176,7 +176,7 @@
typename directed_vertex<V,O,I>::edge_descriptor
directed_vertex<V,O,I>::bind_connection(out_iterator i, in_iterator j)
{
- i->template get<2>().put(j);
+ i->third.put(j);
j->second.put(i);
return edge_descriptor(j->first, i);
}
@@ -200,7 +200,7 @@
{
// Get the input iterator from the edge.
out_iterator o = e.out_edge();
- in_iterator i = o->template get<2>().template get<in_iterator>();
+ in_iterator i = o->third.template get<in_iterator>();
_in.remove(i);
}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -2,6 +2,9 @@
#ifndef EDGE_LIST_HPP
#define EDGE_LIST_HPP
+#include "triple.hpp"
+#include "placeholder.hpp"
+
#include "property_list.hpp"
#include "incidence_list.hpp"
#include "out_list.hpp"
@@ -17,9 +20,9 @@
* types for adjacency lists.
*/
template <
- template <typename> class FirstAlloc,
- template <typename> class SecondAlloc>
-struct basic_edge_list
+ template <typename> class FirstAlloc = std::allocator,
+ template <typename> class SecondAlloc = std::allocator>
+struct edge_list
{
// The property store metafunction generates the underlying global store
// type for edge properties in undirected graphs.
@@ -50,7 +53,7 @@
// vertex, edge properties, and in edge iterator (placeheld). The in
// edge type is the source vertex and the out edge iterator (placeheld).
typedef placeholder<sizeof(typename std::list<int>::iterator)> dummy_type;
- typedef boost::tuple<VertexDesc, Props, dummy_type> edge;
+ typedef triple<VertexDesc, Props, dummy_type> edge;
typedef FirstAlloc<edge> allocator;
typedef out_list<edge, allocator> type;
};
@@ -71,7 +74,4 @@
};
};
-struct edge_list : basic_edge_list<std::allocator, std::allocator> { };
-
#endif
-
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -17,10 +17,10 @@
* @param SecondAlloc - An allocator template for either global properties or in edges.
*/
template <
- template <typename> class Compare,
- template <typename> class FirstAlloc,
- template <typename> class SecondAlloc>
-struct basic_edge_set
+ template <typename> class Compare = std::less,
+ template <typename> class FirstAlloc = std::allocator,
+ template <typename> class SecondAlloc = std::allocator>
+struct edge_set
{
// The property store metafunnction generates the global store type
// for undirected graphs.
@@ -66,13 +66,5 @@
};
};
-/**
- * The most common edge set uses standard allocators and allows parameterization
- * of the comparison function. The comparison function must operate on vertex
- * descriptors.
- */
-template <template <typename> class Compare = std::less>
-struct edge_set : basic_edge_set<Compare, std::allocator, std::allocator> { };
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -2,9 +2,9 @@
#ifndef EDGE_VECTOR_HPP
#define EDGE_VECTOR_HPP
-#include <boost/tuple/tuple.hpp>
-
+#include "triple.hpp"
#include "placeholder.hpp"
+
#include "property_vector.hpp"
#include "incidence_vector.hpp"
#include "out_vector.hpp"
@@ -36,9 +36,9 @@
* out- and in-edge stores respectively.
*/
template <
- template <typename> class FirstAlloc,
- template <typename> class SecondAlloc>
-struct basic_edge_vector
+ template <typename> class FirstAlloc = std::allocator,
+ template <typename> class SecondAlloc = std::allocator>
+struct edge_vector
{
// The property store metafunction generates the type of vector used to
// store global properties for undirected graphs.
@@ -69,7 +69,7 @@
// vertex, edge properties, and in edge iterator (placeheld). The in
// edge type is the source vertex and the out edge iterator (placeheld).
typedef placeholder<sizeof(typename std::vector<int>::iterator)> dummy_type;
- typedef boost::tuple<VertexDesc, Props, dummy_type> edge;
+ typedef triple<VertexDesc, Props, dummy_type> edge;
typedef FirstAlloc<edge> allocator;
typedef out_vector<edge, allocator> type;
};
@@ -90,11 +90,4 @@
};
};
-/**
- * The default edge vector is a basic edge vector that uses the standard
- * allocators for both the first and second allocators.
- */
-struct edge_vector : basic_edge_vector<std::allocator, std::allocator> { };
-
#endif
-
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -16,8 +16,8 @@
typedef typename Edge::out_iterator out_iterator;
typedef typename out_iterator::value_type out_tuple;
public:
- typedef typename boost::tuples::element<0, out_tuple>::type vertex_descriptor;
- typedef typename boost::tuples::element<1, out_tuple>::type edge_properties;
+ typedef typename out_tuple::first_type vertex_descriptor;
+ typedef typename out_tuple::second_type edge_properties;
// This is a little misleading. This iterator can be either bidi or random.
// Clearly, we're going to be constraining members using some concept stuff
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -72,7 +72,7 @@
// Iterators are equivalent if they reference the same edge.
inline bool operator==(incidence_iterator const& x) const
- { return **this == *x; }
+ { return operator*() == *x; }
inline bool operator!=(incidence_iterator const& x) const
{ return !this->operator==(x); }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -13,8 +13,8 @@
typedef typename Edge::out_iterator base_iterator;
public:
typedef typename base_iterator::value_type out_tuple;
- typedef typename boost::tuples::element<0, out_tuple>::type vertex_descriptor;
- typedef typename boost::tuples::element<1, out_tuple>::type edge_properties;
+ typedef typename out_tuple::first_type vertex_descriptor;
+ typedef typename out_tuple::second_type edge_properties;
// This is a little misleading. This iterator can be either bidi or random.
// Clearly, we're going to be constraining members using some concept stuff
@@ -62,7 +62,7 @@
// Iterators are equivalent if they reference the same edge.
inline bool operator==(basic_out_iterator const& x) const
- { return **this == *x; }
+ { return operator*() == *x; }
inline bool operator!=(basic_out_iterator const& x) const
{ return !this->operator==(x); }
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-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -5,7 +5,6 @@
#include <list>
#include <boost/next_prior.hpp>
-#include <boost/tuple/tuple.hpp>
/**
* The out list implements list-based, out-edge storage for directed graphs.
@@ -23,10 +22,10 @@
typedef std::list<Edge, Alloc> store_type;
public:
typedef Edge out_tuple;
- typedef typename boost::tuples::element<0, Edge>::type vertex_descriptor;
- typedef typename boost::tuples::element<1, Edge>::type edge_properties;
+ typedef typename Edge::first_type vertex_descriptor;
+ typedef typename Edge::second_type edge_properties;
private:
- typedef typename boost::tuples::element<1, Edge>::type in_edge_place;
+ typedef typename Edge::third_type in_edge_place;
public:
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
@@ -66,7 +65,7 @@
// TODO How do I write this with std::find?
iterator i = _edges.begin(), end = _edges.end();
for( ; i != end; ++i) {
- if(i->template get<0>() == v) return i;
+ if(i->first == v) return i;
}
return end;
}
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-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -4,8 +4,6 @@
#include <vector>
-#include <boost/tuple/tuple.hpp>
-
/**
* The in/out vector implements vector-based, edge storage for directed graphs.
* Each out edge is capable of referencing its corresponding in edge in another
@@ -20,10 +18,10 @@
typedef std::vector<Edge, Alloc> store_type;
public:
typedef Edge out_tuple;
- typedef typename boost::tuples::element<0, Edge>::type vertex_descriptor;
- typedef typename boost::tuples::element<1, Edge>::type edge_properties;
+ typedef typename Edge::first_type vertex_descriptor;
+ typedef typename Edge::second_type edge_properties;
private:
- typedef typename boost::tuples::element<2, Edge>::type in_edge_place;
+ typedef typename Edge::third_type in_edge_place;
public:
typedef std::pair<vertex_descriptor, edge_properties> out_pair;
typedef typename store_type::iterator iterator;
@@ -56,7 +54,7 @@
// TODO How do I write this with std::find?
iterator i = _edges.begin(), end = _edges.end();
for( ; i != end; ++i) {
- if(i->template get<0>() == v) return i;
+ if(i->first == v) return i;
}
return end;
}
Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp (from r46472, /sandbox/SOC/2008/graphs/branches/first/boost/graphs/properties.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/branches/first/boost/graphs/properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -1,6 +1,6 @@
-#ifndef BOOST_GRAPHS_PROPERTIES_HPP
-#define BOOST_GRAPHS_PROPERTIES_HPP
+#ifndef PROPERTIES_HPP
+#define PROPERTIES_HPP
#include <vector>
#include <tr1/unordered_map>
@@ -8,48 +8,85 @@
#include <boost/type_traits.hpp>
#include <boost/mpl/if.hpp>
-#include <boost/graphs/property_map/simple_properties.hpp>
-#include <boost/graphs/property_map/bundled_properties.hpp>
-#include <boost/graphs/property_map/hashed_properties.hpp>
-#include <boost/graphs/property_map/indexed_properties.hpp>
-
-namespace boost {
-namespace graphs {
-
-/**
- * Default color types for this library.
- */
-enum color {
- white_color,
- gray_color,
- black_color,
- red_color,
- green_color,
- blue_color
-};
-
-/**
- * A traits class for colors. Specialize this if, for some reason, you ever
- * plan to specialize the notion of colors - which may be possible.
- *
- * @todo Obviously, this will be conceptized. See below.
- */
-template <typename Color>
-struct color_traits
-{
- static color white() { return white_color; }
- static color gray() { return gray_color; }
- static color black() { return black_color; }
- static color red() { return red_color; }
- static color green() { return green_color; }
- static color blue() { return blue_color; }
-};
+#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
+template <typename Selector, typename Descriptor, typename Property>
+struct choose_container
+{
+ typedef typename boost::mpl::if_<
+ use_hashing<Selector>,
+ hashed_property_container<Descriptor, Property>,
+ indexed_property_container<Descriptor, Property>
+ >::type type;
+};
+
+template <typename Graph, typename Property>
+struct exterior_vertex_property
+ : choose_container<
+ typename Graph::vertex_store_selector, typename Graph::vertex_descriptor, Property
+ >::type
+{
+ typedef typename choose_container<
+ 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)
+ : base_type(g.begin_vertices(), g.end_vertices(), p)
+ { }
+};
+
+template <typename Graph, typename Property>
+struct exterior_edge_property
+ : choose_container<
+ typename Graph::edge_store_selector, typename Graph::edge_descriptor, Property
+ >::type
+{
+ typedef typename choose_container<
+ typename Graph::edge_store_selector, typename Graph::edge_descriptor, Property
+ >::type base_type;
+
+ exterior_edge_property(const Graph& g)
+ : base_type(g.num_edges())
+ { }
+
+ exterior_edge_property(Graph const& g, Property const& p)
+ : 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 { };
@@ -59,9 +96,9 @@
struct exterior_property
{
typedef typename mpl::if_<
- is_same<Tag, hashed_property_map_tag>, // predicate
- hashed_property_container<Iterator, Property>, // on true
- indexed_property_container<Iterator, Property> // on false
+ is_same<Tag, hashed_property_map_tag>,
+ hashed_property_container<Iterator, Property>,
+ indexed_property_container<Iterator, Property>
>::type container_type;
typedef typename mpl::if_<
@@ -140,7 +177,6 @@
> map_type;
};
-} /* namespace graphs */
-} /* namespace boost */
+#endif
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp
==============================================================================
--- /sandbox/SOC/2008/graphs/branches/first/boost/graphs/property_map/hashed_properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/hashed_properties.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -1,46 +1,59 @@
-#ifndef BOOST_GRAPHS_PROPERTY_MAP_HASHED_PROPERTIES_HPP
-#define BOOST_GRAPHS_PROPERTY_MAP_HASHED_PROPERTIES_HPP
+#ifndef HASHED_PROPERTIES_HPP
+#define HASHED_PROPERTIES_HPP
#include <tr1/unordered_map>
#include <boost/functional/hash.hpp>
-namespace boost {
-namespace graphs {
-
namespace detail {
-template <typename Iterator, typename Property>
-struct make_pair_iterator
+/**
+ * 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 Iterator::iterator_category iterator_category;
- typedef typename Iterator::difference_type difference_type;
- typedef std::pair<typename Iterator::value_type, Property> value_type;
+ 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;
- make_pair_iterator(Iterator i)
+ key_value_iterator(Iter i)
+ : iter(i)
+ , value()
+ { }
+
+ key_value_iterator(Iter i, Prop const& p)
: iter(i)
+ , value(p)
{ }
- make_pair_iterator& operator++()
+ key_value_iterator& operator++()
{ ++iter; return *this; }
reference operator*()
- { return make_pair(*iter, Property()); }
+ { return make_pair(*iter, value); }
- bool operator==(make_pair_iterator const& x) const
+ bool operator==(key_value_iterator const& x) const
{ return iter == x.iter; }
- bool operator!=(make_pair_iterator const& x) const
+ bool operator!=(key_value_iterator const& x) const
{ return iter != x.iter; }
- Iterator iter;
+ Iter iter;
+ Prop value;
};
-} /* namespace detail */
+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
@@ -50,34 +63,41 @@
* 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 Iterator, typename Property>
+template <typename Descriptor, typename Property>
class hashed_property_container
{
- typedef detail::make_pair_iterator<Iterator, Property> pair_iterator;
public:
typedef Property value_type;
- typedef typename Iterator::value_type key_type;
- typedef std::tr1::unordered_map<key_type, value_type, hash<key_type> > container_type;
-
-
- // Construct the container over n elements with the given default property
- // value. If a number of buckets is explicitly given (and is not 0), then
- // construct the object with b buckets. Otherwise, construct with n buckets.
- // The default behavior will prevent rehashing during construction.
- inline hashed_property_container(Iterator f, Iterator l)
- : _map(pair_iterator(f), pair_iterator(l))
+ 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)
{ }
- inline hashed_property_container(std::pair<Iterator, Iterator> rng)
- : _map(pair_iterator(rng.first), pair_iterator(rng.second))
+ /**
+ * 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 _map[k]; }
+ { return data[k]; }
-private:
- container_type _map;
+ container_type data;
};
/**
@@ -103,24 +123,4 @@
container_type& data;
};
-template <typename I, typename P>
-typename hashed_property_map<I,P>::property_type const&
-get(hashed_property_map<I,P> const& pm,
- typename hashed_property_map<I,P>::key_type const& x)
-{
- return pm.data[x];
-}
-
-template <typename I, typename P>
-void
-put(hashed_property_map<I,P>& pm,
- typename hashed_property_map<I,P>::key_type const& x,
- typename hashed_property_map<I,P>::property_type const& v)
-{
- pm.data[x] = v;
-}
-
-} /* namesapce graphs */
-} /* namespace boost */
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp
==============================================================================
--- /sandbox/SOC/2008/graphs/branches/first/boost/graphs/property_map/indexed_properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -1,39 +1,92 @@
-#ifndef BOOST_GRAPHS_PROPERTY_MAP_INDEXED_PROPERTIES_HPP
-#define BOOST_GRAPHS_PROPERTY_MAP_INDEXED_PROPERTIES_HPP
+#ifndef INDEXED_PROPERTIES_HPP
+#define INDEXED_PROPERTIES_HPP
#include <iterator>
#include <vector>
-namespace boost {
-namespace graphs {
+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 Iterator, typename Property>
+template <typename Descriptor, typename Property>
struct indexed_property_container
{
typedef Property value_type;
- typedef typename Iterator::value_type key_type;
+ typedef Descriptor key_type;
typedef std::vector<Property> container_type;
- // Construct the container over the elements given by the iterator range
- // and the default property value.
- indexed_property_container(Iterator f, Iterator l)
- : _map(std::distance(f, l), Property())
+ inline indexed_property_container(std::size_t n)
+ : data(n)
{ }
- indexed_property_container(std::pair<Iterator, Iterator> rng)
- : _map(std::distance(rng.first, rng.second), Property())
+ /**
+ * 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()))
{ }
- value_type& operator[](key_type const& k)
- { return _map[k.get()]; }
+ inline value_type& operator[](key_type const& k)
+ { return data[k.get()]; }
- container_type _map;
+ container_type data;
};
@@ -60,24 +113,4 @@
container_type& data;
};
-template <typename I, typename P>
-typename indexed_property_map<I,P>::property_type const&
-get(indexed_property_map<I,P> const& pm,
- typename indexed_property_map<I,P>::key_type const& x)
-{
- return pm.data[x];
-}
-
-template <typename I, typename P>
-void
-put(indexed_property_map<I,P>& pm,
- typename indexed_property_map<I,P>::key_type const& x,
- typename indexed_property_map<I,P>::property_type const& v)
-{
- pm.data[x] = v;
-}
-
-} /* namesapce graphs */
-} /* namespace boost */
-
#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/triple.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/triple.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -0,0 +1,79 @@
+
+#ifndef TRIPLE_HPP
+#define TRIPLE_HPP
+
+/**
+ * Like a pair, but with three elements. This gets around having to use the
+ * Boost.Tuple library and generating exceedingly long type names in compiler
+ * errors.
+ */
+template <typename First, typename Second, typename Third>
+struct triple
+{
+ typedef First first_type;
+ typedef Second second_type;
+ typedef Third third_type;
+
+ triple()
+ : first(), second(), third()
+ { }
+
+ triple(first_type const& f, second_type const& s, third_type const& t)
+ : first(f), second(s), third(t)
+ { }
+
+ first_type first;
+ second_type second;
+ third_type third;
+};
+
+template <typename F, typename S, typename T>
+inline bool
+operator==(triple<F,S,T> const& a, triple<F,S,T> const& b)
+{ return (a.first == b.first) && (a.second == b.second) && (a.third == b.third); }
+
+template <typename F, typename S, typename T>
+inline bool
+operator!=(triple<F,S,T> const& a, triple<F,S,T> const& b)
+{ return !(a == b); }
+
+template <typename F, typename S, typename T>
+inline bool
+operator<(triple<F,S,T> const& a, triple<F,S,T> const& b)
+{
+ // TODO There is definitely a prettier way to write this, but I'm too lazy
+ // to figure it out right now.
+ if(a.first == b.first) {
+ if(a.second == b.second) {
+ return a.third < b.third;
+ }
+ else {
+ return a.second < b.second;
+ }
+ }
+ else {
+ return a.first < b.first;
+ }
+}
+
+template <typename F, typename S, typename T>
+inline bool
+operator>(triple<F,S,T> const& a, triple<F,S,T> const& b)
+{ return b < a; }
+
+template <typename F, typename S, typename T>
+inline bool
+operator<=(triple<F,S,T> const& a, triple<F,S,T> const& b)
+{ return !(b < a); }
+
+template <typename F, typename S, typename T>
+inline bool
+operator>=(triple<F,S,T> const& a, triple<F,S,T> const& b)
+{ return !(a < b); }
+
+template <typename F, typename S, typename T>
+inline triple<F,S,T>
+make_triple(F const& f, S const& s, T const& t)
+{ return triple<F,S,T>(f, s, t); }
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -28,6 +28,8 @@
public:
typedef VertexProps vertex_properties;
typedef EdgeProps edge_properties;
+ typedef VertexStore vertex_store_selector;
+ typedef EdgeStore edge_store_selector;
// Generate the property store type first. We can do this first because
// it's basically independant of everything else, but contributes to almost
@@ -468,7 +470,7 @@
template <BOOST_GRAPH_UG_PARAMS>
std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
undirected_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
- vertex_properties const& v)
+ vertex_properties const& v) const
{
return edge(find_vertex(u), find_vertex(v));
}
@@ -481,8 +483,8 @@
*/
template <BOOST_GRAPH_UG_PARAMS>
std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
-undirected_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
- vertex_properties const& v)
+undirected_graph<VP,EP,VS,ES>::edge(vertex_key const& u,
+ vertex_key const& v) const
{
return edge(find_vertex(u), find_vertex(v));
}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -4,6 +4,8 @@
#include <iosfwd>
+#include <boost/functional/hash.hpp>
+
// Important notes about descriptors
//
// A descriptor is basically an opaque reference to an object. It's kind of
@@ -108,5 +110,10 @@
std::ostream& operator<<(std::ostream& os, const basic_vertex_descriptor<D>& v)
{ return os << v.get(); }
+template <typename D>
+std::size_t hash_value(basic_vertex_descriptor<D> const& x)
+{ return boost::hash_value(x.get()); }
+
+
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -19,8 +19,8 @@
* iterator and then re-casting the buffered data as an iterator whenever we
* need it. That's a bit hacky, but it gets rid of redundant storage.
*/
-template <template <typename> class Allocator>
-struct basic_vertex_list
+template <template <typename> class Allocator = std::allocator>
+struct vertex_list
{
typedef unused key_type;
typedef basic_vertex_descriptor<void*> descriptor_type;
@@ -35,11 +35,6 @@
};
/**
- * The default vertex list uses the standard allocator.
- */
-struct vertex_list : basic_vertex_list<std::allocator> { };
-
-/**
* Pad the vertex type with an iterator back into the list. See above for a
* way around this.
*/
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -21,8 +21,8 @@
*
* @param Alloc A unary template class that will allocate stored vertices.
*/
-template <template <typename> class Alloc>
-struct basic_vertex_vector
+template <template <typename> class Alloc = std::allocator>
+struct vertex_vector
{
typedef unused key_type;
typedef basic_vertex_descriptor<std::size_t> descriptor_type;
@@ -40,12 +40,6 @@
};
/**
- * The default vertex vector uses the standard allocator.
- */
-struct vertex_vector : basic_vertex_vector<std::allocator> { };
-
-
-/**
* The vertex_vector template implements veretex storage for adjacency lists
* as a vector. This essentially provides a heavily constrained interface
* to the underlying vector. Note that many operations normally supported by
@@ -91,10 +85,10 @@
/** @name Vertex Iterators */
//@{
vertex_iterator begin_vertices() const
- { return _verts.begin(); }
+ { return vertex_iterator(_verts, _verts.begin()); }
vertex_iterator end_vertices() const
- { return _verts.end(); }
+ { return vertex_iterator(_verts, _verts.end()); }
vertex_range vertices() const
{ return std::make_pair(begin_vertices(), end_vertices()); }
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-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -4,3 +4,4 @@
exe set : set.cpp : <include>../../ <include>/usr/local/include ;
exe map : map.cpp : <include>../../ <include>/usr/local/include ;
exe test : test.cpp : <include>../../ <include>/usr/local/include ;
+exe props : props.cpp : <include>../../ <include>/usr/local/include ;
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -253,7 +253,7 @@
void vec_vec()
{
cout << "---- vec/vec ----" << endl;
- typedef directed_graph<City, Road, vertex_vector, edge_vector> Graph;
+ typedef directed_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
test_add_vertices<Graph>();
test_add_edges<Graph>();
test_add_multi_edges<Graph>();
@@ -264,7 +264,7 @@
void list_list()
{
cout << "---- list/list ----" << endl;
- typedef directed_graph<City, Road, vertex_list, edge_list> Graph;
+ typedef directed_graph<City, Road, vertex_list<>, edge_list<> > Graph;
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
test_disconnect_vertex<Graph>();
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -0,0 +1,63 @@
+
+#include <iostream>
+#include <string>
+#include <list>
+
+#include <boost/graphs/directed_graph.hpp>
+#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/properties.hpp>
+
+#include "demangle.hpp"
+
+using namespace std;
+using namespace boost;
+
+void un_vec_vec();
+void un_list_list();
+
+template <typename Graph>
+void make_square(Graph& g)
+{
+ typename Graph::vertex_descriptor v[4];
+ v[0] = g.add_vertex(0);
+ v[1] = g.add_vertex(0);
+ v[2] = g.add_vertex(0);
+ v[3] = g.add_vertex(0);
+ g.add_edge(v[0], v[1]);
+ g.add_edge(v[1], v[2]);
+ g.add_edge(v[2], v[3]);
+ g.add_edge(v[3], v[0]);
+ g.add_edge(v[0], v[2]);
+ g.add_edge(v[1], v[3]);
+}
+
+template <typename Graph>
+void test_ext_vertex_props(Graph& g)
+{
+ exterior_vertex_property<Graph, double> vp(g, 5.0);
+ cout << demangle<typename exterior_vertex_property<Graph, double>::base_type>() << endl;
+}
+
+int main()
+{
+ un_vec_vec();
+ un_list_list();
+
+ return 0;
+}
+
+void un_vec_vec()
+{
+ typedef undirected_graph<int, int, vertex_vector<>, edge_vector<> > Graph;
+ Graph g;
+ make_square(g);
+ test_ext_vertex_props(g);
+}
+
+void un_list_list()
+{
+ typedef undirected_graph<int, int, vertex_list<>, edge_list<> > Graph;
+ Graph g;
+ make_square(g);
+ test_ext_vertex_props(g);
+}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -84,7 +84,7 @@
g.add_vertex("Jan");
cout << g[g.find_vertex("Jan")] << endl;
- typedef undirected_graph<none, int, vertex_list, edge_list> Tmp;
+ typedef undirected_graph<none, int, vertex_list<>, edge_list<> > Tmp;
Tmp f;
f.remove_vertex(0);
}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp 2008-06-25 10:24:46 EDT (Wed, 25 Jun 2008)
@@ -222,7 +222,7 @@
void vec_vec()
{
cout << "---- vec/vec ----" << endl;
- typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
+ typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
test_add_vertices<Graph>();
test_add_edges<Graph>();
test_add_multi_edges<Graph>();
@@ -233,7 +233,7 @@
void list_list()
{
cout << "---- list/list ----" << endl;
- typedef undirected_graph<City, Road, vertex_list, edge_list> Graph;
+ typedef undirected_graph<City, Road, vertex_list<>, edge_list<> > Graph;
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
test_disconnect_vertex<Graph>();
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