I am looking for a way to model a tree with an arbitrary amount of childrens per nodes.
This answer suggests using the Boost Graph Library for this task:
What's a good and stable C++ tree implementation?
The main operations that I need to perform are traversal functions (preorder, children, leafs) for the tree, as well as its subtrees. I will also need functions that gather data from the children upwards.
Is BGL the right choice for this, and how would a preorder traversal of a simple tree be implemented? In the documentation I could only find information on regular graphs.
EDIT: I am also aware of the tree.hh
library but its license does not seem suited for everyone.
I've made improvments to this tree. Both the vertex and edge iterators are now wrapped in the facade. If I make more major changes, I'll post them. I had use tree.hh a while back for a smallish project but didn't really like it. I'll replace it with this to see what else it needs.
#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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With