|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-26 19:09:58
Author: bernhard.reiter
Date: 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
New Revision: 46753
URL: http://svn.boost.org/trac/boost/changeset/46753
Log:
More work on graph interoperability.
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp | 3
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp | 126 ++++++++++++++++++++++++++-------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp | 85 ++++++++++++++++++++++----
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 25 ++++---
7 files changed, 179 insertions(+), 78 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
@@ -43,10 +43,10 @@
template <class Val, class Meta, class Meta2 = empty_class>
struct augmented_type {
typedef Val value_type;
- //typedef Meta metadata_type;
- struct metadata_type : public Meta, public Meta2 {
- metadata_type() : Meta(), Meta2() {}
- };
+ typedef Meta metadata_type;
+// struct metadata_type : public Meta, public Meta2 {
+// metadata_type() : Meta(), Meta2() {}
+// };
value_type data;
metadata_type meta;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
@@ -250,7 +250,7 @@
template <class InputCursor>
cursor insert(cursor pos, InputCursor subtree)
{
- subtree = subtree.begin();
+ subtree.to_begin();
insert(pos, *subtree);
if (!subtree.empty())
insert(pos.begin(), subtree);
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
@@ -20,6 +20,9 @@
// These algorithms are actually mostly preorder, as it's most efficient, but I
// think it doesn't make much sense having in- and postorder versions of them.
+// The only reason I can think of is that there might be some cases
+// where it's likely to find a mismatch or whatever faster in in- or postorder
+// than in preorder -- but for things like size() or count(), this doesn't really matter.
// What about the subtree shapes?
/**
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
@@ -159,22 +159,22 @@
}
// Container specific
- bool const empty_() const
+ bool empty_() const
{
return m_node->operator[](m_pos)->empty();
}
- size_type size_()
+ size_type size_() const
{
return m_node->size();
}
- size_type max_size_()
+ size_type max_size_() const
{
return m_node->max_size();
}
- size_type const par() const
+ size_type par() const
{
return m_pos;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
@@ -13,10 +13,12 @@
#define BOOST_TREE_GRAPH_HPP
#include <boost/tree/cursor.hpp>
+#include <boost/tree/binary_tree.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/multi_index/identity.hpp>
#include <boost/type_traits/integral_constant.hpp>
#include <boost/type_traits/is_convertible.hpp>
@@ -31,7 +33,7 @@
template <class Cursor>
class out_edge_iterator
- : public iterator_facade<out_edge_iterator< std::pair<Cursor, Cursor> >
+ : public iterator_facade<out_edge_iterator<Cursor>
, std::pair<Cursor, Cursor>
, typename cursor_horizontal_traversal<Cursor>::type
/*, Reference, Difference*/> {
@@ -63,22 +65,37 @@
}
void increment()
- { ++m_edge.second; }
+ {
+ // We also need to account for the cursor's end()!
+ if (m_edge.second == m_edge.first.end()) {
+ m_edge.second = m_edge.first;
+ return;
+ }
+ ++m_edge.second;
+ }
void decrement()
- { --m_edge.second; }
+ {
+ if (m_edge.second == m_edge.first) {
+ m_edge.second = m_edge.first.end();
+ return;
+ }
+ --m_edge.second;
+ }
std::pair<Cursor, Cursor>& dereference() const
- { return m_edge; }
+ { return const_cast<std::pair<Cursor, Cursor>&>(m_edge); }
std::pair<Cursor, Cursor> m_edge;
};
} // namespace tree
-template <class Tree>
-struct graph_traits<typename Tree::cursor> {
- typedef typename Tree::cursor vertex_descriptor;
+using boost::tree::binary_tree;
+
+template <class Tp, class Alloc>
+struct graph_traits< binary_tree<Tp, Alloc> > {
+ typedef typename binary_tree<Tp, Alloc>::cursor vertex_descriptor;
typedef std::pair<vertex_descriptor
, vertex_descriptor> edge_descriptor; // Might be tunable...
@@ -98,57 +115,80 @@
degree_size_type;
};
-template <class Tree>
-typename graph_traits<typename Tree::cursor>::vertex_descriptor
-source(
- typename graph_traits<typename Tree::cursor>::edge_descriptor e,
- const typename Tree::cursor& g)
-{
- return e.first;
-}
-
-template <class Tree>
-typename graph_traits<typename Tree::cursor>::vertex_descriptor
-target(
- typename graph_traits<typename Tree::cursor>::edge_descriptor e,
- const typename Tree::cursor& g)
-{
- return e.second;
-}
+//template <class Tp, class Alloc>
+//typename graph_traits< binary_tree<Tp, Alloc> >::vertex_descriptor
+//source(
+// typename graph_traits< binary_tree<Tp, Alloc> >::edge_descriptor e,
+// const binary_tree<Tp, Alloc>& g)
+//{
+// return e.first;
+//}
+//
+//template <class Tp, class Alloc>
+//typename graph_traits< binary_tree<Tp, Alloc> >::vertex_descriptor
+//target(
+// typename graph_traits< binary_tree<Tp, Alloc> >::edge_descriptor e,
+// const binary_tree<Tp, Alloc>& g)
+//{
+// return e.second;
+//}
-template <class Tree>
+template <class Tp, class Alloc>
inline std::pair<
- typename graph_traits<typename Tree::cursor>::out_edge_iterator,
- typename graph_traits<typename Tree::cursor>::out_edge_iterator >
+ typename graph_traits< binary_tree<Tp, Alloc> >::out_edge_iterator,
+ typename graph_traits< binary_tree<Tp, Alloc> >::out_edge_iterator >
out_edges(
- typename graph_traits<typename Tree::cursor>::vertex_descriptor u,
- const typename Tree::cursor& g)
+ typename graph_traits< binary_tree<Tp, Alloc> >::vertex_descriptor u,
+ const binary_tree<Tp, Alloc>& g)
{
typedef
- typename graph_traits<typename Tree::cursor>::out_edge_iterator
+ typename graph_traits< binary_tree<Tp, Alloc> >::out_edge_iterator
Iter;
- return std::make_pair(Iter(u, u.begin()), Iter(u, u.end()));
+ return std::make_pair(Iter(u, u.begin()), Iter(u, u));
}
-template <class Cursor> struct deref_property_map;
+template <class Tp, class Alloc>
+inline typename graph_traits< binary_tree<Tp, Alloc> >::degree_size_type
+out_degree(
+ typename graph_traits< binary_tree<Tp, Alloc> >::vertex_descriptor u,
+ const binary_tree<Tp, Alloc>& g)
+{
+ return u.size();
+}
-template <class Cursor>
-struct deref_property_map
-: public boost::put_get_helper<typename boost::tree::cursor_reference<Cursor>::type
- , deref_property_map<Cursor> >
+template <
+ class Cursor,
+ class Op //= typename identity<typename boost::tree::cursor_value<Cursor>::type>
+>
+struct extract_property_map;
+
+template <class Cursor, class Op>
+class extract_property_map
+: public boost::put_get_helper<typename Op::result_type&
+ , extract_property_map<Cursor, Op> >
{
+public:
typedef Cursor key_type;
- typedef typename boost::tree::cursor_value<Cursor>::type value_type;
- typedef typename boost::tree::cursor_reference<Cursor>::type reference;
+ typedef typename Op::result_type value_type;
+ typedef value_type& reference;
typedef boost::lvalue_property_map_tag category;
- inline reference operator[](const key_type& v) const { return *v; }
-};
+ extract_property_map(Op op = Op()) : m_op(op) {}
-// TODO
-// We still need suitable property_maps, don't we?
-// (which have to invoke *c.begin())
+ inline reference operator[](key_type v) const
+ {
+ return m_op(*v.to_begin());
+ }
+
+private:
+ Op m_op;
+};
+template <class Tree>
+bool empty_cursor(typename Tree::cursor u, Tree)
+{
+ return u.empty();
+}
} // namespace boost
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
@@ -11,7 +11,6 @@
#include <boost/test/minimal.hpp>
-#include <vector>
#include <list>
#include <iterator>
@@ -20,10 +19,16 @@
int test_main(int, char* [])
{
+ using namespace boost;
using boost::tree::binary_tree;
- typedef binary_tree<int>::cursor cursor;
- binary_tree<int> test_tree;
+ typedef color_traits<default_color_type> Color;
+ typedef augmented_type< int, boost::default_color_type > data_type;
+
+ typedef binary_tree< data_type > tree_type;
+ typedef tree_type::cursor cursor;
+
+ tree_type test_tree;
create_test_data_tree(test_tree);
std::list<int> test_list;
@@ -39,22 +44,72 @@
// a visitor that is invoked at entering (preorder)
// the vertices.
- boost::deref_property_map<cursor> dpm;
- BOOST_CHECK(get(dpm, test_tree.root().begin()) == 8); // Check the entire tree?
-
- boost::dfs_visitor< boost::property_writer<
- boost::deref_property_map<cursor>,
- bi_list_int_type,
- boost::on_discover_vertex>
- >
+ boost::extract_property_map<
+ cursor,
+ boost::tree::cursor_value<cursor>::type::extract_data
+ > dpm;
+
+ boost::extract_property_map<
+ cursor,
+ boost::tree::cursor_value<cursor>::type::extract_meta
+ > cpm;
+
+ BOOST_CHECK(get(dpm, test_tree.root()) == 8); // Check the entire tree?
+ BOOST_CHECK(get(cpm, test_tree.root()) == Color::white());
+
+ put(cpm, test_tree.root(), Color::gray());
+ BOOST_CHECK(get(cpm, test_tree.root()) == Color::gray());
+ put(cpm, test_tree.root(), Color::white());
+ BOOST_CHECK(get(cpm, test_tree.root()) == Color::white());
+
+ boost::dfs_visitor<
+ boost::property_writer<
+ boost::extract_property_map<
+ cursor,
+ boost::tree::cursor_value<cursor>::type::extract_data
+ >,
+ bi_list_int_type,
+ boost::on_discover_vertex>
+ >
preorder_writer(write_property(dpm, bi_list_int,
boost::on_discover_vertex()));
+
+// boost::depth_first_visit(test_tree, test_tree.root(), preorder_writer, cpm, empty_cursor<tree_type>);
+
+ graph_traits<tree_type>::vertex_descriptor v = test_tree.root();
+
+ graph_traits<tree_type>::out_edge_iterator oei, oei_end;
+ tie(oei, oei_end) = out_edges(v, test_tree);
+
+ cursor w = target(*oei, test_tree);
+
+ w = test_tree.root().begin().end().begin();
+ default_color_type color = get(cpm, w);
+ BOOST_CHECK(color == Color::white());
+
+ put(cpm, w, Color::white());
+ BOOST_CHECK(get(cpm, w) == Color::white());
+
+ BOOST_CHECK(!empty_cursor(v, test_tree));
+
+ BOOST_CHECK(oei != oei_end);
+
+ BOOST_CHECK(source(*oei, test_tree) == test_tree.root());
+ BOOST_CHECK(source(*oei_end, test_tree) == test_tree.root());
+
+ BOOST_CHECK(target(*oei, test_tree) == test_tree.root().begin());
+ BOOST_CHECK(target(*oei_end, test_tree) == test_tree.root());
- // We need a color map!
+ BOOST_CHECK(out_degree(v, test_tree) == 2);
+//
+// BOOST_CHECK(test_list.size() == 2);
+//
+// std::list<int>::const_iterator ci = test_list.begin();
+//
+// BOOST_CHECK(*ci == 8);
+// BOOST_CHECK(*++ci == 10); //FIXME
- std::vector<boost::default_color_type> color(test_tree.size());
-
- //boost::depth_first_visit(test_tree, test_tree.root(), preorder_writer, &color[0]);
+// test::preorder::traversal(test_list.begin(), test_list.end());
// Output test_tree using write_graphviz. This might require copying
// the IncidenceGraph to a VertexListGraph (using copy_component)
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp 2008-06-26 19:09:57 EDT (Thu, 26 Jun 2008)
@@ -18,17 +18,20 @@
template <class Tree>
void create_test_data_tree(Tree& ret)
{
- typename Tree::cursor cur = ret.insert(ret.root(), 8);
- cur = ret.insert(cur, 3);
- ret.insert(cur, 1);
- cur = ret.insert(++cur, 6);
- ret.insert(cur, 4);
- ret.insert(++cur, 7);
- cur = ret.insert(ret.root().end(), 10);
- cur = ret.insert(ret.root().end().end(), 14);
- cur = ret.insert(cur, 13);
- cur = ret.insert(cur, 11);
- cur = ret.insert(++cur, 12);
+ // For augmented trees. (Why is this necessary? Nothing here is explicit!)
+ typedef typename Tree::value_type value_type;
+
+ typename Tree::cursor cur = ret.insert(ret.root(), value_type(8));
+ cur = ret.insert(cur, value_type(3));
+ ret.insert(cur, value_type(1));
+ cur = ret.insert(++cur, value_type(6));
+ ret.insert(cur, value_type(4));
+ ret.insert(++cur, value_type(7));
+ cur = ret.insert(ret.root().end(), value_type(10));
+ cur = ret.insert(ret.root().end().end(), value_type(14));
+ cur = ret.insert(cur, value_type(13));
+ cur = ret.insert(cur, value_type(11));
+ cur = ret.insert(++cur, value_type(12));
}
template <class Tree>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk