Modelowanie dowolnego drzewa w C++ (z iteratorami)

Question

Szukam sposobu modelowania drzewa z dowolną liczbą dzieci na węzły.

Ta odpowiedź sugeruje użycie Boost Graph Library dla tego zadania:

What's a good and stable C++ tree implementation?

podstawowych operacji, które trzeba wykonać są funkcjami traversal (preorder, dzieci, liść) na drzewie, a także jego poddrzew. Potrzebne mi będą także funkcje, które zbierają dane od dzieci w górę.

Czy BGL jest właściwym wyborem w tym przypadku, i w jaki sposób zrealizowane zostanie wstępne przejście prostego drzewa? W dokumentacji mogłem znaleźć jedynie informacje na temat zwykłych wykresów.

EDIT: Zdaję sobie również sprawę z biblioteki tree.hh ale jego licencja nie wydaje się odpowiednie dla każdego.

Answer 1

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

Answer 2

Biblioteka programu Boost Graph jest potężną biblioteką. Ale jak dla mnie, w twoim przypadku jest to zbyt dodatkowe narzędzie. Masz niewielką liczbę łatwych operacji. Nie potrzebujesz skomplikowanych algorytmów graficznych, takich jak wyszukiwanie ścieżek, podziałów wykresów itp. Co więcej, główną strukturą danych w twoim przypadku jest tylko drzewo (nie jest to GENERALNY wykres!). W takim przypadku możesz spróbować użyć następującego kodu:

#include <iostream> 
#include <list> 
#include <functional> 
#include <memory> 

// TODO: (dev) T should not be pointer type, in such case you will get memory leak! 
// Wrap it with unique_ptr, or create other specialization, or keep key in unique_ptr 
template <typename T> 
class Node 
{ 
public: 
typedef T key_type; 
typedef std::list<Node<T>*> nodes_type; 

Node(key_type key) : 
    m_key(key) 
{ 
} 

template <typename Func> 
void process_preorder(Func f) const 
{ 
    f(m_key); 
    for (nodes_type::const_iterator loc = m_nodes.begin(); loc != m_nodes.end(); ++loc) 
     (*loc)->process_preorder(f); 
} 

template <typename Func> 
void process_children(Func f) const 
{ 
    for (nodes_type::const_iterator loc = m_nodes.begin(); loc != m_nodes.end(); ++loc) 
     f((*loc)->m_key); 
} 

template <typename Func> 
void process_leafs(Func f) const 
{ 
    if (m_nodes.empty()) 
     f(m_key); 
    for (nodes_type::const_iterator loc = m_nodes.begin(); loc != m_nodes.end(); ++loc) 
     (*loc)->process_leafs(f); 
} 

Node<T>& add_child(key_type key) 
{ 
    Node<T>* new_node = new Node(key); 
    m_nodes.push_back(new_node); 
    return *new_node; 
} 
~Node() 
{ 
    std::cout << "Deletion node with key: " << m_key << std::endl; 
    // Children deletion 
    while (!m_nodes.empty()) 
    { 
     delete m_nodes.back(); 
     m_nodes.pop_back(); 
    } 
} 
private: 
key_type m_key; 
nodes_type m_nodes; 
}; 

int main() 
{ 
{ 
    typedef Node<int> node_type; 
    std::unique_ptr<node_type> n = std::make_unique<node_type>(0); 
    { 
     for (int i = 1; i <= 3; ++i) 
     { 
      node_type& current_child = n->add_child(i); 
      for (int j = 1; j <= 3; ++j) 
       current_child.add_child(i * 10 + j); 
     } 
    } 
    std::function<void(node_type::key_type)> printer = [](const node_type::key_type key) {std::cout << key << std::endl;}; 
    std::cout << "Printing via preorder" << std::endl; 
    n->process_preorder(printer); 
    std::cout << "Printing children of node with key: " << std::endl; 
    n->process_children(printer); 
    std::cout << "Printing leafs" << std::endl; 
    n->process_leafs(printer); 
} 
int i = 0; 
std::cin >> i; 
return 0; 
}