[prev in list] [next in list] [prev in thread] [next in thread]
List: boost-commit
Subject: [Boost-commit] svn:boost r55938 - in
From: mlopez7 () kent ! edu
Date: 2009-08-31 23:58:18
Message-ID: 20090831235818.B28DC2F8E5F () wowbagger ! osl ! iu ! edu
[Download RAW message or body]
Author: lopezeant
Date: 2009-08-31 19:58:17 EDT (Mon, 31 Aug 2009)
New Revision: 55938
URL: http://svn.boost.org/trac/boost/changeset/55938
Log:
Rearranged the function graph functions and iterators to match refinement concepts as \
they are seen on the web page. Added:
sandbox/SOC/2009/function_graph/libs/function_graph/doc/quirks_list.txt \
(contents, props changed) Text files modified:
sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp | 566 \
+++++++++++++++++++-------------------- 1 files changed, 281 insertions(+), 285 \
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-08-31 \
19:58:17 EDT (Mon, 31 Aug 2009) @@ -17,43 +17,41 @@
#include <boost/mpl/bool.hpp>
#include <boost/type_traits/is_same.hpp>
-/** @todo The List
- * Recheck all iterators and verify that they are input iterators, no overload
- * constructors
- * Redo comments
- * Rearrange the items in order of compilation and readability
- * Finish todo list
+/** @todo: How to grill me on the next code audit
+ * -The equality comparison on the iterators should now take the Graph* g. But
+ * they always come in pairs, so should g be considered.
+ * -I have a stray meta-function. It needs a better home. Right now the odd bits
+ * lie between the iterators and the functions.
+ * -Iterators should use the iterator adaptor.
*/
-
namespace boost {
-/** In Edge Iterator */
+/** Out Edge Iterator */
template<typename Graph>
-struct function_graph_in_edge_iterator {
+struct function_graph_out_edge_iterator {
private:
- typedef function_graph_in_edge_iterator<Graph> This;
+ typedef function_graph_out_edge_iterator<Graph> This;
public:
typedef Graph graph_type;
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;
typedef edge_descriptor value_type;
- typedef int different_type;
+ typedef int difference_type;
typedef value_type* pointer;
typedef value_type& reference;
/** @name Constructors */
//@{
- function_graph_in_edge_iterator()
+ function_graph_out_edge_iterator()
: g_(0)
{ }
- function_graph_in_edge_iterator(graph_type const& g,
+ function_graph_out_edge_iterator(graph_type const& g,
vertex_descriptor const& vertex,
vertex_iterator const& i_at)
: g_(&g),
@@ -62,19 +60,19 @@
{
const vertex_iterator i_end = end(g.range);
- while((i_at_ != i_end) && !has_edge(g.edge(*i_at_, vertex_)))
+ while((i_at_ != i_end) && !has_edge(g.edge(vertex_, *i_at_)))
{ ++i_at_; }
}
// Constructs an end iterator without computation
- function_graph_in_edge_iterator(graph_type const& g,
+ function_graph_out_edge_iterator(graph_type const& g,
vertex_descriptor const& vertex)
: g_(&g),
vertex_(vertex),
i_at_(end(g.range))
{ }
- function_graph_in_edge_iterator(This const& cp)
+ function_graph_out_edge_iterator(This const& cp)
: g_(cp.g_),
vertex_(cp.vertex_),
i_at_(cp.i_at_)
@@ -90,27 +88,27 @@
// or the end of the list is found
do {
++i_at_;
- } while((i_at_ != i_end) && !has_edge(g_->edge(*i_at_, vertex_)));
+ } while((i_at_ != i_end) && !has_edge(g_->edge(vertex_, *i_at_)));
return *this;
}
This operator++(int)
{
- const This temp = *this;
- const vertex_iterator i_end = end(g_->range);
+ const This temp = *this;
+ const vertex_iterator i_end = end(g_->range);
+ // Cycle through the range until an edge is found,
+ // or the end of the list is found
do {
++i_at_;
- } while((i_at_ != i_end) && !has_edge(g_->edge(*i_at_, vertex_)));
+ } while((i_at_ != i_end) && !has_edge(g_->edge(vertex_, *i_at_)));
return temp;
}
edge_descriptor operator*()
- {
- return edge_descriptor(g_->edge(*i_at_, vertex_), *i_at_, vertex_);
- }
+ { return edge_descriptor(g_->edge(vertex_, *i_at_), vertex_, *i_at_); }
const graph_type* g_;
vertex_descriptor vertex_;
@@ -118,8 +116,8 @@
};
template<typename Graph>
-bool operator==(function_graph_in_edge_iterator<Graph> const& lhs,
- function_graph_in_edge_iterator<Graph> const& rhs)
+bool operator==(function_graph_out_edge_iterator<Graph> const& lhs,
+ function_graph_out_edge_iterator<Graph> const& rhs)
{
return //lhs.g_ == rhs.g_ && // g_ is an odd case, consider this line
lhs.vertex_ == rhs.vertex_ &&
@@ -127,8 +125,8 @@
}
template<typename Graph>
-bool operator!=(function_graph_in_edge_iterator<Graph> const& lhs,
- function_graph_in_edge_iterator<Graph> const& rhs)
+bool operator!=(function_graph_out_edge_iterator<Graph> const& lhs,
+ function_graph_out_edge_iterator<Graph> const& rhs)
{
return //lhs.g_ != rhs.g_ || // g_ is an odd case, consider this line
lhs.vertex_ != rhs.vertex_ ||
@@ -137,33 +135,33 @@
-/** Out Edge Iterator */
+/** In Edge Iterator */
template<typename Graph>
-struct function_graph_out_edge_iterator {
+struct function_graph_in_edge_iterator {
private:
- typedef function_graph_out_edge_iterator<Graph> This;
+ typedef function_graph_in_edge_iterator<Graph> This;
public:
typedef Graph graph_type;
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;
typedef edge_descriptor value_type;
- typedef int difference_type;
+ typedef int different_type;
typedef value_type* pointer;
typedef value_type& reference;
/** @name Constructors */
//@{
-
- function_graph_out_edge_iterator()
+ function_graph_in_edge_iterator()
: g_(0)
{ }
- function_graph_out_edge_iterator(graph_type const& g,
+ function_graph_in_edge_iterator(graph_type const& g,
vertex_descriptor const& vertex,
vertex_iterator const& i_at)
: g_(&g),
@@ -172,19 +170,19 @@
{
const vertex_iterator i_end = end(g.range);
- while((i_at_ != i_end) && !has_edge(g.edge(vertex_, *i_at_)))
+ while((i_at_ != i_end) && !has_edge(g.edge(*i_at_, vertex_)))
{ ++i_at_; }
}
// Constructs an end iterator without computation
- function_graph_out_edge_iterator(graph_type const& g,
+ function_graph_in_edge_iterator(graph_type const& g,
vertex_descriptor const& vertex)
: g_(&g),
vertex_(vertex),
i_at_(end(g.range))
{ }
- function_graph_out_edge_iterator(This const& cp)
+ function_graph_in_edge_iterator(This const& cp)
: g_(cp.g_),
vertex_(cp.vertex_),
i_at_(cp.i_at_)
@@ -200,27 +198,27 @@
// or the end of the list is found
do {
++i_at_;
- } while((i_at_ != i_end) && !has_edge(g_->edge(vertex_, *i_at_)));
+ } while((i_at_ != i_end) && !has_edge(g_->edge(*i_at_, vertex_)));
return *this;
}
This operator++(int)
{
- const This temp = *this;
- const vertex_iterator i_end = end(g_->range);
+ const This temp = *this;
+ const vertex_iterator i_end = end(g_->range);
- // Cycle through the range until an edge is found,
- // or the end of the list is found
do {
++i_at_;
- } while((i_at_ != i_end) && !has_edge(g_->edge(vertex_, *i_at_)));
+ } while((i_at_ != i_end) && !has_edge(g_->edge(*i_at_, vertex_)));
return temp;
}
edge_descriptor operator*()
- { return edge_descriptor(g_->edge(vertex_, *i_at_), vertex_, *i_at_); }
+ {
+ return edge_descriptor(g_->edge(*i_at_, vertex_), *i_at_, vertex_);
+ }
const graph_type* g_;
vertex_descriptor vertex_;
@@ -228,8 +226,8 @@
};
template<typename Graph>
-bool operator==(function_graph_out_edge_iterator<Graph> const& lhs,
- function_graph_out_edge_iterator<Graph> const& rhs)
+bool operator==(function_graph_in_edge_iterator<Graph> const& lhs,
+ function_graph_in_edge_iterator<Graph> const& rhs)
{
return //lhs.g_ == rhs.g_ && // g_ is an odd case, consider this line
lhs.vertex_ == rhs.vertex_ &&
@@ -237,8 +235,8 @@
}
template<typename Graph>
-bool operator!=(function_graph_out_edge_iterator<Graph> const& lhs,
- function_graph_out_edge_iterator<Graph> const& rhs)
+bool operator!=(function_graph_in_edge_iterator<Graph> const& lhs,
+ function_graph_in_edge_iterator<Graph> const& rhs)
{
return //lhs.g_ != rhs.g_ || // g_ is an odd case, consider this line
lhs.vertex_ != rhs.vertex_ ||
@@ -247,11 +245,11 @@
-/** Edge Iterator */
+/** Adjacency Iterator */
template<typename Graph>
-struct function_graph_edge_iterator {
+struct function_graph_adjacency_iterator {
private:
- typedef function_graph_edge_iterator<Graph> This;
+ typedef function_graph_adjacency_iterator<Graph> This;
public:
typedef Graph graph_type;
@@ -266,67 +264,65 @@
typedef value_type* pointer;
typedef value_type& reference;
- /** @name Constructors */
+ /** @name Constructor */
//@{
- function_graph_edge_iterator()
- : g_(0)
- { }
-
- function_graph_edge_iterator(graph_type const& g)
- : g_(&g), i_at_1_(begin(g.range)), i_at_2_(begin(g.range))
+ 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)
{
const vertex_iterator i_begin = begin(g.range);
const vertex_iterator i_end = end(g.range);
- bool done = true;
- for(; i_at_1_ != i_end; ++i_at_1_)
+ while(i_at_ != i_end && !has_edge(g.edge(*i_at_, vertex_)))
+ { ++i_at_; }
+ if(i_at_ == i_end)
{
- for(; i_at_2_ != i_end; ++i_at_2_)
- {
- if(has_edge(g.edge(*i_at_1_, *i_at_2_)))
- {
- done = true;
- break;
- }
- }
- if(done) break;
+ in_edge_check_ = false;
+ i_at_ = begin(g.range);
+ while(i_at_ != i_end && !has_edge(g.edge(vertex_, *i_at_)))
+ { ++i_at_; }
}
}
- // initialize to the end
- function_graph_edge_iterator(graph_type const& g, bool)
- : g_(&g), i_at_1_(end(g.range)), i_at_2_(end(g.range))
+ function_graph_adjacency_iterator(graph_type const& g,
+ vertex_descriptor const& vertex,
+ bool)
+ : g_(&g),
+ vertex_(vertex),
+ i_at_(end(g.range)),
+ in_edge_check_(false)
{ }
- function_graph_edge_iterator(This const& cp)
- : g_(cp.g_), i_at_1_(cp.i_at_1_), i_at_2_(cp.i_at_2_)
+ function_graph_adjacency_iterator(This const& cp)
+ : g_(cp.g_),
+ vertex_(cp.vertex_),
+ i_at_(cp.i_at_),
+ in_edge_check_(cp.in_edge_check_)
{ }
//@}
This& operator++()
{
- const vertex_iterator i_begin = begin(g_->range);
const vertex_iterator i_end = end(g_->range);
- bool done = false;
-
- if(++i_at_2_ == i_end)
- {
- ++i_at_1_;
- if(i_at_1_ != i_end) i_at_2_ = i_begin;
- }
-
- for(; i_at_1_ != i_end; ++i_at_1_)
+ if(in_edge_check_)
{
- for(; i_at_2_ != i_end; ++i_at_2_)
+ do {
+ ++i_at_;
+ } while(i_at_ != i_end && !has_edge(g_->edge(*i_at_, vertex_)));
+ if(i_at_ == i_end)
{
- if(has_edge(g_->edge(*i_at_1_, *i_at_2_)))
- {
- done = true;
- break;
- }
+ in_edge_check_ = false;
+ i_at_ = begin(g_->range);
+ if(has_edge(g_->edge(vertex_, *i_at_)))
+ { return *this; }
}
- if(done) break;
+ }
+ if(!in_edge_check_)
+ {
+ do {
+ ++i_at_;
+ } while(i_at_ != i_end && !has_edge(g_->edge(vertex_, *i_at_)));
}
return *this;
@@ -335,71 +331,69 @@
This operator++(int)
{
const This temp = *this;
- const vertex_iterator i_begin = begin(g_->range);
const vertex_iterator i_end = end(g_->range);
- bool done = false;
-
- if(++i_at_2_ == i_end)
- {
- ++i_at_1_;
- if(i_at_1_ != i_end) i_at_2_ = i_begin;
- }
-
- for(; i_at_1_ != i_end; ++i_at_1_)
+ if(in_edge_check_)
{
- for(; i_at_2_ != i_end; ++i_at_2_)
+ do {
+ ++i_at_;
+ } while(i_at_ != i_end && !has_edge(g_->edge(*i_at_, vertex_)));
+ if(i_at_ == i_end)
{
- if(has_edge(g_->edge(*i_at_1_, *i_at_2_)))
- {
- done = true;
- break;
- }
+ in_edge_check_ = false;
+ i_at_ = begin(g_->range);
+ if(has_edge(g_->edge(vertex_, *i_at_)))
+ { return *this; }
}
- if(done) break;
+ }
+ if(!in_edge_check_)
+ {
+ do {
+ ++i_at_;
+ } while(i_at_ != i_end && !has_edge(g_->edge(vertex_, *i_at_)));
}
return temp;
}
- edge_descriptor operator*()
+ vertex_descriptor operator*()
{
- //return edge(*i_at_1_, *i_at_2_, *g_).first;
- return edge_descriptor(g_->edge(*i_at_1_, *i_at_2_),
- *i_at_1_,
- *i_at_2_);
+ return *i_at_;
}
const graph_type* g_;
- vertex_iterator i_at_1_;
- vertex_iterator i_at_2_;
+ vertex_descriptor vertex_;
+ vertex_iterator i_at_;
+ bool in_edge_check_;
};
template<typename Graph>
-bool operator==(function_graph_edge_iterator<Graph> const& lhs,
- function_graph_edge_iterator<Graph> const& rhs)
+bool operator==(function_graph_adjacency_iterator<Graph> const& lhs,
+ function_graph_adjacency_iterator<Graph> const& rhs)
{
return //lhs.g_ == rhs.g_ && // g_ is an odd case, consider this line
- lhs.i_at_1_ == rhs.i_at_1_ &&
- lhs.i_at_2_ == rhs.i_at_2_;
+ lhs.vertex_ == rhs.vertex_ &&
+ lhs.i_at_ == rhs.i_at_ &&
+ lhs.in_edge_check_ == rhs.in_edge_check_;
}
template<typename Graph>
-bool operator!=(function_graph_edge_iterator<Graph> const& lhs,
- function_graph_edge_iterator<Graph> const& rhs)
+bool operator!=(function_graph_adjacency_iterator<Graph> const& lhs,
+ function_graph_adjacency_iterator<Graph> const& rhs)
{
return //lhs.g_ != rhs.g_ || // g_ is an odd case, consider this line
- lhs.i_at_1_ != rhs.i_at_1_ ||
- lhs.i_at_2_ != rhs.i_at_2_;
+ lhs.vertex_ != rhs.vertex_ ||
+ lhs.i_at_ != rhs.i_at_ ||
+ lhs.in_edge_check_ != rhs.in_edge_check_;
}
-/** Adjacency Iterator */
+/** Edge Iterator */
template<typename Graph>
-struct function_graph_adjacency_iterator {
+struct function_graph_edge_iterator {
private:
- typedef function_graph_adjacency_iterator<Graph> This;
+ typedef function_graph_edge_iterator<Graph> This;
public:
typedef Graph graph_type;
@@ -414,65 +408,67 @@
typedef value_type* pointer;
typedef value_type& reference;
- /** @name Constructor */
+ /** @name Constructors */
//@{
- 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)
+ function_graph_edge_iterator()
+ : g_(0)
+ { }
+
+ function_graph_edge_iterator(graph_type const& g)
+ : g_(&g), i_at_1_(begin(g.range)), i_at_2_(begin(g.range))
{
const vertex_iterator i_begin = begin(g.range);
const vertex_iterator i_end = end(g.range);
+ bool done = true;
- while(i_at_ != i_end && !has_edge(g.edge(*i_at_, vertex_)))
- { ++i_at_; }
- if(i_at_ == i_end)
+ for(; i_at_1_ != i_end; ++i_at_1_)
{
- in_edge_check_ = false;
- i_at_ = begin(g.range);
- while(i_at_ != i_end && !has_edge(g.edge(vertex_, *i_at_)))
- { ++i_at_; }
+ for(; i_at_2_ != i_end; ++i_at_2_)
+ {
+ if(has_edge(g.edge(*i_at_1_, *i_at_2_)))
+ {
+ done = true;
+ break;
+ }
+ }
+ if(done) break;
}
}
- function_graph_adjacency_iterator(graph_type const& g,
- vertex_descriptor const& vertex,
- bool)
- : g_(&g),
- vertex_(vertex),
- i_at_(end(g.range)),
- in_edge_check_(false)
+ // initialize to the end
+ function_graph_edge_iterator(graph_type const& g, bool)
+ : g_(&g), i_at_1_(end(g.range)), i_at_2_(end(g.range))
{ }
- function_graph_adjacency_iterator(This const& cp)
- : g_(cp.g_),
- vertex_(cp.vertex_),
- i_at_(cp.i_at_),
- in_edge_check_(cp.in_edge_check_)
+ function_graph_edge_iterator(This const& cp)
+ : g_(cp.g_), i_at_1_(cp.i_at_1_), i_at_2_(cp.i_at_2_)
{ }
//@}
This& operator++()
{
+ const vertex_iterator i_begin = begin(g_->range);
const vertex_iterator i_end = end(g_->range);
+ bool done = false;
- if(in_edge_check_)
+
+ if(++i_at_2_ == i_end)
{
- do {
- ++i_at_;
- } while(i_at_ != i_end && !has_edge(g_->edge(*i_at_, vertex_)));
- if(i_at_ == i_end)
- {
- in_edge_check_ = false;
- i_at_ = begin(g_->range);
- if(has_edge(g_->edge(vertex_, *i_at_)))
- { return *this; }
- }
+ ++i_at_1_;
+ if(i_at_1_ != i_end) i_at_2_ = i_begin;
}
- if(!in_edge_check_)
+
+ for(; i_at_1_ != i_end; ++i_at_1_)
{
- do {
- ++i_at_;
- } while(i_at_ != i_end && !has_edge(g_->edge(vertex_, *i_at_)));
+ for(; i_at_2_ != i_end; ++i_at_2_)
+ {
+ if(has_edge(g_->edge(*i_at_1_, *i_at_2_)))
+ {
+ done = true;
+ break;
+ }
+ }
+ if(done) break;
}
return *this;
@@ -481,60 +477,61 @@
This operator++(int)
{
const This temp = *this;
+ const vertex_iterator i_begin = begin(g_->range);
const vertex_iterator i_end = end(g_->range);
+ bool done = false;
- if(in_edge_check_)
+
+ if(++i_at_2_ == i_end)
{
- do {
- ++i_at_;
- } while(i_at_ != i_end && !has_edge(g_->edge(*i_at_, vertex_)));
- if(i_at_ == i_end)
- {
- in_edge_check_ = false;
- i_at_ = begin(g_->range);
- if(has_edge(g_->edge(vertex_, *i_at_)))
- { return *this; }
- }
+ ++i_at_1_;
+ if(i_at_1_ != i_end) i_at_2_ = i_begin;
}
- if(!in_edge_check_)
+
+ for(; i_at_1_ != i_end; ++i_at_1_)
{
- do {
- ++i_at_;
- } while(i_at_ != i_end && !has_edge(g_->edge(vertex_, *i_at_)));
+ for(; i_at_2_ != i_end; ++i_at_2_)
+ {
+ if(has_edge(g_->edge(*i_at_1_, *i_at_2_)))
+ {
+ done = true;
+ break;
+ }
+ }
+ if(done) break;
}
return temp;
}
- vertex_descriptor operator*()
+ edge_descriptor operator*()
{
- return *i_at_;
+ return edge_descriptor(g_->edge(*i_at_1_, *i_at_2_),
+ *i_at_1_,
+ *i_at_2_);
}
const graph_type* g_;
- vertex_descriptor vertex_;
- vertex_iterator i_at_;
- bool in_edge_check_;
+ vertex_iterator i_at_1_;
+ vertex_iterator i_at_2_;
};
template<typename Graph>
-bool operator==(function_graph_adjacency_iterator<Graph> const& lhs,
- function_graph_adjacency_iterator<Graph> const& rhs)
+bool operator==(function_graph_edge_iterator<Graph> const& lhs,
+ function_graph_edge_iterator<Graph> const& rhs)
{
return //lhs.g_ == rhs.g_ && // g_ is an odd case, consider this line
- lhs.vertex_ == rhs.vertex_ &&
- lhs.i_at_ == rhs.i_at_ &&
- lhs.in_edge_check_ == rhs.in_edge_check_;
+ lhs.i_at_1_ == rhs.i_at_1_ &&
+ lhs.i_at_2_ == rhs.i_at_2_;
}
template<typename Graph>
-bool operator!=(function_graph_adjacency_iterator<Graph> const& lhs,
- function_graph_adjacency_iterator<Graph> const& rhs)
+bool operator!=(function_graph_edge_iterator<Graph> const& lhs,
+ function_graph_edge_iterator<Graph> const& rhs)
{
return //lhs.g_ != rhs.g_ || // g_ is an odd case, consider this line
- lhs.vertex_ != rhs.vertex_ ||
- lhs.i_at_ != rhs.i_at_ ||
- lhs.in_edge_check_ != rhs.in_edge_check_;
+ lhs.i_at_1_ != rhs.i_at_1_ ||
+ lhs.i_at_2_ != rhs.i_at_2_;
}
@@ -575,10 +572,10 @@
function_graph_edge_descriptor()
{ }
- function_graph_edge_descriptor(result_type rslt,
- vertex_descriptor src,
- vertex_descriptor trg)
- : result(rslt), source(src), target(trg)
+ function_graph_edge_descriptor(result_type result,
+ vertex_descriptor source,
+ vertex_descriptor target)
+ : result(result), source(source), target(target)
{ }
result_type result;
@@ -766,7 +763,27 @@
-/** source(e, g) and target(e, g) are part of the incedence graph concept. */
+#define FUNC_GRAPH \
+ function_graph<Result(Vertex, Vertex), Range>
+
+////////////////////////////////////////////////////////////////////////////////
+// IncedenceGraph Functions
+
+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 function_graph<Result(Vertex, Vertex), Range> Graph;
+ typedef typename Graph::out_edge_iterator out_edge_iterator;
+
+ out_edge_iterator out_edge_begin(g, u, begin(g.range));
+ out_edge_iterator out_edge_end(g, u);
+
+ return std::make_pair(out_edge_begin, out_edge_end);
+}
template <typename Result, typename Vertex, typename Range>
Vertex source(function_graph_edge_descriptor<Result, Vertex> const& e,
@@ -778,12 +795,6 @@
function_graph<Result(Vertex, Vertex), Range>)
{ return e.target; }
-
-
-#define FUNC_GRAPH \
- function_graph<Result(Vertex, Vertex), Range>
-
-/** 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)
@@ -803,6 +814,27 @@
return out_edges;
}
+
+
+////////////////////////////////////////////////////////////////////////////////
+// BidirectionalGraph Functions
+
+template<typename Result, typename Vertex, typename Range>
+std::pair<
+ typename FUNC_GRAPH::in_edge_iterator,
+ typename FUNC_GRAPH::in_edge_iterator
+>
+in_edges(typename FUNC_GRAPH::vertex_descriptor const& v, FUNC_GRAPH const& g)
+{
+ typedef function_graph<Result(Vertex, Vertex), Range> Graph;
+ typedef typename Graph::in_edge_iterator in_edge_iterator;
+
+ in_edge_iterator in_edge_begin(g, v, begin(g.range));
+ in_edge_iterator in_edge_end(g, v);
+
+ return std::make_pair(in_edge_begin, in_edge_end);
+}
+
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)
@@ -852,104 +884,47 @@
-/** vertices(g) is part of the vertex list concept. */
+////////////////////////////////////////////////////////////////////////////////
+// AdjacencyGraph Functions
template <typename Result, typename Vertex, typename Range>
std::pair<
- typename FUNC_GRAPH::vertex_iterator,
- typename FUNC_GRAPH::vertex_iterator
+ typename FUNC_GRAPH::adjacency_iterator,
+ typename FUNC_GRAPH::adjacency_iterator
>
-vertices(function_graph<Result(Vertex, Vertex), Range> const& g)
-{ return std::make_pair(begin(g.range), end(g.range)); }
-
-
-
-/** 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); }
-
-
-
-template <typename Result, typename Vertex, typename Range>
-std::pair<typename FUNC_GRAPH::edge_descriptor, bool>
-edge(typename FUNC_GRAPH::vertex_descriptor u,
- typename FUNC_GRAPH::vertex_descriptor v,
- FUNC_GRAPH const& g)
+adjacent_vertices(typename FUNC_GRAPH::vertex_descriptor const& v,
+ FUNC_GRAPH const& g)
{
typedef FUNC_GRAPH graph_type;
- typedef typename graph_type::result_type result_type;
- typedef typename graph_type::edge_descriptor edge_descriptor;
-
- const result_type r = g.edge(u, v);
- return std::make_pair(edge_descriptor(r, u, v), has_edge(r));
-}
-
-//@}
-
-/** 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.
- */
-template<typename Result, typename Vertex, typename Range>
-std::pair<
- typename FUNC_GRAPH::in_edge_iterator,
- typename FUNC_GRAPH::in_edge_iterator
->
-in_edges(typename FUNC_GRAPH::vertex_descriptor const& v, FUNC_GRAPH const& g)
-{
- typedef function_graph<Result(Vertex, Vertex), Range> Graph;
- typedef typename Graph::in_edge_iterator in_edge_iterator;
-
- in_edge_iterator in_edge_begin(g, v, begin(g.range));
- in_edge_iterator in_edge_end(g, v);
+ typedef typename graph_type::adjacency_iterator adjacency_iterator;
- return std::make_pair(in_edge_begin, in_edge_end);
+ return std::make_pair(adjacency_iterator(g, v),
+ adjacency_iterator(g, v, true));
}
-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 function_graph<Result(Vertex, Vertex), Range> Graph;
- typedef typename Graph::out_edge_iterator out_edge_iterator;
-
- out_edge_iterator out_edge_begin(g, u, begin(g.range));
- out_edge_iterator out_edge_end(g, u);
-
- return std::make_pair(out_edge_begin, out_edge_end);
-}
+////////////////////////////////////////////////////////////////////////////////
+// VertexListGraph Functions
-/** adjacent_vertices - returns a pair of adjacency iterators relative to v. */
template <typename Result, typename Vertex, typename Range>
std::pair<
- typename FUNC_GRAPH::adjacency_iterator,
- typename FUNC_GRAPH::adjacency_iterator
+ typename FUNC_GRAPH::vertex_iterator,
+ typename FUNC_GRAPH::vertex_iterator
>
-adjacent_vertices(typename FUNC_GRAPH::vertex_descriptor const& v,
- FUNC_GRAPH const& g)
-{
- typedef FUNC_GRAPH graph_type;
- typedef typename graph_type::adjacency_iterator adjacency_iterator;
+vertices(function_graph<Result(Vertex, Vertex), Range> const& g)
+{ return std::make_pair(begin(g.range), end(g.range)); }
- return std::make_pair(adjacency_iterator(g, v),
- adjacency_iterator(g, v, true));
-}
+template<typename Result, typename Vertex, typename Range>
+typename FUNC_GRAPH::vertices_size_type
+num_vertices(FUNC_GRAPH const& g)
+{ return size(g.range); }
-/** edges(g) - part of the EdgeList concept
- * @notes This algorithm is O(n^2) and, along with some other algorithms, is
- * why the integration of closures should be considered.
- */
+////////////////////////////////////////////////////////////////////////////////
+// EdgeListGraph Functions
+
template<typename Result, typename Vertex, typename Range>
std::pair<
typename FUNC_GRAPH::edge_iterator,
@@ -988,6 +963,27 @@
return edges_count;
}
+// Note: source and target have been defined in the IncedenceGraph portion above
+
+
+
+////////////////////////////////////////////////////////////////////////////////
+// AdjacencyMatrix Functions
+
+template <typename Result, typename Vertex, typename Range>
+std::pair<typename FUNC_GRAPH::edge_descriptor, bool>
+edge(typename FUNC_GRAPH::vertex_descriptor u,
+ typename FUNC_GRAPH::vertex_descriptor v,
+ FUNC_GRAPH const& g)
+{
+ typedef FUNC_GRAPH graph_type;
+ typedef typename graph_type::result_type result_type;
+ typedef typename graph_type::edge_descriptor edge_descriptor;
+
+ const result_type r = g.edge(u, v);
+ return std::make_pair(edge_descriptor(r, u, v), has_edge(r));
+}
+
#undef FUNC_GRAPH
} // boost namespace
Added: sandbox/SOC/2009/function_graph/libs/function_graph/doc/quirks_list.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2009/function_graph/libs/function_graph/doc/quirks_list.txt 2009-08-31 \
19:58:17 EDT (Mon, 31 Aug 2009) @@ -0,0 +1,5 @@
+ Users should know that technically a set contains only unique elements. Thus, \
function graph should only have a set of elements that are all unique somehow. This \
is mentioned only because function graph does not check for this. However, there is \
no adverse behavior caused by this when the BGL functions or iterators are used. The \
issues come up when associative property maps are used. +
+ Since function graph does not contain the elements it acts over, all property \
map detail is left up to the user. Associative property maps work very well with \
function graph. +
+ Function graphs that don't use boolean or optional<T> returning function, are \
complete graphs. Say you have n vectors, this means you will have n^2 edges. \
_______________________________________________ Boost-commit mailing list
Boost-commit@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-commit
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic