35 #endif // GUM_NO_INLINE 37 #ifndef DOXYGEN_SHOULD_SKIP_THIS 54 const NodeProperty< double >* log_domain_sizes,
55 NodeProperty< double >* log_weights,
57 double theThreshold) :
58 __graph(graph != nullptr
61 "SimplicialSet requires a valid graph")),
62 __log_weights(log_weights != nullptr
66 "requires non-null log weights")),
67 __log_domain_sizes(log_domain_sizes != nullptr
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) {
81 GUM_CONSTRUCTOR(SimplicialSet);
92 const NodeProperty< double >* log_domain_sizes,
93 NodeProperty< double >* log_weights,
95 __graph(graph != nullptr
98 "SimplicialSet requires a valid graph")),
99 __log_weights(log_weights != nullptr
103 "requires non-null log weights")),
105 log_domain_sizes != nullptr
109 "requires non-null domain sizes")) {
113 if ((__graph == from.__graph) || (__log_weights == from.__log_weights)
114 || (*__graph != *from.__graph)
115 || (*__log_domain_sizes != *from.__log_domain_sizes)) {
117 "SimplicialSet requires fresh copies of " 118 "graph, log weights and log domain sizes");
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;
138 GUM_CONS_CPY(SimplicialSet);
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)) {
157 GUM_CONS_MOV(SimplicialSet);
163 GUM_DESTRUCTOR(SimplicialSet);
169 if (__changed_status.contains(
id)) __updateList(
id);
182 if (__simplicial_nodes.contains(
id)) {
184 }
else if (__almost_simplicial_nodes.contains(
id)) {
189 const NodeSet& nei = __graph->neighbours(
id);
190 Size nb_adj = nei.size();
191 Size nb = __nb_adjacent_neighbours[id];
198 Size nb_almost = ((nb_adj - 1) * (nb_adj - 2)) / 2;
201 for (
const auto current_node : nei) {
202 if (nb_almost == nb - __nb_triangles[Edge(current_node,
id)]) {
212 node1 = current_node;
217 double log_domain_size_node1 = (*__log_domain_sizes)[node1];
218 double& __log_weights_node1 = (*__log_weights)[node1];
226 unsigned int nb_n1 = 0;
230 for (
const auto node2 : nei) {
231 if ((node2 != node1) && !__graph->existsEdge(node1, node2)) {
233 const Edge e1_2(node1, node2);
234 __graph->addEdge(node1, node2);
236 if (__we_want_fill_ins) __fill_ins_list.insert(e1_2);
238 if (!__changed_status.contains(node2)) __changed_status.insert(node2);
240 __log_weights_node1 += (*__log_domain_sizes)[node2];
241 (*__log_weights)[node2] += log_domain_size_node1;
242 __nb_triangles.insert(e1_2, 0);
247 unsigned int nb_n2 = 0;
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)) {
260 ++__nb_adjacent_neighbours[neighbor];
261 ++__nb_triangles[Edge(node1, neighbor)];
262 ++__nb_triangles[Edge(node2, neighbor)];
264 if (!__changed_status.contains(neighbor))
265 __changed_status.insert(neighbor);
269 for (
const auto neighbor : __graph->neighbours(node2)) {
270 if (__graph->existsEdge(neighbor, node1)) {
276 ++__nb_adjacent_neighbours[neighbor];
277 ++__nb_triangles[Edge(node2, neighbor)];
278 ++__nb_triangles[Edge(node1, neighbor)];
280 if (!__changed_status.contains(neighbor))
281 __changed_status.insert(neighbor);
286 __nb_adjacent_neighbours[node2] += nb_n2;
287 __nb_triangles[e1_2] += nb_n2;
291 if (!__changed_status.contains(node1)) __changed_status.insert(node1);
293 __nb_adjacent_neighbours[node1] += nb_n1;
299 const NodeSet& nei = __graph->neighbours(
id);
301 for (
auto iter1 = nei.begin(); iter1 != nei.end(); ++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;
308 auto iterEdge2 = iter1;
310 for (++iterEdge2; iterEdge2 != nei.end(); ++iterEdge2) {
311 const NodeId node2 = *iterEdge2;
312 const Edge e1_2(node1, node2);
314 if (!__graph->existsEdge(e1_2)) {
316 __graph->addEdge(node1, node2);
318 if (__we_want_fill_ins) __fill_ins_list.insert(e1_2);
320 if (!__changed_status.contains(node2)) __changed_status.insert(node2);
323 __log_weights_node1 += (*__log_domain_sizes)[node2];
324 (*__log_weights)[node2] += log_domain_size_node1;
325 __nb_triangles.insert(e1_2, 0);
329 unsigned int nb_n2 = 0;
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)) {
339 ++__nb_adjacent_neighbours[neighbor];
340 ++__nb_triangles[Edge(node1, neighbor)];
341 ++__nb_triangles[Edge(node2, neighbor)];
343 if (!__changed_status.contains(neighbor))
344 __changed_status.insert(neighbor);
347 for (
const auto neighbor : __graph->neighbours(node2)) {
348 if (__graph->existsEdge(neighbor, node1)) {
353 ++__nb_adjacent_neighbours[neighbor];
354 ++__nb_triangles[Edge(node2, neighbor)];
355 ++__nb_triangles[Edge(node1, neighbor)];
357 if (!__changed_status.contains(neighbor))
358 __changed_status.insert(neighbor);
363 __nb_adjacent_neighbours[node2] += nb_n2;
364 __nb_triangles[e1_2] += nb_n2;
368 __nb_adjacent_neighbours[node1] += nb_n1;
370 if (node1_status && !__changed_status.contains(node1))
371 __changed_status.insert(node1);
376 if (!__simplicial_nodes.contains(
id)) {
377 if (__changed_status.contains(
id)) __changed_status.erase(
id);
379 switch (__containing_list[
id]) {
380 case __Belong::ALMOST_SIMPLICIAL:
381 __almost_simplicial_nodes.erase(
id);
384 case __Belong::QUASI_SIMPLICIAL: __quasi_simplicial_nodes.erase(
id);
break;
389 __simplicial_nodes.insert(
id, (*__log_weights)[
id]);
390 __containing_list[id] = __Belong::SIMPLICIAL;
392 if (__changed_status.contains(
id)) { __changed_status.erase(
id); }
399 if (!__graph->exists(
id)) {
400 GUM_ERROR(NotFound,
"Node " <<
id <<
" does not belong to the graph");
403 const NodeSet nei = __graph->neighbours(
id);
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");
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;
418 if (!__changed_status.contains(node1)) __changed_status.insert(node1);
420 __nb_triangles.erase(Edge(node1,
id));
423 for (++iter2; iter2 != nei.end(); ++iter2)
424 --__nb_triangles[Edge(node1, *iter2)];
427 __log_tree_width = std::max(__log_tree_width, (*__log_weights)[
id]);
429 switch (__containing_list[
id]) {
430 case __Belong::SIMPLICIAL: __simplicial_nodes.erase(
id);
break;
432 case __Belong::ALMOST_SIMPLICIAL: __almost_simplicial_nodes.erase(
id);
break;
434 case __Belong::QUASI_SIMPLICIAL: __quasi_simplicial_nodes.erase(
id);
break;
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);
449 if (!__graph->exists(
id)) {
450 GUM_ERROR(NotFound,
"Node " <<
id <<
" does not belong to the graph");
454 const NodeSet& nei = __graph->neighbours(
id);
456 for (
auto iter = nei.beginSafe(); iter != nei.endSafe();
458 eraseEdge(Edge(*iter,
id));
460 switch (__containing_list[
id]) {
461 case __Belong::SIMPLICIAL: __simplicial_nodes.
erase(
id);
break;
463 case __Belong::ALMOST_SIMPLICIAL: __almost_simplicial_nodes.erase(
id);
break;
465 case __Belong::QUASI_SIMPLICIAL: __quasi_simplicial_nodes.erase(
id);
break;
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);
480 if (!__graph->existsEdge(edge)) {
481 GUM_ERROR(NotFound,
"Edge " << edge <<
" does not belong to the graph");
485 const NodeId node1 = edge.first();
486 const NodeId node2 = edge.second();
489 __graph->eraseEdge(edge);
490 __nb_triangles.erase(edge);
493 (*__log_weights)[node1] -= (*__log_domain_sizes)[node2];
494 (*__log_weights)[node2] -= (*__log_domain_sizes)[node1];
497 unsigned int nb_neigh_n1_n2 = 0;
498 for (
const auto othernode : __graph->neighbours(node1)) {
499 if (__graph->existsEdge(node2, othernode)) {
502 --__nb_triangles[Edge(node1, othernode)];
503 --__nb_triangles[Edge(node2, othernode)];
506 --__nb_adjacent_neighbours[othernode];
508 if (!__changed_status.contains(othernode))
509 __changed_status.insert(othernode);
513 __nb_adjacent_neighbours[node1] -= nb_neigh_n1_n2;
514 __nb_adjacent_neighbours[node2] -= nb_neigh_n1_n2;
516 if (!__changed_status.contains(node1)) __changed_status.insert(node1);
517 if (!__changed_status.contains(node2)) __changed_status.insert(node2);
523 const Edge edge(node1, node2);
525 if (__graph->existsEdge(edge))
return;
528 (*__log_weights)[node1] += (*__log_domain_sizes)[node2];
529 (*__log_weights)[node2] += (*__log_domain_sizes)[node1];
531 unsigned int nb_triangle_in_new_edge = 0;
532 unsigned int nb_neigh_n1_n2 = 0;
534 for (
const auto othernode : __graph->neighbours(node1)) {
535 if (__graph->existsEdge(node2, othernode)) {
538 ++__nb_triangles[Edge(node1, othernode)];
539 ++__nb_triangles[Edge(node2, othernode)];
540 ++nb_triangle_in_new_edge;
544 ++__nb_adjacent_neighbours[othernode];
546 if (!__changed_status.contains(othernode))
547 __changed_status.insert(othernode);
551 __nb_adjacent_neighbours[node1] += nb_neigh_n1_n2;
552 __nb_adjacent_neighbours[node2] += nb_neigh_n1_n2;
555 __graph->addEdge(node1, node2);
556 __nb_triangles.insert(edge, nb_triangle_in_new_edge);
558 if (!__changed_status.contains(node1)) __changed_status.insert(node1);
559 if (!__changed_status.contains(node2)) __changed_status.insert(node2);
566 if (!__graph->exists(
id)) {
567 GUM_ERROR(NotFound,
"Node " <<
id <<
" could not be found");
571 if (!__changed_status.contains(
id))
return;
573 __changed_status.erase(
id);
575 __Belong& belong = __containing_list[id];
576 const NodeSet& nei = __graph->neighbours(
id);
577 Size nb_adj = nei.size();
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);
587 __simplicial_nodes.insert(
id, (*__log_weights)[
id]);
588 belong = __Belong::SIMPLICIAL;
595 Size nb_almost = ((nb_adj - 1) * (nb_adj - 2)) / 2;
596 Size nb = __nb_adjacent_neighbours[id];
598 for (
const auto cur : nei) {
599 if (nb_almost == nb - __nb_triangles[Edge(cur,
id)]) {
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);
607 __almost_simplicial_nodes.insert(
id, (*__log_weights)[
id]);
608 belong = __Belong::ALMOST_SIMPLICIAL;
610 __almost_simplicial_nodes.setPriority(
id, (*__log_weights)[
id]);
617 if (__nb_adjacent_neighbours[
id] / ((nb_adj * (nb_adj - 1)) / 2)
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);
625 __quasi_simplicial_nodes.insert(
id, (*__log_weights)[
id]);
626 belong = __Belong::QUASI_SIMPLICIAL;
628 __quasi_simplicial_nodes.setPriority(
id, (*__log_weights)[
id]);
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);
642 belong = __Belong::NO_LIST;
648 double limit = __log_tree_width + __log_threshold;
652 for (
auto iter = __changed_status.beginSafe();
653 iter != __changed_status.endSafe();
655 if (__almost_simplicial_nodes.contains(*iter)) __updateList(*iter);
659 if (!__almost_simplicial_nodes.empty()
660 && ((*__log_weights)[__almost_simplicial_nodes.top()] <= limit))
665 for (
auto iter = __changed_status.beginSafe();
666 iter != __changed_status.endSafe();
670 if (!__almost_simplicial_nodes.empty()
671 && ((*__log_weights)[__almost_simplicial_nodes.top()] <= limit))
682 for (
auto iter = __changed_status.beginSafe();
683 iter != __changed_status.endSafe();
685 if (__simplicial_nodes.contains(*iter)) __updateList(*iter);
689 if (!__simplicial_nodes.empty())
return true;
693 for (
auto iter = __changed_status.beginSafe();
694 iter != __changed_status.endSafe();
698 if (!__simplicial_nodes.empty())
return true;
707 double limit = __log_tree_width + __log_threshold;
711 for (
auto iter = __changed_status.beginSafe();
712 iter != __changed_status.endSafe();
714 if (__quasi_simplicial_nodes.contains(*iter)) __updateList(*iter);
718 if (!__quasi_simplicial_nodes.empty()
719 && ((*__log_weights)[__quasi_simplicial_nodes.top()] <= limit))
724 for (
auto iter = __changed_status.beginSafe();
725 iter != __changed_status.endSafe();
729 if (!__quasi_simplicial_nodes.empty()
730 && ((*__log_weights)[__quasi_simplicial_nodes.top()] <= limit))
741 if (__graph->size() == 0)
return;
745 __log_tree_width = std::numeric_limits< double >::max();
746 __log_weights->clear();
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];
753 __log_weights->insert(nodeX, log_weight);
754 if (__log_tree_width > log_weight) __log_tree_width = log_weight;
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();
768 for (
const auto nodeX : *__graph) {
769 Size& nb_adjacent_neighbors_idX = __nb_adjacent_neighbours[nodeX];
770 const NodeSet& nei = __graph->neighbours(nodeX);
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];
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)];
794 const NodeProperty< double >* log_domain_sizes,
795 NodeProperty< double >* log_weights,
797 double theThreshold) {
799 if ((graph ==
nullptr) || (log_domain_sizes ==
nullptr)
800 || (log_weights ==
nullptr)) {
801 GUM_ERROR(OperationNotAllowed,
"SimplicialSet requires non-null pointers");
806 __log_weights = log_weights;
807 __log_domain_sizes = log_domain_sizes;
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());
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());
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();
836 NodeProperty< double >* new_weights) {
838 if (old_weights != __log_weights)
840 "the old set of weights shall be identical " 841 "to the current one");
843 __log_weights = new_weights;
void makeClique(const NodeId id)
adds the necessary edges so that node 'id' 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' 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
void erase(const Key &k)
Erases an element from the set.
gum is the global namespace for all aGrUM entities
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.
~SimplicialSet()
destructor
Size NodeId
Type for node ids.
#define GUM_ERROR_IN_EXPR(type, msg)
#define GUM_ERROR(type, msg)
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