[Boost-commit] svn:boost r47273 - in sandbox/SOC/2008/graphs/trunk: boost/graphs libs/graphs

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>();