1 #ifndef TERRACES_CONSTRAINTS_HPP 2 #define TERRACES_CONSTRAINTS_HPP 3 4 #include <iosfwd> 5 #include <tuple> 6 #include <vector> 7 8 #include "trees.hpp" 9 10 namespace terraces { 11 12 /** 13 * Represents a LCA constraint on leaves of a tree. 14 * It is of the form \code 15 * lca(left, shared) < lca(shared, right) 16 * where the LCA's are compared by their height in the tree. 17 */ 18 struct constraint { 19 index left; 20 index shared; 21 index right; 22 constraintterraces::constraint23 constraint(index left, index shared, index right) 24 : left{left}, shared{shared}, right{right} {} 25 operator ==terraces::constraint26 bool operator==(const constraint& o) const { 27 return std::tie(left, shared, right) == std::tie(o.left, o.shared, o.right); 28 } 29 operator !=terraces::constraint30 bool operator!=(const constraint& o) const { return !(o == *this); } 31 }; 32 33 using constraints = std::vector<constraint>; 34 35 std::ostream& operator<<(std::ostream& s, const constraint& c); 36 37 /** 38 * Extracts all LCA constraints from the input trees. 39 * \param trees The input trees. 40 * \returns All LCA constraints for the input trees. 41 * For every inner edge, one LCA constraint based on the leftmost and rightmost descendant 42 * of the endpoints are is extracted. 43 */ 44 constraints compute_constraints(const std::vector<tree>& trees); 45 46 /** 47 * Removes duplicate constraints from the input vector 48 * \param in_c The input constraints. 49 * \returns The input constraints without duplicates and possibly reordered. 50 */ 51 index deduplicate_constraints(constraints& in_c); 52 53 } // namespace terraces 54 55 #endif // TERRACES_CONSTRAINTS_HPP 56