[Boost-commit] svn:boost r46380 - sandbox/SOC/2006/tree/trunk/boost/tree

From: ockham_at_[hidden]
Date: 2008-06-13 19:00:40

Author: bernhard.reiter
Date: 2008-06-13 19:00:40 EDT (Fri, 13 Jun 2008)
New Revision: 46380
URL: http://svn.boost.org/trac/boost/changeset/46380

Log:
First steps toward BGL interoperability.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp   (contents, props changed)

Added: sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp	2008-06-13 19:00:40 EDT (Fri, 13 Jun 2008)
@@ -0,0 +1,132 @@
+//  Copyright (c) 2006-2008, Bernhard Reiter
+//
+//  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)
+
+/** 
+ * @file graph.hpp
+ * Interoperability with the BGL (Boost Graph Library).
+ */
+ 
+#ifndef BOOST_TREE_GRAPH_HPP
+#define BOOST_TREE_GRAPH_HPP
+
+#include <boost/tree/cursor.hpp>
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+
+#include <boost/type_traits/integral_constant.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/utility/enable_if.hpp>
+
+namespace boost {
+
+using boost::tree::cursor_size;
+using boost::tree::cursor_horizontal_traversal;
+
+namespace tree {
+
+template <class Cursor>
+class out_edge_iterator
+ : public iterator_facade<out_edge_iterator< std::pair<Cursor, Cursor> >
+ 						, std::pair<Cursor, Cursor>
+ 						, typename cursor_horizontal_traversal<Cursor>::type
+ 						/*, Reference, Difference*/> {
+
+	struct enabler {};
+public:
+	out_edge_iterator() : m_edge() {}
+	
+	explicit out_edge_iterator(Cursor u, Cursor v) : m_edge(u, v) {}
+
+    template <class OtherCursor>
+    out_edge_iterator(
+        out_edge_iterator<OtherCursor> const& other
+      , typename boost::enable_if<
+            boost::is_convertible<OtherCursor*,Cursor*>
+          , enabler
+        >::type = enabler()
+    )
+      : m_edge(other.m_edge) {}
+
+	
+private:
+	friend class boost::iterator_core_access;
+
+    template <class OtherCursor>
+    bool equal(out_edge_iterator<OtherCursor> const& other) const
+    {
+        return this->m_edge == other.m_edge;
+    }
+
+    void increment()
+    { ++m_edge.second; }
+
+    void decrement()
+    { --m_edge.second; }
+
+    std::pair<Cursor, Cursor>& dereference() const
+    { return m_edge; }
+
+	std::pair<Cursor, Cursor> m_edge; 
+};
+
+} // namespace tree
+
+template <class Tree>
+struct graph_traits<typename Tree::cursor> {
+	typedef typename Tree::cursor Cursor;
+    typedef Cursor vertex_descriptor;
+    typedef std::pair<Cursor, Cursor> edge_descriptor; // Might be tunable...
+
+	typedef boost::tree::out_edge_iterator<Cursor> out_edge_iterator;
+
+    typedef directed_tag directed_category;
+    typedef disallow_parallel_edge_tag edge_parallel_category;
+	typedef incidence_graph_tag traversal_category;
+    typedef typename cursor_size<Cursor>::type vertices_size_type;
+    typedef typename cursor_size<Cursor>::type edges_size_type;
+    typedef typename cursor_size<Cursor>::type degree_size_type;
+};
+
+template <class Cursor>
+typename graph_traits<Cursor>::vertex_descriptor
+source(
+    typename graph_traits<Cursor>::edge_descriptor e,
+    const Cursor& g)
+{
+    return e.first;
+}
+
+template <class Cursor>
+typename graph_traits<Cursor>::vertex_descriptor
+target(
+    typename graph_traits<Cursor>::edge_descriptor e,
+    const Cursor& g)
+{
+    return e.second;
+}
+
+template <class Cursor>
+inline std::pair<
+    typename graph_traits<Cursor>::out_edge_iterator,
+    typename graph_traits<Cursor>::out_edge_iterator >  
+out_edges(
+    typename graph_traits<Cursor>::vertex_descriptor u, 
+    const Cursor& g)
+{
+    typedef typename graph_traits<Cursor>::out_edge_iterator Iter;
+    return std::make_pair(Iter(u, u.begin()), Iter(u, u.end()));
+}
+
+// TODO
+// We still need suitable property_maps, don't we?
+// (which have to invoke *c.begin())
+
+
+} // namespace boost
+
+
+#endif // BOOST_TREE_GRAPH_HPP