aGrUM  0.14.2
simplicialSet.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
25 #include <agrum/core/math/math.h>
28 #include <limits>
29 #include <limits>
30 #include <sstream>
31 #include <sstream>
32 
33 #ifdef GUM_NO_INLINE
35 #endif // GUM_NO_INLINE
36 
37 #ifndef DOXYGEN_SHOULD_SKIP_THIS
38 
39 namespace gum {
40 
41  /* ===========================================================================
42  */
43  /* ===========================================================================
44  */
45  /* === CLASS FOR RETRIEVING SIMPLICIAL, ALMOST AND QUASI SIMPLICIAL NODES ===
46  */
47  /* ===========================================================================
48  */
49  /* ===========================================================================
50  */
51 
53  SimplicialSet::SimplicialSet(UndiGraph* graph,
54  const NodeProperty< double >* log_domain_sizes,
55  NodeProperty< double >* log_weights,
56  double theRatio,
57  double theThreshold) :
58  __graph(graph != nullptr
59  ? graph
60  : GUM_ERROR_IN_EXPR(OperationNotAllowed,
61  "SimplicialSet requires a valid graph")),
62  __log_weights(log_weights != nullptr
63  ? log_weights
64  : GUM_ERROR_IN_EXPR(OperationNotAllowed,
65  "SimplicialSet "
66  "requires non-null log weights")),
67  __log_domain_sizes(log_domain_sizes != nullptr
68  ? log_domain_sizes
69  : GUM_ERROR_IN_EXPR(OperationNotAllowed,
70  "SimplicialSet "
71  "requires non-null domain sizes")),
72  __simplicial_nodes(std::less< double >(), __graph->size()),
73  __almost_simplicial_nodes(std::less< double >(), __graph->size()),
74  __quasi_simplicial_nodes(std::less< double >(), __graph->size()),
75  __containing_list(__graph->size()),
76  __nb_triangles(__graph->size() * __graph->size() / 2),
77  __nb_adjacent_neighbours(__graph->size()), __quasi_ratio(theRatio),
78  __log_threshold(std::log(1 + theThreshold)) {
79  if (graph != nullptr) {
80  // for debugging purposes
81  GUM_CONSTRUCTOR(SimplicialSet);
82  }
83 
84  // end of initialization: compute __nb_triangles, __nb_adjacent_neighbours,
85  // etc
86  __initialize();
87  }
88 
90  SimplicialSet::SimplicialSet(const SimplicialSet& from,
91  UndiGraph* graph,
92  const NodeProperty< double >* log_domain_sizes,
93  NodeProperty< double >* log_weights,
94  bool avoid_check) :
95  __graph(graph != nullptr
96  ? graph
97  : GUM_ERROR_IN_EXPR(OperationNotAllowed,
98  "SimplicialSet requires a valid graph")),
99  __log_weights(log_weights != nullptr
100  ? log_weights
101  : GUM_ERROR_IN_EXPR(OperationNotAllowed,
102  "SimplicialSet "
103  "requires non-null log weights")),
104  __log_domain_sizes(
105  log_domain_sizes != nullptr
106  ? log_domain_sizes
107  : GUM_ERROR_IN_EXPR(OperationNotAllowed,
108  "SimplicialSet "
109  "requires non-null domain sizes")) {
110  if (!avoid_check) {
111  // check whether the graph, the log weights and the log_modalities
112  // are similar to those of from
113  if ((__graph == from.__graph) || (__log_weights == from.__log_weights)
114  || (*__graph != *from.__graph)
115  || (*__log_domain_sizes != *from.__log_domain_sizes)) {
116  GUM_ERROR(OperationNotAllowed,
117  "SimplicialSet requires fresh copies of "
118  "graph, log weights and log domain sizes");
119  }
120  }
121 
122  // copy the current content of from
123  *__log_weights = *from.__log_weights;
124  __simplicial_nodes = from.__simplicial_nodes;
125  __almost_simplicial_nodes = from.__almost_simplicial_nodes;
126  __quasi_simplicial_nodes = from.__quasi_simplicial_nodes;
127  __containing_list = from.__containing_list;
128  __nb_triangles = from.__nb_triangles;
129  __nb_adjacent_neighbours = from.__nb_adjacent_neighbours;
130  __log_tree_width = from.__log_tree_width;
131  __quasi_ratio = from.__quasi_ratio;
132  __log_threshold = from.__log_threshold;
133  __changed_status = from.__changed_status;
134  __we_want_fill_ins = from.__we_want_fill_ins;
135  __fill_ins_list = from.__fill_ins_list;
136 
137  // for debugging purposes
138  GUM_CONS_CPY(SimplicialSet);
139  }
140 
142  SimplicialSet::SimplicialSet(SimplicialSet&& from) :
143  __graph(from.__graph), __log_weights(from.__log_weights),
144  __log_domain_sizes(from.__log_domain_sizes),
145  __simplicial_nodes(std::move(from.__simplicial_nodes)),
146  __almost_simplicial_nodes(std::move(from.__almost_simplicial_nodes)),
147  __quasi_simplicial_nodes(std::move(from.__quasi_simplicial_nodes)),
148  __containing_list(std::move(from.__containing_list)),
149  __nb_triangles(std::move(from.__nb_triangles)),
150  __nb_adjacent_neighbours(std::move(from.__nb_adjacent_neighbours)),
151  __log_tree_width(from.__log_tree_width), __quasi_ratio(from.__quasi_ratio),
152  __log_threshold(from.__log_threshold),
153  __changed_status(std::move(from.__changed_status)),
154  __we_want_fill_ins(from.__we_want_fill_ins),
155  __fill_ins_list(std::move(from.__fill_ins_list)) {
156  // for debugging purposes
157  GUM_CONS_MOV(SimplicialSet);
158  }
159 
162  // for debugging purposes
163  GUM_DESTRUCTOR(SimplicialSet);
164  }
165 
167  void SimplicialSet::makeClique(const NodeId id) {
168  // first, update the list to which belongs the node
169  if (__changed_status.contains(id)) __updateList(id);
170 
171  // to make id be a clique, we may have to add edges. Hence, this will create
172  // new triangles and we should update the number of triangles passing
173  // through the new edges. Moreover, we should also update the number of
174  // adjacent neighbors for each node involved in these new triangles as well
175  // as the new weights of the nodes. Finally, we should update the
176  // simplicial,
177  // almost and quasi simplicial lists. However, to optimize the code, we use
178  // a lazy list update: we just update a hashtable indicating whether a list
179  // update should be performed for a given node. This enables performing the
180  // updates only when necessary. if the node is known to be simplicial, there
181  // is nothing to do
182  if (__simplicial_nodes.contains(id)) {
183  return;
184  } else if (__almost_simplicial_nodes.contains(id)) {
185  // get the neighbor that does not form a clique with the other neighbors
186  // recall that id is an almost simplicial node if there exists a node,
187  // say Y, such that, after deleting Y, id and its adjacent nodes form a
188  // clique.
189  const NodeSet& nei = __graph->neighbours(id);
190  Size nb_adj = nei.size();
191  Size nb = __nb_adjacent_neighbours[id];
192 
193  // nb_almost = the number of edges that should link the neighbors of
194  // node id, after node Y mentioned above has been removed. Recall that
195  // these neighbors and id form a clique. Hence this corresponds to the
196  // number of triangles involving id and 2 of its neighbors, after node
197  // Y has been removed.
198  Size nb_almost = ((nb_adj - 1) * (nb_adj - 2)) / 2;
199  NodeId node1 = 0;
200 
201  for (const auto current_node : nei) {
202  if (nb_almost == nb - __nb_triangles[Edge(current_node, id)]) {
203  // we found the neighbor we were looking for: nb = the number of
204  // pairs of neighbors of id that are adjacent. In other words, this
205  // is the number of triangles involving node id. Now remove from it
206  // the
207  // triangles involving edge (id,node1), and you get the number of
208  // triangles involving id, but not node1. If id is almost simplicial,
209  // then this number should be equal to the set of combinations of
210  // all the possible pairs of neighbors of id except node1, hence
211  // to nb_almost.
212  node1 = current_node;
213  break;
214  }
215  }
216 
217  double log_domain_size_node1 = (*__log_domain_sizes)[node1];
218  double& __log_weights_node1 = (*__log_weights)[node1];
219 
220  // now, to make a clique between id and its neighbors, there just remains
221  // to add the missing edges between node1 and the other neighbors of id.
222 
223  // nb_n1 will contain the number of pairs of neighbors of node1 that
224  // will be adjacent after the clique is constructed but that
225  // are not yet adjacent
226  unsigned int nb_n1 = 0;
227 
228  // update the number of triangles of the edges and keep track of the
229  // nodes involved.
230  for (const auto node2 : nei) {
231  if ((node2 != node1) && !__graph->existsEdge(node1, node2)) {
232  // add the edge
233  const Edge e1_2(node1, node2);
234  __graph->addEdge(node1, node2);
235 
236  if (__we_want_fill_ins) __fill_ins_list.insert(e1_2);
237 
238  if (!__changed_status.contains(node2)) __changed_status.insert(node2);
239 
240  __log_weights_node1 += (*__log_domain_sizes)[node2];
241  (*__log_weights)[node2] += log_domain_size_node1;
242  __nb_triangles.insert(e1_2, 0);
243 
244  // nb_n2 will contain the number of pairs of neighbors of node2 that
245  // will be adjacent after the clique is constructed but that
246  // are not yet adjacent
247  unsigned int nb_n2 = 0;
248 
249  // for all common neighbors of node1 and node2, update the number of
250  // triangles as well as the number of adjacent neighbors
251  if (__graph->neighbours(node1).size()
252  <= __graph->neighbours(node2).size()) {
253  for (const auto neighbor : __graph->neighbours(node1)) {
254  if (__graph->existsEdge(neighbor, node2)) {
255  // here iter->other (node1) is a neighbor of node1 and node2
256  // hence there is a new triangle to be taken into account:
257  // that between node1, node2 and iterEdge->other( node1 )
258  ++nb_n1;
259  ++nb_n2;
260  ++__nb_adjacent_neighbours[neighbor];
261  ++__nb_triangles[Edge(node1, neighbor)];
262  ++__nb_triangles[Edge(node2, neighbor)];
263 
264  if (!__changed_status.contains(neighbor))
265  __changed_status.insert(neighbor);
266  }
267  }
268  } else {
269  for (const auto neighbor : __graph->neighbours(node2)) {
270  if (__graph->existsEdge(neighbor, node1)) {
271  // here iter->other (node2) is a neighbor of node1 and node2
272  // hence there is a new triangle to be taken into account:
273  // that between node1, node2 and iterEdge->other( node2 )
274  ++nb_n1;
275  ++nb_n2;
276  ++__nb_adjacent_neighbours[neighbor];
277  ++__nb_triangles[Edge(node2, neighbor)];
278  ++__nb_triangles[Edge(node1, neighbor)];
279 
280  if (!__changed_status.contains(neighbor))
281  __changed_status.insert(neighbor);
282  }
283  }
284  }
285 
286  __nb_adjacent_neighbours[node2] += nb_n2;
287  __nb_triangles[e1_2] += nb_n2;
288  }
289  }
290 
291  if (!__changed_status.contains(node1)) __changed_status.insert(node1);
292 
293  __nb_adjacent_neighbours[node1] += nb_n1;
294  } else {
295  // here, id is neither a simplicial node nor an almost simplicial node
296 
297  // update the number of triangles of the edges and keep track of the
298  // nodes involved.
299  const NodeSet& nei = __graph->neighbours(id);
300 
301  for (auto iter1 = nei.begin(); iter1 != nei.end(); ++iter1) {
302  NodeId node1 = *iter1;
303  double log_domain_size_node1 = (*__log_domain_sizes)[node1];
304  double& __log_weights_node1 = (*__log_weights)[node1];
305  bool node1_status = false;
306  unsigned int nb_n1 = 0;
307 
308  auto iterEdge2 = iter1;
309 
310  for (++iterEdge2; iterEdge2 != nei.end(); ++iterEdge2) {
311  const NodeId node2 = *iterEdge2;
312  const Edge e1_2(node1, node2);
313 
314  if (!__graph->existsEdge(e1_2)) {
315  // add the edge
316  __graph->addEdge(node1, node2);
317 
318  if (__we_want_fill_ins) __fill_ins_list.insert(e1_2);
319 
320  if (!__changed_status.contains(node2)) __changed_status.insert(node2);
321 
322  node1_status = true;
323  __log_weights_node1 += (*__log_domain_sizes)[node2];
324  (*__log_weights)[node2] += log_domain_size_node1;
325  __nb_triangles.insert(e1_2, 0);
326 
327  // for all common neighbors of node1 and node2, update the number
328  // of triangles as well as the number of adjacent neighbors
329  unsigned int nb_n2 = 0;
330 
331  if (__graph->neighbours(node1).size()
332  <= __graph->neighbours(node2).size()) {
333  for (const auto neighbor : __graph->neighbours(node1))
334  if (__graph->existsEdge(neighbor, node2)) {
335  // here iterEdge->other (node1) is a neighbor of
336  // both node1 and node2
337  ++nb_n1;
338  ++nb_n2;
339  ++__nb_adjacent_neighbours[neighbor];
340  ++__nb_triangles[Edge(node1, neighbor)];
341  ++__nb_triangles[Edge(node2, neighbor)];
342 
343  if (!__changed_status.contains(neighbor))
344  __changed_status.insert(neighbor);
345  }
346  } else {
347  for (const auto neighbor : __graph->neighbours(node2)) {
348  if (__graph->existsEdge(neighbor, node1)) {
349  // here iterEdge->other (node2) is a neighbor of
350  // both node1 and node2
351  ++nb_n1;
352  ++nb_n2;
353  ++__nb_adjacent_neighbours[neighbor];
354  ++__nb_triangles[Edge(node2, neighbor)];
355  ++__nb_triangles[Edge(node1, neighbor)];
356 
357  if (!__changed_status.contains(neighbor))
358  __changed_status.insert(neighbor);
359  }
360  }
361  }
362 
363  __nb_adjacent_neighbours[node2] += nb_n2;
364  __nb_triangles[e1_2] += nb_n2;
365  }
366  }
367 
368  __nb_adjacent_neighbours[node1] += nb_n1;
369 
370  if (node1_status && !__changed_status.contains(node1))
371  __changed_status.insert(node1);
372  }
373  }
374 
375  // update the __changed_status of node id as well as its containing list
376  if (!__simplicial_nodes.contains(id)) {
377  if (__changed_status.contains(id)) __changed_status.erase(id);
378 
379  switch (__containing_list[id]) {
380  case __Belong::ALMOST_SIMPLICIAL:
381  __almost_simplicial_nodes.erase(id);
382  break;
383 
384  case __Belong::QUASI_SIMPLICIAL: __quasi_simplicial_nodes.erase(id); break;
385 
386  default: break;
387  }
388 
389  __simplicial_nodes.insert(id, (*__log_weights)[id]);
390  __containing_list[id] = __Belong::SIMPLICIAL;
391  } else {
392  if (__changed_status.contains(id)) { __changed_status.erase(id); }
393  }
394  }
395 
397  void SimplicialSet::eraseClique(const NodeId id) {
398  // check if the node we wish to remove actually belongs to the __graph
399  if (!__graph->exists(id)) {
400  GUM_ERROR(NotFound, "Node " << id << " does not belong to the graph");
401  }
402 
403  const NodeSet nei = __graph->neighbours(id);
404 
405  // check that node id is actually a clique
406  Size nb_adj = nei.size();
407  if (__nb_adjacent_neighbours[id] != (nb_adj * (nb_adj - 1)) / 2) {
408  GUM_ERROR(NotFound, "Node " << id << " is not a clique");
409  }
410 
411  // remove the node and its adjacent edges
412  double log_domain_size_id = (*__log_domain_sizes)[id];
413  for (auto iter1 = nei.begin(); iter1 != nei.end(); ++iter1) {
414  const NodeId node1 = *iter1;
415  __nb_adjacent_neighbours[node1] -= nb_adj - 1;
416  (*__log_weights)[node1] -= log_domain_size_id;
417 
418  if (!__changed_status.contains(node1)) __changed_status.insert(node1);
419 
420  __nb_triangles.erase(Edge(node1, id));
421 
422  auto iter2 = iter1;
423  for (++iter2; iter2 != nei.end(); ++iter2)
424  --__nb_triangles[Edge(node1, *iter2)];
425  }
426 
427  __log_tree_width = std::max(__log_tree_width, (*__log_weights)[id]);
428 
429  switch (__containing_list[id]) {
430  case __Belong::SIMPLICIAL: __simplicial_nodes.erase(id); break;
431 
432  case __Belong::ALMOST_SIMPLICIAL: __almost_simplicial_nodes.erase(id); break;
433 
434  case __Belong::QUASI_SIMPLICIAL: __quasi_simplicial_nodes.erase(id); break;
435 
436  default: break;
437  }
438 
439  __nb_adjacent_neighbours.erase(id);
440  __containing_list.erase(id);
441  __changed_status.erase(id);
442  __graph->eraseNode(id);
443  __log_weights->erase(id);
444  }
445 
447  void SimplicialSet::eraseNode(const NodeId id) {
448  // check if the node we wish to remove actually belongs to the __graph
449  if (!__graph->exists(id)) {
450  GUM_ERROR(NotFound, "Node " << id << " does not belong to the graph");
451  }
452 
453  // remove the node and its adjacent edges
454  const NodeSet& nei = __graph->neighbours(id);
455 
456  for (auto iter = nei.beginSafe(); iter != nei.endSafe();
457  ++iter) // safe iterator needed here for deletions
458  eraseEdge(Edge(*iter, id));
459 
460  switch (__containing_list[id]) {
461  case __Belong::SIMPLICIAL: __simplicial_nodes.erase(id); break;
462 
463  case __Belong::ALMOST_SIMPLICIAL: __almost_simplicial_nodes.erase(id); break;
464 
465  case __Belong::QUASI_SIMPLICIAL: __quasi_simplicial_nodes.erase(id); break;
466 
467  default: break;
468  }
469 
470  __nb_adjacent_neighbours.erase(id);
471  __containing_list.erase(id);
472  __changed_status.erase(id);
473  __graph->eraseNode(id);
474  __log_weights->erase(id);
475  }
476 
478  void SimplicialSet::eraseEdge(const Edge& edge) {
479  // check if the edge we wish to remove actually belongs to the __graph
480  if (!__graph->existsEdge(edge)) {
481  GUM_ERROR(NotFound, "Edge " << edge << " does not belong to the graph");
482  }
483 
484  // get the extremal nodes of the edge
485  const NodeId node1 = edge.first();
486  const NodeId node2 = edge.second();
487 
488  // remove the edge
489  __graph->eraseEdge(edge);
490  __nb_triangles.erase(edge);
491 
492  // update the __log_weights of both nodes
493  (*__log_weights)[node1] -= (*__log_domain_sizes)[node2];
494  (*__log_weights)[node2] -= (*__log_domain_sizes)[node1];
495 
496  // update the number of triangles and the adjacent neighbors
497  unsigned int nb_neigh_n1_n2 = 0;
498  for (const auto othernode : __graph->neighbours(node1)) {
499  if (__graph->existsEdge(node2, othernode)) {
500  // udate the number of triangles passing through the egdes of the
501  // __graph
502  --__nb_triangles[Edge(node1, othernode)];
503  --__nb_triangles[Edge(node2, othernode)];
504  // update the neighbors
505  ++nb_neigh_n1_n2;
506  --__nb_adjacent_neighbours[othernode];
507 
508  if (!__changed_status.contains(othernode))
509  __changed_status.insert(othernode);
510  }
511  }
512 
513  __nb_adjacent_neighbours[node1] -= nb_neigh_n1_n2;
514  __nb_adjacent_neighbours[node2] -= nb_neigh_n1_n2;
515 
516  if (!__changed_status.contains(node1)) __changed_status.insert(node1);
517  if (!__changed_status.contains(node2)) __changed_status.insert(node2);
518  }
519 
521  void SimplicialSet::addEdge(NodeId node1, NodeId node2) {
522  // if the edge already exists, do nothing
523  const Edge edge(node1, node2);
524 
525  if (__graph->existsEdge(edge)) return;
526 
527  // update the __log_weights of both nodes
528  (*__log_weights)[node1] += (*__log_domain_sizes)[node2];
529  (*__log_weights)[node2] += (*__log_domain_sizes)[node1];
530 
531  unsigned int nb_triangle_in_new_edge = 0;
532  unsigned int nb_neigh_n1_n2 = 0;
533 
534  for (const auto othernode : __graph->neighbours(node1)) {
535  if (__graph->existsEdge(node2, othernode)) {
536  // udate the number of triangles passing through the egdes of the
537  // __graph
538  ++__nb_triangles[Edge(node1, othernode)];
539  ++__nb_triangles[Edge(node2, othernode)];
540  ++nb_triangle_in_new_edge;
541 
542  // update the neighbors
543  ++nb_neigh_n1_n2;
544  ++__nb_adjacent_neighbours[othernode];
545 
546  if (!__changed_status.contains(othernode))
547  __changed_status.insert(othernode);
548  }
549  }
550 
551  __nb_adjacent_neighbours[node1] += nb_neigh_n1_n2;
552  __nb_adjacent_neighbours[node2] += nb_neigh_n1_n2;
553 
554  // add the edge
555  __graph->addEdge(node1, node2);
556  __nb_triangles.insert(edge, nb_triangle_in_new_edge);
557 
558  if (!__changed_status.contains(node1)) __changed_status.insert(node1);
559  if (!__changed_status.contains(node2)) __changed_status.insert(node2);
560  }
561 
564  void SimplicialSet::__updateList(const NodeId id) {
565  // check if the node belongs to the __graph
566  if (!__graph->exists(id)) {
567  GUM_ERROR(NotFound, "Node " << id << " could not be found");
568  }
569 
570  // check if the status of the node has changed
571  if (!__changed_status.contains(id)) return;
572 
573  __changed_status.erase(id);
574 
575  __Belong& belong = __containing_list[id];
576  const NodeSet& nei = __graph->neighbours(id);
577  Size nb_adj = nei.size();
578 
579  // check if the node should belong to the simplicial set
580  if (__nb_adjacent_neighbours[id] == (nb_adj * (nb_adj - 1)) / 2) {
581  if (belong != __Belong::SIMPLICIAL) {
582  if (belong == __Belong::ALMOST_SIMPLICIAL)
583  __almost_simplicial_nodes.erase(id);
584  else if (belong == __Belong::QUASI_SIMPLICIAL)
585  __quasi_simplicial_nodes.erase(id);
586 
587  __simplicial_nodes.insert(id, (*__log_weights)[id]);
588  belong = __Belong::SIMPLICIAL;
589  }
590 
591  return;
592  }
593 
594  // check if the node should belong to the almost simplicial set
595  Size nb_almost = ((nb_adj - 1) * (nb_adj - 2)) / 2;
596  Size nb = __nb_adjacent_neighbours[id];
597 
598  for (const auto cur : nei) {
599  if (nb_almost == nb - __nb_triangles[Edge(cur, id)]) {
600  // the node is an almost simplicial node
601  if (belong != __Belong::ALMOST_SIMPLICIAL) {
602  if (belong == __Belong::SIMPLICIAL)
603  __simplicial_nodes.erase(id);
604  else if (belong == __Belong::QUASI_SIMPLICIAL)
605  __quasi_simplicial_nodes.erase(id);
606 
607  __almost_simplicial_nodes.insert(id, (*__log_weights)[id]);
608  belong = __Belong::ALMOST_SIMPLICIAL;
609  } else
610  __almost_simplicial_nodes.setPriority(id, (*__log_weights)[id]);
611 
612  return;
613  }
614  }
615 
616  // check if the node should belong to the quasi simplicial nodes
617  if (__nb_adjacent_neighbours[id] / ((nb_adj * (nb_adj - 1)) / 2)
618  >= __quasi_ratio) {
619  if (belong != __Belong::QUASI_SIMPLICIAL) {
620  if (belong == __Belong::SIMPLICIAL)
621  __simplicial_nodes.erase(id);
622  else if (belong == __Belong::ALMOST_SIMPLICIAL)
623  __almost_simplicial_nodes.erase(id);
624 
625  __quasi_simplicial_nodes.insert(id, (*__log_weights)[id]);
626  belong = __Belong::QUASI_SIMPLICIAL;
627  } else
628  __quasi_simplicial_nodes.setPriority(id, (*__log_weights)[id]);
629 
630  return;
631  }
632 
633  // the node does not belong to any list, so remove the node from
634  // its current list
635  if (belong == __Belong::QUASI_SIMPLICIAL)
636  __quasi_simplicial_nodes.erase(id);
637  else if (belong == __Belong::ALMOST_SIMPLICIAL)
638  __almost_simplicial_nodes.erase(id);
639  else if (belong == __Belong::SIMPLICIAL)
640  __simplicial_nodes.erase(id);
641 
642  belong = __Belong::NO_LIST;
643  }
644 
647  // set the limit weight value
648  double limit = __log_tree_width + __log_threshold;
649 
650  // update the elements currently in the almost simplicial list that may
651  // now be contained in another list
652  for (auto iter = __changed_status.beginSafe(); // safe iterator needed here
653  iter != __changed_status.endSafe();
654  ++iter) {
655  if (__almost_simplicial_nodes.contains(*iter)) __updateList(*iter);
656  }
657 
658  // check the current almost simplicial list
659  if (!__almost_simplicial_nodes.empty()
660  && ((*__log_weights)[__almost_simplicial_nodes.top()] <= limit))
661  return true;
662 
663  // if the almost simplicial list does not contain any node that has a low
664  // weight, check if a node can enter the almost simplicial list
665  for (auto iter = __changed_status.beginSafe(); // safe iterator needed here
666  iter != __changed_status.endSafe();
667  ++iter) {
668  __updateList(*iter);
669 
670  if (!__almost_simplicial_nodes.empty()
671  && ((*__log_weights)[__almost_simplicial_nodes.top()] <= limit))
672  return true;
673  }
674 
675  return false;
676  }
677 
680  // update the elements currently in the simplicial list that may
681  // now be contained in another list
682  for (auto iter = __changed_status.beginSafe(); // safe iterator needed here
683  iter != __changed_status.endSafe();
684  ++iter) {
685  if (__simplicial_nodes.contains(*iter)) __updateList(*iter);
686  }
687 
688  // check the current almost simplicial list
689  if (!__simplicial_nodes.empty()) return true;
690 
691  // if the simplicial list does not contain any node, check if a
692  // node can enter the simplicial list
693  for (auto iter = __changed_status.beginSafe(); // safe iterator needed here
694  iter != __changed_status.endSafe();
695  ++iter) {
696  __updateList(*iter);
697 
698  if (!__simplicial_nodes.empty()) return true;
699  }
700 
701  return false;
702  }
703 
706  // set the limit weight value
707  double limit = __log_tree_width + __log_threshold;
708 
709  // update the elements currently in the quasi simplicial list that may
710  // now be contained in another list
711  for (auto iter = __changed_status.beginSafe(); // safe iterator needed here
712  iter != __changed_status.endSafe();
713  ++iter) {
714  if (__quasi_simplicial_nodes.contains(*iter)) __updateList(*iter);
715  }
716 
717  // check the current quasi simplicial list
718  if (!__quasi_simplicial_nodes.empty()
719  && ((*__log_weights)[__quasi_simplicial_nodes.top()] <= limit))
720  return true;
721 
722  // if the quasi simplicial list does not contain any node that has a low
723  // weight, check if a node can enter the quasi simplicial list
724  for (auto iter = __changed_status.beginSafe(); // safe iterator needed here
725  iter != __changed_status.endSafe();
726  ++iter) {
727  __updateList(*iter);
728 
729  if (!__quasi_simplicial_nodes.empty()
730  && ((*__log_weights)[__quasi_simplicial_nodes.top()] <= limit))
731  return true;
732  }
733 
734  return false;
735  }
736 
740  // if the __graph is empty, do nothing
741  if (__graph->size() == 0) return;
742 
743  // set the weights of the nodes and the initial tree_width (min of the
744  // weights)
745  __log_tree_width = std::numeric_limits< double >::max();
746  __log_weights->clear();
747 
748  for (const auto nodeX : *__graph) {
749  double log_weight = (*__log_domain_sizes)[nodeX];
750  for (const auto& nei : __graph->neighbours(nodeX))
751  log_weight += (*__log_domain_sizes)[nei];
752 
753  __log_weights->insert(nodeX, log_weight);
754  if (__log_tree_width > log_weight) __log_tree_width = log_weight;
755  }
756 
757  // initialize the __nb_triangles so that there is no need to check whether
758  // __nb_triangles need new insertions
759  __nb_triangles = __graph->edgesProperty(Size(0));
760  __nb_adjacent_neighbours = __graph->nodesProperty(Size(0));
761  __containing_list = __graph->nodesProperty(__Belong::NO_LIST);
762  __changed_status = __graph->asNodeSet();
763 
764  // set the __nb_triangles and the __nb_adjacent_neighbours: for each
765  // triangle, update the __nb_triangles. To count the triangles only once,
766  // parse for each node X the set of its neighbors Y,Z that are adjacent to
767  // each other and such that the Id of Y and Z are greater than X.
768  for (const auto nodeX : *__graph) {
769  Size& nb_adjacent_neighbors_idX = __nb_adjacent_neighbours[nodeX];
770  const NodeSet& nei = __graph->neighbours(nodeX);
771 
772  for (auto iterY = nei.begin(); iterY != nei.end(); ++iterY)
773  if (*iterY > nodeX) {
774  const NodeId node_idY = *iterY;
775  Size& nb_adjacent_neighbors_idY = __nb_adjacent_neighbours[node_idY];
776 
777  auto iterZ = iterY;
778  for (++iterZ; iterZ != nei.end(); ++iterZ)
779  if ((*iterZ > nodeX) && __graph->existsEdge(node_idY, *iterZ)) {
780  const NodeId node_idZ = *iterZ;
781  ++nb_adjacent_neighbors_idX;
782  ++nb_adjacent_neighbors_idY;
783  ++__nb_adjacent_neighbours[node_idZ];
784  ++__nb_triangles[Edge(nodeX, node_idY)];
785  ++__nb_triangles[Edge(nodeX, node_idZ)];
786  ++__nb_triangles[Edge(node_idZ, node_idY)];
787  }
788  }
789  }
790  }
791 
793  void SimplicialSet::setGraph(UndiGraph* graph,
794  const NodeProperty< double >* log_domain_sizes,
795  NodeProperty< double >* log_weights,
796  double theRatio,
797  double theThreshold) {
798  // check that the pointers passed in argument are all different from 0
799  if ((graph == nullptr) || (log_domain_sizes == nullptr)
800  || (log_weights == nullptr)) {
801  GUM_ERROR(OperationNotAllowed, "SimplicialSet requires non-null pointers");
802  }
803 
804  // clear the structures used for the previous graph and assign the new graph
805  __graph = graph;
806  __log_weights = log_weights;
807  __log_domain_sizes = log_domain_sizes;
808 
809  __simplicial_nodes.clear();
810  __almost_simplicial_nodes.clear();
811  __quasi_simplicial_nodes.clear();
812  __simplicial_nodes.resize(__graph->size());
813  __almost_simplicial_nodes.resize(__graph->size());
814  __quasi_simplicial_nodes.resize(__graph->size());
815 
816  __containing_list.clear();
817  __containing_list.resize(__graph->size());
818  __nb_triangles.clear();
819  __nb_triangles.resize(__graph->size() * __graph->size() / 2);
820  __nb_adjacent_neighbours.clear();
821  __nb_adjacent_neighbours.resize(__graph->size());
822 
823  __log_tree_width = std::numeric_limits< double >::max();
824  __quasi_ratio = theRatio;
825  __log_threshold = std::log(1 + theThreshold);
826  __changed_status.clear();
827  __fill_ins_list.clear();
828 
829  // end of initialization: compute __nb_triangles, __nb_adjacent_neighbours,
830  // etc
831  __initialize();
832  }
833 
835  void SimplicialSet::replaceLogWeights(NodeProperty< double >* old_weights,
836  NodeProperty< double >* new_weights) {
837  // check that the current weights are the old_weights
838  if (old_weights != __log_weights)
839  GUM_ERROR(InvalidArgument,
840  "the old set of weights shall be identical "
841  "to the current one");
842 
843  __log_weights = new_weights;
844  }
845 
846 } /* namespace gum */
847 
848 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
Useful macros for maths.
void makeClique(const NodeId id)
adds the necessary edges so that node &#39;id&#39; and its neighbors form a clique
void __initialize()
initialize: compute __nb_triangles, __nb_adjacent_neighbors, etc when a new graph is set ...
void eraseNode(const NodeId id)
removes a node and its adjacent edges from the underlying graph
Class for fast retrieval of simplicial and quasi/almost simplicial nodes.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
void setGraph(UndiGraph *graph, const NodeProperty< double > *log_domain_sizes, NodeProperty< double > *log_weights, double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
initialize the simplicial set w.r.t. a new graph
bool hasQuasiSimplicialNode()
indicates whether there exists a quasi simplicial node
void replaceLogWeights(NodeProperty< double > *old_weigths, NodeProperty< double > *new_weights)
reassigns a new set of cliques&#39; log weights (with the same content)
bool hasAlmostSimplicialNode()
indicates whether there exists an almost simplicial node
void eraseClique(const NodeId id)
removes a node and its adjacent edges from the underlying graph
STL namespace.
void erase(const Key &k)
Erases an element from the set.
Definition: set_tpl.h:653
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
void __updateList(const NodeId id)
put node id in the correct simplicial/almost simplicial/quasi simplicial list
inline implementations of simplicial set
void addEdge(NodeId first, NodeId second)
adds a new edge to the graph and recomputes the simplicial set
bool hasSimplicialNode()
indicates whether there exists a simplicial node
SimplicialSet(UndiGraph *graph, const NodeProperty< double > *log_domain_sizes, NodeProperty< double > *log_weights, double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
constructor. initializes the simplicial set w.r.t. a given graph
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
~SimplicialSet()
destructor
Size NodeId
Type for node ids.
Definition: graphElements.h:97
#define GUM_ERROR_IN_EXPR(type, msg)
Definition: exceptions.h:36
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52
some utils for topology : NodeId, Edge, Arc and consorts ...
void eraseEdge(const Edge &edge)
removes an edge from the graph and recomputes the simplicial set