aGrUM  0.20.2
a C++ library for (probabilistic) graphical models
graphChangesSelector4DiGraph_tpl.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@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 mecanism to compute the next available graph changes for directed
24  * structure learning search algorithms.
25  *
26  * @author Christophe GONZALES(@AMU) and Pierre-Henri WUILLEMIN(@LIP6)
27  */
28 #ifndef DOXYGEN_SHOULD_SKIP_THIS
29 
30 # include <limits>
31 
32 namespace gum {
33 
34  namespace learning {
35 
36  /// default constructor
37  template < typename STRUCTURAL_CONSTRAINT,
38  typename GRAPH_CHANGES_GENERATOR,
39  template < typename >
40  class ALLOC >
41  INLINE GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
42  GRAPH_CHANGES_GENERATOR,
43  ALLOC >::
44  GraphChangesSelector4DiGraph(Score< ALLOC >& score,
45  STRUCTURAL_CONSTRAINT& constraint,
46  GRAPH_CHANGES_GENERATOR& changes_generator) :
47  score__(score.clone()),
48  constraint__(&constraint), changes_generator__(&changes_generator) {
49  parents__.resize(32);
50  GUM_CONSTRUCTOR(GraphChangesSelector4DiGraph);
51  }
52 
53  /// copy constructor
54  template < typename STRUCTURAL_CONSTRAINT,
55  typename GRAPH_CHANGES_GENERATOR,
56  template < typename >
57  class ALLOC >
58  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
59  GRAPH_CHANGES_GENERATOR,
60  ALLOC >::
61  GraphChangesSelector4DiGraph(
62  const GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
63  GRAPH_CHANGES_GENERATOR,
64  ALLOC >& from) :
65  score__(from.score__ != nullptr ? from.score__->clone() : nullptr),
66  constraint__(from.constraint__),
67  changes_generator__(from.changes_generator__), changes__(from.changes__),
68  change_scores__(from.change_scores__),
69  change_queue_per_node__(from.change_queue_per_node__),
70  node_queue__(from.node_queue__), illegal_changes__(from.illegal_changes__),
71  node_current_scores__(from.node_current_scores__),
72  parents__(from.parents__), queues_valid__(from.queues_valid__),
73  queues_to_update__(from.queues_to_update__) {
74  // for debugging
75  GUM_CONS_CPY(GraphChangesSelector4DiGraph);
76  }
77 
78  /// move constructor
79  template < typename STRUCTURAL_CONSTRAINT,
80  typename GRAPH_CHANGES_GENERATOR,
81  template < typename >
82  class ALLOC >
83  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
84  GRAPH_CHANGES_GENERATOR,
85  ALLOC >::
86  GraphChangesSelector4DiGraph(
87  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
88  GRAPH_CHANGES_GENERATOR,
89  ALLOC >&& from) :
90  score__(from.score__),
91  constraint__(std::move(from.constraint__)),
92  changes_generator__(std::move(from.changes_generator__)),
93  changes__(std::move(from.changes__)),
94  change_scores__(std::move(from.change_scores__)),
95  change_queue_per_node__(std::move(from.change_queue_per_node__)),
96  node_queue__(std::move(from.node_queue__)),
97  illegal_changes__(std::move(from.illegal_changes__)),
98  node_current_scores__(std::move(from.node_current_scores__)),
99  parents__(std::move(from.parents__)),
100  queues_valid__(std::move(from.queues_valid__)),
101  queues_to_update__(std::move(from.queues_to_update__)) {
102  from.score__ = nullptr;
103  // for debugging
104  GUM_CONS_MOV(GraphChangesSelector4DiGraph);
105  }
106 
107  /// destructor
108  template < typename STRUCTURAL_CONSTRAINT,
109  typename GRAPH_CHANGES_GENERATOR,
110  template < typename >
111  class ALLOC >
112  INLINE GraphChangesSelector4DiGraph<
113 
114  STRUCTURAL_CONSTRAINT,
115  GRAPH_CHANGES_GENERATOR,
116  ALLOC >::~GraphChangesSelector4DiGraph() {
117  if (score__ != nullptr) {
118  ALLOC< Score< ALLOC > > allocator(score__->getAllocator());
119  allocator.destroy(score__);
120  allocator.deallocate(score__, 1);
121  }
122  GUM_DESTRUCTOR(GraphChangesSelector4DiGraph);
123  }
124 
125  /// copy operator
126  template < typename STRUCTURAL_CONSTRAINT,
127  typename GRAPH_CHANGES_GENERATOR,
128  template < typename >
129  class ALLOC >
130  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
131  GRAPH_CHANGES_GENERATOR,
132  ALLOC >&
133  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
134  GRAPH_CHANGES_GENERATOR,
135  ALLOC >::
136  operator=(const GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
137  GRAPH_CHANGES_GENERATOR,
138  ALLOC >& from) {
139  if (this != &from) {
140  // remove the old score
141  if (score__ != nullptr) {
142  ALLOC< Score< ALLOC > > allocator(score__->getAllocator());
143  allocator.destroy(score__);
144  allocator.deallocate(score__, 1);
145  score__ = nullptr;
146  }
147 
148  if (from.score__ != nullptr) score__ = from.score__->clone();
149  constraint__ = from.constraint__;
150  changes_generator__ = from.changes_generator__;
151  changes__ = from.changes__;
152  change_scores__ = from.change_scores__;
153  change_queue_per_node__ = from.change_queue_per_node__;
154  node_queue__ = from.node_queue__;
155  illegal_changes__ = from.illegal_changes__;
156  node_current_scores__ = from.node_current_scores__;
157  parents__ = from.parents__;
158  queues_valid__ = from.queues_valid__;
159  queues_to_update__ = from.queues_to_update__;
160  }
161 
162  return *this;
163  }
164 
165  /// move operator
166  template < typename STRUCTURAL_CONSTRAINT,
167  typename GRAPH_CHANGES_GENERATOR,
168  template < typename >
169  class ALLOC >
170  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
171  GRAPH_CHANGES_GENERATOR,
172  ALLOC >&
173  GraphChangesSelector4DiGraph<
174  STRUCTURAL_CONSTRAINT,
175  GRAPH_CHANGES_GENERATOR,
176  ALLOC >::operator=(GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
177  GRAPH_CHANGES_GENERATOR,
178  ALLOC >&& from) {
179  if (this != &from) {
180  score__ = from.score__;
181  from.score__ = nullptr;
182 
183  constraint__ = std::move(from.constraint__);
184  changes_generator__ = std::move(from.changes_generator__);
185  changes__ = std::move(from.changes__);
186  change_scores__ = std::move(from.change_scores__);
187  change_queue_per_node__ = std::move(from.change_queue_per_node__);
188  node_queue__ = std::move(from.node_queue__);
189  illegal_changes__ = std::move(from.illegal_changes__);
190  node_current_scores__ = std::move(from.node_current_scores__);
191  parents__ = std::move(from.parents__);
192  queues_valid__ = std::move(from.queues_valid__);
193  queues_to_update__ = std::move(from.queues_to_update__);
194  }
195 
196  return *this;
197  }
198 
199 
200  /// indicates whether a given change is valid or not
201  template < typename STRUCTURAL_CONSTRAINT,
202  typename GRAPH_CHANGES_GENERATOR,
203  template < typename >
204  class ALLOC >
205  INLINE bool
206  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
207  GRAPH_CHANGES_GENERATOR,
208  ALLOC >::isChangeValid(const GraphChange&
209  change) const {
210  return constraint__->checkModification(change);
211  }
212 
213 
214  /// indicates whether a given change is valid or not
215  template < typename STRUCTURAL_CONSTRAINT,
216  typename GRAPH_CHANGES_GENERATOR,
217  template < typename >
218  class ALLOC >
219  INLINE bool
220  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
221  GRAPH_CHANGES_GENERATOR,
222  ALLOC >::isChangeValid__(const std::size_t
223  index) const {
224  return isChangeValid(changes__[index]);
225  }
226 
227 
228  /// sets the graph from which scores are computed
229  template < typename STRUCTURAL_CONSTRAINT,
230  typename GRAPH_CHANGES_GENERATOR,
231  template < typename >
232  class ALLOC >
233  void GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
234  GRAPH_CHANGES_GENERATOR,
235  ALLOC >::setGraph(DiGraph& graph) {
236  // fill the DAG with all the missing nodes
237  const DatabaseTable< ALLOC >& database = score__->database();
238  const auto& nodeId2Columns = score__->nodeId2Columns();
239 
240  if (nodeId2Columns.empty()) {
241  const NodeId nb_nodes = NodeId(database.nbVariables());
242  for (NodeId i = NodeId(0); i < nb_nodes; ++i) {
243  if (!graph.existsNode(i)) { graph.addNodeWithId(i); }
244  }
245  } else {
246  for (auto iter = nodeId2Columns.cbegin(); iter != nodeId2Columns.cend();
247  ++iter) {
248  const NodeId id = iter.first();
249  if (!graph.existsNode(id)) { graph.addNodeWithId(id); }
250  }
251  }
252 
253 
254  // remove the node that do belong neither to the database
255  // nor to nodeId2Columns
256  if (nodeId2Columns.empty()) {
257  const NodeId nb_nodes = NodeId(database.nbVariables());
258  for (auto node: graph) {
259  if (node >= nb_nodes) { graph.eraseNode(node); }
260  }
261  } else {
262  for (auto node: graph) {
263  if (!nodeId2Columns.existsFirst(node)) { graph.eraseNode(node); }
264  }
265  }
266 
267 
268  // constraint__ is the constraint used by the selector to restrict the set
269  // of applicable changes. However, the generator may have a different set
270  // of constraints (e.g., a constraintSliceOrder needs be tested only by the
271  // generator because the changes returned by the generator will always
272  // statisfy this constraint, hence the selector needs not test this
273  // constraint). Therefore, if the selector and generator have different
274  // constraints, both should use method setGraph() to initialize
275  // themselves.
276  constraint__->setGraph(graph);
277  if (reinterpret_cast< STRUCTURAL_CONSTRAINT* >(
278  &(changes_generator__->constraint()))
279  != constraint__) {
280  changes_generator__->constraint().setGraph(graph);
281  }
282 
283  changes_generator__->setGraph(graph);
284 
285 
286  // save the set of parents of each node (this will speed-up the
287  // computations of the scores)
288  const std::size_t nb_nodes = graph.size();
289  {
290  const std::vector< NodeId, ALLOC< NodeId > > empty_pars;
291  parents__.clear();
292  parents__.resize(nb_nodes);
293  for (const auto node: graph) {
294  auto& node_parents = parents__.insert(node, empty_pars).second;
295  const NodeSet& dag_parents = graph.parents(node);
296  if (!dag_parents.empty()) {
297  node_parents.resize(dag_parents.size());
298  std::size_t j = std::size_t(0);
299  for (const auto par: dag_parents) {
300  node_parents[j] = par;
301  ++j;
302  }
303  }
304  }
305  }
306 
307  // assign a score to each node given its parents in the current graph
308  node_current_scores__.clear();
309  node_current_scores__.resize(nb_nodes);
310  for (const auto node: graph) {
311  node_current_scores__.insert(node, score__->score(node, parents__[node]));
312  }
313 
314  // compute all the possible changes
315  changes__.clear();
316  changes__.resize(nb_nodes);
317  for (const auto& change: *changes_generator__) {
318  changes__ << change;
319  }
320  changes_generator__->notifyGetCompleted();
321 
322  // determine the changes that are illegal and prepare the computation of
323  // the scores of all the legal changes
324  illegal_changes__.clear();
325 
326  // set the change_scores__ and change_queue_per_node__ for legal changes
327  change_scores__.clear();
328  change_scores__.resize(
329  changes__.size(),
330  std::pair< double, double >(std::numeric_limits< double >::min(),
331  std::numeric_limits< double >::min()));
332  change_queue_per_node__.clear();
333  change_queue_per_node__.resize(nb_nodes);
334  {
335  const PriorityQueue< std::size_t, double, std::greater< double > >
336  empty_prio;
337  for (const auto node: graph) {
338  change_queue_per_node__.insert(node, empty_prio);
339  }
340  }
341 
342  for (std::size_t i = std::size_t(0); i < changes__.size(); ++i) {
343  if (!isChangeValid__(i)) {
344  illegal_changes__.insert(i);
345  } else {
346  const GraphChange& change = changes__[i];
347 
348  switch (change.type()) {
349  case GraphChangeType::ARC_ADDITION: {
350  auto& parents = parents__[change.node2()];
351  parents.push_back(change.node1());
352  const double delta = score__->score(change.node2(), parents)
353  - node_current_scores__[change.node2()];
354  parents.pop_back();
355 
356  change_scores__[i].second = delta;
357  change_queue_per_node__[change.node2()].insert(i, delta);
358  } break;
359 
360  case GraphChangeType::ARC_DELETION: {
361  auto& parents = parents__[change.node2()];
362  for (auto& par: parents) {
363  if (par == change.node1()) {
364  par = *(parents.rbegin());
365  parents.pop_back();
366  break;
367  }
368  }
369  const double delta = score__->score(change.node2(), parents)
370  - node_current_scores__[change.node2()];
371  parents.push_back(change.node1());
372 
373  change_scores__[i].second = delta;
374  change_queue_per_node__[change.node2()].insert(i, delta);
375  } break;
376 
377  case GraphChangeType::ARC_REVERSAL: {
378  // remove arc ( node1 -> node2 )
379  auto& parents2 = parents__[change.node2()];
380  for (auto& par: parents2) {
381  if (par == change.node1()) {
382  par = *(parents2.rbegin());
383  parents2.pop_back();
384  break;
385  }
386  }
387 
388  const double delta2 = score__->score(change.node2(), parents2)
389  - node_current_scores__[change.node2()];
390  parents2.push_back(change.node1());
391 
392  // add arc ( node2 -> node1 )
393  auto& parents1 = parents__[change.node1()];
394  parents1.push_back(change.node2());
395  const double delta1 = score__->score(change.node1(), parents1)
396  - node_current_scores__[change.node1()];
397  parents1.pop_back();
398 
399  change_scores__[i].first = delta1;
400  change_scores__[i].second = delta2;
401 
402  const double delta = delta1 + delta2;
403  change_queue_per_node__[change.node1()].insert(i, delta);
404  change_queue_per_node__[change.node2()].insert(i, delta);
405 
406  } break;
407 
408  default: {
409  GUM_ERROR(NotImplementedYet,
410  "Method setGraph of GraphChangesSelector4DiGraph "
411  << "does not handle yet graph change of type "
412  << change.type());
413  }
414  }
415  }
416  }
417 
418  // update the global queue
419  node_queue__.clear();
420  for (const auto node: graph) {
421  node_queue__.insert(node,
422  change_queue_per_node__[node].empty()
423  ? std::numeric_limits< double >::min()
424  : change_queue_per_node__[node].topPriority());
425  }
426  queues_valid__ = true;
427  queues_to_update__.clear();
428  }
429 
430 
431  /// put a change into the illegal set
432  template < typename STRUCTURAL_CONSTRAINT,
433  typename GRAPH_CHANGES_GENERATOR,
434  template < typename >
435  class ALLOC >
436  void
437  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
438  GRAPH_CHANGES_GENERATOR,
439  ALLOC >::invalidateChange__(const std::size_t
440  change_index) {
441  const GraphChange& change = changes__[change_index];
442  if (change.type() == GraphChangeType::ARC_REVERSAL) {
443  // remove the tail change from its priority queue
444  PriorityQueue< std::size_t, double, std::greater< double > >& queue1
445  = change_queue_per_node__[change.node1()];
446  queue1.erase(change_index);
447 
448  // recompute the top priority for the changes of the head
449  const double new_priority = queue1.empty()
450  ? std::numeric_limits< double >::min()
451  : queue1.topPriority();
452  node_queue__.setPriority(change.node1(), new_priority);
453  }
454 
455  // remove the head change from its priority queue
456  PriorityQueue< std::size_t, double, std::greater< double > >& queue2
457  = change_queue_per_node__[change.node2()];
458  queue2.erase(change_index);
459 
460  // recompute the top priority for the changes of the head
461  const double new_priority = queue2.empty()
462  ? std::numeric_limits< double >::min()
463  : queue2.topPriority();
464  node_queue__.setPriority(change.node2(), new_priority);
465 
466  // put the change into the illegal set
467  illegal_changes__.insert(change_index);
468  }
469 
470 
471  /// indicates whether the selector still contain graph changes
472  template < typename STRUCTURAL_CONSTRAINT,
473  typename GRAPH_CHANGES_GENERATOR,
474  template < typename >
475  class ALLOC >
476  bool GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
477  GRAPH_CHANGES_GENERATOR,
478  ALLOC >::empty() {
479  // put into the illegal change set all the top elements of the different
480  // queues that are not valid anymore
481  if (!queues_valid__) {
482  for (auto& queue_pair: change_queue_per_node__) {
483  auto& queue = queue_pair.second;
484  while (!queue.empty() && !isChangeValid__(queue.top())) {
485  invalidateChange__(queue.top());
486  }
487  }
488  queues_valid__ = true;
489  }
490 
491  return node_queue__.topPriority() == std::numeric_limits< double >::min();
492  }
493 
494 
495  /// indicates whether the selector still contain graph changes
496  /// in the ith queue
497  template < typename STRUCTURAL_CONSTRAINT,
498  typename GRAPH_CHANGES_GENERATOR,
499  template < typename >
500  class ALLOC >
501  bool GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
502  GRAPH_CHANGES_GENERATOR,
503  ALLOC >::empty(const NodeId node) {
504  // put into the illegal change set all the top elements of the different
505  // queues that are not valid anymore
506  if (!queues_valid__) {
507  for (auto& queue_pair: change_queue_per_node__) {
508  auto& queue = queue_pair.second;
509  while (!queue.empty() && !isChangeValid__(queue.top())) {
510  invalidateChange__(queue.top());
511  }
512  }
513  queues_valid__ = true;
514  }
515 
516  return change_queue_per_node__[node].empty();
517  }
518 
519 
520  /// returns the best graph change to examine
521  template < typename STRUCTURAL_CONSTRAINT,
522  typename GRAPH_CHANGES_GENERATOR,
523  template < typename >
524  class ALLOC >
525  INLINE const GraphChange&
526  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
527  GRAPH_CHANGES_GENERATOR,
528  ALLOC >::bestChange() {
529  if (!empty())
530  return changes__[change_queue_per_node__[node_queue__.top()].top()];
531  else
532  GUM_ERROR(NotFound, "there exists no graph change applicable");
533  }
534 
535 
536  /// returns the best graph change to examine in the ith queue
537  template < typename STRUCTURAL_CONSTRAINT,
538  typename GRAPH_CHANGES_GENERATOR,
539  template < typename >
540  class ALLOC >
541  INLINE const GraphChange&
542  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
543  GRAPH_CHANGES_GENERATOR,
544  ALLOC >::bestChange(const NodeId node) {
545  if (!empty(node))
546  return changes__[change_queue_per_node__[node].top()];
547  else
548  GUM_ERROR(NotFound, "there exists no graph change applicable");
549  }
550 
551 
552  /// return the score of the best graph change
553  template < typename STRUCTURAL_CONSTRAINT,
554  typename GRAPH_CHANGES_GENERATOR,
555  template < typename >
556  class ALLOC >
557  INLINE double GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
558  GRAPH_CHANGES_GENERATOR,
559  ALLOC >::bestScore() {
560  if (!empty())
561  return change_queue_per_node__[node_queue__.top()].topPriority();
562  else
563  GUM_ERROR(NotFound, "there exists no graph change applicable");
564  }
565 
566 
567  /// return the score of the best graph change in the ith queue
568  template < typename STRUCTURAL_CONSTRAINT,
569  typename GRAPH_CHANGES_GENERATOR,
570  template < typename >
571  class ALLOC >
572  INLINE double
573  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
574  GRAPH_CHANGES_GENERATOR,
575  ALLOC >::bestScore(const NodeId node) {
576  if (!empty(node))
577  return change_queue_per_node__[node].topPriority();
578  else
579  GUM_ERROR(NotFound, "there exists no graph change applicable");
580  }
581 
582 
583  /// remove the now legal changes from the illegal set
584  template < typename STRUCTURAL_CONSTRAINT,
585  typename GRAPH_CHANGES_GENERATOR,
586  template < typename >
587  class ALLOC >
588  void GraphChangesSelector4DiGraph<
589  STRUCTURAL_CONSTRAINT,
590  GRAPH_CHANGES_GENERATOR,
591  ALLOC >::illegal2LegalChanges__(Set< std::size_t >& changes_to_recompute) {
592  for (auto iter = illegal_changes__.beginSafe();
593  iter != illegal_changes__.endSafe();
594  ++iter) {
595  if (isChangeValid__(*iter)) {
596  const GraphChange& change = changes__[*iter];
597  if (change.type() == GraphChangeType::ARC_REVERSAL) {
598  change_queue_per_node__[change.node1()].insert(
599  *iter,
600  std::numeric_limits< double >::min());
601  }
602  change_queue_per_node__[change.node2()].insert(
603  *iter,
604  std::numeric_limits< double >::min());
605 
606  changes_to_recompute.insert(*iter);
607  illegal_changes__.erase(iter);
608  }
609  }
610  }
611 
612 
613  /// finds the changes that are affected by a given node modification
614  template < typename STRUCTURAL_CONSTRAINT,
615  typename GRAPH_CHANGES_GENERATOR,
616  template < typename >
617  class ALLOC >
618  void GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
619  GRAPH_CHANGES_GENERATOR,
620  ALLOC >::
621  findLegalChangesNeedingUpdate__(Set< std::size_t >& changes_to_recompute,
622  const NodeId target_node) {
623  const HashTable< std::size_t, Size >& changes
624  = change_queue_per_node__[target_node].allValues();
625  for (auto iter = changes.cbeginSafe(); iter != changes.cendSafe(); ++iter) {
626  if (!changes_to_recompute.exists(iter.key())) {
627  if (isChangeValid__(iter.key())) {
628  changes_to_recompute.insert(iter.key());
629  } else {
630  invalidateChange__(iter.key());
631  }
632  }
633  }
634  }
635 
636 
637  /// perform the necessary updates of the scores
638  template < typename STRUCTURAL_CONSTRAINT,
639  typename GRAPH_CHANGES_GENERATOR,
640  template < typename >
641  class ALLOC >
642  void GraphChangesSelector4DiGraph<
643  STRUCTURAL_CONSTRAINT,
644  GRAPH_CHANGES_GENERATOR,
645  ALLOC >::updateScores__(const Set< std::size_t >& changes_to_recompute) {
646  Set< NodeId > modified_nodes(changes_to_recompute.size());
647 
648  for (const auto change_index: changes_to_recompute) {
649  const GraphChange& change = changes__[change_index];
650 
651  switch (change.type()) {
652  case GraphChangeType::ARC_ADDITION: {
653  // add the arc
654  auto& parents = parents__[change.node2()];
655  parents.push_back(change.node1());
656  const double delta = score__->score(change.node2(), parents)
657  - node_current_scores__[change.node2()];
658  parents.pop_back();
659 
660  // update the score
661  change_scores__[change_index].second = delta;
662 
663  // update the head queue
664  change_queue_per_node__[change.node2()].setPriority(change_index,
665  delta);
666  // indicate which queue was modified
667  modified_nodes.insert(change.node2());
668  } break;
669 
670  case GraphChangeType::ARC_DELETION: {
671  // remove the arc
672  auto& parents = parents__[change.node2()];
673  for (auto& par: parents) {
674  if (par == change.node1()) {
675  par = *(parents.rbegin());
676  parents.pop_back();
677  break;
678  }
679  }
680  const double delta = score__->score(change.node2(), parents)
681  - node_current_scores__[change.node2()];
682  parents.push_back(change.node1());
683 
684  // update the score
685  change_scores__[change_index].second = delta;
686 
687  // update the head queue
688  change_queue_per_node__[change.node2()].setPriority(change_index,
689  delta);
690  // indicate which queue was modified
691  modified_nodes.insert(change.node2());
692  } break;
693 
694  case GraphChangeType::ARC_REVERSAL: {
695  // remove arc ( node1 -> node2 )
696  auto& parents2 = parents__[change.node2()];
697  for (auto& par: parents2) {
698  if (par == change.node1()) {
699  par = *(parents2.rbegin());
700  parents2.pop_back();
701  break;
702  }
703  }
704 
705  const double delta2 = score__->score(change.node2(), parents2)
706  - node_current_scores__[change.node2()];
707  parents2.push_back(change.node1());
708 
709  // add arc ( node2 -> node1 )
710  auto& parents1 = parents__[change.node1()];
711  parents1.push_back(change.node2());
712  const double delta1 = score__->score(change.node1(), parents1)
713  - node_current_scores__[change.node1()];
714  parents1.pop_back();
715 
716  // update the scores
717  change_scores__[change_index].first = delta1;
718  change_scores__[change_index].second = delta2;
719 
720  // update the queues
721  const double delta = delta1 + delta2;
722  change_queue_per_node__[change.node1()].setPriority(change_index,
723  delta);
724  change_queue_per_node__[change.node2()].setPriority(change_index,
725  delta);
726 
727  // indicate which queues were modified
728  modified_nodes.insert(change.node1());
729  modified_nodes.insert(change.node2());
730  } break;
731 
732  default: {
733  GUM_ERROR(NotImplementedYet,
734  "Method updateScores__ of GraphChangesSelector4DiGraph "
735  << "does not handle yet graph change of type "
736  << change.type());
737  }
738  }
739  }
740 
741  // update the node queue
742  for (const auto node: modified_nodes) {
743  node_queue__.setPriority(node,
744  change_queue_per_node__[node].empty()
745  ? std::numeric_limits< double >::min()
746  : change_queue_per_node__[node].topPriority());
747  }
748  }
749 
750 
751  /// get from the graph change generator a new set of changes
752  template < typename STRUCTURAL_CONSTRAINT,
753  typename GRAPH_CHANGES_GENERATOR,
754  template < typename >
755  class ALLOC >
756  void GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
757  GRAPH_CHANGES_GENERATOR,
758  ALLOC >::getNewChanges__() {
759  // ask the graph change generator for all its available changes
760  for (const auto& change: *changes_generator__) {
761  // check that the change does not already exist
762  if (!changes__.exists(change)) {
763  // add the new change. To make the addition simple, we put the new
764  // change into the illegal changes set. Afterwards, the applyChange
765  // function will put the legal changes again into the queues
766  illegal_changes__.insert(changes__.size());
767  changes__ << change;
768  change_scores__.push_back(
769  std::pair< double, double >(std::numeric_limits< double >::min(),
770  std::numeric_limits< double >::min()));
771  }
772  }
773 
774  // indicate to the generator that we have finished retrieving its changes
775  changes_generator__->notifyGetCompleted();
776  }
777 
778 
779  /// indicate to the selector that its best score has been applied
780  template < typename STRUCTURAL_CONSTRAINT,
781  typename GRAPH_CHANGES_GENERATOR,
782  template < typename >
783  class ALLOC >
784  void GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
785  GRAPH_CHANGES_GENERATOR,
786  ALLOC >::applyChange(const GraphChange&
787  change) {
788  // first, we get the index of the change
789  const std::size_t change_index = changes__.pos(change);
790 
791  // perform the change
792  Set< std::size_t > changes_to_recompute;
793  switch (change.type()) {
794  case GraphChangeType::ARC_ADDITION: {
795  // update the current score
796  node_current_scores__[change.node2()]
797  += change_scores__[change_index].second;
798  parents__[change.node2()].push_back(change.node1());
799 
800  // inform the constraint that the graph has been modified
801  constraint__->modifyGraph(static_cast< const ArcAddition& >(change));
802  if (reinterpret_cast< STRUCTURAL_CONSTRAINT* >(
803  &(changes_generator__->constraint()))
804  != constraint__) {
805  changes_generator__->constraint().modifyGraph(
806  static_cast< const ArcAddition& >(change));
807  }
808 
809  // get new possible changes from the graph change generator
810  // warning: put the next 3 lines before calling illegal2LegalChanges__
811  changes_generator__->modifyGraph(
812  static_cast< const ArcAddition& >(change));
813  getNewChanges__();
814 
815  // check whether some illegal changes can be put into the valid queues
816  illegal2LegalChanges__(changes_to_recompute);
817  invalidateChange__(change_index);
818  findLegalChangesNeedingUpdate__(changes_to_recompute, change.node2());
819  updateScores__(changes_to_recompute);
820  } break;
821 
822  case GraphChangeType::ARC_DELETION: {
823  // update the current score
824  node_current_scores__[change.node2()]
825  += change_scores__[change_index].second;
826  auto& parents = parents__[change.node2()];
827  for (auto& par: parents) {
828  if (par == change.node1()) {
829  par = *(parents.rbegin());
830  parents.pop_back();
831  break;
832  }
833  }
834 
835  // inform the constraint that the graph has been modified
836  constraint__->modifyGraph(static_cast< const ArcDeletion& >(change));
837  if (reinterpret_cast< STRUCTURAL_CONSTRAINT* >(
838  &(changes_generator__->constraint()))
839  != constraint__) {
840  changes_generator__->constraint().modifyGraph(
841  static_cast< const ArcDeletion& >(change));
842  }
843 
844  // get new possible changes from the graph change generator
845  // warning: put the next 3 lines before calling illegal2LegalChanges__
846  changes_generator__->modifyGraph(
847  static_cast< const ArcDeletion& >(change));
848  getNewChanges__();
849 
850  // check whether some illegal changes can be put into the valid queues
851  illegal2LegalChanges__(changes_to_recompute);
852  invalidateChange__(change_index);
853  findLegalChangesNeedingUpdate__(changes_to_recompute, change.node2());
854  updateScores__(changes_to_recompute);
855  } break;
856 
857  case GraphChangeType::ARC_REVERSAL: {
858  // update the current score
859  node_current_scores__[change.node1()]
860  += change_scores__[change_index].first;
861  node_current_scores__[change.node2()]
862  += change_scores__[change_index].second;
863  parents__[change.node1()].push_back(change.node2());
864  auto& parents = parents__[change.node2()];
865  for (auto& par: parents) {
866  if (par == change.node1()) {
867  par = *(parents.rbegin());
868  parents.pop_back();
869  break;
870  }
871  }
872 
873  // inform the constraint that the graph has been modified
874  constraint__->modifyGraph(static_cast< const ArcReversal& >(change));
875  if (reinterpret_cast< STRUCTURAL_CONSTRAINT* >(
876  &(changes_generator__->constraint()))
877  != constraint__) {
878  changes_generator__->constraint().modifyGraph(
879  static_cast< const ArcReversal& >(change));
880  }
881 
882  // get new possible changes from the graph change generator
883  // warning: put the next 3 lines before calling illegal2LegalChanges__
884  changes_generator__->modifyGraph(
885  static_cast< const ArcReversal& >(change));
886  getNewChanges__();
887 
888  // check whether some illegal changes can be put into the valid queues
889  illegal2LegalChanges__(changes_to_recompute);
890  invalidateChange__(change_index);
891  findLegalChangesNeedingUpdate__(changes_to_recompute, change.node1());
892  findLegalChangesNeedingUpdate__(changes_to_recompute, change.node2());
893  updateScores__(changes_to_recompute);
894  } break;
895 
896  default:
897  GUM_ERROR(NotImplementedYet,
898  "Method applyChange of GraphChangesSelector4DiGraph "
899  << "does not handle yet graph change of type "
900  << change.type());
901  }
902 
903  queues_valid__ = false;
904  }
905 
906 
907  /// applies several changes at a time
908  template < typename STRUCTURAL_CONSTRAINT,
909  typename GRAPH_CHANGES_GENERATOR,
910  template < typename >
911  class ALLOC >
912  void GraphChangesSelector4DiGraph<
913  STRUCTURAL_CONSTRAINT,
914  GRAPH_CHANGES_GENERATOR,
915  ALLOC >::applyChangeWithoutScoreUpdate(const GraphChange& change) {
916  // first, we get the index of the change
917  const std::size_t change_index = changes__.pos(change);
918 
919  // perform the change
920  switch (change.type()) {
921  case GraphChangeType::ARC_ADDITION: {
922  // update the current score
923  node_current_scores__[change.node2()]
924  += change_scores__[change_index].second;
925  parents__[change.node2()].push_back(change.node1());
926 
927  // inform the constraint that the graph has been modified
928  constraint__->modifyGraph(static_cast< const ArcAddition& >(change));
929  if (reinterpret_cast< STRUCTURAL_CONSTRAINT* >(
930  &(changes_generator__->constraint()))
931  != constraint__) {
932  changes_generator__->constraint().modifyGraph(
933  static_cast< const ArcAddition& >(change));
934  }
935 
936  // get new possible changes from the graph change generator
937  // warning: put the next 3 lines before calling illegal2LegalChanges__
938  changes_generator__->modifyGraph(
939  static_cast< const ArcAddition& >(change));
940  getNewChanges__();
941 
942  // indicate that we have just applied the change
943  invalidateChange__(change_index);
944 
945  // indicate that the queue to which the change belongs needs be
946  // updated
947  queues_to_update__.insert(change.node2());
948  } break;
949 
950  case GraphChangeType::ARC_DELETION: {
951  // update the current score
952  node_current_scores__[change.node2()]
953  += change_scores__[change_index].second;
954  auto& parents = parents__[change.node2()];
955  for (auto& par: parents) {
956  if (par == change.node1()) {
957  par = *(parents.rbegin());
958  parents.pop_back();
959  break;
960  }
961  }
962 
963  // inform the constraint that the graph has been modified
964  constraint__->modifyGraph(static_cast< const ArcDeletion& >(change));
965  if (reinterpret_cast< STRUCTURAL_CONSTRAINT* >(
966  &(changes_generator__->constraint()))
967  != constraint__) {
968  changes_generator__->constraint().modifyGraph(
969  static_cast< const ArcDeletion& >(change));
970  }
971 
972  // get new possible changes from the graph change generator
973  // warning: put the next 3 lines before calling illegal2LegalChanges__
974  changes_generator__->modifyGraph(
975  static_cast< const ArcDeletion& >(change));
976  getNewChanges__();
977 
978  // indicate that we have just applied the change
979  invalidateChange__(change_index);
980 
981  // indicate that the queue to which the change belongs needs be
982  // updated
983  queues_to_update__.insert(change.node2());
984  } break;
985 
986  case GraphChangeType::ARC_REVERSAL: {
987  // update the current score
988  node_current_scores__[change.node1()]
989  += change_scores__[change_index].first;
990  node_current_scores__[change.node2()]
991  += change_scores__[change_index].second;
992  parents__[change.node1()].push_back(change.node2());
993  auto& parents = parents__[change.node2()];
994  for (auto& par: parents) {
995  if (par == change.node1()) {
996  par = *(parents.rbegin());
997  parents.pop_back();
998  break;
999  }
1000  }
1001 
1002  // inform the constraint that the graph has been modified
1003  constraint__->modifyGraph(static_cast< const ArcReversal& >(change));
1004  if (reinterpret_cast< STRUCTURAL_CONSTRAINT* >(
1005  &(changes_generator__->constraint()))
1006  != constraint__) {
1007  changes_generator__->constraint().modifyGraph(
1008  static_cast< const ArcReversal& >(change));
1009  }
1010 
1011  // get new possible changes from the graph change generator
1012  // warning: put the next 3 lines before calling illegal2LegalChanges__
1013  changes_generator__->modifyGraph(
1014  static_cast< const ArcReversal& >(change));
1015  getNewChanges__();
1016 
1017  // indicate that we have just applied the change
1018  invalidateChange__(change_index);
1019 
1020  // indicate that the queue to which the change belongs needs be
1021  // updated
1022  queues_to_update__.insert(change.node1());
1023  queues_to_update__.insert(change.node2());
1024  } break;
1025 
1026  default:
1027  GUM_ERROR(NotImplementedYet,
1028  "Method applyChangeWithoutScoreUpdate of "
1029  << "GraphChangesSelector4DiGraph "
1030  << "does not handle yet graph change of type "
1031  << change.type());
1032  }
1033  }
1034 
1035 
1036  /// applies several changes at a time
1037  template < typename STRUCTURAL_CONSTRAINT,
1038  typename GRAPH_CHANGES_GENERATOR,
1039  template < typename >
1040  class ALLOC >
1041  void GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
1042  GRAPH_CHANGES_GENERATOR,
1043  ALLOC >::updateScoresAfterAppliedChanges() {
1044  // determine which changes in the illegal set are now legal
1045  Set< std::size_t > new_legal_changes;
1046  for (auto iter = illegal_changes__.beginSafe();
1047  iter != illegal_changes__.endSafe();
1048  ++iter) {
1049  if (isChangeValid__(*iter)) {
1050  new_legal_changes.insert(*iter);
1051  illegal_changes__.erase(iter);
1052  }
1053  }
1054 
1055  // update the scores that need be updated
1056  Set< std::size_t > changes_to_recompute;
1057  for (const auto& node: queues_to_update__) {
1058  findLegalChangesNeedingUpdate__(changes_to_recompute, node);
1059  }
1060  queues_to_update__.clear();
1061 
1062  // put the previously illegal changes that are now legal into their queues
1063  for (const auto change_index: new_legal_changes) {
1064  const GraphChange& change = changes__[change_index];
1065  if (change.type() == GraphChangeType::ARC_REVERSAL) {
1066  change_queue_per_node__[change.node1()].insert(
1067  change_index,
1068  std::numeric_limits< double >::min());
1069  }
1070  change_queue_per_node__[change.node2()].insert(
1071  change_index,
1072  std::numeric_limits< double >::min());
1073 
1074  changes_to_recompute.insert(change_index);
1075  }
1076 
1077  // compute the scores that we need
1078  updateScores__(changes_to_recompute);
1079 
1080  queues_valid__ = false;
1081  }
1082 
1083 
1084  /// returns the set of queues sorted by decreasing top priority
1085  template < typename STRUCTURAL_CONSTRAINT,
1086  typename GRAPH_CHANGES_GENERATOR,
1087  template < typename >
1088  class ALLOC >
1089  std::vector< std::pair< NodeId, double > >
1090  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
1091  GRAPH_CHANGES_GENERATOR,
1092  ALLOC >::nodesSortedByBestScore() const {
1093  std::vector< std::pair< NodeId, double > > result(node_queue__.size());
1094  for (std::size_t i = std::size_t(0); i < node_queue__.size(); ++i) {
1095  result[i].first = node_queue__[i];
1096  result[i].second = node_queue__.priorityByPos(i);
1097  }
1098 
1099  std::sort(result.begin(),
1100  result.end(),
1101  [](const std::pair< NodeId, double >& a,
1102  const std::pair< NodeId, double >& b) -> bool {
1103  return a.second > b.second;
1104  });
1105 
1106  return result;
1107  }
1108 
1109 
1110  /// returns the set of queues sorted by decreasing top priority
1111  template < typename STRUCTURAL_CONSTRAINT,
1112  typename GRAPH_CHANGES_GENERATOR,
1113  template < typename >
1114  class ALLOC >
1115  std::vector< std::pair< NodeId, double > >
1116  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
1117  GRAPH_CHANGES_GENERATOR,
1118  ALLOC >::nodesUnsortedWithScore() const {
1119  std::vector< std::pair< NodeId, double > > result(node_queue__.size());
1120  for (std::size_t i = std::size_t(0); i < node_queue__.size(); ++i) {
1121  result[i].first = node_queue__[i];
1122  result[i].second = node_queue__.priorityByPos(i);
1123  }
1124 
1125  return result;
1126  }
1127 
1128 
1129  /// returns the generator used by the selector
1130  template < typename STRUCTURAL_CONSTRAINT,
1131  typename GRAPH_CHANGES_GENERATOR,
1132  template < typename >
1133  class ALLOC >
1134  INLINE typename GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
1135  GRAPH_CHANGES_GENERATOR,
1136  ALLOC >::GeneratorType&
1137  GraphChangesSelector4DiGraph< STRUCTURAL_CONSTRAINT,
1138  GRAPH_CHANGES_GENERATOR,
1139  ALLOC >::graphChangeGenerator()
1140  const noexcept {
1141  return *changes_generator__;
1142  }
1143 
1144 
1145  } /* namespace learning */
1146 
1147 } /* namespace gum */
1148 
1149 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
gum::Set::emplace
INLINE void emplace(Args &&... args)
Definition: set_tpl.h:669
gum::learning::genericBNLearner::Database::Database
Database(const std::string &filename, const BayesNet< GUM_SCALAR > &bn, const std::vector< std::string > &missing_symbols)
Definition: genericBNLearner_tpl.h:31
aGrUM 0.20.2
Sun May 2 2021 12:35:42
© PHW&CG&others - 2021
DoXyGeN 1.8.13