Subject: [Boost-commit] svn:boost r54877 - in sandbox/SOC/2009/function_graph: boost/function_graph libs/test
From: mlopez7_at_[hidden]
Date: 2009-07-10 21:56:42
Author: lopezeant
Date: 2009-07-10 21:56:42 EDT (Fri, 10 Jul 2009)
New Revision: 54877
URL: http://svn.boost.org/trac/boost/changeset/54877
Log:
A quick version of adjacent vertices and adjacent iterators.
Text files modified:
sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp | 207 ++++++++++++++++++++++++++++-----------
sandbox/SOC/2009/function_graph/libs/test/test3.cpp | 5
2 files changed, 151 insertions(+), 61 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-10 21:56:42 EDT (Fri, 10 Jul 2009)
@@ -22,6 +22,8 @@
#include <boost/range/iterator.hpp>
#include <iterator>
+/** Error checking */
+#include <iostream>
namespace boost {
@@ -363,20 +365,6 @@
return detail::bind_edge(result, u, v);
}
-/*
-template <typename Graph>
-std::pair<typename Graph::edge_descriptor, bool>
-edge(typename Graph::vertex_descriptor u,
- typename Graph::vertex_descriptor v,
- Graph const& g)
-{
- typedef Graph graph_type;
- typedef typename Graph::result_type result_type;
- result_type result = g.edge(u, v);
- return detail::bind_edge(result, u, v);
-}
-*/
-
//@}
/** in_edges(v, g) and out_edges(u, g)
@@ -398,8 +386,6 @@
vertex_iterator vertex_begin = begin(g.range_);
vertex_iterator vertex_end = end(g.range_);
- while((vertex_begin != vertex_end) && !edge(*vertex_begin, v, g).second)
- { ++vertex_begin; }
in_edge_iterator in_edge_begin(g, v, vertex_begin, vertex_end);
in_edge_iterator in_edge_end(g, v, vertex_end, vertex_end);
@@ -420,17 +406,12 @@
vertex_iterator vertex_begin = begin(g.range_);
vertex_iterator vertex_end = end(g.range_);
- while((vertex_begin != vertex_end) && !edge(u, *vertex_begin, g).second)
- { ++vertex_begin; }
out_edge_iterator out_edge_begin(g, u, vertex_begin, vertex_end);
out_edge_iterator out_edge_end(g, u, vertex_end, vertex_end);
return std::make_pair(out_edge_begin, out_edge_end);
}
-#undef FUNC_GRAPH
-
-
/** @name In-Edge Iterator
* @description Iterates through the in edges of a vertex.
*/
@@ -454,25 +435,27 @@
typedef value_type* pointer;
typedef value_type& reference;
- /** @internal Constructors */
+ /** @name Constructors */
//@{
function_graph_in_edge_iterator(graph_type const& g,
vertex_descriptor const& v,
- vertex_iterator const& v_begin,
- vertex_iterator const& v_end)
+ vertex_iterator const& i_begin,
+ vertex_iterator const& i_end)
: g_(g),
vertex_(v),
- vertex_begin_(v_begin),
- vertex_end_(v_end)
- { };
+ i_begin_(i_begin),
+ i_end_(i_end)
+ {
+ while((i_begin_ != i_end_) && !edge(*i_begin_, vertex_, g_).second)
+ { ++i_begin_; }
+ };
- // Copy constructor
function_graph_in_edge_iterator(This const& cp)
: g_(cp.g_),
vertex_(cp.vertex_),
- vertex_begin_(cp.vertex_begin_),
- vertex_end_(cp.vertex_end_)
+ i_begin_(cp.i_begin_),
+ i_end_(cp.i_end_)
{ };
//@}
@@ -482,20 +465,20 @@
// Cycle through the range until an edge is found,
// or the end of the list is found
do {
- ++vertex_begin_;
- } while((vertex_begin_ != vertex_end_) &&
- !edge(*vertex_begin_, vertex_, g_).second);
+ ++i_begin_;
+ } while((i_begin_ != i_end_) &&
+ !edge(*i_begin_, vertex_, g_).second);
return *this;
}
edge_descriptor operator*()
- { return edge_descriptor(edge(*vertex_begin_, vertex_, g_).first); }
+ { return edge_descriptor(edge(*i_begin_, vertex_, g_).first); }
graph_type const& g_;
vertex_descriptor vertex_;
- vertex_iterator vertex_begin_;
- vertex_iterator vertex_end_;
+ vertex_iterator i_begin_;
+ vertex_iterator i_end_;
};
template<typename Graph>
@@ -503,8 +486,8 @@
function_graph_in_edge_iterator<Graph> const& rhs)
{
return lhs.vertex_ == rhs.vertex_ &&
- lhs.vertex_begin_ == rhs.vertex_begin_ &&
- lhs.vertex_end_ == rhs.vertex_end_;
+ lhs.i_begin_ == rhs.i_begin_ &&
+ lhs.i_end_ == rhs.i_end_;
}
template<typename Graph>
@@ -512,8 +495,8 @@
function_graph_in_edge_iterator<Graph> const& rhs)
{
return !(lhs.vertex_ == rhs.vertex_ &&
- lhs.vertex_begin_ == rhs.vertex_begin_ &&
- lhs.vertex_end_ == rhs.vertex_end_);
+ lhs.i_begin_ == rhs.i_begin_ &&
+ lhs.i_end_ == rhs.i_end_);
}
@@ -532,7 +515,6 @@
typedef typename graph_type::vertex_iterator vertex_iterator;
typedef typename graph_type::edge_descriptor edge_descriptor;
typedef typename graph_type::vertex_descriptor vertex_descriptor;
- typedef typename graph_type::function_type function_type;
/** Iterator traits */
typedef std::input_iterator_tag iterator_category;
@@ -541,26 +523,28 @@
typedef value_type* pointer;
typedef value_type& reference;
- /** @internal Constructors */
+ /** @name Constructors */
//@{
function_graph_out_edge_iterator(graph_type const& g,
vertex_descriptor const& v,
- vertex_iterator const& v_begin,
- vertex_iterator const& v_end)
+ vertex_iterator const& i_begin,
+ vertex_iterator const& i_end)
: g_(g),
vertex_(v),
- vertex_begin_(v_begin),
- vertex_end_(v_end)
- { };
+ i_begin_(i_begin),
+ i_end_(i_end)
+ {
+ while((i_begin_ != i_end_) && !edge(vertex_, *i_begin_, g_).second)
+ { ++i_begin_; }
+ }
- // Copy constructor
function_graph_out_edge_iterator(This const& cp)
: g_(cp.g_),
vertex_(cp.vertex_),
- vertex_begin_(cp.vertex_begin_),
- vertex_end_(cp.vertex_end_)
- { };
+ i_begin_(cp.i_begin_),
+ i_end_(cp.i_end_)
+ { }
//@}
/** Input Iterator operator overloads */
@@ -569,20 +553,20 @@
// Cycle through the range until an edge is found,
// or the end of the list is found
do {
- ++vertex_begin_;
- } while((vertex_begin_ != vertex_end_) &&
- !edge(vertex_, *vertex_begin_, g_).second);
+ ++i_begin_;
+ } while((i_begin_ != i_end_) &&
+ !edge(vertex_, *i_begin_, g_).second);
return *this;
}
edge_descriptor operator*()
- { return edge_descriptor(edge(vertex_, *vertex_begin_, g_).first); }
+ { return edge_descriptor(edge(vertex_, *i_begin_, g_).first); }
graph_type const& g_;
vertex_descriptor vertex_;
- vertex_iterator vertex_begin_;
- vertex_iterator vertex_end_;
+ vertex_iterator i_begin_;
+ vertex_iterator i_end_;
};
template<typename Graph>
@@ -590,8 +574,8 @@
function_graph_out_edge_iterator<Graph> const& rhs)
{
return lhs.vertex_ == rhs.vertex_ &&
- lhs.vertex_begin_ == rhs.vertex_begin_ &&
- lhs.vertex_end_ == rhs.vertex_end_;
+ lhs.i_begin_ == rhs.i_begin_ &&
+ lhs.i_end_ == rhs.i_end_;
}
template<typename Graph>
@@ -599,10 +583,111 @@
function_graph_out_edge_iterator<Graph> const& rhs)
{
return !(lhs.vertex_ == rhs.vertex_ &&
- lhs.vertex_begin_ == rhs.vertex_begin_ &&
- lhs.vertex_end_ == rhs.vertex_end_);
+ lhs.i_begin_ == rhs.i_begin_ &&
+ lhs.i_end_ == rhs.i_end_);
+}
+
+/** Adjacency Iterator - iterates through all of the edges adjacent to a vector
+ * v.
+ * @todo
+ */
+template <typename Graph>
+struct function_graph_adjacency_iterator {
+private:
+ typedef function_graph_adjacency_iterator<Graph> This;
+
+public:
+ typedef Graph graph_type;
+ typedef typename graph_type::vertex_iterator vertex_iterator;
+ typedef typename graph_type::in_edge_iterator in_edge_iterator;
+ typedef typename graph_type::out_edge_iterator out_edge_iterator;
+ typedef typename graph_type::edge_descriptor edge_descriptor;
+ typedef typename graph_type::vertex_descriptor vertex_descriptor;
+
+ /** Iterator traits */
+ typedef std::input_iterator_tag iterator_category;
+ typedef edge_descriptor value_type;
+ typedef std::size_t different_type;
+ typedef value_type* pointer;
+ typedef value_type& reference;
+
+ /** @name Constructor */
+ //@{
+ function_graph_adjacency_iterator(graph_type const& g,
+ vertex_descriptor const& vertex,
+ vertex_iterator const& i_begin,
+ vertex_iterator const& i_end)
+ : g_(g),
+ vertex_(vertex),
+ i_in_edges_(g, vertex, i_begin, i_end),
+ i_out_edges_(g, vertex, i_begin, i_end),
+ use_in_edges_(true)
+ { }
+
+ function_graph_adjacency_iterator(This const& cp)
+ : g_(cp.g_),
+ vertex_(cp.vertex_),
+ i_in_edges_(cp.i_begin_),
+ i_out_edges_(cp.i_end_),
+ use_in_edges_(cp.use_in_edges_)
+ { }
+
+ This& operator++()
+ {
+ if(use_in_edges_)
+ {
+ ++i_in_edges_;
+ if(i_in_edges_.i_begin_ == i_in_edges_.i_end_)
+ { use_in_edges_ = false; }
+ }
+ else
+ {
+ ++i_out_edges_;
+ }
+ }
+
+ edge_descriptor operator*()
+ { return use_in_edges_ ? (*i_in_edges_).source_ : (*i_out_edges_).source_; }
+ //@}
+private:
+ graph_type const& g_;
+ vertex_descriptor vertex_;
+ in_edge_iterator i_in_edges_;
+ out_edge_iterator i_out_edges_;
+ bool use_in_edges_;
+};
+
+template<typename Graph>
+bool operator==(function_graph_adjacency_iterator<Graph> const& lhs,
+ function_graph_adjacency_iterator<Graph> const& rhs)
+{
+ return lhs.vertex_ == rhs.vertex_ &&
+ lhs.i_in_edges_ == rhs.i_in_edges_ &&
+ lhs.i_out_edges_ == rhs.i_out_edges_ &&
+ lhs.use_in_edges_ == rhs.use_in_edges_;
}
+template<typename Graph>
+bool operator!=(function_graph_adjacency_iterator<Graph> const& lhs,
+ function_graph_adjacency_iterator<Graph> const& rhs)
+{ return !(lhs == rhs); }
+
+/** adjacent_vertices function */
+template<typename Result, typename Vertex, typename Range>
+std::pair<
+ typename FUNC_GRAPH::adjacent_iterator,
+ typename FUNC_GRAPH::adjacent_iterator
+>
+adjacent_vertices(typename FUNC_GRAPH::vertex_descriptor const& v,
+ FUNC_GRAPH const& g)
+{
+ typedef FUNC_GRAPH graph_type;
+ typedef typename graph_type::adjacent_iterator adjacent_iterator;
+
+ return std::make_pair(,);
+}
+
+#undef FUNC_GRAPH
} // boost namespace
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-10 21:56:42 EDT (Fri, 10 Jul 2009)
@@ -132,5 +132,10 @@
++out_edges_wght.first;
}
+
+
+ ////////
+ // Check adjacency iterators
+
return 0;
}