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 The class for computing the set of graph changes (over a subgraph)
24  * transmitted to learning algorithms
25  *
26  * Structure learning algorithm try different modifications of the graph. Class
27  * GraphChangesGeneratorOnSubDiGraph provides a simple way to compute those that
28  * we wish to perform when we wish to limit the set of changes over a subgraph
29  *of
30  * the graph we learn. For instance, we may wish to relearn an already partially
31  * learnt structure just around nodes A,B,C. In this case, we can set the set of
32  * target nodes of the GraphChangesGeneratorOnSubDiGraph to {A,B,C} and the set
33  * of starting nodes as all the nodes of the graph. In this case, only the arcs
34  * whose heads are A, B or C will be trnasmitted to the learning algorithm.
35  *
36  * Basically, the idea is to use method setGraph at the beginning of the
37  * structure learning in order to initialize the possible set of operators.
38  * Then, parse this set using a for ( auto iter = operator_set.begin ();
39  * iter != operator_set.end (); ++iter ) loop and compute the scores
40  * induced by these changes. When this is done, flush the operator set by
41  * calling method clearChanges. Then iterate changes and after each new change
42  * applied, used again the iterator for loop, and so on. Note that, whenever
43  * you execute method modifyGraph, this will automatically flush the current
44  * list of changes and put into the list only the changes that are affected
45  * by the graph modification.
46  *
47  * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6)
48  */
49 #ifndef GUM_LEARNING_GRAPH_CHANGES_GENERATOR_ON_SUBDIGRAPH_H
50 #define GUM_LEARNING_GRAPH_CHANGES_GENERATOR_ON_SUBDIGRAPH_H
51 
52 #include <agrum/agrum.h>
53 #include <agrum/tools/core/OMPThreads.h>
54 #include <agrum/tools/core/set.h>
55 #include <agrum/tools/graphs/diGraph.h>
56 #include <agrum/BN/learning/structureUtils/IGraphChangesGenerator4DiGraph.h>
57 #include <agrum/BN/learning/structureUtils/graphChange.h>
58 
59 namespace gum {
60 
61   namespace learning {
62 
63     /** @class GraphChangesGeneratorOnSubDiGraph
64      * @brief The basic class for computing the next graph changes possible in a
65      * structure learning algorithm
66      *
67      * Structure learning algorithm try different modifications of the graph.
68      *Class
69      * GraphChangesGeneratorOnSubDiGraph provides a simple way to compute those
70      * that we wish to perform when we wish to limit the set of changes over a
71      * subgraph of the graph we learn. For instance, we may wish to relearn an
72      * already partially learnt structure just around nodes A,B,C. In this case,
73      * we can set the set of target nodes of the
74      *GraphChangesGeneratorOnSubDiGraph
75      * to {A,B,C} and the set of "tail" nodes as all the nodes of the graph. In
76      * this case, only the arcs whose heads are A, B or C will be trnasmitted to
77      * the learning algorithm.
78      *
79      * Basically, the idea is to use method setGraph at the beginning of the
80      * structure learning in order to initialize the possible set of operators.
81      * Then, parse this set using a for ( auto iter = operator_set.begin ();
82      * iter != operator_set.end (); ++iter ) loop and compute the scores
83      * induced by these changes. When this is done, flush the operator set by
84      * calling method clearChanges. Then iterate changes and after each new
85      *change
86      * applied, used again the iterator for loop, and so on. Note that, whenever
87      * you execute method modifyGraph, this will automatically flush the current
88      * list of changes and put into the list only the changes that are affected
89      * by the graph modification.
90      *
91      * @ingroup learning_group
92      */
93     template < typename STRUCT_CONSTRAINT >
94     class GraphChangesGeneratorOnSubDiGraph: public IGraphChangesGenerator4DiGraph {
95       public:
96       /// the iterator for parsing the list of possible graph change operators
97       using iterator = typename Set< GraphChange >::const_iterator;
98 
99       /// the const iterator for parsing the list of graph change operators
100       using const_iterator = iterator;
101 
102       // ##########################################################################
103       /// @name Constructors / Destructors
104       // ##########################################################################
105       /// @{
106 
107       /// default constructor
108       GraphChangesGeneratorOnSubDiGraph(STRUCT_CONSTRAINT& constraint);
109 
110       /// copy constructor
111       GraphChangesGeneratorOnSubDiGraph(
112          const GraphChangesGeneratorOnSubDiGraph< STRUCT_CONSTRAINT >& from);
113 
114       /// move operator
115       GraphChangesGeneratorOnSubDiGraph(
116          GraphChangesGeneratorOnSubDiGraph< STRUCT_CONSTRAINT >&& from);
117 
118       /// destructor
119       virtual ~GraphChangesGeneratorOnSubDiGraph();
120 
121       /// @}
122 
123       // ##########################################################################
124       /// @name Operators
125       // ##########################################################################
126       /// @{
127 
128       /// copy operator
129       GraphChangesGeneratorOnSubDiGraph< STRUCT_CONSTRAINT >&
130          operator=(const GraphChangesGeneratorOnSubDiGraph< STRUCT_CONSTRAINT >& from);
131 
132       /// move operator
133       GraphChangesGeneratorOnSubDiGraph< STRUCT_CONSTRAINT >&
134          operator=(GraphChangesGeneratorOnSubDiGraph< STRUCT_CONSTRAINT >&& from);
135 
136       /// @}
137 
138       // ##########################################################################
139       /// @name Iterators
140       // ##########################################################################
141       /// @{
142 
143       /// returns an (unsafe) iterator on the beginning of the list of operators
144       iterator begin() const;
145 
146       /// returns an (unsafe) iterator on the end of the list of operators
147       const iterator& end() const;
148 
149       /// @}
150 
151       // ##########################################################################
152       /// @name Accessors / Modifiers
153       // ##########################################################################
154       /// @{
155 
156       /// returns the constraint that is used by the generator
157       STRUCT_CONSTRAINT& constraint() const noexcept;
158 
159       /// sets a new graph from which the operator will compute possible changes
160       void setGraph(const DiGraph& graph);
161 
162       /// assign a set of target nodes
163       void setTargets(const NodeSet& nodes);
164 
165       /// adds a new target node
166       void addTarget(NodeId node);
167 
168       /// removes a target
169       void eraseTarget(NodeId node);
170 
171       /// assign a set of "tail" nodes
172       void setTails(const NodeSet& nodes);
173 
174       /// assign a set of "tail" nodes from 0 to nb_nodes - 1
175       void setTails(Size nb_nodes);
176 
177       /// adds a new "tail" node
178       void addTail(NodeId node);
179 
180       /// removes a tail node
181       void eraseTail(NodeId node);
182 
183       /// notify the operator set of a change applied to the graph
184       void modifyGraph(const ArcAddition& change);
185 
186       /// notify the operator set of a change applied to the graph
187       void modifyGraph(const ArcDeletion& change);
188 
189       /// notify the operator set of a change applied to the graph
190       void modifyGraph(const ArcReversal& change);
191 
192       /// notify the operator set of a change applied to the graph
193       void modifyGraph(const GraphChange& change);
194 
195       /// empty the set of possible change operators that can be applied
196       void clearChanges() noexcept;
197 
198       /// notifies the generator that we have parsed all its legal changes
199       void notifyGetCompleted();
200 
201       /// sets the maximum number of threads used to compute the set of changes
202       void setMaxNbThreads(Size nb) noexcept;
203 
204       /// @}
205 
206       protected:
207       /// a reference on the structural constraint used to restrict the changes
208       STRUCT_CONSTRAINT* constraint_;
209 
210       /// the set of target nodes
211       NodeSet target_nodes_;
212 
213       /// the tail nodes (other extremities than the targets)
214       NodeSet tail_nodes_;
215 
216       /// the current set of operators
217       Set< GraphChange > legal_changes_;
218 
219       /// create the set of legal and illegal changes from a given graph
220       void createChanges_();
221 
222       private:
223 /// the max number of threads authorized
224 #if defined(_OPENMP) && !defined(GUM_DEBUG_MODE)
225       Size _max_threads_number_{getMaxNumberOfThreads()};
226 #else
227       Size _max_threads_number_{1};
228 #endif /* GUM_DEBUG_MODE */
229     };
230 
231   } /* namespace learning */
232 
233 } /* namespace gum */
234 
235 /// always include the templated functions
236 #include <agrum/BN/learning/structureUtils/graphChangesGeneratorOnSubDiGraph_tpl.h>
237 
238 #endif /* GUM_LEARNING_GRAPH_CHANGES_GENERATOR_ON_SUBDIGRAPH_H */
239