From: asutton_at_[hidden]
Date: 2008-07-09 13:04:53
Author: asutton
Date: 2008-07-09 13:04:51 EDT (Wed, 09 Jul 2008)
New Revision: 47273
URL: http://svn.boost.org/trac/boost/changeset/47273
Log:
Reimplemented edge addition for directed graphs.
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 9 +++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 46 ++++++++++++++++-----------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp | 24 ++++++++++++--------
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 5 +++
4 files changed, 46 insertions(+), 38 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp 2008-07-09 13:04:51 EDT (Wed, 09 Jul 2008)
@@ -34,6 +34,15 @@
{ }
//@}
+ /** @name Descriptor-like Functions. */
+ //@{
+ inline bool is_null() const
+ { return out.is_null(); }
+
+ inline operator bool() const
+ { return !is_null(); }
+ //@}
+
/** Return the source vertex descriptor. */
inline vertex_descriptor source() const
{ return ends.first; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp 2008-07-09 13:04:51 EDT (Wed, 09 Jul 2008)
@@ -68,10 +68,10 @@
typedef typename types::out_edge_range out_edge_range;
typedef typename types::in_edge_iterator in_edge_iterator;
typedef typename types::in_edge_range in_edge_range;
- typedef typename types::incident_edge_iterator incident_edge_iterator;
- typedef typename types::incident_edge_range incident_edge_range;
- typedef typename types::adjacent_vertex_iterator adjacent_vertex_iterator;
- typedef typename types::adjacent_vertex_range adjacent_vertex_range;
+ // typedef typename types::incident_edge_iterator incident_edge_iterator;
+ // typedef typename types::incident_edge_range incident_edge_range;
+ // typedef typename types::adjacent_vertex_iterator adjacent_vertex_iterator;
+ // typedef typename types::adjacent_vertex_range adjacent_vertex_range;
// Sizes for vertices, and degree.
typedef typename types::vertices_size_type vertices_size_type;
@@ -384,35 +384,27 @@
vertex_descriptor v,
edge_properties const& ep)
{
- typedef typename vertex_type::out_iterator out_iterator;
- typedef typename vertex_type::in_iterator in_iterator;
-
vertex_type &src = _verts.vertex(u);
vertex_type &tgt = _verts.vertex(v);
- // Do we add the edge or not?
- std::pair<out_iterator, bool> ins = src.allow(v);
- if(ins.second) {
- // If the returned iterator is past the end, then we have to create and
- // connect the edge.
- if(ins.first == src.end_out()) {
- ++_edges;
-
- // Insert the edge stubs, getting iterators to each stub.
- out_iterator i = src.connect_target(v, ep);
- in_iterator j = tgt.connect_source(u);
- edge_descriptor e = vertex_type::bind_connection(i, j);
- return e;
- }
- else {
- return edge_descriptor(u, ins.first);
- }
+ insertion_result<out_descriptor> first = src.connect_target(v, ep);
+ if(first.succeeded()) {
+ insertion_result<in_descriptor> second = tgt.connect_source(u, first.value);
+ BOOST_ASSERT(second.succeeded());
+
+ // Bind the out edge to the in edge and return the edge (incrementing
+ // the locally stored number of edges also).
+ src.bind_target(first.value, second.value);
+ ++_edges;
+ return edge_descriptor(u, v, first.value);
+ }
+ else if(first.retained()) {
+ // Return an edge over the existing values.
+ return edge_descriptor(u, v, first.value);
}
else {
- // Can't add the edge? This is a flat refusal (as in a loop).
+ return edge_descriptor();
}
-
- return edge_descriptor();
}
/**
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp 2008-07-09 13:04:51 EDT (Wed, 09 Jul 2008)
@@ -35,7 +35,7 @@
* implement a directed graph.
*/
template <typename VertexProps, typename EdgeProps, typename VertexStore, typename EdgeStore>
-class directed_types
+struct directed_types
{
// Start by generating all of the descriptors.
typedef typename VertexStore::vertex_descriptor vertex_descriptor;
@@ -46,17 +46,17 @@
typedef directed_edge<out_descriptor, in_descriptor> edge_descriptor;
// Generate the out store and related types
- typedef typename EdgeStore::template out_store<vertex_descriptor, EdgeProps> out_store;
+ typedef typename EdgeStore::template out_store<vertex_descriptor, EdgeProps>::type out_store;
typedef typename out_store::size_type out_edges_size_type;
typedef typename out_store::size_type edges_size_type;
- typedef basic_out_iterator<out_store, edge_descriptor> out_edge_iterator;
- typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
// Generate the in store and related types
- typedef typename EdgeStore::template in_store<vertex_descriptor> in_store;
- typedef typename in_store::size_type in_edge_size_type;
- typedef basic_in_iterator<typename in_store::iterator, edge_descriptor> in_edge_iterator;
- typedef std::pair<in_edge_iterator, in_edge_iterator> in_edge_range;
+ typedef typename EdgeStore::template in_store<vertex_descriptor>::type in_store;
+ typedef typename in_store::size_type in_edges_size_type;
+
+ // Generate the incident edge size type. It should be the larger of the two,
+ // but for now it's just the out edges.
+ typedef out_edges_size_type incident_edges_size_type;
// Generate the vertex, its store, and related types.
typedef directed_vertex<VertexProps, out_store, in_store> vertex_type;
@@ -64,9 +64,13 @@
typedef typename vertex_store::size_type vertices_size_type;
typedef typename vertex_store::vertex_iterator vertex_iterator;
typedef typename vertex_store::vertex_range vertex_range;
- typedef typename vertex_store::vertex_key vertex_key;
+ typedef typename VertexStore::key_type vertex_key;
- // Generate the edge iterators as far back as possible...
+ // Generate a bunch of iterators
+ typedef basic_out_iterator<out_store, edge_descriptor> out_edge_iterator;
+ typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
+ typedef basic_in_iterator<typename in_store::iterator, edge_descriptor> in_edge_iterator;
+ typedef std::pair<in_edge_iterator, in_edge_iterator> in_edge_range;
typedef directed_edge_iterator<vertex_store, edge_descriptor> edge_iterator;
typedef std::pair<edge_iterator, edge_iterator> edge_range;
};
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-07-09 13:04:51 EDT (Wed, 09 Jul 2008)
@@ -33,6 +33,7 @@
void test_add_vertices()
{
Graph g;
+ cout << " * adding vertices" << endl;
list<typename Graph::vertex_descriptor> V;
for(int i = 0; i < 5; ++i) {
V.push_back(g.add_vertex(i));
@@ -63,6 +64,8 @@
for(int i = 0; i < 3; ++i) {
V.push_back(g.add_vertex(i));
}
+
+ cout << " * adding edges" << endl;
g.add_edge(V[0], V[1]);
g.add_edge(V[1], V[2]);
g.add_edge(V[2], V[0]);
@@ -255,10 +258,10 @@
void vec_vec()
{
cout << "---- vec/vec ----" << endl;
- /*
typedef directed_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
test_add_vertices<Graph>();
test_add_edges<Graph>();
+ /*
test_add_multi_edges<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();