|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-06-04 07:27:38
Author: asutton
Date: 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
New Revision: 46110
URL: http://svn.boost.org/trac/boost/changeset/46110
Log:
Lots of branches, and work.
Added:
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store.hpp
- copied, changed from r46069, /sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store
sandbox/SOC/2008/graphs/branches/tue/
sandbox/SOC/2008/graphs/branches/tue/boost/
sandbox/SOC/2008/graphs/branches/tue/boost/graphs/
sandbox/SOC/2008/graphs/branches/tue/libs/
sandbox/SOC/2008/graphs/branches/tue/libs/graphs/
Removed:
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store
Text files modified:
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/adjacency_list.hpp | 31 +++++-
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_list.hpp | 158 +++++++++++++++++---------------
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_set.hpp | 166 ++++++++++++++++++----------------
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_vector.hpp | 70 ++++++++------
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_list.hpp | 6
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_set.hpp | 6
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store.hpp | 4
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_vector.hpp | 30 +++++
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/storage.hpp | 7
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/edge.hpp | 10 +
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/undirected.hpp | 36 ++++++
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/vertex.hpp | 2
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_list.hpp | 140 ++++++++++++++++-------------
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_map.hpp | 190 +++++++++++++++++++--------------------
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_set.hpp | 184 +++++++++++++++++--------------------
sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_vector.hpp | 49 +++++----
sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/Jamfile | 8
sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/adjacency_list.cpp | 32 +++++-
18 files changed, 633 insertions(+), 496 deletions(-)
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/adjacency_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/adjacency_list.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/adjacency_list.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -23,7 +23,7 @@
/**
*/
template <
- typename Direction = none,
+ typename Type = none,
typename VertexProps = none,
typename EdgeProps = none,
typename VertexStore = none,
@@ -34,25 +34,44 @@
class adjacency_list
{
public:
+ typedef VertexProps vertex_properties;
typedef typename VertexStore::descriptor_type vertex_descriptor;
+
+ typedef EdgeProps edge_properties;
typedef typename EdgeStore::descriptor_type edge_descriptor;
+
+ typedef typename IncidenceStore::template store<edge_descriptor>::type incidence_store;
+
+ typedef typename Type::template vertex<vertex_properties, vertex_descriptor, incidence_store>::type vertex_type;
+ typedef typename Type::template edge<edge_properties, edge_descriptor, vertex_descriptor>::type edge_type;
+
+ // Note that vertex_type != vertex_store::vertex_type
+ typedef typename VertexStore::template store<vertex_type>::type vertex_store;
+ typedef typename EdgeStore::template store<edge_type>::type edge_store;
+
adjacency_list();
+
+private:
+ vertex_store _verts;
+ edge_store _edges;
};
// Functions
-#define BOOST_GRAPH_ADJLIST_PARAMS \
- typename D, typename VP, typename EP, typename VS, typename ES, typename IS, typename AEP
+#define BOOST_GRAPHS_AL_PARAMS \
+ typename T, typename VP, typename EP, typename VS, typename ES, typename IS, typename AEP
/**
* Construct an empty adjacency list.
*/
-template <BOOST_GRAPH_ADJLIST_PARAMS>
-adjacency_list<D,VP,EP,VS,ES,OS,AEP>::adjacency_list()
+template <BOOST_GRAPHS_AL_PARAMS>
+adjacency_list<T,VP,EP,VS,ES,IS,AEP>::adjacency_list()
+ : _verts()
+ , _edges()
{ }
-#undef BOOST_GRAPH_ADJLIST_PARAMS
+#undef BOOST_GRAPHS_ADJLIST_PARAMS
} /* namespace adj_list */
} /* namespace graphs */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_list.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_list.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -10,60 +10,66 @@
namespace graphs {
namespace adj_list {
-namespace detail {
- // Extend the notion of an edge for the edge set. Here, each edge also
- // stores an iterator to itself in the store. A little incestuous, but
- // it enables constant-time removals.
- template <typename Edge, template <typename> class Alloc>
- class basic_edge_list_node
- : public Edge
- {
- typedef basic_edge_list_node<Edge, Alloc> this_type;
- public:
- typedef typename Edge::vertex_descriptor vertex_descriptor;
- typedef typename Edge::properties_type properties_type;
-
- typedef typename std::list<
- this_type, Alloc<this_type>
- >::iterator iterator;
-
- inline basic_edge_list_node(vertex_descriptor u,
- vertex_descriptor v,
- properties_type const& p)
- : Edge(u, v, p)
- , iter()
- { }
+// Forward declarations
+template <typename E, template <typename> class A> class edge_list_elem;
+template <typename E, typename A> class edge_list_impl;
+
+template <template <typename> class Allocator>
+struct basic_edge_list
+{
+ typedef basic_edge_descriptor<void*> descriptor_type;
- iterator iter;
+ template <typename Edge>
+ struct store
+ {
+ typedef edge_list_elem<Edge, Allocator> stored_edge;
+ typedef edge_list_impl<stored_edge, Allocator<stored_edge> > type;
};
+};
-} /* namespace detail */
+struct edge_list : basic_edge_list<std::allocator> { };
+
+// Extend the notion of an edge for the edge set. Here, each edge also
+// stores an iterator to itself in the store. A little incestuous, but
+// it enables constant-time removals.
+template <typename Edge, template <typename> class Alloc>
+class edge_list_elem
+ : public Edge
+{
+ typedef edge_list_elem<Edge, Alloc> this_type;
+public:
+ typedef typename std::list<this_type, Alloc<this_type> >::iterator iterator;
+
+ inline edge_list_elem(typename Edge::vertex_descriptor u,
+ typename Edge::vertex_descriptor v,
+ typename Edge::edge_properties const& p)
+ : Edge(u, v, p)
+ , iter()
+ { }
+
+ iterator iter;
+};
/**
* The edge list can be used to implement multigraphs with removable edges.
* It's insert and remove functions are constant time functions, but accessing
* the number of edges is a linear time operation.
*/
-template <
- typename Edge,
- template <typename> class Alloc
- >
-class basic_edge_list
+template <typename Edge, typename Allocator>
+class edge_list_impl
{
+ typedef std::list<Edge, Allocator> edge_store;
public:
- typedef detail::basic_edge_list_node<Edge, Alloc> edge_type;
- typedef typename edge_type::descriptor_type edge_descriptor;
- typedef typename edge_type::vertex_descriptor vertex_descriptor;
- typedef typename edge_type::properties_type edge_properties;
-
- typedef std::list<edge_type, Alloc<edge_type> > edge_store;
- typedef simple_edge_iterator<edge_store> edge_iterator;
+ typedef Edge edge_type;
+ typedef typename Edge::vertex_descriptor vertex_descriptor;
+ typedef typename Edge::edge_descriptor edge_descriptor;
+ typedef typename Edge::edge_properties edge_properties;
typedef typename edge_store::size_type edges_size_type;
+ typedef simple_edge_iterator<edge_store> edge_iterator;
+ typedef std::pair<edge_iterator, edge_iterator> edge_range;
- // FIXME:
- typedef hashed_property_map_tag edge_property_map_category;
-
- basic_edge_list();
+ // Constructors.
+ edge_list_impl();
// Add edge
edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
@@ -94,22 +100,24 @@
edge_store _edges;
};
+#define BOOST_GRAPHS_EL_PARAMS \
+ typename E, typename A
+
+template <BOOST_GRAPHS_EL_PARAMS>
+edge_list_impl<E,A>::edge_list_impl()
+ : _edges()
+{ }
+
+#if 0
/**
* The default specialization uses the standard less comparator and the
* standard allocator.
*/
template <typename Edge>
-struct edge_list : basic_edge_list<Edge, std::allocator> { };
+struct edge_list : edge_list_impl<Edge, std::allocator> { };
// Functions
-#define BOOST_GRAPH_EL_PARAMS \
- typename E, template <typename> class A
-
-template <BOOST_GRAPH_EL_PARAMS>
-basic_edge_list<E,A>::basic_edge_list()
- : _edges()
-{ }
/**
* Add an edge to the set with no or default properties. If the edge already
@@ -117,8 +125,8 @@
* or existing edge.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_descriptor
-basic_edge_list<E,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
+typename edge_list_impl<E,A>::edge_descriptor
+edge_list_impl<E,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
{
return add(u, v, edge_properties());
}
@@ -128,8 +136,8 @@
* then no action is taken. Return a descriptor for the added or existing edge.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_descriptor
-basic_edge_list<E,A>::add_edge(vertex_descriptor u,
+typename edge_list_impl<E,A>::edge_descriptor
+edge_list_impl<E,A>::add_edge(vertex_descriptor u,
vertex_descriptor v,
edge_properties const& ep)
{
@@ -146,7 +154,7 @@
*/
template <BOOST_GRAPH_EL_PARAMS>
void
-basic_edge_list<E,A>::remove_edge(edge_descriptor e)
+edge_list_impl<E,A>::remove_edge(edge_descriptor e)
{
// Basically, iterate over the edge list until we find the descriptor
// e, then erase it. Note that descriptors are unique so there's really
@@ -167,7 +175,7 @@
*/
template <BOOST_GRAPH_EL_PARAMS>
void
-basic_edge_list<E,A>::remove_edge(vertex_descriptor u, vertex_descriptor v)
+edge_list_impl<E,A>::remove_edge(vertex_descriptor u, vertex_descriptor v)
{
// Create a temporary edge over u and v. This will sort the vertices as
// needed before actually inserting it.
@@ -190,8 +198,8 @@
* Get the number of edges in the edge set.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edges_size_type
-basic_edge_list<E,A>::num_edges() const
+typename edge_list_impl<E,A>::edges_size_type
+edge_list_impl<E,A>::num_edges() const
{
return _edges.size();
}
@@ -201,10 +209,10 @@
*/
template <BOOST_GRAPH_EL_PARAMS>
std::pair<
- typename basic_edge_list<E,A>::edge_iterator,
- typename basic_edge_list<E,A>::edge_iterator
+ typename edge_list_impl<E,A>::edge_iterator,
+ typename edge_list_impl<E,A>::edge_iterator
>
-basic_edge_list<E,A>::edges() const
+edge_list_impl<E,A>::edges() const
{
return std::make_pair(begin_edges(), end_edges());
}
@@ -213,8 +221,8 @@
* Get an iterator to the first edge in the set.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_iterator
-basic_edge_list<E,A>::begin_edges() const
+typename edge_list_impl<E,A>::edge_iterator
+edge_list_impl<E,A>::begin_edges() const
{
return _edges.begin();
}
@@ -223,8 +231,8 @@
* Get an iterator past the end of the edge set.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_iterator
-basic_edge_list<E,A>::end_edges() const
+typename edge_list_impl<E,A>::edge_iterator
+edge_list_impl<E,A>::end_edges() const
{
return _edges.end();
}
@@ -233,8 +241,8 @@
* Get access to the given edge.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_type&
-basic_edge_list<E,A>::edge(edge_descriptor e)
+typename edge_list_impl<E,A>::edge_type&
+edge_list_impl<E,A>::edge(edge_descriptor e)
{
return *static_cast<edge_type*>(e.desc);
}
@@ -243,8 +251,8 @@
* Get access to the given edge.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_type const&
-basic_edge_list<E,A>::edge(edge_descriptor e) const
+typename edge_list_impl<E,A>::edge_type const&
+edge_list_impl<E,A>::edge(edge_descriptor e) const
{
return *static_cast<edge_type*>(e.desc);
}
@@ -253,8 +261,8 @@
* Get a descriptor for the given edge.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_descriptor
-basic_edge_list<E,A>::descriptor(edge_type const& e) const
+typename edge_list_impl<E,A>::edge_descriptor
+edge_list_impl<E,A>::descriptor(edge_type const& e) const
{
return &const_cast<edge_type&>(e);
}
@@ -264,8 +272,8 @@
* Access the properties of the given edge.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_properties&
-basic_edge_list<E,A>::properties(edge_descriptor e)
+typename edge_list_impl<E,A>::edge_properties&
+edge_list_impl<E,A>::properties(edge_descriptor e)
{
return *edge(e);
}
@@ -274,14 +282,16 @@
* Access the properties of the given edge.
*/
template <BOOST_GRAPH_EL_PARAMS>
-typename basic_edge_list<E,A>::edge_properties const&
-basic_edge_list<E,A>::properties(edge_descriptor e) const
+typename edge_list_impl<E,A>::edge_properties const&
+edge_list_impl<E,A>::properties(edge_descriptor e) const
{
return *edge(e);
}
#undef BOOST_GRAPH_EL_PARAMS
+#endif
+
} /* namespace adj_list */
} /* namespace graphs */
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_set.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_set.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -10,38 +10,47 @@
namespace graphs {
namespace adj_list {
-namespace detail {
- // Extend the notion of an edge for the edge set. Here, each edge also
- // stores an iterator to itself in the store. A little incestuous, but
- // it enables constant-time removals.
- template <
- typename Edge,
- template <typename> class Compare,
- template <typename> class Alloc
- >
- class basic_edge_set_node
- : public Edge
- {
- typedef basic_edge_set_node<Edge, Compare, Alloc> this_type;
- public:
- typedef typename Edge::vertex_descriptor vertex_descriptor;
- typedef typename Edge::properties_type properties_type;
-
- typedef typename std::set<
- this_type, Compare<this_type>, Alloc<this_type>
- >::iterator iterator;
+template <typename, template <typename> class, template <typename> class> class edge_set_elem;
+template <typename, typename, typename> class edge_set_impl;
- inline basic_edge_set_node(vertex_descriptor u,
- vertex_descriptor v,
- properties_type const& ep)
- : Edge(u, v, ep)
- , iter()
- { }
+template <template <typename> class Compare, template <typename> class Allocator>
+struct basic_edge_set
+{
+ typedef basic_edge_descriptor<void*> descriptor_type;
- iterator iter;
+ template <typename Edge>
+ struct store
+ {
+ typedef edge_set_elem<Edge, Compare, Allocator> stored_edge;
+ typedef edge_set_impl<stored_edge, Compare<stored_edge>, Allocator<stored_edge> > type;
};
+};
+
+template <template <typename> class Compare = std::less>
+struct edge_set : basic_edge_set<Compare, std::allocator> { };
-} /* namespace detail */
+// Extend the notion of an edge for the edge set. Here, each edge also
+// stores an iterator to itself in the store. A little incestuous, but
+// it enables constant-time removals.
+template <typename Edge, template <typename> class Compare, template <typename> class Allocator>
+class edge_set_elem
+ : public Edge
+{
+ typedef edge_set_elem<Edge, Compare, Allocator> this_type;
+public:
+ typedef typename std::set<
+ this_type, Compare<this_type>, Allocator<this_type>
+ >::iterator iterator;
+
+ inline edge_set_elem(typename Edge::vertex_descriptor u,
+ typename Edge::vertex_descriptor v,
+ typename Edge::edge_properties const& ep)
+ : Edge(u, v, ep)
+ , iter()
+ { }
+
+ iterator iter;
+};
/**
* The edge set is basically used to implement simple graphs by not adding
@@ -51,28 +60,21 @@
*
* Note that this underlying store also supports edge removals.
*/
-template <
- typename Edge,
- template <typename> class Compare,
- template <typename> class Alloc
- >
-class basic_edge_set
+template <typename Edge, typename Compare, typename Allocator>
+class edge_set_impl
{
+ typedef std::set<Edge, Compare, Allocator> edge_store;
public:
- typedef detail::basic_edge_set_node<Edge, Compare, Alloc> edge_type;
- typedef typename edge_type::descriptor_type edge_descriptor;
- typedef typename edge_type::properties_type edge_properties;
-
- typedef typename edge_type::vertex_descriptor vertex_descriptor;
-
- typedef std::set<edge_type, Compare<edge_type>, Alloc<edge_type> > edge_store;
- typedef simple_edge_iterator<edge_store> edge_iterator;
+ typedef Edge edge_type;
+ typedef typename Edge::edge_descriptor edge_descriptor;
+ typedef typename Edge::edge_properties edge_properties;
+ typedef typename Edge::vertex_descriptor vertex_descriptor;
typedef typename edge_store::size_type edges_size_type;
+ typedef simple_edge_iterator<edge_store> edge_iterator;
+ typedef std::pair<edge_iterator, edge_iterator> edge_range;
- // FIXME:
- typedef hashed_property_map_tag edge_property_map_category;
-
- basic_edge_set();
+ // Constructors.
+ edge_set_impl();
// Add edge
edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
@@ -86,7 +88,7 @@
edges_size_type num_edges() const;
// Edge iterator accessors.
- std::pair<edge_iterator, edge_iterator> edges() const;
+ edge_range edges() const;
edge_iterator begin_edges() const;
edge_iterator end_edges() const;
@@ -100,20 +102,30 @@
edge_store _edges;
};
+#define BOOST_GRAPHS_ES_PARAMS \
+ typename E, typename C, typename A
+
+template <BOOST_GRAPHS_ES_PARAMS>
+edge_set_impl<E,C,A>::edge_set_impl()
+ : _edges()
+{ }
+
+#undef BOOST_GRAPHS_ES_PARAMS
+
+#if 0
+
/**
* The default specialization uses the standard less comparator and the
* standard allocator.
*/
template <typename Edge>
-struct edge_set : basic_edge_set<Edge, std::less, std::allocator> { };
+struct edge_set : edge_set_impl<Edge, std::less, std::allocator> { };
// Functions
-#define BOOST_GRAPH_ES_PARAMS \
- typename E, template <typename> class C, template <typename> class A
template <BOOST_GRAPH_ES_PARAMS>
-basic_edge_set<E,C,A>::basic_edge_set()
+edge_set_impl<E,C,A>::edge_set_impl()
: _edges()
{ }
@@ -123,8 +135,8 @@
* or existing edge.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_descriptor
-basic_edge_set<E,C,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
+typename edge_set_impl<E,C,A>::edge_descriptor
+edge_set_impl<E,C,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
{
return insert_edge(u, v).first;
}
@@ -134,8 +146,8 @@
* then no action is taken. Return a descriptor for the added or existing edge.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_descriptor
-basic_edge_set<E,C,A>::add_edge(vertex_descriptor u,
+typename edge_set_impl<E,C,A>::edge_descriptor
+edge_set_impl<E,C,A>::add_edge(vertex_descriptor u,
vertex_descriptor v,
edge_properties const& ep)
{
@@ -146,8 +158,8 @@
*
*/
template <BOOST_GRAPH_ES_PARAMS>
-std::pair<typename basic_edge_set<E,C,A>::edge_descriptor, bool>
-basic_edge_set<E,C,A>::insert_edge(vertex_descriptor u, vertex_descriptor v)
+std::pair<typename edge_set_impl<E,C,A>::edge_descriptor, bool>
+edge_set_impl<E,C,A>::insert_edge(vertex_descriptor u, vertex_descriptor v)
{
return insert_edge(u, v, edge_properties());
}
@@ -157,8 +169,8 @@
* Add an edge with the given properties to the edge store.
*/
template <BOOST_GRAPH_ES_PARAMS>
-std::pair<typename basic_edge_set<E,C,A>::edge_descriptor, bool>
-basic_edge_set<E,C,A>::insert_edge(vertex_descriptor u,
+std::pair<typename edge_set_impl<E,C,A>::edge_descriptor, bool>
+edge_set_impl<E,C,A>::insert_edge(vertex_descriptor u,
vertex_descriptor v,
edge_properties const& ep)
{
@@ -184,8 +196,8 @@
* Get the number of edges in the edge set.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edges_size_type
-basic_edge_set<E,C,A>::num_edges() const
+typename edge_set_impl<E,C,A>::edges_size_type
+edge_set_impl<E,C,A>::num_edges() const
{
return _edges.size();
}
@@ -195,10 +207,10 @@
*/
template <BOOST_GRAPH_ES_PARAMS>
std::pair<
- typename basic_edge_set<E,C,A>::edge_iterator,
- typename basic_edge_set<E,C,A>::edge_iterator
+ typename edge_set_impl<E,C,A>::edge_iterator,
+ typename edge_set_impl<E,C,A>::edge_iterator
>
-basic_edge_set<E,C,A>::edges() const
+edge_set_impl<E,C,A>::edges() const
{
return std::make_pair(begin_edges(), end_edges());
}
@@ -207,8 +219,8 @@
* Get an iterator to the first edge in the set.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_iterator
-basic_edge_set<E,C,A>::begin_edges() const
+typename edge_set_impl<E,C,A>::edge_iterator
+edge_set_impl<E,C,A>::begin_edges() const
{
return _edges.begin();
}
@@ -217,8 +229,8 @@
* Get an iterator past the end of the edge set.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_iterator
-basic_edge_set<E,C,A>::end_edges() const
+typename edge_set_impl<E,C,A>::edge_iterator
+edge_set_impl<E,C,A>::end_edges() const
{
return _edges.end();
}
@@ -227,8 +239,8 @@
* Get access to the given edge.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_type&
-basic_edge_set<E,C,A>::edge(edge_descriptor e)
+typename edge_set_impl<E,C,A>::edge_type&
+edge_set_impl<E,C,A>::edge(edge_descriptor e)
{
return *static_cast<edge_type*>(e.desc);
}
@@ -237,8 +249,8 @@
* Get access to the given edge.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_type const&
-basic_edge_set<E,C,A>::edge(edge_descriptor e) const
+typename edge_set_impl<E,C,A>::edge_type const&
+edge_set_impl<E,C,A>::edge(edge_descriptor e) const
{
return *static_cast<edge_type*>(e.desc);
}
@@ -247,8 +259,8 @@
* Access the properties of the given edge.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_properties&
-basic_edge_set<E,C,A>::properties(edge_descriptor e)
+typename edge_set_impl<E,C,A>::edge_properties&
+edge_set_impl<E,C,A>::properties(edge_descriptor e)
{
return *edge(e);
}
@@ -257,14 +269,16 @@
* Access the properties of the given edge.
*/
template <BOOST_GRAPH_ES_PARAMS>
-typename basic_edge_set<E,C,A>::edge_properties const&
-basic_edge_set<E,C,A>::properties(edge_descriptor e) const
+typename edge_set_impl<E,C,A>::edge_properties const&
+edge_set_impl<E,C,A>::properties(edge_descriptor e) const
{
return *edge(e);
}
#undef BOOST_GRAPH_ES_PARAMS
+#endif
+
} /* namespace adj_list */
} /* namespace graphs */
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/es/edge_vector.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -10,43 +10,43 @@
namespace graphs {
namespace adj_list {
+// Forward declarations
+template <typename Edge, typename Allocator> class edge_vector_impl;
+
template <template <typename> class Allocator>
struct basic_edge_vector
{
typedef basic_edge_descriptor<std::size_t> descriptor_type;
template <typename Edge>
- struct type
+ struct store
{
+ typedef edge_vector_impl<Edge, Allocator<Edge> > type;
};
};
struct edge_vector : basic_edge_vector<std::allocator> { };
-#if 0
/**
* The edge vector implements a trivial multiset of edges for a graph (i.e., a
* multigraph). Note that the underlying store does not permit the removal of
* edges from the graph.
*/
-template <typename Edge, template <typename> class Alloc>
-class basic_edge_vector
+template <typename Edge, typename Allocator>
+class edge_vector_impl
{
+ typedef std::vector<Edge, Allocator> edge_store;
public:
typedef Edge edge_type;
- typedef typename edge_type::descriptor_type edge_descriptor;
+ typedef typename edge_type::edge_properties edge_properties;
+ typedef typename edge_type::edge_descriptor edge_descriptor;
typedef typename edge_type::vertex_descriptor vertex_descriptor;
- typedef typename edge_type::properties_type edge_properties;
-
- typedef std::vector<edge_type, Alloc<edge_type> > edge_store;
- typedef indexed_edge_iterator<edge_store> edge_iterator;
typedef typename edge_store::size_type edges_size_type;
+ typedef indexed_edge_iterator<edge_store> edge_iterator;
- // FIXME:
- typedef indexed_property_map_tag edge_property_map_category;
-
- basic_edge_vector();
+ // Constructors
+ edge_vector_impl();
// Add edge
edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
@@ -64,6 +64,18 @@
edge_store _edges;
};
+#define BOOST_GRAPHS_EV_PARAMS \
+ typename E, typename A
+
+template <BOOST_GRAPHS_EV_PARAMS>
+edge_vector_impl<E,A>::edge_vector_impl()
+ : _edges()
+{ }
+
+#undef BOOST_GRAPHS_EV_PARAMS
+
+#if 0
+
/**
* Specialize storage traits for all types of edge vectors to use indexed
* descriptors rather than memory descriptors.
@@ -71,7 +83,7 @@
* @todo This don't work.
*/
template <typename Edge, template <typename> class Alloc>
-struct storage_traits< basic_edge_vector<Edge, Alloc> >
+struct storage_traits< edge_vector_impl<Edge, Alloc> >
{
typedef std::size_t descriptor_type;
};
@@ -80,7 +92,7 @@
* The default specialization uses the standard allocator.
*/
template <typename Edge>
-struct edge_vector : basic_edge_vector<Edge, std::allocator> { };
+struct edge_vector : edge_vector_impl<Edge, std::allocator> { };
/**
* Specialize the storage traits for the default specialization. We wouldn't
@@ -96,7 +108,7 @@
// Functions
template <typename E, template <typename> class A>
-basic_edge_vector<E,A>::basic_edge_vector()
+edge_vector_impl<E,A>::edge_vector_impl()
: _edges()
{ }
@@ -110,8 +122,8 @@
* @complexity O(1) amortized
*/
template <typename E, template <typename> class A>
-typename basic_edge_vector<E,A>::edge_descriptor
-basic_edge_vector<E,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
+typename edge_vector_impl<E,A>::edge_descriptor
+edge_vector_impl<E,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
{
return add_edge(u, v, edge_properties());
}
@@ -126,8 +138,8 @@
* @complexity O(1) amortized
*/
template <typename E, template <typename> class A>
-typename basic_edge_vector<E,A>::edge_descriptor
-basic_edge_vector<E,A>::add_edge(vertex_descriptor u,
+typename edge_vector_impl<E,A>::edge_descriptor
+edge_vector_impl<E,A>::add_edge(vertex_descriptor u,
vertex_descriptor v,
edge_properties const& ep)
{
@@ -142,8 +154,8 @@
* @complexity O(1)
*/
template <typename E, template <typename> class A>
-typename basic_edge_vector<E,A>::edges_size_type
-basic_edge_vector<E,A>::num_edges() const
+typename edge_vector_impl<E,A>::edges_size_type
+edge_vector_impl<E,A>::num_edges() const
{
return _edges.size();
}
@@ -153,10 +165,10 @@
*/
template <typename E, template <typename> class A>
std::pair<
- typename basic_edge_vector<E,A>::edge_iterator,
- typename basic_edge_vector<E,A>::edge_iterator
+ typename edge_vector_impl<E,A>::edge_iterator,
+ typename edge_vector_impl<E,A>::edge_iterator
>
-basic_edge_vector<E,A>::edges() const
+edge_vector_impl<E,A>::edges() const
{
return make_pair(begin_edges(), end_edges());
}
@@ -165,15 +177,15 @@
* Get an iterator to the first edge.
*/
template <typename E, template <typename> class A>
-typename basic_edge_vector<E,A>::edge_iterator
-basic_edge_vector<E,A>::begin_edges() const
+typename edge_vector_impl<E,A>::edge_iterator
+edge_vector_impl<E,A>::begin_edges() const
{
return edge_iterator(_edges, _edges.begin());
}
template <typename E, template <typename> class A>
-typename basic_edge_vector<E,A>::edge_iterator
-basic_edge_vector<E,A>::end_edges() const
+typename edge_vector_impl<E,A>::edge_iterator
+edge_vector_impl<E,A>::end_edges() const
{
return edge_iterator(_edges, _edges.end());
}
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_list.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_list.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -1,11 +1,11 @@
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_LIST_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_LIST_HPP
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_LIST_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_LIST_HPP
#include <list>
#include <algorithm>
-#include <boost/graphs/adjacency_list/ves/vertex_edge_store.hpp>
+#include <boost/graphs/adjacency_list/is/incidence_store.hpp>
namespace boost {
namespace graphs {
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_set.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_set.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -1,10 +1,10 @@
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_SET_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_SET_HPP
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_HPP
#include <set>
-#include <boost/graphs/adjacency_list/ves/vertex_edge_store.hpp>
+#include <boost/graphs/adjacency_list/is/incidence_store.hpp>
namespace boost {
namespace graphs {
Deleted: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
+++ (empty file)
@@ -1,76 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_STORE_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_STORE_HPP
-
-#include <set>
-
-namespace boost {
-namespace graphs {
-namespace adj_list {
-
-/**
- * The vertex store is a simple helper class that provides a number of common
- * functions for derived types.
- */
-template <typename Store>
-class vertex_edge_store
-{
-public:
- typedef typename Store::iterator iterator;
- typedef typename Store::const_iterator const_iterator;
- typedef typename Store::size_type size_type;
-
- // Constructors
- vertex_edge_store();
-
- // Iterator access.
- inline iterator begin();
- inline iterator end();
-
- inline const_iterator begin() const;
- inline const_iterator end() const;
-
-protected:
- Store _store;
-};
-
-// Functions
-
-template <typename S>
-vertex_edge_store<S>::vertex_edge_store()
- : _store()
-{ }
-
-template <typename S>
-typename vertex_edge_store<S>::iterator
-vertex_edge_store<S>::begin()
-{
- return _store.begin();
-}
-
-template <typename S>
-typename vertex_edge_store<S>::iterator
-vertex_edge_store<S>::end()
-{
- return _store.end();
-}
-
-template <typename S>
-typename vertex_edge_store<S>::const_iterator
-vertex_edge_store<S>::begin() const
-{
- return _store.begin();
-}
-
-template <typename S>
-typename vertex_edge_store<S>::const_iterator
-vertex_edge_store<S>::end() const
-{
- return _store.end();
-}
-
-} /* namespace adj_list */
-} /* namespace graphs */
-} /* namespace boost */
-
-#endif
Copied: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store.hpp (from r46069, /sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store)
==============================================================================
--- /sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_store.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -1,6 +1,6 @@
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_STORE_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_STORE_HPP
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_STORE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_STORE_HPP
#include <set>
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/is/incidence_vector.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -1,15 +1,37 @@
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_VECTOR_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_VECTOR_HPP
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_VECTOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_VECTOR_HPP
#include <vector>
-#include <boost/graphs/adjacency_list/ves/vertex_edge_store.hpp>
+#include <boost/graphs/adjacency_list/is/incidence_store.hpp>
namespace boost {
namespace graphs {
namespace adj_list {
+// Forward declarations
+template <typename ED, typename A> struct incidence_vector_impl;
+
+template <template <typename> class Allocator>
+struct basic_incidence_vector
+{
+ template <typename EdgeDesc>
+ struct store
+ {
+ typedef incidence_vector_impl<EdgeDesc, Allocator<EdgeDesc> > type;
+ };
+};
+
+struct incidence_vector : basic_incidence_vector<std::allocator> { };
+
+template <typename EdgeDesc, typename Allocator>
+struct incidence_vector_impl
+{
+};
+
+#if 0
+
/**
* The vertex edge vector provides vector-based storage for edges connected to
* vertices. This type supports insertions in constant time, and find and
@@ -88,6 +110,8 @@
return this->_store.size();
}
+#endif
+
} /* namespace adj_list */
} /* namespace graphs */
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/storage.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/storage.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/storage.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -4,7 +4,6 @@
#include <boost/graphs/adjacency_list/storage_traits.hpp>
-
// Vertex storage types
// We can store vertices in almost anything conceivable. These are the default
// options for storing. Note that we could expand this set to also include
@@ -30,8 +29,8 @@
// of each vertex. Like above, there aren't actually too many types of vertex
// edge storage since, for example, mapped containers don't make a lot of sense.
// However, vectors, lists, and sets (both single and multi) work just fine.
-#include <boost/graphs/adjacency_list/ves/vertex_edge_vector.hpp>
-#include <boost/graphs/adjacency_list/ves/vertex_edge_list.hpp>
-#include <boost/graphs/adjacency_list/ves/vertex_edge_set.hpp>
+#include <boost/graphs/adjacency_list/is/incidence_vector.hpp>
+#include <boost/graphs/adjacency_list/is/incidence_list.hpp>
+#include <boost/graphs/adjacency_list/is/incidence_set.hpp>
#endif
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/edge.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/edge.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -1,6 +1,6 @@
#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_EDGE_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_EGE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_EDGE_HPP
#include <boost/graphs/utility/unordered_pair.hpp>
#include <boost/graphs/adjacency_list/edge.hpp>
@@ -9,6 +9,13 @@
namespace graphs {
namespace adj_list {
+template <typename EdgeProps, typename VertexDesc>
+struct undirected_edge
+{
+};
+
+#if 0
+
/**
* An undirected edge is an unordered pair of pointers to its endpoints. Note
* that because the unordered pair is instantiated over pointers, these are
@@ -152,6 +159,7 @@
#undef BOOST_GRAPH_UE_PARAMS
+#endif
} /* namespace adj_list */
} /* namespace graphs */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/undirected.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/undirected.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/undirected.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -6,13 +6,43 @@
namespace graphs {
namespace adj_list {
-struct undirected { };
+// Forward declarations
+template <typename VP, typename VD, typename IS> struct undirected_vertex;
+template <typename EP, typename ED, typename VD> struct undirected_edge;
+
+struct undirected
+{
+ template <typename VertexProps, typename VertexDesc, typename IncidenceStore>
+ struct vertex
+ {
+ typedef undirected_vertex<VertexProps, VertexDesc, IncidenceStore> type;
+ };
+
+ template <typename EdgeProps, typename EdgeDesc, typename VertexDesc>
+ struct edge
+ {
+ typedef undirected_edge<EdgeProps, EdgeDesc, VertexDesc> type;
+ };
+};
+
+template <typename VertexProps, typename VertexDesc, typename IncidenceStore>
+struct undirected_vertex
+{
+ typedef VertexProps vertex_properties;
+ typedef VertexDesc vertex_descriptor;
+};
+
+template <typename EdgeProps, typename EdgeDesc, typename VertexDesc>
+struct undirected_edge
+{
+ typedef EdgeProps edge_properties;
+ typedef EdgeDesc edge_descriptor;
+ typedef VertexDesc vertex_descriptor;
+};
} /* namespace adj_list */
} /* namespace graphs */
} /* namespace boost */
-#include <boost/graphs/adjacency_list/undirected/vertex.hpp>
-// #include <boost/graphs/adjacency_list/undirected/edge.hpp>
#endif
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/undirected/vertex.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -2,7 +2,7 @@
#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_VERTEX_HPP
#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_VERTEX_HPP
-#include <boost/graphs/adjacency_list/vertex.hpp>
+// #include <boost/graphs/adjacency_list/vertex.hpp>
namespace boost {
namespace graphs {
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_list.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -10,29 +10,40 @@
namespace graphs {
namespace adj_list {
-namespace detail {
- // Extend the notion of a vertex for list storage so that we can store each
- // vertex's iterator the vertex. Basically, this is used to provide constant
- // time access to correct vertex in the container. I can't think of a better
- // way to to do this.
- template <typename Vertex, template <typename> class Alloc>
- struct basic_vertex_list_node
- : Vertex
- {
- typedef basic_vertex_list_node<Vertex, Alloc> this_type;
- typedef typename Vertex::properties_type properties_type;
- typedef typename std::list<
- this_type, Alloc<this_type>
- >::iterator iterator;
-
- inline basic_vertex_list_node(properties_type const& vp)
- : Vertex(vp)
- , iter()
- { }
+// Forward declarations
+template <typename V, template <typename> class A> class vertex_list_elem;
+template <typename V, typename A> class vertex_list_impl;
+
+template <template <typename> class Allocator>
+struct basic_vertex_list
+{
+ typedef basic_vertex_descriptor<void*> descriptor_type;
- iterator iter;
+ template <typename Vertex>
+ struct store
+ {
+ typedef vertex_list_elem<Vertex, Allocator> stored_vertex;
+ typedef vertex_list_impl<stored_vertex, Allocator<stored_vertex> > type;
};
-} /* namespace detail */
+};
+
+struct vertex_list : basic_vertex_list<std::allocator> { };
+
+template <typename Vertex, template <typename> class Alloc>
+class vertex_list_elem
+ : public Vertex
+{
+ typedef vertex_list_elem<Vertex, Alloc> this_type;
+public:
+ typedef typename std::list<this_type, Alloc<this_type> >::iterator iterator;
+
+ inline vertex_list_elem(typename Vertex::vertex_properties const& vp)
+ : Vertex(vp)
+ , iter()
+ { }
+
+ iterator iter;
+};
/**
* The basic_vertex_list provides a list-based implementation of vertex storage
@@ -44,27 +55,20 @@
* vertex. All insertions and removals occur in constant time. However, getting
* the number of vertices is linear.
*/
-template <
- typename Vertex,
- template <typename> class Alloc = std::allocator
- >
-class basic_vertex_list
+template <typename Vertex, typename Allocator>
+class vertex_list_impl
{
+ typedef std::list<Vertex, Allocator> vertex_store;
public:
- typedef detail::basic_vertex_list_node<Vertex, Alloc> vertex_type;
- typedef typename vertex_type::descriptor_type vertex_descriptor;
- typedef typename vertex_type::properties_type vertex_properties;
-
- typedef std::list<vertex_type, Alloc<vertex_type> > vertex_store;
- typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+ typedef Vertex vertex_type;
+ typedef typename Vertex::vertex_properties vertex_properties;
+ typedef typename Vertex::vertex_descriptor vertex_descriptor;
typedef typename vertex_store::size_type vertices_size_type;
+ typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+ typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
- // FIXME: Clearly, this should go away during conceptization.
- typedef hashed_property_map_tag vertex_property_map_category;
-
- basic_vertex_list()
- : _verts()
- { }
+ // Constructors
+ vertex_list_impl();
// Add/remove vertices.
vertex_descriptor add_vertex();
@@ -77,7 +81,7 @@
vertices_size_type num_vertices() const;
// Vertex iteration.
- std::pair<vertex_iterator, vertex_iterator> vertices() const;
+ vertex_range vertices() const;
vertex_iterator begin_vertices() const;
vertex_iterator end_vertices() const;
@@ -91,11 +95,21 @@
vertex_store _verts;
};
+#define BOOST_GRAPHS_VL_PARAMS \
+ typename V, typename A
+
+template <BOOST_GRAPHS_VL_PARAMS>
+vertex_list_impl<V,A>::vertex_list_impl()
+ : _verts()
+{ }
+
+#if 0
+
/**
* Create a default specialization of the basic vertex list.
*/
template <typename Vertex>
-struct vertex_list : basic_vertex_list<Vertex> { };
+struct vertex_list : vertex_list_impl<Vertex> { };
/**
* Add a vertex to the store with no or default properties.
@@ -103,8 +117,8 @@
* @complexity O(1)
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_descriptor
-basic_vertex_list<V,A>::add_vertex()
+typename vertex_list_impl<V,A>::vertex_descriptor
+vertex_list_impl<V,A>::add_vertex()
{
return add_vertex(vertex_properties());
}
@@ -119,8 +133,8 @@
* @complexity O(1)
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_descriptor
-basic_vertex_list<V,A>::add_vertex(vertex_properties const& vp)
+typename vertex_list_impl<V,A>::vertex_descriptor
+vertex_list_impl<V,A>::add_vertex(vertex_properties const& vp)
{
typename vertex_store::iterator i = _verts.insert(_verts.end(), vertex_type(vp));
i->iter = i;
@@ -136,7 +150,7 @@
*/
template <typename V, template <typename> class A>
void
-basic_vertex_list<V,A>::remove_vertex(vertex_descriptor v)
+vertex_list_impl<V,A>::remove_vertex(vertex_descriptor v)
{
vertex_type* vp = static_cast<vertex_type*>(v);
_verts.erase(vp->iter);
@@ -152,8 +166,8 @@
* deal to manage the size of this list internally.
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertices_size_type
-basic_vertex_list<V,A>::num_vertices() const
+typename vertex_list_impl<V,A>::vertices_size_type
+vertex_list_impl<V,A>::num_vertices() const
{
return _verts.size();
}
@@ -163,10 +177,10 @@
*/
template <typename V, template <typename> class A>
std::pair<
- typename basic_vertex_list<V,A>::vertex_iterator,
- typename basic_vertex_list<V,A>::vertex_iterator
+ typename vertex_list_impl<V,A>::vertex_iterator,
+ typename vertex_list_impl<V,A>::vertex_iterator
>
-basic_vertex_list<V,A>::vertices() const
+vertex_list_impl<V,A>::vertices() const
{
return std::make_pair(_verts.begin(), _verts.end());
}
@@ -175,8 +189,8 @@
* Return the iterator for the begining of the vertices.
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_iterator
-basic_vertex_list<V,A>::begin_vertices() const
+typename vertex_list_impl<V,A>::vertex_iterator
+vertex_list_impl<V,A>::begin_vertices() const
{
return _verts.begin();
}
@@ -185,8 +199,8 @@
* Return the iterator for the begining of the vertices.
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_iterator
-basic_vertex_list<V,A>::end_vertices() const
+typename vertex_list_impl<V,A>::vertex_iterator
+vertex_list_impl<V,A>::end_vertices() const
{
return _verts.end();
}
@@ -195,8 +209,8 @@
* Get access to the given vertex.
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_type&
-basic_vertex_list<V,A>::vertex(vertex_descriptor v)
+typename vertex_list_impl<V,A>::vertex_type&
+vertex_list_impl<V,A>::vertex(vertex_descriptor v)
{
return *static_cast<vertex_type*>(v.desc);
}
@@ -205,8 +219,8 @@
* Get access to the given vertex.
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_type const&
-basic_vertex_list<V,A>::vertex(vertex_descriptor v) const
+typename vertex_list_impl<V,A>::vertex_type const&
+vertex_list_impl<V,A>::vertex(vertex_descriptor v) const
{
return *static_cast<vertex_type*>(v.desc);
}
@@ -215,8 +229,8 @@
* Access the properties ofthe given vertex.
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_properties&
-basic_vertex_list<V,A>::properties(vertex_descriptor v)
+typename vertex_list_impl<V,A>::vertex_properties&
+vertex_list_impl<V,A>::properties(vertex_descriptor v)
{
return *vertex(v);
}
@@ -225,12 +239,14 @@
* Access the properties ofthe given vertex.
*/
template <typename V, template <typename> class A>
-typename basic_vertex_list<V,A>::vertex_properties const&
-basic_vertex_list<V,A>::properties(vertex_descriptor v) const
+typename vertex_list_impl<V,A>::vertex_properties const&
+vertex_list_impl<V,A>::properties(vertex_descriptor v) const
{
return *vertex(v);
}
+#endif
+
} /* namespace adj_list */
} /* namesapce graphs */
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_map.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_map.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -3,45 +3,63 @@
#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
#include <map>
-#include <string>
+#include <boost/graphs/adjacency_list/descriptor.hpp>
#include <boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp>
namespace boost {
namespace graphs {
namespace adj_list {
-namespace detail {
- // Extend the notion of a vertex for set storage so that we can store each
- // vertex's iterator with current vertex. This is used to provide constant
- // time access to the correct position in the underliying store.
- template <
- typename Vertex,
- typename Key,
- template <typename> class Compare,
- template <typename> class Alloc
- >
- class basic_vertex_map_node
- : public Vertex
- {
- public:
- typedef basic_vertex_map_node<Vertex, Key, Compare, Alloc> this_type;
- typedef typename Vertex::properties_type properties_type;
- typedef typename std::map<
- Key, this_type, Compare<Key>, Alloc< std::pair<Key, this_type> >
- >::iterator iterator;
-
- inline basic_vertex_map_node(properties_type const& vp)
- : Vertex(vp)
- , iter()
- { }
+// Forward declarations
+template <typename V, typename K, template <typename> class C, template <typename> class A> class vertex_map_elem;
+template <typename V, typename K, typename C, typename A> class vertex_map_impl;
+
+template <typename Key, template <typename> class Compare, template <typename> class Allocator>
+struct basic_vertex_map
+{
+ typedef basic_vertex_descriptor<void*> descriptor_type;
- iterator iter;
+ template <typename Vertex>
+ struct store
+ {
+ typedef vertex_map_elem<Vertex, Key, Compare, Allocator> stored_vertex;
+ typedef std::pair<const Key, stored_vertex> stored_value;
+ typedef vertex_map_impl<stored_vertex, Key, Compare<Key>, Allocator<stored_value> > type;
};
-} /* namespace detail */
+};
+
+template <typename Key, template <typename> class Compare = std::less>
+struct vertex_map : basic_vertex_map<Key, Compare, std::allocator> { };
+
+// Extend the notion of a vertex for set storage so that we can store each
+// vertex's iterator with current vertex. This is used to provide constant
+// time access to the correct position in the underliying store.
+template <
+ typename Vertex,
+ typename Key,
+ template <typename> class Compare,
+ template <typename> class Alloc
+ >
+class vertex_map_elem
+ : public Vertex
+{
+ typedef vertex_map_elem<Vertex, Key, Compare, Alloc> this_type;
+public:
+ typedef typename std::map<
+ Key, this_type, Compare<Key>, Alloc< std::pair<Key, this_type> >
+ >::iterator iterator;
+
+ inline vertex_map_elem(typename Vertex::vertex_properties const& vp)
+ : Vertex(vp)
+ , iter()
+ { }
+
+ iterator iter;
+};
/**
- * The basic_vertex_map provides a list-based implementation of vertex storage
+ * The vertex_map_impl provides a list-based implementation of vertex storage
* for an adjacency list. List-based storage is best for graphs with
* unidentified vertices and requirements for fast vertex addition and deletion.
*
@@ -57,32 +75,20 @@
*
* @require LessThanComparable<Vertex::properties_type>
*/
-template <
- typename Vertex,
- typename Key,
- template <typename> class Compare = std::less,
- template <typename> class Alloc = std::allocator
- >
-class basic_vertex_map
+template <typename Vertex, typename Key, typename Compare, typename Allocator>
+class vertex_map_impl
{
+ typedef std::map<Key, Vertex, Compare, Allocator> vertex_store;
public:
- typedef detail::basic_vertex_map_node<Vertex, Key, Compare, Alloc> vertex_type;
- typedef typename vertex_type::descriptor_type vertex_descriptor;
- typedef typename vertex_type::properties_type vertex_properties;
-
typedef Key key_type;
-
- typedef std::map<
- key_type, vertex_type, Compare<key_type>, Alloc< std::pair<key_type, vertex_type> >
- > vertex_store;
- typedef mapped_vertex_iterator<vertex_store> vertex_iterator;
+ typedef Vertex vertex_type;
+ typedef typename Vertex::vertex_properties vertex_properties;
+ typedef typename Vertex::vertex_descriptor vertex_descriptor;
typedef typename vertex_store::size_type vertices_size_type;
-
- // FIXME: Clearly, this should go away during conceptization.
- typedef hashed_property_map_tag vertex_property_map_category;
+ typedef mapped_vertex_iterator<vertex_store> vertex_iterator;
// Constructors
- basic_vertex_map();
+ vertex_map_impl();
// Add or insert a vertex.
vertex_descriptor add_vertex(key_type const& k, vertex_properties const& vp);
@@ -117,32 +123,18 @@
vertex_store _verts;
};
-// There isn't really a single trivial specialization of the mapped vertex
-// store since the key is a required parameter. Basically, using this type
-// requires the programmer to build different specializations of this basic
-// vertex store.
+#define BOOST_GRAPHS_VM_PARAMS \
+ typename V, typename K, typename C, typename A
-/**
- * Provide a specialization for keyed to strings.
- */
-template <typename Vertex>
-struct string_to_vertex_map : basic_vertex_map<Vertex, std::string> { };
-
-/**
- * Provide a specialization for integers.
- */
-template <typename Vertex>
-struct int_to_vertex_map : basic_vertex_map<Vertex, int> { };
-
-
-/**
- * The default constructor creates an empty vertex set.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-basic_vertex_map<V,K,C,A>::basic_vertex_map()
+template <BOOST_GRAPHS_VM_PARAMS>
+vertex_map_impl<V,K,C,A>::vertex_map_impl()
: _verts()
{ }
+#undef BOOST_GRAPHS_VM_PARAMS
+
+#if 0
+
/**
* Add a vertex to the store with the key and properties. If the key is mapped
* to a vertex, do nothing. Return a descriptor to the existing or new vertex.
@@ -150,8 +142,8 @@
* @complexity O(log(V))
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_descriptor
-basic_vertex_map<V,K,C,A>::add_vertex(const K& k, vertex_properties const& vp)
+typename vertex_map_impl<V,K,C,A>::vertex_descriptor
+vertex_map_impl<V,K,C,A>::add_vertex(const K& k, vertex_properties const& vp)
{
return insert_vertex(k, vp).first;
}
@@ -165,8 +157,8 @@
* @complexity O(log(V))
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-std::pair<typename basic_vertex_map<V,K,C,A>::vertex_descriptor, bool>
-basic_vertex_map<V,K,C,A>::insert_vertex(key_type const& k, vertex_properties const& vp)
+std::pair<typename vertex_map_impl<V,K,C,A>::vertex_descriptor, bool>
+vertex_map_impl<V,K,C,A>::insert_vertex(key_type const& k, vertex_properties const& vp)
{
std::pair<vertex_descriptor, bool> ret;
std::pair<typename vertex_store::iterator, bool> ins =
@@ -193,8 +185,8 @@
* descriptor.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_descriptor
-basic_vertex_map<V,K,C,A>::find_vertex(key_type const& k) const
+typename vertex_map_impl<V,K,C,A>::vertex_descriptor
+vertex_map_impl<V,K,C,A>::find_vertex(key_type const& k) const
{
vertex_descriptor ret;
typename vertex_store::const_iterator iter = _verts.find(k);
@@ -216,7 +208,7 @@
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
void
-basic_vertex_map<V,K,C,A>::remove_vertex(vertex_descriptor v)
+vertex_map_impl<V,K,C,A>::remove_vertex(vertex_descriptor v)
{
vertex_type* vp = static_cast<vertex_type*>(v);
_verts.erase(vp->iter);
@@ -232,8 +224,8 @@
* deal to manage the size of this list internally.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertices_size_type
-basic_vertex_map<V,K,C,A>::num_vertices() const
+typename vertex_map_impl<V,K,C,A>::vertices_size_type
+vertex_map_impl<V,K,C,A>::num_vertices() const
{
return _verts.size();
}
@@ -243,10 +235,10 @@
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
std::pair<
- typename basic_vertex_map<V,K,C,A>::vertex_iterator,
- typename basic_vertex_map<V,K,C,A>::vertex_iterator
+ typename vertex_map_impl<V,K,C,A>::vertex_iterator,
+ typename vertex_map_impl<V,K,C,A>::vertex_iterator
>
-basic_vertex_map<V,K,C,A>::vertices() const
+vertex_map_impl<V,K,C,A>::vertices() const
{
return std::make_pair(_verts.begin(), _verts.end());
}
@@ -255,24 +247,24 @@
* Get a vertex iterator to the beginning iterator of the vertices.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_iterator
-basic_vertex_map<V,K,C,A>::begin_vertices() const
+typename vertex_map_impl<V,K,C,A>::vertex_iterator
+vertex_map_impl<V,K,C,A>::begin_vertices() const
{ return _verts.begin(); }
/**
* Get a vertex iterator to an iterator past the end of the vertices.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_iterator
-basic_vertex_map<V,K,C,A>::end_vertices() const
+typename vertex_map_impl<V,K,C,A>::vertex_iterator
+vertex_map_impl<V,K,C,A>::end_vertices() const
{ return _verts.end(); }
/**
* Get access to the given vertex.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_type&
-basic_vertex_map<V,K,C,A>::vertex(vertex_descriptor v)
+typename vertex_map_impl<V,K,C,A>::vertex_type&
+vertex_map_impl<V,K,C,A>::vertex(vertex_descriptor v)
{
return *static_cast<vertex_type*>(v.desc);
}
@@ -281,8 +273,8 @@
* Get access to the given vertex.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_type const&
-basic_vertex_map<V,K,C,A>::vertex(vertex_descriptor v) const
+typename vertex_map_impl<V,K,C,A>::vertex_type const&
+vertex_map_impl<V,K,C,A>::vertex(vertex_descriptor v) const
{
return *static_cast<vertex_type*>(v.desc);
}
@@ -291,8 +283,8 @@
* Return a descriptor for the given vertex.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_descriptor
-basic_vertex_map<V,K,C,A>::descriptor(vertex_type const& v) const
+typename vertex_map_impl<V,K,C,A>::vertex_descriptor
+vertex_map_impl<V,K,C,A>::descriptor(vertex_type const& v) const
{
return &const_cast<vertex_type&>(v);
}
@@ -301,8 +293,8 @@
* Get the key of a vertex descriptor.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::key_type const&
-basic_vertex_map<V,K,C,A>::key(vertex_descriptor v) const
+typename vertex_map_impl<V,K,C,A>::key_type const&
+vertex_map_impl<V,K,C,A>::key(vertex_descriptor v) const
{
vertex_type& vert = *static_cast<vertex_type*>(v.desc);
return vert.iter->first;
@@ -313,8 +305,8 @@
* Get the properties of the given vertex.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_properties&
-basic_vertex_map<V,K,C,A>::properties(vertex_descriptor v)
+typename vertex_map_impl<V,K,C,A>::vertex_properties&
+vertex_map_impl<V,K,C,A>::properties(vertex_descriptor v)
{
return *vertex(v);
}
@@ -323,12 +315,14 @@
* Get the properties of the given vertex.
*/
template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename basic_vertex_map<V,K,C,A>::vertex_properties const&
-basic_vertex_map<V,K,C,A>::properties(vertex_descriptor v) const
+typename vertex_map_impl<V,K,C,A>::vertex_properties const&
+vertex_map_impl<V,K,C,A>::properties(vertex_descriptor v) const
{
return *vertex(v);
}
+#endif
+
} /* namespace adj_list */
} /* namesapce graphs */
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_set.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -5,44 +5,58 @@
#include <set>
#include <tr1/unordered_map>
-#include <boost/graphs/properties.hpp>
+#include <boost/graphs/adjacency_list/descriptor.hpp>
#include <boost/graphs/adjacency_list/vs/simple_vertex_iterator.hpp>
namespace boost {
namespace graphs {
namespace adj_list {
-namespace detail {
- // Extend the notion of a vertex for set storage so that we can store each
- // vertex's iterator with current vertex. This is used to provide constant
- // time access to the correct position in the underliying store.
- template <
- typename Vertex,
- template <typename> class Compare,
- template <typename> class Alloc>
- class basic_vertex_set_node
- : public Vertex
- {
- public:
- typedef basic_vertex_set_node<Vertex, Compare, Alloc> this_type;
- typedef typename Vertex::properties_type properties_type;
-
- typedef typename std::set<
- this_type, Compare<this_type>, Alloc<this_type>
- >::iterator iterator;
-
- inline basic_vertex_set_node(properties_type const& vp)
- : Vertex(vp)
- , iter()
- { }
+// Forward declarations
+template <typename V, template <typename> class C, template <typename> class A> class vertex_set_elem;
+template <typename V, typename C, typename A> class vertex_set_impl;
+
+template <template <typename> class Compare, template <typename> class Allocator>
+struct basic_vertex_set
+{
+ typedef basic_vertex_descriptor<void*> descriptor_type;
- iterator iter;
+ template <typename Vertex>
+ struct store
+ {
+ typedef vertex_set_elem<Vertex, Compare, Allocator> stored_vertex;
+ typedef vertex_set_impl<stored_vertex, Compare<stored_vertex>, Allocator<stored_vertex> > type;
};
+};
+
+template <template <typename> class Compare = std::less>
+struct vertex_set : basic_vertex_set<Compare, std::allocator> { };
+
+// Extend the notion of a vertex for set storage so that we can store each
+// vertex's iterator with current vertex. This is used to provide constant
+// time access to the correct position in the underliying store.
+template <typename Vertex,
+ template <typename> class Compare,
+ template <typename> class Alloc>
+class vertex_set_elem
+ : public Vertex
+{
+ typedef vertex_set_elem<Vertex, Compare, Alloc> this_type;
+public:
+ typedef typename std::set<
+ this_type, Compare<this_type>, Alloc<this_type>
+ >::iterator iterator;
+
+ inline vertex_set_elem(typename Vertex::vertex_properties const& vp)
+ : Vertex(vp)
+ , iter()
+ { }
-} /* namespace detail */
+ iterator iter;
+};
/**
- * The basic_vertex_set provides a list-based implementation of vertex storage
+ * The vertex_set_impl provides a list-based implementation of vertex storage
* for an adjacency list. List-based storage is best for graphs with
* unidentified vertices and requirements for fast vertex addition and deletion.
*
@@ -58,31 +72,20 @@
*
* @require LessThanComparable<Vertex::properties_type>
*/
-template <
- typename Vertex,
- template <typename> class Compare = std::less,
- template <typename> class Alloc = std::allocator
- >
-class basic_vertex_set
+template <typename Vertex, typename Compare, typename Allocator>
+class vertex_set_impl
{
+ typedef std::set<Vertex, Compare, Allocator> vertex_store;
public:
- typedef detail::basic_vertex_set_node<Vertex, Compare, Alloc> vertex_type;
- typedef typename vertex_type::descriptor_type vertex_descriptor;
- typedef typename vertex_type::properties_type vertex_properties;
-
- typedef std::set<
- vertex_type, Compare<vertex_type>, Alloc<vertex_type>
- > vertex_store;
- typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+ typedef Vertex vertex_type;
+ typedef typename Vertex::vertex_properties vertex_properties;
+ typedef typename Vertex::vertex_descriptor vertex_descriptor;
typedef typename vertex_store::size_type vertices_size_type;
-
- // This is kind of hack, but we need some way of communicating a preference
- // of the favored underlying property store to higher level features.
- // FIXME: Clearly, this should go away during conceptization.
- typedef hashed_property_map_tag vertex_property_map_category;
+ typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+ typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
// Constructors
- basic_vertex_set();
+ vertex_set_impl();
// Add vertices. Note that you can't add without properties.
vertex_descriptor add_vertex(vertex_properties const& vp);
@@ -114,36 +117,18 @@
};
-/**
- * The default implementation of a vertex set is given here. Specialized
- * versions of the basic vertex set can be generated using inheritance like
- * this. This version fixes the default comparator and allocator of the vertex
- * set to the common defaults.
- */
-template <typename Vertex>
-struct vertex_set : basic_vertex_set<Vertex> { };
-
-// Some examples of specialized (curried) variants of the basic vertex set.
-// These provide specific orderings. Note that the "less set" is actually the
-// same as the default vertex set.
-template <typename Vertex>
-struct min_vertex_set : public basic_vertex_set<Vertex, std::less> { };
-
-template <typename Vertex>
-struct max_vertex_set : public basic_vertex_set<Vertex, std::greater> { };
-
+#define BOOST_GRAPHS_VS_PARAMS \
+ typename V, typename C, typename A
-#define BOOST_GRAPH_VS_PARAMS \
- typename V, template <typename> class C, template <typename> class A
-
-/**
- * The default constructor creates an empty vertex set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-basic_vertex_set<V,C,A>::basic_vertex_set()
+template <BOOST_GRAPHS_VS_PARAMS>
+vertex_set_impl<V,C,A>::vertex_set_impl()
: _verts()
{ }
+#undef BOOST_GRAPHS_VS_PARAMS
+
+#if 0
+
/**
* Add a vertex to the store with the given properties. If not specified, the
* vertex is created with default properties. Note that vertices are not mapped
@@ -152,8 +137,8 @@
* @complexity O(log(V))
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_descriptor
-basic_vertex_set<V,C,A>::add_vertex(vertex_properties const& vp)
+typename vertex_set_impl<V,C,A>::vertex_descriptor
+vertex_set_impl<V,C,A>::add_vertex(vertex_properties const& vp)
{
return insert_vertex(vp).first;
}
@@ -167,8 +152,8 @@
* @complexity O(log(V))
*/
template <BOOST_GRAPH_VS_PARAMS>
-std::pair<typename basic_vertex_set<V,C,A>::vertex_descriptor, bool>
-basic_vertex_set<V,C,A>::insert_vertex(vertex_properties const& vp)
+std::pair<typename vertex_set_impl<V,C,A>::vertex_descriptor, bool>
+vertex_set_impl<V,C,A>::insert_vertex(vertex_properties const& vp)
{
std::pair<vertex_descriptor, bool> ret;
std::pair<typename vertex_store::iterator, bool> ins =
@@ -197,7 +182,7 @@
*/
template <BOOST_GRAPH_VS_PARAMS>
void
-basic_vertex_set<V,C,A>::remove_vertex(vertex_descriptor v)
+vertex_set_impl<V,C,A>::remove_vertex(vertex_descriptor v)
{
vertex_type* vp = static_cast<vertex_type*>(v.desc);
_verts.erase(vp->iter);
@@ -210,7 +195,7 @@
*/
template <BOOST_GRAPH_VS_PARAMS>
void
-basic_vertex_set<V,C,A>::remove_vertex(vertex_properties const& vp)
+vertex_set_impl<V,C,A>::remove_vertex(vertex_properties const& vp)
{
remove_vertex(find(vp));
}
@@ -221,8 +206,8 @@
* @complexity O(log(V))
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_descriptor
-basic_vertex_set<V,C,A>::find_vertex(vertex_properties const& vp) const
+typename vertex_set_impl<V,C,A>::vertex_descriptor
+vertex_set_impl<V,C,A>::find_vertex(vertex_properties const& vp) const
{
// This is a little gross... We have to tempoararily construct an empty
// vertex with the given properties in order for the find operations to
@@ -245,8 +230,8 @@
* deal to manage the size of this list internally.
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertices_size_type
-basic_vertex_set<V,C,A>::num_vertices() const
+typename vertex_set_impl<V,C,A>::vertices_size_type
+vertex_set_impl<V,C,A>::num_vertices() const
{
return _verts.size();
}
@@ -256,10 +241,10 @@
*/
template <BOOST_GRAPH_VS_PARAMS>
std::pair<
- typename basic_vertex_set<V,C,A>::vertex_iterator,
- typename basic_vertex_set<V,C,A>::vertex_iterator
+ typename vertex_set_impl<V,C,A>::vertex_iterator,
+ typename vertex_set_impl<V,C,A>::vertex_iterator
>
-basic_vertex_set<V,C,A>::vertices() const
+vertex_set_impl<V,C,A>::vertices() const
{
return std::make_pair(_verts.begin(), _verts.end());
}
@@ -268,8 +253,8 @@
* Get a vertex iterator to the beginning iterator of the vertices.
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_iterator
-basic_vertex_set<V,C,A>::begin_vertices() const
+typename vertex_set_impl<V,C,A>::vertex_iterator
+vertex_set_impl<V,C,A>::begin_vertices() const
{
return _verts.begin();
}
@@ -278,8 +263,8 @@
* Get a vertex iterator to an iterator past the end of the vertices.
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_iterator
-basic_vertex_set<V,C,A>::end_vertices() const
+typename vertex_set_impl<V,C,A>::vertex_iterator
+vertex_set_impl<V,C,A>::end_vertices() const
{
return _verts.end();
}
@@ -288,8 +273,8 @@
* Get access to the given vertex.
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_type&
-basic_vertex_set<V,C,A>::vertex(vertex_descriptor v)
+typename vertex_set_impl<V,C,A>::vertex_type&
+vertex_set_impl<V,C,A>::vertex(vertex_descriptor v)
{
return *static_cast<vertex_type*>(v.desc);
}
@@ -298,8 +283,8 @@
* Get access to the given vertex.
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_type const&
-basic_vertex_set<V,C,A>::vertex(vertex_descriptor v) const
+typename vertex_set_impl<V,C,A>::vertex_type const&
+vertex_set_impl<V,C,A>::vertex(vertex_descriptor v) const
{
return *static_cast<vertex_type*>(v.desc);
}
@@ -308,8 +293,8 @@
* Access the properties of the given vertex.
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_properties&
-basic_vertex_set<V,C,A>::properties(vertex_descriptor v)
+typename vertex_set_impl<V,C,A>::vertex_properties&
+vertex_set_impl<V,C,A>::properties(vertex_descriptor v)
{
return *vertex(v);
}
@@ -318,14 +303,15 @@
* Access the properties of the given vertex.
*/
template <BOOST_GRAPH_VS_PARAMS>
-typename basic_vertex_set<V,C,A>::vertex_properties const&
-basic_vertex_set<V,C,A>::properties(vertex_descriptor v) const
+typename vertex_set_impl<V,C,A>::vertex_properties const&
+vertex_set_impl<V,C,A>::properties(vertex_descriptor v) const
{
return *vertex(v);
}
-} /* namespace adj_list */
+#endif
+} /* namespace adj_list */
} /* namesapce graphs */
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/boost/graphs/adjacency_list/vs/vertex_vector.hpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -4,31 +4,30 @@
#include <vector>
-#include <boost/graphs/properties.hpp>
+#include <boost/graphs/adjacency_list/descriptor.hpp>
#include <boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp>
namespace boost {
namespace graphs {
namespace adj_list {
-/**
- */
+// Forward declarations
+template <typename V, typename A> struct vertex_vector_impl;
+
template <template <typename> class Allocator>
struct basic_vertex_vector
{
typedef basic_vertex_descriptor<std::size_t> descriptor_type;
template <typename Vertex>
- struct type
+ struct store
{
- typedef Allocator<Vertex> allocator;
- typedef std::vector<Vertex, allocator> store;
+ typedef vertex_vector_impl<Vertex, Allocator<Vertex> > type;
};
};
struct vertex_vector : basic_vertex_vector<std::allocator> { };
-#if 0
/**
* The vertex_vector template implements veretex storage for adjacency lists
@@ -41,26 +40,20 @@
* corrupt the entire graph (since indices are adjusted). As a result, this
* store type does not provide remove operations.
*/
-template <
- typename Vertex,
- template <typename> class Alloc
- >
-class basic_vertex_vector
+template <typename Vertex, typename Allocator>
+class vertex_vector_impl
{
+ typedef std::vector<Vertex, Allocator> vertex_store;
public:
typedef Vertex vertex_type;
- typedef typename vertex_type::descriptor_type vertex_descriptor;
- typedef typename vertex_type::properties_type vertex_properties;
-
- typedef std::vector<vertex_type, Alloc<vertex_type> > vertex_store;
- typedef indexed_vertex_iterator<vertex_store> vertex_iterator;
+ typedef typename Vertex::vertex_properties vertex_properties;
+ typedef typename Vertex::vertex_descriptor vertex_descriptor;
typedef typename vertex_store::size_type vertices_size_type;
-
- // FIXME: This is old school.
- typedef indexed_property_map_tag vertex_property_map_category;
+ typedef indexed_vertex_iterator<vertex_store> vertex_iterator;
+ typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
// Constructors
- basic_vertex_vector();
+ vertex_vector_impl();
// Add/remove vertex.
vertex_descriptor add_vertex();
@@ -70,7 +63,7 @@
vertices_size_type num_vertices() const;
// Vertex iteration.
- std::pair<vertex_iterator, vertex_iterator> vertices() const;
+ vertex_range vertices() const;
vertex_iterator begin_vertices() const;
vertex_iterator end_vertices() const;
@@ -84,6 +77,18 @@
vertex_store _verts;
};
+#define BOOST_GRAPHS_VV_PARAMS \
+ typename V, typename A
+
+template <BOOST_GRAPHS_VV_PARAMS>
+vertex_vector_impl<V,A>::vertex_vector_impl()
+ : _verts()
+{ }
+
+#undef BOOST_GRAPHS_VV_PARAMS
+
+#if 0
+
/**
* Specialization of the storage traits to redefine the descriptor. Vectors for
* any store type must use their indices as descriptors since the underlying
Modified: sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/Jamfile 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -1,6 +1,6 @@
-exe ordered_pair : ordered_pair.cpp : <include>../../ ;
-exe unordered_pair : unordered_pair.cpp : <include>../../ ;
+# exe ordered_pair : ordered_pair.cpp : <include>../../ ;
+# exe unordered_pair : unordered_pair.cpp : <include>../../ ;
exe adjacency_list : adjacency_list.cpp : <include>../../ <include>/usr/local/include ;
-exe bfs : bfs.cpp : <include>../../ <include>/usr/local/include ;
-exe incidence : incidence.cpp : <include>../../ <include>/usr/local/include ;
+# exe bfs : bfs.cpp : <include>../../ <include>/usr/local/include ;
+# exe incidence : incidence.cpp : <include>../../ <include>/usr/local/include ;
Modified: sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/adjacency_list.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/adjacency_list.cpp (original)
+++ sandbox/SOC/2008/graphs/branches/tagged/libs/graphs/adjacency_list.cpp 2008-06-04 07:27:36 EDT (Wed, 04 Jun 2008)
@@ -26,6 +26,17 @@
static const int V = 100;
static const int E = 100;
+template <typename Graph>
+void print_types(const Graph&)
+{
+ cout << demangle(typeid(typename Graph::vertex_descriptor).name()) << endl << endl;
+ cout << demangle(typeid(typename Graph::edge_descriptor).name()) << endl << endl;
+ cout << demangle(typeid(typename Graph::incidence_store).name()) << endl << endl;
+ cout << demangle(typeid(typename Graph::vertex_type).name()) << endl << endl;
+ cout << demangle(typeid(typename Graph::edge_type).name()) << endl << endl;
+ cout << demangle(typeid(typename Graph::vertex_store).name()) << endl << endl;
+ cout << demangle(typeid(typename Graph::edge_store).name()) << endl << endl;
+}
int
main(int argc, char *argv[])
@@ -43,13 +54,15 @@
void undirected_vector_vector_vector()
{
typedef adjacency_list<
- undirected, int, int, vertex_vector, edge_vector, vertex_edge_vector
+ undirected, int, int, vertex_vector, edge_vector, incidence_vector, none
> Graph;
Graph g;
+ // print_types(g);
+
+ /*
add_vertices(g, V);
add_edges(g, E);
-
- // cout << demangle(typeid(Graph::this_type).name()) << endl;
+ */
}
// Best used for fast graph construction. This graph supports vertex and edge
@@ -58,11 +71,14 @@
void undirected_list_list_list()
{
typedef adjacency_list<
- undirected, int, int, vertex_list, edge_list, vertex_edge_list
+ undirected, int, int, vertex_list, edge_list, incidence_vector, none
> Graph;
Graph g;
+ print_types(g);
+ /*
add_vertices(g, V);
add_edges(g, E);
+ */
}
// This is probably the best all-around implementation of simple graphs
@@ -72,10 +88,12 @@
void undirected_set_set_set()
{
typedef adjacency_list<
- undirected, int, int, vertex_set, edge_set, vertex_edge_set
+ undirected, int, int, vertex_set<>, edge_set<std::greater>, incidence_vector, none
> Graph;
Graph g;
+ /*
add_vertices(g, V);
+ */
}
// Pretty much the same as above, but vertices are mapped to a key.
@@ -85,9 +103,11 @@
void undirected_map_set_set()
{
typedef adjacency_list<
- undirected, int, int, int_to_vertex_map, edge_set, vertex_edge_set
+ undirected, int, int, vertex_map<int>, edge_set<>, incidence_vector, none
> Graph;
Graph g;
+ /*
add_mapped_vertices(g, V);
+ */
}
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