#ifndef FERI_TREESTRUCTURES #define FERI_TREESTRUCTURES // ----------------------------------------------- // Computation of B-Series // // Rooted Tree, TreeList // ----------------------------------------------- #include "main.hpp" // ----------------------------------------------- // rooted tree class RootedTree : public capd::vectalg::Vector { public: typedef capd::vectalg::Vector BaseClass; using BaseClass::operator(); // ----------------------------------------------- // constructor RootedTree(int m_dim) : BaseClass(m_dim) {} RootedTree() : BaseClass(1) {} // ----------------------------------------------- // comparing parental arrays bool operator<(const RootedTree &other) const { // trees of same order if (this->size() == other.size()) { for (int i = 1; i <= this->size(); ++i) { // the i th coordinate is in opposite relation (after first of this kind, we exit with returning false) if ( (*this)(i) > other(i) ) { return false; // the i th coordinate gives < (after first of this kind, we exit with returning true) } else if ( (*this)(i) < other(i) ){ return true; } } // they are equal return false; // trees of different order } else { return (this->size() < other.size()); } } bool operator==(const RootedTree &other) const { // trees of same order if (this->size() == other.size()) { for (int i = 1; i <= this->size(); ++i) { // the i th coordinate is not the same if ( (*this)(i) != other(i) ) { return false; } } // they are equal return true; // trees of different order } else { return false; } } // ----------------------------------------------- // returning number of children (first level subtrees) int numberOfChildren() { int result = 0; for (int i = 1; i <= this->size(); ++i) if ((*this)(i) == 1) ++result; return result; } // returning the number #num child of the tree RootedTree child(const int &num) { int current_child = 0; int start, end; // finding the root of the child start = 0; while (current_child < num) { ++start; if ((*this)(start) == 1) ++current_child; } // finding the next root / end of tree end = start; while ( (current_child == num) && (end < (*this).size()) ){ ++end; if ((*this)(end) == 1) ++current_child; } if (current_child > num) --end; // extracting result RootedTree result(end - start + 1); result(1) = 0; for (int i = 1; i <= end - start; ++i) result(i + 1) = (*this)(start + i) - start + 1; return result; } }; // ----------------------------------------------- // list element class TreeListElement { public: RootedTree tree; VertexDescriptor vertex; // ----------------------------------------------- // constructor TreeListElement(int m_dim) { tree.resize(m_dim); } // ----------------------------------------------- // ordering inline bool operator<(const TreeListElement &other) const { return (tree < other.tree); } inline bool operator==(const TreeListElement &other) const { return (tree == other.tree); } }; // ----------------------------------------------- // the list to hold our trees class TreeList : public std::list { public: typedef std::list BaseClass; // ----------------------------------------------- // saves a tree to the list void saveRootedTree(const RootedTree &raw_tree, const int &order) { TreeListElement list_element(order); // create the standard tree form, that we want to store for (int i = 1; i <= order; ++i) list_element.tree(i) = raw_tree(i); // insert the new tree (*this).push_back(list_element); } // ----------------------------------------------- // generates trees in anti-lexicographic order (w.r. parent array) void rec_generate(int p, int s, int cL, const int &max_order, RootedTree &raw_tree) { if (p <= max_order) { if (cL == 0) { raw_tree(p) = p - 1; } else if (raw_tree(p - cL) < s) { raw_tree(p) = raw_tree(s); } else { raw_tree(p) = cL + raw_tree(p - cL); } this->saveRootedTree(raw_tree, p); rec_generate(p + 1, s, cL, max_order, raw_tree); while (raw_tree(p) > 1) { s = raw_tree(p); raw_tree(p) = raw_tree(s); this->saveRootedTree(raw_tree, p); rec_generate(p + 1, s, p - s, max_order, raw_tree); } } } // start generation of trees up to order: max_order void generate(const int &max_order) { RootedTree raw_tree(max_order); this->rec_generate(1, 0, 0, max_order, raw_tree); this->sort(); } // ----------------------------------------------- // find a rooted tree in the list BaseClass::iterator find(const RootedTree &tree) { TreeListElement list_element(tree.size()); list_element.tree = tree; //return std::equal_range(this->begin(), this->end(), list_element).first; return std::find(this->begin(), this->end(), list_element); } // ----------------------------------------------- // filling the vertex component of the elements from a list void match_vertices(VertexList &vertex_list) { VertexListIterator it_vlist = vertex_list.begin(); for (BaseClass::iterator it = this->begin(); it != this->end(); ++it) { (*it).vertex = *it_vlist; ++it_vlist; } } // ----------------------------------------------- // print list void print() { for (BaseClass::iterator it = this->begin(); it != this->end(); ++it) std::cout << (*it).tree << std::endl; } }; // ~ end of file ~ #endif