在C ++中建模任意树（使用迭代器） [英] Modelling an arbitrary tree in C++ (with iterators)

问题描述

这个答案建议使用Boost Graph Library来完成这个任务：

/ p>

什么是良好和稳定的C ++树实现？我需要执行的主要操作是树的遍历函数（前序，子树，叶子），以及作为其子树。我还需要从孩子们那里收集数据的函数。

BGL是正确的选择，如何实现简单树的预遍历？在文档中，我只能找到有关常规图形的信息。

编辑：我也知道树。 hh library，但它的许可证不适合所有人。 这棵树。顶点迭代器和边缘迭代器现在都包装在外观中。如果我做出更多重大更改，我会发布它们。我曾经使用tree.hh来做一个小型的项目，但是并不喜欢它。

  #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> 
 
 // ........................................ ...... 
模板< typename Tree> 
 void write_graphviz（std :: ostream& os，Tree tree）
 {
 os<< digraph G {\ n; 
 for（auto it：tree）
 os<<它 [\\ n]; [\\ lt;< tree [it]<<\]; \ n; 
 for（auto it：tree.get_edges（））
 os<< it.m_source<<  - > 中<< it.m_target<< ; \\\
; 
 os<< } \\\
; 
} 
 
 // ................................... ........... 
模板< 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; } 
 
模板< typename Tree> 
 const typename boost :: graph_traits< Tree> :: vertex_descriptor get_vertex（Tree& tree，const typename Tree :: vertex_iterator& iter）{return * iter; } 
 
 // ....................................... ....... 
模板< 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：
朋友类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;返回*这个; }; 
 iterator_value_type vertex（）{return get_vertex（tree，iter）; } 
 //如何使这项工作？它吹起来的东西.... 
 // iterator_value_type运算符（）{返回get_vertex（树，iter）; } 
 
私人：
树&树; 
 IteratorType iter; 
}; 
 
 // ........................................ ...... 
模板< typename Tree，typename IterType> //代理容器
类tree_pair_type 
 {
 public：
 typedef typename boost :: graph_traits<树> :: 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; 
}; 
 
 // ........................................ ...... 
模板< 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; 
 
 //得到孩子
 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）; } 
 //获取子树
 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（））; } 
 $ b $ 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，不是按值
 vertex_iterator begin（）{return boost :: vertices（tree）.first; } 
 vertex_iterator end（）{return boost :: vertices（tree）.second; } 
 ValueType&运算符[]（vertex_t at）{return tree [at]; } 
 //通过索引而不是值
 auto get_edges（）{return pair_type（boost :: edges（tree））; } 
 $ b 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; } 
 
私有：
 tree_t树; 
 vertex_t root; 
}; 
 
 // ........................................ ............................................. 
 / / ................................................. .................................... 
 int main（）
 {
 //构建树以匹配文档中的图像
 //https://en.wikipedia.org/wiki/Tree_traversal 
 typedef BGTree< char> char_tree_t; 
 
 char_tree_t树（'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）; 
 
 //可视化
 std :: ofstream os（./graph.dot）; 
 :: write_graphviz（os，tree）; 
 
 std :: cout<< 预购：F，B，A，D，C，E，G，I，H \ n; （auto& i：tree.breadth_first（））
 std :: cout<<<我<< ; 
 std :: cout<< \\\
\\\
; 
 
 std :: cout<< 根的孩子：B，G \ n; （auto& i：tree.get_children（））
 std :: cout<<我<< ; 
 std :: cout<< \\\
\\\
; 
 $ b $ auto it = std :: find_if（
 tree.breadth_first（）.begin（），tree.breadth_first（）.end（），
 []（const char&测试）{return test =='B';}）; 
 std :: cout<< 应该是'B'，find_if：<< *它 \\\
\\\
; 
 
 std :: cout<< 来自迭代器的'B'的孩子：A D \ n; 
 //因为它对树有参考价值，可能是it.get_children（）？ （auto& item：tree.get_children（it.vertex（）））
 std :: cout<<项目<< ; 
 std :: cout<< \\\
\\\
; 
 
返回0; 
} 
  

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;
}

这篇关于在C ++中建模任意树（使用迭代器）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！