[Boost-commit] svn:boost r54981 - in sandbox/SOC/2009/function_graph: boost/function_graph libs/test

Subject: [Boost-commit] svn:boost r54981 - in sandbox/SOC/2009/function_graph: boost/function_graph libs/test
From: mlopez7_at_[hidden]
Date: 2009-07-16 14:32:42

Author: lopezeant
Date: 2009-07-16 14:32:41 EDT (Thu, 16 Jul 2009)
New Revision: 54981
URL: http://svn.boost.org/trac/boost/changeset/54981

Log:
Edge iterator has been added to test3.cpp.
Text files modified: 
   sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp |    95 +++++++++++++++++++++++++++------------ 
   sandbox/SOC/2009/function_graph/libs/test/test3.cpp                     |    79 ++++++++++++++++++++++++++++++--        
   2 files changed, 138 insertions(+), 36 deletions(-)

Modified: sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp
==============================================================================
--- sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp	(original)
+++ sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp	2009-07-16 14:32:41 EDT (Thu, 16 Jul 2009)
@@ -41,8 +41,8 @@
 struct infinite_domain_tag { };
 struct function_graph_traversal_tag
     : public virtual incidence_graph_tag,
-      public virtual adjacency_graph_tag,
       public virtual bidirectional_graph_tag,
+      public virtual adjacency_graph_tag,
       public virtual vertex_list_graph_tag,
       public virtual edge_list_graph_tag,
       public virtual adjacency_matrix_tag
@@ -208,19 +208,19 @@
     typedef typename Base::vertex_type vertex_descriptor;
     typedef typename Base::edge_type edge_descriptor;
     typedef typename Base::result_type result_type;
-    typedef std::size_t degree_size_type;
-    typedef std::size_t vertices_size_type;
+    typedef unsigned int degree_size_type;
+    typedef unsigned int vertices_size_type;
+    typedef unsigned int edges_size_type;
     typedef directed_tag directed_category;
     typedef disallow_parallel_edge_tag edge_parallel_category;
     typedef function_graph_traversal_tag traversal_category;
     typedef Range vertex_iterator_range;
     typedef typename range_iterator<vertex_iterator_range>::type
                          vertex_iterator;
-    typedef function_graph_edge_iterator<This> edge_iterator;
-    typedef std::size_t edges_size_type;
     typedef function_graph_in_edge_iterator<This> in_edge_iterator;
     typedef function_graph_out_edge_iterator<This> out_edge_iterator;
     typedef function_graph_adjacency_iterator<This> adjacency_iterator;
+    typedef function_graph_edge_iterator<This> edge_iterator;
     typedef finite_domain_tag domain_category;
 
     /** Constructor: takes a functor and range */
@@ -310,12 +310,12 @@
     typedef typename Graph::vertex_iterator vertex_iterator;
     typedef typename FUNC_GRAPH::degree_size_type degree_size_type;
 
-    degree_size_type out_edges();
+    degree_size_type out_edges = 0;
     vertex_iterator vertex_at(begin(g.range_));
     vertex_iterator vertex_end(end(g.range_));
     for(;vertex_at != vertex_end; ++vertex_at)
     {
-        if(g.edge_(u, *vertex_at)) ++out_edges;
+        if(edge(u, *vertex_at, g).second) ++out_edges;
     }
 
     return out_edges;
@@ -329,17 +329,18 @@
     typedef typename Graph::vertex_iterator vertex_iterator;
     typedef typename FUNC_GRAPH::degree_size_type degree_size_type;
 
-    degree_size_type in_edges();
+    degree_size_type in_edges = 0;
     vertex_iterator vertex_at(begin(g.range_));
     vertex_iterator vertex_end(end(g.range_));
     for(;vertex_at != vertex_end; ++vertex_at)
     {
-        if(g.edge_(*vertex_at, v)) ++in_edges;
+        if(edge(*vertex_at, v, g).second) ++in_edges;
     }
 
     return in_edges;
 }
 
+/** @note Should not rely on in_degree and out_degree */
 template<typename Result, typename Vertex, typename Range>
 typename FUNC_GRAPH::degree_size_type
 degree(typename FUNC_GRAPH::vertex_descriptor const& v, FUNC_GRAPH const& g)
@@ -629,10 +630,7 @@
     //@{
     function_graph_adjacency_iterator(graph_type const& g,
                                       vertex_descriptor const& vertex)
-        : g_(g),
-          vertex_(vertex),
-          i_at_(begin(g_.range_)),
-          in_edge_check_(true)
+        : g_(g), vertex_(vertex), i_at_(begin(g_.range_)), in_edge_check_(true)
     {
         const vertex_iterator i_end = end(g_.range_);
 
@@ -647,6 +645,15 @@
         }
     }
 
+    function_graph_adjacency_iterator(graph_type const& g,
+                                      vertex_descriptor const& vertex,
+                                      bool overload)
+        : g_(g),
+          vertex_(vertex),
+          i_at_(end(g.range_)),
+          in_edge_check_(false)
+    { }
+
     function_graph_adjacency_iterator(This const& cp)
         : g_(cp.g_),
           vertex_(cp.vertex_),
@@ -702,6 +709,22 @@
     return !(lhs == rhs);
 }
 
+/** adjacent_vertices - returns a pair of adjacency iterators relative to v. */
+template <typename Graph>
+std::pair<
+    typename Graph::adjacency_iterator,
+    typename Graph::adjacency_iterator
+>
+adjacent_vertices(typename Graph::vertex_descriptor const& v, Graph const& g)
+{
+    typedef Graph graph_type;
+    typedef typename graph_type::adjacency_iterator adjacency_iterator;
+
+    return std::make_pair(adjacency_iterator(g, v),
+                          adjacency_iterator(g, v, true));
+}
+
+
 
 /** Edge Iterator - iterates through all edges */
 template<typename Graph>
@@ -729,18 +752,19 @@
     {
         const vertex_iterator i_begin = begin(g_.range_);
         const vertex_iterator i_end = end(g_.range_);
-        bool not_done = true;
+        bool done = true;
 
-        for(vertex_iterator i_at_1 = i_begin;
-            i_at_1 != i_end && not_done;
-            ++i_at_1)
+        for(; i_at_1_ != i_end; ++i_at_1_)
         {
-            for(vertex_iterator i_at_2 = i_begin;
-                i_at_2 != i_end && not_done;
-                ++i_at_2)
+            for(; i_at_2_ != i_end; ++i_at_2_)
             {
-                if(edge(*i_at_1, *i_at_2, g).second) not_done = false;
+                if(edge(*i_at_1_, *i_at_2_, g).second)
+                {
+                    done = true;
+                    break;
+                }
             }
+            if(done) break;
         }
     }
 
@@ -758,16 +782,27 @@
     {
         const vertex_iterator i_begin = begin(g_.range_);
         const vertex_iterator i_end = end(g_.range_);
-        bool not_done = true;
+        bool done = false;
 
-        do {
-            do {
-                ++i_at_2_;
-                not_done = !edge(*i_at_1_, *i_at_2_ , g_).second;
-            } while(i_at_2_ != i_end && not_done);
+        
+        if(++i_at_2_ == i_end)
+        {
             ++i_at_1_;
-            i_at_2_ = i_begin;
-        } while(i_at_1_ != i_end && not_done);
+            if(i_at_1_ != i_end) i_at_2_ = i_begin;
+        }
+
+        for(; i_at_1_ != i_end; ++i_at_1_)
+        {
+            for(; i_at_2_ != i_end; ++i_at_2_)
+            {
+                if(edge(*i_at_1_, *i_at_2_, g_).second)
+                {
+                    done = true;
+                    break;
+                }
+            }
+            if(done) break;
+        }
 
         return *this;
     }
@@ -826,7 +861,7 @@
     const vertex_iterator i_begin = begin(g.range_);
     const vertex_iterator i_end = end(g.range_);
 
-    edges_size_type edges_count();
+    edges_size_type edges_count = 0;
 
     for(vertex_iterator i_at_1 = i_begin; i_at_1 != i_end; ++i_at_1)
     {

Modified: sandbox/SOC/2009/function_graph/libs/test/test3.cpp
==============================================================================
--- sandbox/SOC/2009/function_graph/libs/test/test3.cpp	(original)
+++ sandbox/SOC/2009/function_graph/libs/test/test3.cpp	2009-07-16 14:32:41 EDT (Thu, 16 Jul 2009)
@@ -1,8 +1,19 @@
 /**
  * Testing a function that has a range
  *
- * Functions used in test:
- *   vertices(g)
+ * Functions checklist:
+ *  [X] source(e, g)
+ *  [X] target(e, g)
+ *  [X] out_edges(u, g)
+ *  [X] out_degree(u, g)
+ *  [X] in_edges(v, g)
+ *  [X] in_degree(v, g)
+ *  [ ] degree(v, g)
+ *  [ ] adjacent_vertices(v, g)
+ *  [X] vertices(g)
+ *  [X] num_vertives(g)
+ *  [X] edegs(g)
+ *  [X] num_edges(g)
  */
 
 #include <iostream>
@@ -25,6 +36,11 @@
     std::cout << "\nEdge:\n" << "  Source: " << e.source << "\n";
     std::cout << "  Target: " << e.target << "\n";
 }
+template<typename Graph>
+void print_edge_alt(typename Graph::edge_descriptor const& e, Graph const& g)
+{
+    std::cout << "\n(" << e.source << ", " << e.target << ")";
+}
 } // namespace
 
 int main()
@@ -60,6 +76,14 @@
                 weighted_graph::out_edge_iterator,
                 weighted_graph::out_edge_iterator
             > out_edge_wght_range;
+    typedef std::pair<
+                boolean_graph::edge_iterator,
+                boolean_graph::edge_iterator
+            > edge_bool_range;
+    typedef std::pair<
+                weighted_graph::edge_iterator,
+                weighted_graph::edge_iterator
+            > edge_wght_range;
 
 
 
@@ -114,39 +138,52 @@
     in_edge_bool_range in_edges_bool = boost::in_edges(*aVertex, booleanGraph);
     // Print all in_edges from booleanGraph to 572
     // In other words, print pairs of numbers that are less than 572
+    unsigned int in_edges_count = 0;
     while(in_edges_bool.first != in_edges_bool.second)
     {
         test3::print_edge(*in_edges_bool.first, booleanGraph);
         ++in_edges_bool.first;
+        ++in_edges_count;
     }
+    assert(in_edges_count == in_degree(*aVertex, booleanGraph));
 
     in_edge_wght_range in_edges_wght = boost::in_edges(*aVertex, weightedGraph);
     // Print all in_edges from weightedGraph to 572
     // By the function, this prints in_edge - 572
+    in_edges_count = 0;
     while(in_edges_wght.first != in_edges_wght.second)
     {
         std::cout << boost::source(*in_edges_wght.first, weightedGraph)
                   << " - 572 = " << (*in_edges_wght.first).result
                   << "\n";
         ++in_edges_wght.first;
+        ++in_edges_count;
     }
+    assert(in_edges_count == in_degree(*aVertex, weightedGraph));
+    std::cout << "\n\n";
 
 
     ////////
     // Check out edges
-    ++ ++ ++aVertex; // aVertex now holds -2
-     out_edge_bool_range out_edges_bool = boost::out_edges(*aVertex, booleanGraph);
+    ++++++aVertex; // aVertex now holds -2
+     out_edge_bool_range out_edges_bool = boost::out_edges(*aVertex,
+                                                           booleanGraph);
     // Print all out_edges from booleanGraph to -2
     // In other words, print pairs of numbers that are not less than -2
+    unsigned int out_edges_count = 0;
     while(out_edges_bool.first != out_edges_bool.second)
     {
         test3::print_edge(*out_edges_bool.first, booleanGraph);
         ++out_edges_bool.first;
+        ++out_edges_count;
     }
+    assert(out_edges_count == out_degree(*aVertex, booleanGraph));
 
-    out_edge_wght_range out_edges_wght = boost::out_edges(*aVertex, weightedGraph);
+    out_edge_wght_range out_edges_wght = boost::out_edges(*aVertex,
+                                                          weightedGraph);
     // Print all in_edges from weightedGraph to 572
     // By the function, this prints in_edge - 572
+    out_edges_count = 0;
     while(out_edges_wght.first != out_edges_wght.second)
     {
         std::cout << "-2 - "
@@ -155,12 +192,42 @@
                   << (*out_edges_wght.first).result
                   << "\n";
         ++out_edges_wght.first;
+        ++out_edges_count;
+    }
+    
+    assert(out_edges_count == out_degree(*aVertex, weightedGraph));
+    std::cout << "\n";
+
+
+
+    ////////
+    // Check edges
+    edge_bool_range edges_bool = boost::edges(booleanGraph);
+    unsigned int edges_count = 0;
+    while(edges_bool.first != edges_bool.second)
+    {
+        //test3::print_edge_alt(*edges_bool.first, booleanGraph);
+        ++edges_bool.first;
+        ++edges_count;  //TEMP: is 4
+    }
+    assert(edges_count == boost::num_edges(booleanGraph));
+
+    edge_wght_range edges_wght = boost::edges(weightedGraph);
+    edges_count = 0;
+    while(edges_wght.first != edges_wght.second)
+    {
+        test3::print_edge_alt(*edges_wght.first, weightedGraph);
+        ++edges_wght.first;
+        ++edges_count;
     }
+    // Since this checks all possible pairs, the number of edges = 8 * 8 = 64
+    assert(edges_count == num_edges(weightedGraph));
 
 
 
     ////////
-    // Check adjacency iterators
+    // Check adjacent edges
+    ++++aVertex;
 
     return 0;
 }