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;
}