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