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

Subject: [Boost-commit] svn:boost r54599 - in sandbox/SOC/2009/function_graph: boost/function_graph libs/test
From: mlopez7_at_[hidden]
Date: 2009-07-02 19:28:39

Author: lopezeant
Date: 2009-07-02 19:28:36 EDT (Thu, 02 Jul 2009)
New Revision: 54599
URL: http://svn.boost.org/trac/boost/changeset/54599

Log:
Added num_vertices, out_edges, degree functions.
Text files modified: 
   sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp |    94 +++++++++++++++++++++++++++++++++++++++ 
   sandbox/SOC/2009/function_graph/libs/test/test2.cpp                     |     2                                         
   2 files changed, 93 insertions(+), 3 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-02 19:28:36 EDT (Thu, 02 Jul 2009)
@@ -7,6 +7,10 @@
  *
  */
 
+/** @todo Rethink the edge handling mechanism. The need to call a version of
+ * bind edge or edge(u,v,g)
+ */
+
 #ifndef FUNCTION_GRAPH_HPP_
 #define FUNCTION_GRAPH_HPP_
 
@@ -288,6 +292,8 @@
     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 directed_tag directed_category;
     typedef disallow_parallel_edge_tag edge_parallel_category;
     typedef adjacency_matrix_tag traversal_category;
@@ -337,6 +343,8 @@
     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 directed_tag directed_category;
     typedef disallow_parallel_edge_tag edge_parallel_category;
     typedef adjacency_matrix_tag traversal_category;
@@ -371,7 +379,10 @@
 
 
 
-/** in_edges(v, g) is part of the bidirectional graph concept. */
+/** in_edges(v, g) and out_edges(u, g)
+ * @note This is a rough draft for testing purposes and readability. There will
+ * be improvements later.
+ */
 
 #define FUNC_GRAPH \
     function_graph<function<Result(Vertex, Vertex)>, Range>
@@ -398,6 +409,75 @@
     return std::make_pair(in_edge_begin, in_edge_end);
 }
 
+template <typename Result, typename Vertex, typename Range>
+std::pair<
+    typename FUNC_GRAPH::out_edge_iterator,
+    typename FUNC_GRAPH::out_edge_iterator
+>
+out_edges(typename FUNC_GRAPH::vertex_descriptor const& u, FUNC_GRAPH const& g)
+{
+    typedef FUNC_GRAPH Graph;
+    typedef typename Graph::out_edge_iterator out_edge_iterator;
+    typedef typename Graph::vertex_iterator vertex_iterator;
+    typedef std::pair<out_edge_iterator, out_edge_iterator> iter_range;
+
+    vertex_iterator first_vertex_pair = begin(g.range_);
+    vertex_iterator vertex_end = end(g.range_);
+    while((first_vertex_pair != vertex_end) || !g.edge_(first_vertex_pair, u))
+    { ++first_vertex_pair; }
+    out_edge_iterator out_edge_begin(first_vertex_pair, u);
+    out_edge_iterator out_edge_end(vertex_end, u);
+
+    return std::make_pair(out_edge_begin, out_edge_end);
+}
+
+
+
+/** Degree functions */
+
+template<typename Result, typename Vertex, typename Range>
+typename FUNC_GRAPH::degree_size_type
+out_degree(typename FUNC_GRAPH::vertex_descriptor const& u, FUNC_GRAPH const& g)
+{
+    typedef FUNC_GRAPH Graph;
+    typedef typename Graph::vertex_iterator vertex_iterator;
+    typedef typename FUNC_GRAPH::degree_size_type degree_size_type;
+
+    degree_size_type out_edges();
+    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;
+    }
+
+    return out_edges;
+}
+
+template<typename Result, typename Vertex, typename Range>
+typename FUNC_GRAPH::degree_size_type
+in_degree(typename FUNC_GRAPH::vertex_descriptor const& v, FUNC_GRAPH const& g)
+{
+    typedef FUNC_GRAPH Graph;
+    typedef typename Graph::vertex_iterator vertex_iterator;
+    typedef typename FUNC_GRAPH::degree_size_type degree_size_type;
+
+    degree_size_type in_edges();
+    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;
+    }
+
+    return in_edges;
+}
+
+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)
+{ return in_degree(v, g) + out_degree(v, g); }
+
 
 
 /** vertices(g) is part of the vertex list concept. */
@@ -412,6 +492,18 @@
 
 
 
+/** num_vertices(g) is part of the vertex list concept.
+ * @note Uses boost::size() from the iterator_range concept.
+ */
+template<typename Result, typename Vertex, typename Range>
+typename FUNC_GRAPH::vertices_size_type
+num_vertices(FUNC_GRAPH const& g)
+{
+    return size(g.range_);
+}
+
+
+
 /** @name bind_edge
  * edge(u, v, g) is part of the adjacency matrix concept called Direct Edge
  * Access. The function must account for edges that already return. There is

Modified: sandbox/SOC/2009/function_graph/libs/test/test2.cpp
==============================================================================
--- sandbox/SOC/2009/function_graph/libs/test/test2.cpp	(original)
+++ sandbox/SOC/2009/function_graph/libs/test/test2.cpp	2009-07-02 19:28:36 EDT (Thu, 02 Jul 2009)
@@ -29,8 +29,6 @@
     typedef std::pair<std::vector<unsigned int>::iterator,
                       std::vector<unsigned int>::iterator> iterator_range;
     typedef boost::function_graph<boolean_function, iterator_range> FuncGraph;
-    typedef boost::function_graph<boolean_function> FuncGraph2;
-    FuncGraph2 graph2(std::less<int>());
 
     ////////
     // Create vertices and function_graph