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