[Boost-commit] svn:boost r55839 - in sandbox/SOC/2009/function_graph: boost/function_graph libs/function_graph/doc libs/function_graph/example

Subject: [Boost-commit] svn:boost r55839 - in sandbox/SOC/2009/function_graph: boost/function_graph libs/function_graph/doc libs/function_graph/example
From: mlopez7_at_[hidden]
Date: 2009-08-28 13:20:17

Author: lopezeant
Date: 2009-08-28 13:20:15 EDT (Fri, 28 Aug 2009)
New Revision: 55839
URL: http://svn.boost.org/trac/boost/changeset/55839

Log:
First draft of documentation is up.
Added:
   sandbox/SOC/2009/function_graph/libs/function_graph/doc/beta_docu.htm
      - copied, changed from r55596, /sandbox/SOC/2009/function_graph/libs/test/test1.cpp
   sandbox/SOC/2009/function_graph/libs/function_graph/example/simple.cpp
      - copied, changed from r55596, /sandbox/SOC/2009/function_graph/libs/test/test1.cpp
Text files modified: 
   sandbox/SOC/2009/function_graph/boost/function_graph/function_graph.hpp |  1418 +++++++++++++++++++++------------------ 
   sandbox/SOC/2009/function_graph/libs/function_graph/doc/beta_docu.htm   |   490 +++++++++++--                           
   sandbox/SOC/2009/function_graph/libs/function_graph/example/simple.cpp  |   164 ++--                                    
   3 files changed, 1236 insertions(+), 836 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-28 13:20:15 EDT (Fri, 28 Aug 2009)
@@ -7,667 +7,492 @@
  *
  */
 
-/** @todo Remember that all iterators contain references to the graphs from
- *  whence they come from. This means begin and end never need to be stored.
- */
-
 #ifndef FUNCTION_GRAPH_HPP_
 #define FUNCTION_GRAPH_HPP_
 
 #include <boost/graph/graph_traits.hpp>
 #include <boost/function.hpp>
-#include <boost/function_types/function_arity.hpp>
 #include <utility>
-#include <boost/optional/optional_fwd.hpp>
-#include <boost/range/iterator.hpp>
-#include <iterator>
-
-/** @todo REMOVE Error checking */
-#include <iostream>
+#include <boost/range.hpp>
+#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
+ */
 
 namespace boost {
 
-template<typename Graph> struct function_graph_in_edge_iterator;
-template<typename Graph> struct function_graph_out_edge_iterator;
-template<typename Graph> struct function_graph_edge_iterator;
-template<typename Graph> struct function_graph_adjacency_iterator;
-
-/** function_graph tags
- * @description Traits that identify the function_graph as either having a
- * finite domain, a range, or having an infinite domain, no range.
- */
-struct finite_domain_tag { };
-struct infinite_domain_tag { };
-struct function_graph_traversal_tag
-    : public virtual incidence_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
-{ };
+/** In Edge Iterator */
+template<typename Graph>
+struct function_graph_in_edge_iterator {
+private:
+    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 different_type;
+    typedef value_type* pointer;
+    typedef value_type& reference;
 
-// @todo Is a meta-function has_finite_domain<G>::value useful?
+    /** @name Constructors */
+    //@{
+    function_graph_in_edge_iterator()
+        : g_(0)
+    { }
 
+    function_graph_in_edge_iterator(graph_type const& g,
+                                    vertex_descriptor const& vertex,
+                                    vertex_iterator const& i_at)
+        : g_(&g),
+          vertex_(vertex),
+          i_at_(i_at)
+    {
+        const vertex_iterator i_end = end(g.range);
 
+        while((i_at_ != i_end) && !has_edge(g.edge(*i_at_, vertex_)))
+        { ++i_at_; }
+    }
 
-/** @name Edge Descriptor */
-template<typename Result, typename Vertex>
-struct func_graph_edge {
-    typedef Result result_type;
-    typedef Vertex vertex_descriptor;
+    // Constructs an end iterator without computation
+    function_graph_in_edge_iterator(graph_type const& g,
+                                    vertex_descriptor const& vertex)
+        : g_(&g),
+          vertex_(vertex),
+          i_at_(end(g.range))
+    { }
 
-    func_graph_edge(result_type rslt,
-                    vertex_descriptor src,
-                    vertex_descriptor trg)
-        : result(rslt), source(src), target(trg)
+    function_graph_in_edge_iterator(This const& cp)
+        : g_(cp.g_),
+          vertex_(cp.vertex_),
+          i_at_(cp.i_at_)
     { }
+    //@}
 
-    result_type result;
-    vertex_descriptor source;
-    vertex_descriptor target;
-};
+    /** Input Iterator operator overloads */
+    This& operator++()
+    {
+        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_)));
 
+        return *this;
+    }
 
+    This operator++(int)
+    {
+        const This temp = *this;
+        const vertex_iterator i_end = end(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
- * specialization to account for functions that use bool and optional<T>.
- */
-//@{
-namespace detail {
-template<typename Result, typename Vertex>
-std::pair<func_graph_edge<Result, Vertex>, bool>
-bind_edge(Result const& r, Vertex u, Vertex v)
-{
-    return std::make_pair(func_graph_edge<Result, Vertex>(r, u, v), true);
-}
+        do {
+            ++i_at_;
+        } while((i_at_ != i_end) && !has_edge(g_->edge(*i_at_, vertex_)));
+
+        return temp;
+    }
+
+    edge_descriptor operator*()
+    {
+        return edge_descriptor(g_->edge(*i_at_, vertex_), *i_at_, vertex_);
+    }
+
+    const graph_type* g_;
+    vertex_descriptor vertex_;
+    vertex_iterator i_at_;
+};
 
-template <typename Vertex>
-std::pair<func_graph_edge<bool, Vertex>, bool>
-bind_edge(bool r, Vertex u, Vertex v)
+template<typename Graph>
+bool operator==(function_graph_in_edge_iterator<Graph> const& lhs,
+                function_graph_in_edge_iterator<Graph> const& rhs)
 {
-    return std::make_pair(func_graph_edge<bool, Vertex>(r, u, v), r);
+    return //lhs.g_ == rhs.g_ &&  // g_ is an odd case, consider this line
+           lhs.vertex_ == rhs.vertex_ &&
+           lhs.i_at_ == rhs.i_at_;
 }
 
-// This overload is specific to optional<T>
-// 
-/*template <typename OptType, typename Vertex>
-std::pair<detail::func_graph_edge<optional<OptType>, Vertex>, bool>
-bind_edge(optional<OptType> const& r, Vertex u, Vertex v)
+template<typename Graph>
+bool operator!=(function_graph_in_edge_iterator<Graph> const& lhs,
+                function_graph_in_edge_iterator<Graph> const& rhs)
 {
-    return std::make_pair(detail::func_graph_edge<
-                              optional<OptType>, Vertex
-                          >(r, u, v),
-                          (bool)r);
-}*/
+    return //lhs.g_ != rhs.g_ ||  // g_ is an odd case, consider this line
+           lhs.vertex_ != rhs.vertex_ ||
+           lhs.i_at_ != rhs.i_at_;
+}
 
-}   // detail namespace
 
 
+/** Out Edge Iterator */
+template<typename Graph>
+struct function_graph_out_edge_iterator {
+private:
+    typedef function_graph_out_edge_iterator<Graph> This;
 
-/** @name Function Graph Base
- *
- *  @description function_graph_base handles the edge function. A user can
- *  define the function as a boost::function, but the user may only have access
- *  to this function through the function graph via edge().
- */
+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;
 
-//@{
-template <typename Func>
-struct function_graph_base {
-    typedef Func function_type;
-    typedef typename function_type::first_argument_type vertex_type;
-    typedef typename function_type::result_type result_type;
-    typedef func_graph_edge<result_type, vertex_type> edge_type;
+    /** Iterator traits */
+    typedef std::input_iterator_tag iterator_category;
+    typedef edge_descriptor value_type;
+    typedef int difference_type;
+    typedef value_type* pointer;
+    typedef value_type& reference;
 
-    /** Constructors to allow for initialization of edge */
-    function_graph_base(function_type const& f)
-        : edge_(f)
+    /** @name Constructors */
+    //@{
+    
+    function_graph_out_edge_iterator()
+        : g_(0)
     { }
 
-    // Allow access to the function edge_ holds, not edge_ itself.
-    result_type edge (vertex_type v1, vertex_type v2) const
-    { return edge_(v1, v2); }
-
-    function_type edge_;
-};
+    function_graph_out_edge_iterator(graph_type const& g,
+                                    vertex_descriptor const& vertex,
+                                    vertex_iterator const& i_at)
+        : g_(&g),
+          vertex_(vertex),
+          i_at_(i_at)
+    {
+        const vertex_iterator i_end = end(g.range);
 
-template <typename Func, typename Rng>
-struct function_graph_base_range {
+        while((i_at_ != i_end) && !has_edge(g.edge(vertex_, *i_at_)))
+        { ++i_at_; }
+    }
 
-    typedef Func function_type;
-    typedef typename function_type::first_argument_type vertex_type;
-    typedef typename function_type::result_type result_type;
-    typedef func_graph_edge<result_type, vertex_type> edge_type;
-    typedef Rng vertex_iterator_range;
+    // Constructs an end iterator without computation
+    function_graph_out_edge_iterator(graph_type const& g,
+                                    vertex_descriptor const& vertex)
+        : g_(&g),
+          vertex_(vertex),
+          i_at_(end(g.range))
+    { }
 
-    /** Constructors to allow for initialization of edge */
-    function_graph_base_range(function_type const& f,
-                              vertex_iterator_range const& r)
-        : edge_(f), range_(r)
+    function_graph_out_edge_iterator(This const& cp)
+        : g_(cp.g_),
+          vertex_(cp.vertex_),
+          i_at_(cp.i_at_)
     { }
+    //@}
 
-    // Allow access to the function edge_ holds, not edge_ itself.
-    result_type edge (vertex_type v1, vertex_type v2) const
-    { return edge_(v1, v2); }
+    /** Input Iterator operator overloads */
+    This& operator++()
+    {
+        const vertex_iterator i_end = end(g_->range);
 
-    function_type edge_;
-    vertex_iterator_range 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_)));
 
+        return *this;
+    }
 
+    This operator++(int)
+    {
+         const This temp = *this;
+         const vertex_iterator i_end = end(g_->range);
 
-/** @name Function Graph
- * @description function_graph is a data structure that implements implicit
- * graphs and more.
- * @note This is a trap for poor template parameters
- */
+        // 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_)));
 
-template <typename Function, typename Range = infinite_domain_tag>
-struct function_graph;
+        return temp;
+    }
 
+    edge_descriptor operator*()
+    { return edge_descriptor(g_->edge(vertex_, *i_at_), vertex_, *i_at_); }
 
+    const graph_type* g_;
+    vertex_descriptor vertex_;
+    vertex_iterator i_at_;
+};
 
-/**
- * function_graph is a data structure that implements implicit graphs and more.
- * Better documentation and explanation of the data structure to come.
- *
- * @internal The typical user of function graph may not need to change edge
- * function during execution. However, since the code needed is trivial,
- * set_edge is part of the interface. Paired with it is the default constructor.
- */
+template<typename Graph>
+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_ &&
+           lhs.i_at_ == rhs.i_at_;
+}
 
-template <typename Result, typename Vertex, typename Range>
-struct function_graph<function<Result(Vertex, Vertex)>, Range>
-    : private function_graph_base_range<function<Result(Vertex, Vertex)>, Range>
+template<typename Graph>
+bool operator!=(function_graph_out_edge_iterator<Graph> const& lhs,
+                function_graph_out_edge_iterator<Graph> const& rhs)
 {
-private:
-    typedef function_graph_base_range<
-                function<Result(Vertex, Vertex)>,
-                Range
-            > Base;
-    typedef function_graph<function<Result(Vertex, Vertex)>, Range > This;
+    return //lhs.g_ != rhs.g_ ||  // g_ is an odd case, consider this line
+           lhs.vertex_ != rhs.vertex_ ||
+           lhs.i_at_ != rhs.i_at_;
+}
 
-public:
-    typedef typename Base::function_type function_type;
-    typedef typename Base::vertex_type vertex_descriptor;
-    typedef typename Base::edge_type edge_descriptor;
-    typedef typename Base::result_type result_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_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 */
-    function_graph(function_type const& f, vertex_iterator_range const& r)
-        : Base(f, r)
-    { }
 
-    // @todo This must include the edge and the range
-    bool operator==(This const& rhs)
-    { return range_ == rhs.range_; }
+/** Edge Iterator */
+template<typename Graph>
+struct function_graph_edge_iterator {
+private:
+    typedef function_graph_edge_iterator<Graph> This;
 
-    bool operator!=(This const& rhs)
-    { return !(*this == rhs); }
+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;
 
-    using Base::edge;
-    using Base::range_;
-};
+    /** Iterator traits */
+    typedef std::input_iterator_tag iterator_category;
+    typedef edge_descriptor value_type;
+    typedef int different_type;
+    typedef value_type* pointer;
+    typedef value_type& reference;
 
-/** @internal Allow a template function parameter without wrapping it with
- * boost::function.
- */
-/*template <typename Result, typename Vertex, typename Range>
-struct function_graph<Result(Vertex, Vertex), Range>
-    : public function_graph<function<Result(Vertex, Vertex)>, Range>
-{ };*/
+    /** @name Constructors */
+    //@{
+    function_graph_edge_iterator()
+        : g_(0)
+    { }
 
-// Specialization of function_graph without range
-template <typename Result, typename Vertex>
-struct function_graph<function<Result(Vertex, Vertex)>, infinite_domain_tag>
-    : public function_graph_base<function<Result(Vertex, Vertex)> >
-{
-private:
-    typedef function_graph_base<function<Result(Vertex, Vertex)> > Base;
-    typedef function_graph<function<Result(Vertex, Vertex)> > This;
+    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;
 
-public:
-    typedef typename Base::function_type function_type;
-    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;
-    typedef infinite_domain_tag domain_category;
+        for(; i_at_1_ != i_end; ++i_at_1_)
+        {
+            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;
+        }
+    }
 
-    /** Constructor: takes a boost::function or functor */
-    function_graph(function_type const& f)
-        : Base(f)
+    // 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))
     { }
 
-    using Base::edge;
-};
-
-/*template <typename Result, typename Vertex>
-struct function_graph<Result(Vertex, Vertex), infinite_domain_tag>
-    : public function_graph<function<Result(Vertex, Vertex)> >
-{ };*/
-
-
-
-/** source(e, g) and target(e, g) are part of the incedence graph concept. */
-
-template <typename Result, typename Vertex, typename Range>
-Vertex source(func_graph_edge<Result, Vertex> const& e,
-              function_graph<function<Result(Vertex, Vertex)>, Range > const& g)
-{ return e.source; }
-
-template <typename Result, typename Vertex, typename Range>
-Vertex target(func_graph_edge<Result, Vertex> const& e,
-              function_graph<function<Result(Vertex, Vertex)>, Range > const& g)
-{ return e.target; }
-
-
-
-#define FUNC_GRAPH \
-    function_graph<function<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)
-{
-    typedef FUNC_GRAPH Graph;
-    typedef typename Graph::vertex_iterator vertex_iterator;
-    typedef typename FUNC_GRAPH::degree_size_type degree_size_type;
+    function_graph_edge_iterator(This const& cp)
+        : g_(cp.g_), i_at_1_(cp.i_at_1_), i_at_2_(cp.i_at_2_)
+    { }
+    //@}
 
-    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)
+    This& operator++()
     {
-        if(edge(u, *vertex_at, g).second) ++out_edges;
-    }
+        const vertex_iterator i_begin = begin(g_->range);
+        const vertex_iterator i_end = end(g_->range);
+        bool done = false;
 
-    return out_edges;
-}
+        
+        if(++i_at_2_ == i_end)
+        {
+            ++i_at_1_;
+            if(i_at_1_ != i_end) i_at_2_ = i_begin;
+        }
 
-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;
+        for(; i_at_1_ != i_end; ++i_at_1_)
+        {
+            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;
+        }
 
-    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(edge(*vertex_at, v, g).second) ++in_edges;
+        return *this;
     }
 
-    return in_edges;
-}
+    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;
 
-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)
-{
-    typedef FUNC_GRAPH graph_type;
-    typedef typename graph_type::degree_size_type degree_size_type;
-    typedef typename graph_type::vertex_iterator vertex_iterator;
+        
+        if(++i_at_2_ == i_end)
+        {
+            ++i_at_1_;
+            if(i_at_1_ != i_end) i_at_2_ = i_begin;
+        }
 
-    const vertex_iterator i_begin = begin(g.range_);
-    const vertex_iterator i_end = end(g.range_);
-    vertex_iterator i_at = i_begin;
-    degree_size_type degree_count = 0;
+        for(; i_at_1_ != i_end; ++i_at_1_)
+        {
+            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;
+        }
 
-    while(i_at != i_end)
-    {
-        if(edge(v, *i_at, g).second) ++degree_count;
-        ++i_at;
+        return temp;
     }
-    i_at = i_begin;
-    while(i_at != i_end)
+
+    edge_descriptor operator*()
     {
-        if(edge(*i_at, v, g).second) ++degree_count;
-        ++i_at;
+        //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 degree_count;
-}
-
-
-
-/** vertices(g) is part of the vertex list concept. */
-
-template <typename Result, typename Vertex, typename Range>
-std::pair<
-    typename FUNC_GRAPH::vertex_iterator,
-    typename FUNC_GRAPH::vertex_iterator
->
-vertices(function_graph<function<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)
-{ return detail::bind_edge(g.edge(u, v), u, v); }
-
-//@}
+    const graph_type* g_;
+    vertex_iterator i_at_1_;
+    vertex_iterator i_at_2_;
+};
 
-/** 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)
+template<typename Graph>
+bool operator==(function_graph_edge_iterator<Graph> const& lhs,
+                function_graph_edge_iterator<Graph> const& rhs)
 {
-    typedef function_graph<function<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, end(g.range_));
-
-    return std::make_pair(in_edge_begin, in_edge_end);
+    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_;
 }
 
-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)
+template<typename Graph>
+bool operator!=(function_graph_edge_iterator<Graph> const& lhs,
+                function_graph_edge_iterator<Graph> const& rhs)
 {
-    typedef function_graph<function<Result(Vertex, Vertex)>, Range> Graph;
-    typedef typename Graph::out_edge_iterator out_edge_iterator;
+    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_;
+}
 
-    out_edge_iterator out_edge_begin(g, u, begin(g.range_));
-    out_edge_iterator out_edge_end(g, u, end(g.range_));
 
-    return std::make_pair(out_edge_begin, out_edge_end);
-}
 
-/** @name In-Edge Iterator
- * @description Iterates through the in edges of a vertex.
- */
+/** Adjacency Iterator */
 template<typename Graph>
-struct function_graph_in_edge_iterator {
+struct function_graph_adjacency_iterator {
 private:
-    typedef function_graph_in_edge_iterator<Graph> This;
+    typedef function_graph_adjacency_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 std::size_t different_type;
+    typedef int different_type;
     typedef value_type* pointer;
     typedef value_type& reference;
 
-    /** @name Constructors */
+    /** @name Constructor */
     //@{
-    function_graph_in_edge_iterator(graph_type const& g,
-                                    vertex_descriptor const& v,
-                                    vertex_iterator const& i_at)
-        : g_(g),
-          vertex_(v),
-          i_at_(i_at)
+    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_end = end(g.range_);
+        const vertex_iterator i_begin = begin(g.range);
+        const vertex_iterator i_end = end(g.range);
 
-        while((i_at_ != i_end) && !edge(*i_at_, vertex_, g).second)
+        while(i_at_ != i_end && !has_edge(g.edge(*i_at_, vertex_)))
         { ++i_at_; }
-    };
+        if(i_at_ == i_end)
+        {
+            in_edge_check_ = false;
+            i_at_ = begin(g.range);
+            while(i_at_ != i_end && !has_edge(g.edge(vertex_, *i_at_)))
+            {  ++i_at_; }
+        }
+    }
 
-    function_graph_in_edge_iterator(This const& cp)
+    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_adjacency_iterator(This const& cp)
         : g_(cp.g_),
           vertex_(cp.vertex_),
-          i_at_(cp.i_at_)
-    { };
+          i_at_(cp.i_at_),
+          in_edge_check_(cp.in_edge_check_)
+    { }
     //@}
 
-    /** Input Iterator operator overloads */
     This& operator++()
     {
-        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) &&
-              !edge(*i_at_, vertex_, g_).second);
-
-        return *this;
-    }
-
-    edge_descriptor operator*()
-    { return edge_descriptor(edge(*i_at_, vertex_, g_).first); }
-
-    graph_type const& g_;
-    vertex_descriptor vertex_;
-    vertex_iterator i_at_;
-};
+        const vertex_iterator i_end = end(g_->range);
 
-template<typename Graph>
-bool operator==(function_graph_in_edge_iterator<Graph> const& lhs,
-                function_graph_in_edge_iterator<Graph> const& rhs)
-{
-    return lhs.vertex_ == rhs.vertex_ &&
-           lhs.i_at_ == rhs.i_at_;
-}
-
-template<typename Graph>
-bool operator!=(function_graph_in_edge_iterator<Graph> const& lhs,
-                function_graph_in_edge_iterator<Graph> const& rhs)
-{
-    return !(lhs.vertex_ == rhs.vertex_ &&
-             lhs.i_at_ == rhs.i_at_);
-}
-
-
-
-/** @name Out-Edge Iterator
- * @description Iterates through the in edges of a vertex.
- */
-
-template<typename Graph>
-struct function_graph_out_edge_iterator {
-private:
-    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;
-
-    /** 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 Constructors */
-    //@{
-    
-    function_graph_out_edge_iterator(graph_type const& g,
-                                    vertex_descriptor const& v,
-                                    vertex_iterator const& i_at)
-        : g_(g),
-          vertex_(v),
-          i_at_(i_at)
-    {
-        const vertex_iterator i_end = end(g.range_);
-
-        while((i_at_ != i_end) && !edge(vertex_, *i_at_, g_).second)
-        { ++i_at_; }
-    }
-
-    function_graph_out_edge_iterator(This const& cp)
-        : g_(cp.g_),
-          vertex_(cp.vertex_),
-          i_at_(cp.i_at_)
-    { }
-    //@}
-
-    /** Input Iterator operator overloads */
-    This& operator++()
-    {
-        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) &&
-              !edge(vertex_, *i_at_, g_).second);
-
-        return *this;
-    }
-
-    edge_descriptor operator*()
-    { return edge_descriptor(edge(vertex_, *i_at_, g_).first); }
-
-    graph_type const& g_;
-    vertex_descriptor vertex_;
-    vertex_iterator i_at_;
-};
-
-template<typename Graph>
-bool operator==(function_graph_out_edge_iterator<Graph> const& lhs,
-                function_graph_out_edge_iterator<Graph> const& rhs)
-{
-    return lhs.vertex_ == rhs.vertex_ &&
-           lhs.i_at_ == rhs.i_at_;
-}
-
-template<typename Graph>
-bool operator!=(function_graph_out_edge_iterator<Graph> const& lhs,
-                function_graph_out_edge_iterator<Graph> const& rhs)
-{
-    return !(lhs.vertex_ == rhs.vertex_ &&
-             lhs.i_at_ == rhs.i_at_);
-}
-
-/** 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::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)
-        : 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_);
-
-        while(i_at_ != i_end && !edge(*i_at_, vertex_, g_).second)
-        { ++i_at_; }
-        if(i_at_ == i_end)
+        if(in_edge_check_)
         {
-            in_edge_check_ = false;
-            i_at_ = begin(g_.range_);
-            while(i_at_ != i_end && !edge(vertex_, *i_at_, g_).second)
-            {  ++i_at_; }
+            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; }
+            }
+        }
+        if(!in_edge_check_)
+        {
+            do {
+                ++i_at_;
+            } while(i_at_ != i_end && !has_edge(g_->edge(vertex_, *i_at_)));
         }
-    }
-
-    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_),
-          i_at_(cp.i_at_),
-          in_edge_check_(cp.in_edge_check_)
-    { }
-    //@}
+        return *this;
+    }
 
-    This& operator++()
+    This operator++(int)
     {
-        const vertex_iterator i_end = end(g_.range_);
+        const This temp = *this;
+        const vertex_iterator i_end = end(g_->range);
 
         if(in_edge_check_)
         {
             do {
                 ++i_at_;
-            } while(i_at_ != i_end && !edge(*i_at_, vertex_, g_).second);
+            } 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(edge(vertex_, *i_at_, g_).second)
+                i_at_ = begin(g_->range);
+                if(has_edge(g_->edge(vertex_, *i_at_)))
                 { return *this; }
             }
         }
@@ -675,10 +500,10 @@
         {
             do {
                 ++i_at_;
-            } while(i_at_ != i_end && !edge(vertex_, *i_at_, g_).second);
+            } while(i_at_ != i_end && !has_edge(g_->edge(vertex_, *i_at_)));
         }
 
-        return *this;
+        return temp;
     }
 
     vertex_descriptor operator*()
@@ -686,7 +511,7 @@
         return *i_at_;
     }
 
-    graph_type const& g_;
+    const graph_type* g_;
     vertex_descriptor vertex_;
     vertex_iterator i_at_;
     bool in_edge_check_;
@@ -696,140 +521,431 @@
 bool operator==(function_graph_adjacency_iterator<Graph> const& lhs,
                 function_graph_adjacency_iterator<Graph> const& rhs)
 {
-    return lhs.vertex_ == rhs.vertex_ &&
-           lhs.i_at_ == rhs.i_at_;
+    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_;
 }
 
 template<typename Graph>
 bool operator!=(function_graph_adjacency_iterator<Graph> const& lhs,
                 function_graph_adjacency_iterator<Graph> const& rhs)
 {
-    return !(lhs == 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_;
 }
 
-/** 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));
-}
 
+/** function_graph tags */
+struct finite_domain_tag { };
+struct infinite_domain_tag { };
+struct function_graph_traversal_tag
+    : public virtual incidence_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
+{ };
 
 
-/** Edge Iterator - iterates through all edges */
-template<typename Graph>
-struct function_graph_edge_iterator {
-private:
-    typedef function_graph_edge_iterator<Graph> This;
+/** has_domain determines whether or not a function graph has a fintie domain */
+template<typename Function_Graph>
+struct has_finite_domain
+    : mpl::bool_<
+          is_same<
+              typename Function_Graph::domain_category,
+              finite_domain_tag
+          >::value
+      >
+{ };
 
-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;
 
-    /** 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 Constructors */
-    //@{
-    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;
 
-        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;
-        }
-    }
+/** @name Edge Descriptor */
+template<typename Result, typename Vertex>
+struct function_graph_edge_descriptor {
+    typedef Result result_type;
+    typedef Vertex vertex_descriptor;
 
-    // initialize to the end
-    function_graph_edge_iterator(graph_type const& g, bool overload)
-        : g_(g), i_at_1_(end(g.range_)), i_at_2_(end(g.range_))
+    function_graph_edge_descriptor()
     { }
 
-    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_edge_descriptor(result_type rslt,
+                                   vertex_descriptor src,
+                                   vertex_descriptor trg)
+        : result(rslt), source(src), target(trg)
     { }
-    //@}
-
-    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_)
-        {
-            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;
-    }
-
-    edge_descriptor operator*()
-    {
-        return edge(*i_at_1_, *i_at_2_, g_).first;
-    }
 
-    graph_type const& g_;
-    vertex_iterator i_at_1_;
-    vertex_iterator i_at_2_;
+    result_type result;
+    vertex_descriptor source;
+    vertex_descriptor target;
 };
 
-template<typename Graph>
-bool operator==(function_graph_edge_iterator<Graph> const& lhs,
-                function_graph_edge_iterator<Graph> const& rhs)
+template<typename Result, typename Vertex>
+bool operator==(function_graph_edge_descriptor<Result, Vertex> const& lhs,
+                function_graph_edge_descriptor<Result, Vertex> const& rhs)
 {
-    return lhs.i_at_1_ == rhs.i_at_1_ &&
-           lhs.i_at_2_ == rhs.i_at_2_;
+    return lhs.result == rhs.result &&
+           lhs.source == rhs.source &&
+           lhs.target == rhs.target;
 }
 
-template<typename Graph>
-bool operator!=(function_graph_edge_iterator<Graph> const& lhs,
-                function_graph_edge_iterator<Graph> const& rhs)
+template<typename Result, typename Vertex>
+bool operator!=(function_graph_edge_descriptor<Result, Vertex> const& lhs,
+                function_graph_edge_descriptor<Result, Vertex> const& rhs)
 {
-    return !(lhs == rhs);
+    return lhs.result != rhs.result ||
+           lhs.source != rhs.source ||
+           lhs.target != rhs.target;
 }
 
+
+
+/** @name has_edge(r)
+ *  @description Determine the existence 
+ */
+//@{
+template<typename Result>
+bool
+has_edge(Result)
+{ return true; }
+
+bool
+has_edge(bool r)
+{ return r; }
+//@}
+
+
+
+/** @name Function Graph Base
+ *
+ *  @description function_graph_base handles the edge function. A user can
+ *  define the function as a boost::function, but the user may only have access
+ *  to this function through the function graph via edge().
+ */
+
+//@{
+template <typename Func>
+struct function_graph_base {
+    typedef Func function_type;
+    typedef typename function_type::first_argument_type vertex_type;
+    typedef typename function_type::result_type result_type;
+    typedef function_graph_edge_descriptor<result_type, vertex_type> edge_type;
+
+    /** Constructors to allow for initialization of edge */
+    function_graph_base(function_type const& f)
+        : edge_(f)
+    { }
+
+    // Allow access to the function edge_ holds, not edge_ itself.
+    result_type edge (vertex_type v1, vertex_type v2) const
+    { return edge_(v1, v2); }
+
+    function_type edge_;
+};
+
+template <typename Func, typename Rng>
+struct function_graph_base_range {
+
+    typedef Func function_type;
+    typedef typename function_type::first_argument_type vertex_type;
+    typedef typename function_type::result_type result_type;
+    typedef function_graph_edge_descriptor<result_type, vertex_type> edge_type;
+    typedef Rng vertex_iterator_range;
+
+    /** Constructors to allow for initialization of edge */
+    function_graph_base_range(function_type const& f,
+                              vertex_iterator_range const& r)
+        : edge_(f), range(r)
+    { }
+
+    // Allow access to the function edge_ holds, not edge_ itself.
+    result_type edge (vertex_type v1, vertex_type v2) const
+    { return edge_(v1, v2); }
+
+    function_type edge_;
+    vertex_iterator_range range;
+};
+//@}
+
+
+
+/**
+ * @name Function Graph
+ * @description function_graph is a data structure that implements implicit
+ * graphs and more.
+ * @note This is a trap for poor template parameters
+ */
+
+template <typename Function, typename Range = infinite_domain_tag>
+struct function_graph;
+
+
+
+/**
+ * function_graph is a data structure that implements implicit graphs and more.
+ * Better documentation and explanation of the data structure to come.
+ *
+ * @internal The typical user of function graph may not need to change edge
+ * function during execution. However, since the code needed is trivial,
+ * set_edge is part of the interface. Paired with it is the default constructor.
+ */
+template <typename Result, typename Vertex, typename Range>
+struct function_graph<Result(Vertex, Vertex), Range>
+    : private function_graph_base_range<function<Result(Vertex, Vertex)>, Range>
+{
+private:
+    typedef function_graph_base_range<
+                function<Result(Vertex, Vertex)>,
+                Range
+            > Base;
+    typedef function_graph<Result(Vertex, Vertex), Range> This;
+
+public:
+    typedef typename Base::function_type function_type;
+    typedef typename Base::vertex_type vertex_descriptor;
+    typedef typename Base::edge_type edge_descriptor;
+    typedef typename Base::result_type result_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_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 */
+    function_graph(function_type const& f, vertex_iterator_range const& r)
+        : Base(f, r)
+    { }
+
+    using Base::edge;
+    using Base::range;
+};
+
+// Specialization of function_graph without range
+template <typename Result, typename Vertex>
+struct function_graph<Result(Vertex, Vertex), infinite_domain_tag>
+    : public function_graph_base<function<Result(Vertex, Vertex)> >
+{
+private:
+    typedef function_graph_base<function<Result(Vertex, Vertex)> > Base;
+    typedef function_graph<function<Result(Vertex, Vertex)> > This;
+
+public:
+    typedef typename Base::function_type function_type;
+    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;
+    typedef infinite_domain_tag domain_category;
+
+    /** Constructor: takes a boost::function or functor */
+    function_graph(function_type const& f)
+        : Base(f)
+    { }
+
+    using Base::edge;
+};
+
+
+
+/** source(e, g) and target(e, g) are part of the incedence graph concept. */
+
+template <typename Result, typename Vertex, typename Range>
+Vertex source(function_graph_edge_descriptor<Result, Vertex> const& e,
+              function_graph<Result(Vertex, Vertex), Range>)
+{ return e.source; }
+
+template <typename Result, typename Vertex, typename Range>
+Vertex target(function_graph_edge_descriptor<Result, Vertex> const& e,
+              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)
+{
+    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 = 0;
+    vertex_iterator vertex_at(begin(g.range));
+    vertex_iterator vertex_end(end(g.range));
+    for(;vertex_at != vertex_end; ++vertex_at)
+    {
+        if(has_edge(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 = 0;
+    vertex_iterator vertex_at(begin(g.range));
+    vertex_iterator vertex_end(end(g.range));
+    for(;vertex_at != vertex_end; ++vertex_at)
+    {
+        if(has_edge(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)
+{
+    typedef FUNC_GRAPH graph_type;
+    typedef typename graph_type::degree_size_type degree_size_type;
+    typedef typename graph_type::vertex_iterator vertex_iterator;
+
+    const vertex_iterator i_begin = begin(g.range);
+    const vertex_iterator i_end = end(g.range);
+    vertex_iterator i_at = i_begin;
+    degree_size_type degree_count = 0;
+
+    while(i_at != i_end)
+    {
+        if(has_edge(g.edge(v, *i_at))) ++degree_count;
+        ++i_at;
+    }
+    i_at = i_begin;
+    while(i_at != i_end)
+    {
+        if(has_edge(g.edge(*i_at, v))) ++degree_count;
+        ++i_at;
+    }
+
+    return degree_count;
+}
+
+
+
+/** vertices(g) is part of the vertex list concept. */
+
+template <typename Result, typename Vertex, typename Range>
+std::pair<
+    typename FUNC_GRAPH::vertex_iterator,
+    typename FUNC_GRAPH::vertex_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)
+{
+    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);
+
+    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 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);
+}
+
+
+
+/** 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
+>
+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;
+
+    return std::make_pair(adjacency_iterator(g, v),
+                          adjacency_iterator(g, v, true));
+}
+
+
+
 /** 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.
@@ -856,8 +972,8 @@
     typedef typename FUNC_GRAPH::edges_size_type edges_size_type;
     typedef typename FUNC_GRAPH::vertex_iterator vertex_iterator;
 
-    const vertex_iterator i_begin = begin(g.range_);
-    const vertex_iterator i_end = end(g.range_);
+    const vertex_iterator i_begin = begin(g.range);
+    const vertex_iterator i_end = end(g.range);
 
     edges_size_type edges_count = 0;
 
@@ -865,7 +981,7 @@
     {
         for(vertex_iterator i_at_2 = i_begin; i_at_2 != i_end; ++i_at_2)
         {
-            if(edge(*i_at_1, *i_at_2, g).second) ++edges_count;
+            if(has_edge(g.edge(*i_at_1, *i_at_2))) ++edges_count;
         }
     }
 

Copied: sandbox/SOC/2009/function_graph/libs/function_graph/doc/beta_docu.htm (from r55596, /sandbox/SOC/2009/function_graph/libs/test/test1.cpp)
==============================================================================
--- /sandbox/SOC/2009/function_graph/libs/test/test1.cpp	(original)
+++ sandbox/SOC/2009/function_graph/libs/function_graph/doc/beta_docu.htm	2009-08-28 13:20:15 EDT (Fri, 28 Aug 2009)
@@ -1,102 +1,396 @@
-/**
- * Testing a function that returns a boolean
- *
- * Functions used in test:
- *   source(e, g)
- *   target(e, g)
- *   edge(u, v, g)
- *     detail::bind_edge(r, u, v) - general type
- *     detail::bind_edge(r, u, v) - boolean
- *     detail::bind_edge(r, u, v) - optional<T>
- */
-
-#include <iostream>
-#include <boost/function.hpp>
-#include <boost/optional.hpp>
-#include <functional>
-#include <algorithm>
-#include <vector>
-#include <utility>
-#include "function_graph.hpp"
-#include <cassert>
-#include <cmath>
-
-////////
-// Boolean function
-template <typename T>
-struct less_than {
-    bool operator() (T a, T b) { return a < b; }
-};
-
-////////
-// Normal function
-template <typename T>
-struct sum {
-    int operator() (T a, T b) { return a + b; }
-};
-
-////////
-// optional<T> function - returns difference if a and b differ by less than 5
-struct difference_within_five {
-    boost::optional<int> operator() (int a, int b) {
-        int diff_check = a - b;
-        
-        boost::optional<int> difference;
-        if(diff_check < 5) difference = diff_check;
-        //std::cerr << a << ":" << b << ":" << diff_check << ":" << difference << "\n";
-        return difference;
+<html><head>
+
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
+<title>Function Graph</title>
+<link rel="stylesheet" href="data/boostbook.css" type="text/css">
+<meta name="generator" content="Bluefish 1.0.7">
+<link rel="home" href="http://www.boost.org/doc/libs/1_39_0/doc/html/index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
+<link rel="up" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook.html" title="Chapter&nbsp;29.&nbsp;Quickbook 1.4">
+<link rel="prev" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook/change_log.html" title="Change Log">
+<link rel="next" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook/install.html" title="Installation and configuration">
+<link rel="icon" href="http://www.boost.org/favicon.ico" type="image/ico">
+<link rel="stylesheet" type="text/css" href="data/section-basic.css">
+
+</head><body text="black" vlink="#840084" alink="#0000ff" bgcolor="white" link="#0000ff">  <div id="boost-common-heading-doc">
+
+      <div id="heading-placard"></div>
+
+  <h1 id="heading-title"><a href="http://www.boost.org/"><img src="data/space.png" alt="Boost C++ Libraries" id="heading-logo"><span id="boost">Boost</span>
+
+  <span id="cpplibraries">C++ Libraries</span></a></h1>
+
+  <p id="heading-quote"><span class="quote">&#8220;...one of the most highly
+  regarded and expertly designed C++ library projects in the
+  world.&#8221;</span> <span class="attribution">&#8212; Herb Sutter and <a href="http://en.wikipedia.org/wiki/Andrei_Alexandrescu" class="external">Andrei
+  Alexandrescu</a>, <a href="http://safari.awprofessional.com/?XmlId=0321113586" class="external">C++
+  Coding Standards</a></span></p>
+
+ 
+
+  </div>
+
+  <div id="boost-common-heading-doc-spacer"></div>
+
+<table width="100%" cellpadding="2"><tbody><tr>
+<td valign="top"><img alt="Boost C++ Libraries" src="data/boost.png" width="277" height="86"></td>
+<td align="center">Home</td>
+<td align="center">Libraries</td>
+<td align="center">People</td>
+<td align="center">FAQ</td>
+<td align="center">More</td>
+
+</tr></tbody></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook/change_log.html"><img src="data/prev.png" alt="Prev"></a>
+<a accesskey="u" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook.html"><img src="data/up.png" alt="Up"></a>
+<a accesskey="h" href="http://www.boost.org/doc/libs/1_39_0/doc/html/index.html"><img src="data/home.png" alt="Home"></a>
+<a accesskey="n" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook/install.html"><img src="data/next.png" alt="Next"></a>
+</div>
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h2 class="title" style="clear: both;">
+<a name="quickbook.syntax"></a><a class="link" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook/syntax.html" title="Syntax Summary">Function Graph</a>
+</h2></div></div></div>
+<div class="toc"><dl>
+<dt><span class="section">Introduction</span></dt>
+<dt><span class="section">The basics</span></dt>
+<dt><span class="section">Members</span></dt>
+<dt><span class="section">Dealing with edges</span></dt>
+<dt><span class="section">Properties</span></dt>
+</dl></div>
+
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="function_graph.intro"></a>
+<a class="link" href="fgraph2.htm#function_graph.intro" title="Introduction">Introduction</a>
+</h3></div></div></div>
+<p>
+      Function graph is a graph built over a function.
+      It is a data structure that using a set of vertices and a binary function that stisfies most of the Boost Graph Library concepts and, therefore, may use most of the BGL algorithms.
+      Since function graph relies on a binary function to determine its structure (basically, its set of edges), it trades edge storage and look up costs with computation.
+      Note: Function graph takes functors only. Any mention of binary function in this text refers to functors modeling the STL concept binary function. Thanks you.
+</p>
+
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="function_graph.basics"></a>
+<a class="link" href="fgraph.htm#function_graph.basics" title="The basics">The basics</a>
+</h3></div></div></div>
+
+<p>
+    A function graph requires only one parameter: a functor that models binary function.
+</p>
+
+<pre class="programlisting">
+    function_graph&lt;Function&gt;
+</pre>
+
+<p>
+    The binary function passed to the function graph defines the graph's types.
+    The vertex_descriptor type is defined by the argument type of the binary function.
+    Bipartite function graphs are not yet supported, so the binary function must have arguments of the same type.
+    The edge_descriptor type uses the result type of the binary function(note1 but is not only the result_type Trust me, I made this data structure).
+    So the following statement
+</p>
+
+<pre class="programlisting">
+    function_graph&lt;std::less&lt;int&gt; &gt; simple_less_fg;
+</pre>
+
+<p>
+    defines a function graph simple_less_fg where the vertex_descriptor is int and the edge descriptor uses the type bool.
+</p>
+
+<p>
+    A function graph with a range implements enough of the Boost graph concepts to work with a wide variety of algorithms in the BGL.
+    The template parameter Range uses should be compatible with the Boost iterator range concept.
+</p>
+
+<p>
+    However, this graph isn't particularly useful.
+    As it satisfies the Graph and AdjacencyMatrix concepts it has access to a few BGL functions, but these functions, edge(u, v, g), source(edge, g) and target(edge, g), don't give you anything more than what you could do without having to use function graph.
+    The problem is that the set of vertices simple_less_fg is not bounded to a finite range (note2 char may be acceptable, but overflow/modular arithmetic makes it not working things), which means that we can't iterate over the edges of iterators.
+    I suppose we can, but iterating over an infinite number of potential edges with n^2 checks seems a bit ludicrous.
+</p>
+
+<p>
+    A function graph can have a range and the type is given as an optional second template paramter.
+</p>
+
+<pre class="programlisting">
+    function_graph&lt;Function, Range&gt;
+</pre>
+
+<p>
+    Range must adhere to the Boost IteratorRange concept.
+</p>
+
+<p>
+    Let us say that two friends, Mr. Darci and Mr. Bingley, decide to travel the country side one morning on horse back.
+    The horses can only travel distance of five miles at a time before they require rest and water.
+    The estates in the general area are all fond of Darci and Bingely's company, so they can rest at these estates.
+    We can construct a function graph for this situation, where an estate is a vertex, and the binary predicate is a function that determines if two estates are within five miles.
+    For this example, let 'estates' be a vector of estates, where estates hold double[2] (coordinates) and a string (name).
+</p>
+
+<pre class="programlisting">
+    // the distance predicate
+    struct dist_of_five {
+        bool operator()(Estate const& a, Estate const& b);   // returns false if dist(a, b) > 5.0f
+        typedef bool result_type;
+        typedef Estate first_argument_type;
+        typedef Estate second_argument_type;
+    };
+
+    typedef function_graph&lt;dist_of_five, iterator_range&lt;estates::iterator&gt; &gt; CountryGraph;
+    CountryGraph country_side('range');
+</pre>
+
+<p>
+    dist_of_five is the binary predicate that will determine the existance of each edge and is passed to function graph via the first template parameter.
+    The second template parameter is the iterator range type of range of vertices.
+    In this case, the range is the container of estates.
+    The actual range is passed to the function_graph country_side through a constructor.
+</p>
+
+<p>
+    Thats all well and good, but let us find some use for this graph. Let us find to which estates Mr. Darci and Mr. Bingley can reach from estate 2.
+    In graph terms, we will print all of the out edges relative to estate 2.
+</p>
+
+<pre class="programlisting">
+    typedef std::pair&lt;CountryGraph::out_edge_iterator, CountryGraph::out_edge_iterator&gt; OutEdges;
+    typedef CountryGraph::edge_descriptor edge_descriptor;
+
+    OutEdges from_estate_2 = out_edges(estates[2], country_side);
+    while(from_estate_2.first != from_estate_2.second)
+    {
+        //print edges
+        edge_descriptor the_edge(*from_estate_2.first);
+        std::cout &lt;&lt; target(the_edge, country_side).name &lt;&lt; "\n";
+
+        ++from_estate_2.first;
     }
-};
+</pre>
+
+<p>
+    Up until the opening comment in the while statement, this is a typical loop through all of the out edges relative to estate 2.
+    Dereferencing an out_edge_iterator returns the edge, stored in the_edge.
+    target(u, g) takes the vertex that the out edge iterator points to.
+    Since the vertex is of type estate, it has a name member and that is what gets printed.
+</p>
+
+<p>
+    So far we have covered binary predicates, one with an infinite range and one with a range.
+    Function graph is not limited to predicates, function graph takes any binary function.
+    Whereas a binary predicate is used to determine the existance of an edge, a (non-boolean) binary function is used to calculate the weight of an edge.
+    Since the function returns only weight, all edges in a function graph with a non-boolean function exist.
+    To illustrate this, let us map all of the distances between some moving particles at a certain frame of time.
+    The function `attract` will calculate the attraction between the particles.
+</p>
+
+<pre class="programlisting">
+    std::vector&lt;Particle&gt; particles;
+    // pushback x particles
+
+    // the attraction function
+    struct attract {
+        float operator()(Particle const& a, Particle const& b);   // returns attractive or repulsive force between particles
+        typedef float result_type;
+        typedef Particle first_argument_type;
+        typedef Particle second_argument_type;
+    };
+
+    typedef function_graph&lt;attract, iterator_range&lt;vector&lt;Particles&gt;::iterator&gt; &gt; ParticleGraph;
+    ParticleGraph particle_graph('range');
+</pre>
+
+<p>
+    The only real difference between this code and the code for the 'country_side' graph is that this functor, attract, returns the type 'float'.
+    The effects of this are revieled in the following code.
+</p>
+
+<pre class="programlisting">
+    typedef std::pair&lt;ParticleGraph::edge_iterator, ParticleGraph::out_edge_iterator&gt; Edges;
+    typedef ParticleGraph::edge_descriptor EdgeDescriptor;
+
+    Edges particle_edges = edges(particle_graph);
+    while(particle_edges.first != particle_edges.second)
+    {
+        //print particle x and particle y have a force of z
+        EdgeDescriptor the_edge(*particle_edges.first);
+        std::cout &lt;&lt; "The force between particles "
+                  &lt;&lt; target(the_edge, particle_graph).id
+                  &lt;&lt; " and "
+                  &lt;&lt; source(the_edge, particle_graph).id
+                  &lt;&lt; " is "
+                  &lt;&lt; the_edge.result
+                  &lt;&lt; ".\n";
+        ++particle_edges.first;
+    }
+</pre>
+
+<p>
+    Ignoring the id element that is assumed to be part of the particle data type, the only big difference is the expression 'the_edge.result'.
+    All function graph edges contain an element named result, which is determined by the binary function.
+</p>
+
+<p>
+    There is one property that the above graph has that limits its use.
+    Function graphs that use binary functions that don't return boolean results are always complete graphs.
+    Since a weight is always returned, it is assumed that the edge always exists.
+    Enter Fernando Luis Cacciola Carballal (author of the Boost.Optional library).
+</p>
+
+<p>
+    By creating binary functions with a result type of optional&lt;T&gt;, function graph can easily determine which edges exist and the weight of the edges the do exist.
+</p>
+
+<p>
+    Consider once again the situation involving Mr. Darci and Mr. Bingley.
+    An edge between vectors exists if and only if the edge is no more than five miles.
+    For those edges that do exist, let us use a binary function that returns the distance.
+</p>
+
+<pre class="programlisting">
+    // the distance function
+    struct dist_of_five_opt {
+        optional&lt;float&gt; operator()(Estate const& a, Estate const& b);
+        typedef bool result_type;
+        typedef Estate first_argument_type;
+        typedef Estate second_argument_type;
+    };
+
+    typedef function_graph&lt;dist_of_five_opt, iterator_range&lt;estates::iterator&gt; &gt; BetterCountryGraph;
+    BetterCountryGraph country_side_opt('range');
+</pre>
+
+<p>
+    The only startling change so far is that the result_type of function graph is optional&lt;float&gt;.
+    Let us print all of the estates around estate number 2.
+</p>
+
+<pre class="programlisting">
+    typedef std::pair&lt;BetterCountryGraph::out_edge_iterator, BetterCountryGraph::out_edge_iterator&gt; OutEdges;
+    typedef BetterCountryGraph::edge_descriptor EdgeDescriptor;
+
+    OutEdges from_estate_2 = out_edges(estates[2], country_side);
+    while(from_estate_2.first != from_estate_2.second)
+    {
+        //print edges
+        EdgeDescriptor the_edge(*from_estate_2.first);
+        std::cout &lt;&lt; "The distance to "
+                  &lt;&lt;  target(the_edge, country_side_opt).name
+                  &lt;&lt; " from here is "
+                  &lt;&lt; *the_edge.result
+                  &lt;&lt; "miles.\n";
+
+        ++from_estate_2.first;
+    }
+</pre>
+
+<p>
+    Nothing looks really different from the previous example.
+    Most of the magic happens behind the scenes.
+    The only worry you should have is to dereference the result, since it is an optional.
+</p>
+
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="function_graph.edges"></a><a class="link" href="fgraph.htm#function_graph.edges" title="Edges">Reference</a>
+</h3></div></div></div>
+
+<p>
+    function_graph_iterators.hpp reference
+</p>
+
+<pre class="programlisting">
+namespace boost {
+
+    template&lt;typename Graph&gt;
+    struct function_graph_in_edge_iterator {
+    private:
+        typedef function_graph_in_edge_iterator&lt;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;
+
+        typedef std::input_iterator_tag iterator_category;
+        typedef edge_descriptor value_type;
+        typedef int different_type;
+        typedef value_type* pointer;
+        typedef value_type& reference;
+
+        function_graph_in_edge_iterator();
+
+        function_graph_in_edge_iterator(graph_type const& g,
+                                        vertex_descriptor const& vertex,
+                                        vertex_iterator const& i_at);
+
+        function_graph_in_edge_iterator(graph_type const& g,
+                                        vertex_descriptor const& vertex);
+
+        function_graph_in_edge_iterator(This const& cp);
+
+        This& operator++();
+
+        This operator++(int);
+
+        edge_descriptor operator*();
+
+        const graph_type* g_;
+        vertex_descriptor vertex_;
+        vertex_iterator i_at_;
+    };
+
+    template&lt;typename Graph>
+    bool operator==(function_graph_in_edge_iterator&lt;Graph> const& lhs,
+                    function_graph_in_edge_iterator&lt;Graph> const& rhs);
+
+    template&lt;typename Graph>
+    bool operator!=(function_graph_in_edge_iterator&lt;Graph> const& lhs,
+                    function_graph_in_edge_iterator&lt;Graph> const& rhs);
+
+} // boost namespace
+</pre>
+
+
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="function_graph.properties"></a><a class="link" href="fgraph.htm#function_graph.properties" title="Properties">Dealing with properties</a>
+</h3></div></div></div>
+
+<p>
+    Properties are left totally unto the user.
+    Since function graph does not store the vertices, there are no interior properties.
+    Example (insert example) shows how an associative property map can be used in an algorithm.
+</p>
+
+
+
+
+
+
+
+
 
 
-int main()
-{
-    ////////
-    // Create typedefs for functions and function graphs
-    typedef boost::function<bool(int,int)> function_boolean;
-    typedef boost::function_graph<function_boolean> graph_boolean;
-
-    typedef boost::function<int(int,int)> function_normal;
-    typedef boost::function_graph<function_normal> graph_normal;
-
-    typedef boost::function<boost::optional<int>(int,int)> function_optional;
-    typedef boost::function_graph<function_optional> graph_optional;
-
-
-    ////////
-    // Create functions, graphs and edges
-    function_boolean f = less_than<int>();
-    graph_boolean funcGraph_boolean(f);
-    graph_boolean::vertex_descriptor x = 1;
-    graph_boolean::vertex_descriptor y = 2;
-
-    function_normal g = sum<int>();
-    graph_normal funcGraph_normal(g);
-    graph_normal::vertex_descriptor u = 1;
-    graph_normal::vertex_descriptor v = 2;
-
-    function_optional h = difference_within_five();
-    graph_optional funcGraph_optional(h);
-    graph_optional::vertex_descriptor r = 1;
-    graph_optional::vertex_descriptor s = 2;
-
-
-    ////////
-    // Assert all edges
-    graph_boolean::edge_descriptor e1 = edge(x, y, funcGraph_boolean).first;
-    assert(source(e1, funcGraph_boolean) == x);
-    assert(target(e1, funcGraph_boolean) == y);
-    assert(e1.result_ == (1 < 2));
-
-    graph_normal::edge_descriptor e2 = edge(u, v, funcGraph_normal).first;
-    assert(source(e2, funcGraph_normal) == u);
-    assert(target(e2, funcGraph_normal) == v);
-    assert(e2.result_ == (u + v));
-
-    graph_optional::edge_descriptor e3 = edge(r, s, funcGraph_optional).first;
-    assert(source(e3, funcGraph_optional) == r);
-    assert(target(e3, funcGraph_optional) == s);
-    assert(e2.result_ == -1);
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tbody><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright &#169; 2009 Michael Lopez
+<p>
+        Distributed under the Boost Software License, Version 1.0. (See accompanying
+        file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+      </p>
+</div></td>
+</tr></tbody></table>
+<hr>
 
-    return 0;
-}
+<div class="spirit-nav">
+<a accesskey="p" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook/change_log.html"><img src="qbk%20syntax_files/prev.png" alt="Prev"></a><a accesskey="u" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook.html"><img src="qbk%20syntax_files/up.png" alt="Up"></a><a accesskey="h" href="http://www.boost.org/doc/libs/1_39_0/doc/html/index.html"><img src="qbk%20syntax_files/home.png" alt="Home"></a><a accesskey="n" href="http://www.boost.org/doc/libs/1_39_0/doc/html/quickbook/install.html"><img src="qbk%20syntax_files/next.png" alt="Next"></a>
+</div>
+</body></html>

Copied: sandbox/SOC/2009/function_graph/libs/function_graph/example/simple.cpp (from r55596, /sandbox/SOC/2009/function_graph/libs/test/test1.cpp)
==============================================================================
--- /sandbox/SOC/2009/function_graph/libs/test/test1.cpp	(original)
+++ sandbox/SOC/2009/function_graph/libs/function_graph/example/simple.cpp	2009-08-28 13:20:15 EDT (Fri, 28 Aug 2009)
@@ -1,102 +1,92 @@
 /**
- * Testing a function that returns a boolean
+ * This is a simple example of how to create a function_graph.
  *
- * Functions used in test:
- *   source(e, g)
- *   target(e, g)
- *   edge(u, v, g)
- *     detail::bind_edge(r, u, v) - general type
- *     detail::bind_edge(r, u, v) - boolean
- *     detail::bind_edge(r, u, v) - optional<T>
+ * It isn't so hard. A function graph needs only a binary function. Since a
+ * function graph without a range is almost nothing, this example also includes
+ * a range.
+ *
+ * Please read the documentation before pursuing this exercise. Do it.
  */
 
-#include <iostream>
-#include <boost/function.hpp>
-#include <boost/optional.hpp>
 #include <functional>
-#include <algorithm>
-#include <vector>
 #include <utility>
 #include "function_graph.hpp"
-#include <cassert>
-#include <cmath>
+#include <boost/assert.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/utility.hpp>
 
-////////
-// Boolean function
-template <typename T>
-struct less_than {
-    bool operator() (T a, T b) { return a < b; }
-};
-
-////////
-// Normal function
-template <typename T>
-struct sum {
-    int operator() (T a, T b) { return a + b; }
-};
-
-////////
-// optional<T> function - returns difference if a and b differ by less than 5
-struct difference_within_five {
-    boost::optional<int> operator() (int a, int b) {
-        int diff_check = a - b;
-        
-        boost::optional<int> difference;
-        if(diff_check < 5) difference = diff_check;
-        //std::cerr << a << ":" << b << ":" << diff_check << ":" << difference << "\n";
-        return difference;
-    }
-};
+using namespace boost;
 
+const unsigned int arr_size = 10;
 
 int main()
 {
-    ////////
-    // Create typedefs for functions and function graphs
-    typedef boost::function<bool(int,int)> function_boolean;
-    typedef boost::function_graph<function_boolean> graph_boolean;
-
-    typedef boost::function<int(int,int)> function_normal;
-    typedef boost::function_graph<function_normal> graph_normal;
-
-    typedef boost::function<boost::optional<int>(int,int)> function_optional;
-    typedef boost::function_graph<function_optional> graph_optional;
-
-
-    ////////
-    // Create functions, graphs and edges
-    function_boolean f = less_than<int>();
-    graph_boolean funcGraph_boolean(f);
-    graph_boolean::vertex_descriptor x = 1;
-    graph_boolean::vertex_descriptor y = 2;
-
-    function_normal g = sum<int>();
-    graph_normal funcGraph_normal(g);
-    graph_normal::vertex_descriptor u = 1;
-    graph_normal::vertex_descriptor v = 2;
-
-    function_optional h = difference_within_five();
-    graph_optional funcGraph_optional(h);
-    graph_optional::vertex_descriptor r = 1;
-    graph_optional::vertex_descriptor s = 2;
-
-
-    ////////
-    // Assert all edges
-    graph_boolean::edge_descriptor e1 = edge(x, y, funcGraph_boolean).first;
-    assert(source(e1, funcGraph_boolean) == x);
-    assert(target(e1, funcGraph_boolean) == y);
-    assert(e1.result_ == (1 < 2));
-
-    graph_normal::edge_descriptor e2 = edge(u, v, funcGraph_normal).first;
-    assert(source(e2, funcGraph_normal) == u);
-    assert(target(e2, funcGraph_normal) == v);
-    assert(e2.result_ == (u + v));
-
-    graph_optional::edge_descriptor e3 = edge(r, s, funcGraph_optional).first;
-    assert(source(e3, funcGraph_optional) == r);
-    assert(target(e3, funcGraph_optional) == s);
-    assert(e2.result_ == -1);
+    // The iterator range in this case will be a simple integer vector
+    typedef std::pair<int*, int*> IterRng;
+    int vertices[arr_size] = {  -53456,   0, 12,   1345,     224,
+                             -6745732, 777, -1, 996212, -758342};
+
+
+    // The function we will use is std::less<long>, so we prepare with the type
+    // bool(long, long). What is done is done. The function graph is finished.
+    typedef function_graph<bool(int, int), IterRng> LessGraph;
+    LessGraph less_graph(std::less<int>(),
+                         std::make_pair(vertices, vertices + arr_size));
+
+
+    // These are the all important edges. This is simply a wrapper for the
+    // std::less<int> and, therefor, returns a bool.
+    bool i_am_a_bool = less_graph.edge(vertices[3], vertices[7]);
+
+
+    // I mentioned in the documentation that the result_type (return type for
+    // the function) is not the same as an edge_descriptor. Uncomment this
+    // section for proof.
+    /*BOOST_ASSERT(bool(
+        is_same<
+            LessGraph::result_type,
+            LessGraph::edge_descriptor
+        >::value
+    ));*/
+
+
+    // The way to get a right and proper edge is to use the BGL concepts. The
+    // AdjacencyMatrix concept gives us the edge(u, v, g) function, which does
+    // return a value edge of type edge_descriptor.
+    LessGraph::edge_descriptor an_edge;
+    bool edge_exists;
+    tie(an_edge, edge_exists) = edge(vertices[3], vertices[7], less_graph);
+    BOOST_ASSERT(an_edge.source == vertices[3]);
+    BOOST_ASSERT(an_edge.target == vertices[7]);
+    BOOST_ASSERT(an_edge.result == i_am_a_bool);
+
+
+    // Please continue reading the tutorial. The rest is to show that the
+    // function graph actually works and shows some of the functions found in
+    // the BGL.
+    BOOST_ASSERT(arr_size == num_vertices(less_graph));
+
+
+    // Those who understand how less_than creates a lattice will see that the
+    // number of edges is the sum of integers starting at 1 and ending at the
+    // number of vertices - 1. Those who don't see this immediately (sane
+    // people), will have to count the edges by hand.
+    BOOST_ASSERT(45 == num_edges(less_graph));
+
+
+    // Recall that the second vertex is zero. So if we check all of the target
+    // vertices of the out edges of this vertex, it should give us all of the
+    // positive vertices.
+    typedef std::pair<
+                LessGraph::out_edge_iterator,
+                LessGraph::out_edge_iterator
+            > OutEdges;
+    OutEdges out_edges_to_0 = out_edges(vertices[2], less_graph);
+    while(out_edges_to_0.first != out_edges_to_0.second)
+    {
+        BOOST_ASSERT((*out_edges_to_0.first).target > 0);
+        ++out_edges_to_0.first;
+    }
 
     return 0;
 }