Udało mi się ulepszyć to drzewo. Zarówno iteratory wierzchołków, jak i wierzchołków są teraz owinięte w elewację. Jeśli wprowadzę więcej istotnych zmian, opublikuję je. Wykorzystałem tree.hh jakiś czas temu na niewielki projekt, ale nie bardzo to lubię. Zastąpię to tym, aby zobaczyć, czego jeszcze potrzebuje.
#include<iostream>
#include <string>
#include <boost/shared_ptr.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>
// ..............................................
template< typename Tree >
void write_graphviz(std::ostream& os, Tree tree)
{
os << "digraph G {\n";
for(auto it : tree)
os << it << "[label=\"" << tree[ it ] << "\"];\n";
for(auto it : tree.get_edges())
os << it.m_source << "->" << it.m_target << ";\n";
os << "}\n";
}
// ..............................................
template< typename Tree >
const typename boost::graph_traits<Tree>::vertex_descriptor get_vertex(Tree& tree, const typename Tree::out_edge_iterator& iter) { return iter->m_target; }
template< typename Tree >
const typename boost::graph_traits<Tree>::vertex_descriptor get_vertex(Tree& tree, const typename Tree::vertex_iterator& iter) { return *iter; }
// ..............................................
template< typename Tree, typename IteratorType >
class tree_iter_type
: public boost::iterator_facade<
tree_iter_type< typename Tree, typename IteratorType >
,typename Tree::vertex_property_type
,boost::forward_traversal_tag
>
{
public:
typedef typename tree_iter_type< typename Tree, typename IteratorType > other_type;
typedef typename boost::graph_traits<Tree>::vertex_descriptor iterator_value_type;
typedef typename boost::graph_traits<Tree>::edge_descriptor eiterator_value_type;
typedef typename Tree::vertex_property_type value_type;
private:
friend class boost::iterator_core_access;
value_type& dereference() const { return tree[ get_vertex(tree, iter) ]; }
void increment() { ++iter; }
bool equal(other_type const& other) const { return iter == other.iter; }
public:
tree_iter_type(Tree& tree, IteratorType iter) : tree(tree), iter(iter) { }
//http://stackoverflow.com/questions/31264984/c-compiler-error-c2280-attempting-to-reference-a-deleted-function-in-visual
other_type& operator=(other_type const& a){ tree= a.tree, iter= a.iter; return *this; };
iterator_value_type vertex() { return get_vertex(tree, iter); }
//how to make this work? It blows things up....
//iterator_value_type operator () { return get_vertex(tree, iter); }
private:
Tree& tree;
IteratorType iter;
};
// ..............................................
template< typename Tree, typename IterType > //proxy container
class tree_pair_type
{
public:
typedef typename boost::graph_traits<Tree>::vertex_descriptor vertex_t;
typedef std::pair< IterType, IterType > iterator_pair_t;
tree_pair_type(iterator_pair_t pair) :pair(pair){ }
IterType begin() { return pair.first; }
IterType end() { return pair.second; }
private:
iterator_pair_t pair;
};
// ..............................................
template< typename ValueType >
class BGTree
{
public:
typedef boost::adjacency_list<
boost::mapS,
boost::vecS,
boost::bidirectionalS,
ValueType >
tree_t;
typedef typename ValueType value_type;
typedef typename boost::graph_traits<tree_t>::vertex_descriptor vertex_t;
typedef typename boost::graph_traits<tree_t>::edge_descriptor edge_t;
typedef typename tree_t::vertex_iterator vertex_iterator;
typedef typename tree_t::edge_iterator edge_iterator;
typedef typename tree_t::out_edge_iterator out_edge_iterator;
typedef typename tree_iter_type< tree_t, typename tree_t::out_edge_iterator > out_tree_iterator;
typedef typename tree_iter_type< tree_t, typename tree_t::vertex_iterator > vertex_tree_iterator;
typedef tree_pair_type< tree_t, edge_iterator > pair_type;
typedef tree_pair_type< tree_t, out_tree_iterator > out_pair_type;
typedef tree_pair_type< tree_t, vertex_tree_iterator > vertex_pair_type;
//get children
auto make_out_iterator(vertex_t pos) { return out_tree_iterator(tree, boost::out_edges(pos, tree).first); }
auto make_out_iterator_end(vertex_t pos) { return out_tree_iterator(tree, boost::out_edges(pos, tree).second); }
//get sub tree
auto make_range_iterator(vertex_t pos) { return vertex_tree_iterator(tree, begin()); }
auto make_range_iterator_end(vertex_t pos) { return vertex_tree_iterator(tree, end()); }
public:
BGTree(const ValueType& root)
:root(boost::add_vertex(root, tree)) { }
vertex_t get_root() const { return root; }
vertex_t add_child(const ValueType& item, vertex_t where) {
auto temp= boost::add_vertex(item, tree);
boost::add_edge(where, temp, tree);
return temp;
}
vertex_t get_parent(vertex_t from) const { return boost::in_edges(from, tree).first->m_source; }
auto get_bundle() { return boost::get(vertex_bundle, tree); }
//vertext set, not by value
vertex_iterator begin() { return boost::vertices(tree).first; }
vertex_iterator end() { return boost::vertices(tree).second; }
ValueType& operator [ ] (vertex_t at) { return tree[ at ]; }
//by index, not by value
auto get_edges() { return pair_type(boost::edges(tree)); }
auto get_children(vertex_t pos= 0) {
return out_pair_type(std::make_pair(
make_out_iterator(pos), make_out_iterator_end(pos)));
}
auto breadth_first(vertex_t pos= 0) {
return vertex_pair_type(std::make_pair(
make_range_iterator(pos), make_range_iterator_end(pos)));
}
auto get_vertex_children(vertex_t pos) { return out_pair_type(boost::out_edges(pos, tree)); }
auto get_boost_graph_tree() { return tree; }
private:
tree_t tree;
vertex_t root;
};
// .....................................................................................
// .....................................................................................
int main()
{
//build tree to match the images in documentation
//https://en.wikipedia.org/wiki/Tree_traversal
typedef BGTree<char> char_tree_t;
char_tree_t tree('F');
auto last= tree.get_root();
last= tree.add_child('B' , last);
tree.add_child('A' , last);
last= tree.add_child('D' , last);
tree.add_child('C' , last);
tree.add_child('E' , last);
last= tree.get_root();
last= tree.add_child('G' , last);
last= tree.add_child('I' , last);
last= tree.add_child('H' , last);
// visualization
std::ofstream os("./graph.dot");
::write_graphviz(os, tree);
std::cout << "Pre-order: F, B, A, D, C, E, G, I, H\n";
for(auto& i : tree.breadth_first())
std::cout << i << " ";
std::cout << "\n\n";
std::cout << "Children of root: B, G\n";
for(auto& i : tree.get_children())
std::cout << i << " ";
std::cout << "\n\n";
auto it= std::find_if(
tree.breadth_first().begin(), tree.breadth_first().end(),
[ ] (const char& test) { return test == 'B'; });
std::cout << "should be 'B', find_if: " << *it << "\n\n";
std::cout << "children of 'B' from iterator: A D\n";
//as it has a referance to tree, could be it.get_children()?
for(auto& item : tree.get_children(it.vertex()))
std::cout << item << " ";
std::cout << "\n\n";
return 0;
}
Było [norma Propozycja] (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html) na drzewie biblioteki STL kompletny stylu kilka lat temu (który został odrzucony, głównie dlatego, że był duży i nie opierał się na dobrze znanej bibliotece). Nadal możesz znaleźć [implementację] (https://github.com/grafikrobot/boost-tree) przez autora wniosku. Może to będzie pasowało do twoich potrzeb. – Morwenn
Ta biblioteka zawiera w szczególności 'nary_tree' oraz iteratory i algorytmy do obsługi preorder, postorder i inorder. Co więcej, zapewnia również * kursory *, aby umożliwić większą elastyczność w modelu iteracji. Jest również gorzej zauważając, że pomimo swojej nazwy, nie jest on również częścią Boost (nie jest pewne, czy został odrzucony, czy nigdy nie został zaproponowany). Jest wydany na licencji Boost, więc nie powinieneś mieć problemów z licencjami, niezależnie od tego, co chcesz z tym zrobić. – Morwenn