1 /** 2 * 3 * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 4 * info_at_agrum_dot_org 5 * 6 * This library is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public License 17 * along with this library. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 21 22 /** @file 23 * @brief Base class for all elimination sequence algorithm that impose a given 24 * partial ordering on the nodes elimination sequence, that is, the set of all 25 * the nodes is divided into several subsets. Within each subset, any ordering 26 * can be chosen. But all the nodes of the first subset must be eliminated 27 * before the nodes of the second, which must be eliminated before those of the 28 * third subset, and so on. 29 * 30 * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6) 31 */ 32 33 #include <agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/partialOrderedEliminationSequenceStrategy.h> 34 35 #ifdef GUM_NO_INLINE 36 # include <agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/partialOrderedEliminationSequenceStrategy_inl.h> 37 #endif // GUM_NOINLINE 38 39 namespace gum { 40 41 /// default constructor PartialOrderedEliminationSequenceStrategy()42 PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy() { 43 // for debugging purposes 44 GUM_CONSTRUCTOR(PartialOrderedEliminationSequenceStrategy); 45 } 46 47 /// constructor for an a priori non empty graph PartialOrderedEliminationSequenceStrategy(UndiGraph * graph,const NodeProperty<Size> * dom_sizes,const List<NodeSet> * subsets)48 PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy( 49 UndiGraph* graph, 50 const NodeProperty< Size >* dom_sizes, 51 const List< NodeSet >* subsets) { 52 setGraph(graph, dom_sizes); 53 setPartialOrder(subsets); 54 55 // for debugging purposes 56 GUM_CONSTRUCTOR(PartialOrderedEliminationSequenceStrategy); 57 } 58 59 /// copy constructor PartialOrderedEliminationSequenceStrategy(const PartialOrderedEliminationSequenceStrategy & from)60 PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy( 61 const PartialOrderedEliminationSequenceStrategy& from) : 62 EliminationSequenceStrategy(from), 63 subsets_(from.subsets_), subset_iter_(from.subset_iter_), nodeset_(from.nodeset_), 64 partial_order_needed_(from.partial_order_needed_) { 65 // for debugging purposes 66 GUM_CONS_CPY(PartialOrderedEliminationSequenceStrategy); 67 } 68 69 /// move constructor PartialOrderedEliminationSequenceStrategy(PartialOrderedEliminationSequenceStrategy && from)70 PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy( 71 PartialOrderedEliminationSequenceStrategy&& from) : 72 EliminationSequenceStrategy(std::move(from)), 73 subsets_(from.subsets_), subset_iter_(from.subset_iter_), nodeset_(std::move(from.nodeset_)), 74 partial_order_needed_(from.partial_order_needed_) { 75 from.partial_order_needed_ = true; 76 77 // for debugging purposes 78 GUM_CONS_MOV(PartialOrderedEliminationSequenceStrategy); 79 } 80 81 /// destructor ~PartialOrderedEliminationSequenceStrategy()82 PartialOrderedEliminationSequenceStrategy::~PartialOrderedEliminationSequenceStrategy() { 83 // for debugging purposes 84 GUM_DESTRUCTOR(PartialOrderedEliminationSequenceStrategy); 85 } 86 87 /// sets a new graph to be triangulated 88 bool setGraph(UndiGraph * graph,const NodeProperty<Size> * domain_sizes)89 PartialOrderedEliminationSequenceStrategy::setGraph(UndiGraph* graph, 90 const NodeProperty< Size >* domain_sizes) { 91 if (EliminationSequenceStrategy::setGraph(graph, domain_sizes)) { 92 setPartialOrder(subsets_); 93 return true; 94 } 95 return false; 96 } 97 98 /// indicate whether a partial ordering is compatible with the current graph isPartialOrderNeeded_(const List<NodeSet> * subsets) const99 bool PartialOrderedEliminationSequenceStrategy::isPartialOrderNeeded_( 100 const List< NodeSet >* subsets) const { 101 if ((graph_ == nullptr) || (subsets == nullptr)) return true; 102 103 // determine the set of nodes in the subsets that belong to the graph 104 NodeSet nodes_found(graph_->size() / 2); 105 for (const auto& nodes: *subsets) { 106 for (const auto node: nodes) { 107 if (graph_->existsNode(node)) { nodes_found.insert(node); } 108 } 109 } 110 111 // check that the size of nodes_found is equal to that of the graph 112 return nodes_found.size() != graph_->size(); 113 } 114 115 /// sets a new partial order setPartialOrder(const List<NodeSet> * subsets)116 bool PartialOrderedEliminationSequenceStrategy::setPartialOrder(const List< NodeSet >* subsets) { 117 // check that the partial order contains all the nodes of the graph 118 partial_order_needed_ = isPartialOrderNeeded_(subsets); 119 120 if (!partial_order_needed_) { 121 subsets_ = subsets; 122 123 // initialize properly the set of nodes that can be currently eliminated: 124 // find the first subset that contains some node(s) of the graph 125 nodeset_.clear(); 126 for (subset_iter_ = subsets_->cbegin(); subset_iter_ != subsets_->cend(); ++subset_iter_) { 127 for (const auto node: *subset_iter_) { 128 if (graph_->existsNode(node)) { nodeset_.insert(node); } 129 } 130 if (!nodeset_.empty()) return true; 131 } 132 } 133 134 return false; 135 } 136 137 /// clears the sequence (to prepare, for instance, a new elimination sequence) clear()138 void PartialOrderedEliminationSequenceStrategy::clear() { 139 EliminationSequenceStrategy::clear(); 140 subsets_ = nullptr; 141 nodeset_.clear(); 142 partial_order_needed_ = true; 143 } 144 145 } /* namespace gum */ 146