aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
cliqueGraph.cpp
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2026 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2026 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40
41
47#include <algorithm>
48#include <cmath>
49#include <sstream>
50
53
54
55#ifdef GUM_NO_INLINE
57#endif // GU%_NO_INLINE
58
59#ifndef DOXYGEN_SHOULD_SKIP_THIS
60
61namespace gum {
62
63 /* =================================================================== */
64 /* =================================================================== */
65 /* === IMPLEMENTATION OF GUM_CLIQUE_GRAPH === */
66 /* =================================================================== */
67 /* =================================================================== */
68
70
72 bool nodes_resize_policy,
73 Size edges_size,
74 bool edges_resize_policy) :
75 NodeGraphPart(nodes_size, nodes_resize_policy),
76 UndiGraph(nodes_size, nodes_resize_policy, edges_size, edges_resize_policy) {
77 // for debugging purposes
78 GUM_CONSTRUCTOR(CliqueGraph)
79 }
80
82
83 CliqueGraph::CliqueGraph(const CliqueGraph& from) :
84 NodeGraphPart(from), // needed because NodeGraphPart is a virtual inherited
85 UndiGraph(from), // class (see C++ FAQ Lite #25.12 for details)
86 _cliques_(from._cliques_), _separators_(from._separators_) { // for debugging purposes
87 GUM_CONS_CPY(CliqueGraph)
88 }
89
90 CliqueGraph::CliqueGraph(CliqueGraph&& from) :
91 NodeGraphPart(std::move(from)), // virtual base — must be listed explicitly
92 UndiGraph(std::move(from)), _cliques_(std::move(from._cliques_)),
93 _separators_(std::move(from._separators_)) { // for debugging purposes
94 GUM_CONS_MOV(CliqueGraph)
95 }
96
98
99 CliqueGraph::~CliqueGraph() { // for debugging purposes
100 GUM_DESTRUCTOR(CliqueGraph)
101 }
102
105
106 std::vector< NodeId > CliqueGraph::containerPath(const NodeId node1, const NodeId node2) const {
107 // get a path from a _clique_ containing node1 to a _clique_ containing
108 // node2
109 auto opt = undirectedPath(container(node1), container(node2));
110 if (!opt) GUM_ERROR(NotFound, "no path between cliques containing the given nodes")
111 std::vector< NodeId > path = std::move(*opt);
112
113 // it may happen that the path contains several nodes containing node1 and
114 // node2. Hence we shall remove the superfluous nodes
115 while ((path.size() >= 2) && (clique(path[path.size() - 2]).contains(node2)))
116 path.pop_back();
117
118 while ((path.size() >= 2) && (clique(path[1]).contains(node1)))
119 path.erase(path.begin());
120
121 return path;
122 }
123
127
128 void CliqueGraph::addToClique(const NodeId clique_id, const NodeId node_id) {
129 // get the current clique set
130 NodeSet& clique = _cliques_[clique_id];
131
132 // check if the node already exists, in which case throw an exception
133 if (clique.contains(node_id)) {
134 GUM_ERROR(DuplicateElement, "the clique set already contains the node " << node_id)
135 }
136
137 clique.insert(node_id);
138
139 // update the _separators_ adjacent to clique 'id'
140 for (const auto nei: neighbours(clique_id))
141 if (_cliques_[nei].contains(node_id)) _separators_[Edge(nei, clique_id)].insert(node_id);
142 }
143
145
146 void CliqueGraph::eraseFromClique(const NodeId clique_id, const NodeId node_id) {
147 // get the current _clique_ set
148 NodeSet& clique = _cliques_[clique_id];
149
150 // check if the node does not exist, in which case throw an exception
151 if (clique.contains(node_id)) {
152 clique.erase(node_id);
153
154 // update the _separators_ adjacent to _clique_ 'id'
155 for (const auto nei: neighbours(clique_id)) {
156 Edge edge(nei, clique_id);
157
158 if (_separators_[edge].contains(node_id)) _separators_[edge].erase(node_id);
159 }
160 }
161 }
162
164
165 bool CliqueGraph::_runningIntersectionDFS_(const NodeId clique,
166 const NodeId from,
167 CliqueGraph::_RunningIntersect_& infos_DFS) const {
168 // check that no node in the clique belongs to the set of nodes belonging to
169 // other connected components of the cliqueGraph
170 const NodeSet& nodes_clique = _cliques_[clique];
171
172 for (const auto node: nodes_clique)
173 if (infos_DFS.nodes_other_components.contains(node)) return false;
174
175 // update the structure that keeps track of the cliques that still require
176 // chains to access some of their nodes
177 for (const auto node: nodes_clique)
178 if (!infos_DFS.nodes_DFS_forbidden.contains(node))
179 infos_DFS.cliques_DFS_chain[clique].erase(node);
180
181 // if the clique had already been visited, no need to see its neighbours
182 // or to update the list of visited nodes
183 if (infos_DFS.visited_cliques.contains(clique)) return true;
184
185 // update the list of nodes visited during the DFS
186 for (const auto node: nodes_clique)
187 if (!infos_DFS.nodes_DFS_seen.contains(node)) infos_DFS.nodes_DFS_seen.insert(node);
188
189 // update the fact that the clique has been visited
190 infos_DFS.visited_cliques.insert(clique);
191
192 // check the neighbours that are different from "from" and that have not
193 // been visited yet
194
195 for (const auto otherID: neighbours(clique))
196 if (otherID != from) {
197 // update the list of forbidden nodes in the DFS, i.e., the nodes that
198 // belong to the clique but not to the separator
199 const Edge edge(otherID, clique);
200 const NodeSet& from_separ = _separators_[edge];
201
202 for (const auto node: nodes_clique) {
203 if (!from_separ.contains(node)) infos_DFS.nodes_DFS_forbidden.insert(node);
204 }
205
206 // check the neighbour
207 if (!_runningIntersectionDFS_(otherID, clique, infos_DFS)) return false;
208
209 // remove from the forbidden list the nodes that belong to clique
210 for (const auto node: nodes_clique)
211 infos_DFS.nodes_DFS_forbidden.erase(node);
212
213 // check again the structure that keeps track of the cliques that still
214 // require chains to access some of their nodes: the chain may be
215 // the neighbour we just encountered
216 for (const auto node: nodes_clique) {
217 if (!infos_DFS.nodes_DFS_forbidden.contains(node))
218 infos_DFS.cliques_DFS_chain[clique].erase(node);
219 }
220 }
221
222 // when a node is terminal, i.e., it has at most one neighbour, add its
223 // nodes
224 // to the nodes forbidden by the DFS. It will prevent non adjacent extremal
225 // cliques to contain the same node while this one does not belong to any
226 // separator
227 if (neighbours(clique).size() <= 1)
228 for (const auto node: nodes_clique)
229 if (!infos_DFS.nodes_DFS_forbidden.contains(node))
230 infos_DFS.nodes_DFS_forbidden.insert(node);
231
232 // here everything was OK. A priori, the running intersection property holds
233 return true;
234 }
235
237
238 bool CliqueGraph::hasRunningIntersection() const {
239 // create a RunningIntersect structure and initialize it
240 _RunningIntersect_ infos_DFS;
241 infos_DFS.cliques_DFS_chain = _cliques_;
242
243 // while there exist unvisited cliques, perform a DFS on them
244 for (const auto DFSnode: nodes())
245 if (!infos_DFS.visited_cliques.contains(DFSnode)) {
246 // no nodes are forbidden priori in the DFS
247 infos_DFS.nodes_DFS_forbidden.clear();
248
249 // no node has already been seen in the DFS
250 infos_DFS.nodes_DFS_seen.clear();
251
252 // here iter_DFS points on a clique that has not been visited yet
253 // visit the clique graph from this clique
254 if (!_runningIntersectionDFS_(DFSnode, DFSnode, infos_DFS)) return false;
255
256 // the nodes that were seen during the DFS belong to a connected
257 // component
258 // that is different from the connected components of the subsequent DFS
259 for (const auto node: infos_DFS.nodes_DFS_seen)
260 if (!infos_DFS.nodes_other_components.contains(node))
261 infos_DFS.nodes_other_components.insert(node);
262 }
263
264 // check that no clique requires an additional chain to guarantee the
265 // running intersection property
266 for (const auto& [node, nodes]: infos_DFS.cliques_DFS_chain)
267 if (!nodes.empty()) return false;
268
269 return true;
270 }
271
273
274 bool CliqueGraph::operator==(const CliqueGraph& from) const {
275 // check if both graphical structures are identical
276 if (!UndiGraph::operator==(from)) return false;
277
278 // check if the _cliques_ are identical
279 for (const auto& [node, nodes]: _cliques_)
280 if (nodes != from._cliques_[node]) return false;
281
282 return true;
283 }
284
285 std::string CliqueGraph::toString() const {
286 std::stringstream stream;
287 stream << "list of nodes:\n";
288
289 for (const auto node: nodes()) {
290 stream << std::format(" -- node: {}\n clique:", node);
291
292 for (const auto cliq: clique(node))
293 stream << " " << cliq;
294
295 stream << '\n';
296 }
297
298 stream << "\n\nlist of edges:\n";
299
300 for (const auto& edge: edges())
301 stream << edge << " ";
302
303 return stream.str();
304 }
305
306 namespace {
307 // "0-1-3", the identifiers of a set of nodes
308 std::string expandCliqueContent(const NodeSet& clique, std::string_view delim = "-") {
309 std::string result;
310 bool first = true;
311
312 std::vector< NodeId > sorted(clique.begin(), clique.end());
313 std::sort(sorted.begin(), sorted.end());
314 for (auto node: sorted) {
315 if (!first) { result += delim; }
316 result += std::to_string(node);
317 first = false;
318 }
319
320 return result;
321 }
322
323 // "size : 2", then one identifier by line
324 std::string expandCliqueTooltip(const NodeSet& clique) {
325 return std::format("size : {}\n{}", clique.size(), expandCliqueContent(clique, "\n"));
326 }
327
328 // the node that stands for the separator of an edge
329 std::string separatorId(const Edge& edge) {
330 return std::format("{}~{}", edge.first(), edge.second());
331 }
332
333 // a size, without the rounding errors of the products (0.3 * 4 is 1.2000000000000002)
334 std::string dotSize(double value) {
335 return dot::DotWriter::number(std::round(value * 1e6) / 1e6);
336 }
337 } // namespace
338
339 std::string CliqueGraph::toDot() const { return toDot(dot::DotOptions()); }
340
341 std::string CliqueGraph::toDot(const dot::DotOptions& options) const {
342 const auto style = dot::JunctionTreeDotStyle::read();
343 dot::DotWriter writer(false);
344 dot::writePreamble(writer, style, options);
345
346 // the font color of a node is adaptive against its own background
347 auto cliqueStyle = static_cast< dot::DotStyle >(style);
348 cliqueStyle.nodeBgColor = style.cliqueBgColor;
349 auto separatorStyle = static_cast< dot::DotStyle >(style);
350 separatorStyle.nodeBgColor = style.separatorBgColor;
351
352 // cliques as nodes
353 for (const auto node: nodes()) {
354 auto attributes = dot::nodeAttributes(cliqueStyle,
355 options.node(node),
356 expandCliqueContent(clique(node)),
357 expandCliqueTooltip(clique(node)));
358 dot::addDefaultAttribute(attributes, "fontsize", std::to_string(style.cliqueFontSize));
359 dot::addDefaultAttribute(attributes, "fontcolor", style.cliqueFgColor);
360 dot::addDefaultAttribute(attributes, "fillcolor", style.cliqueBgColor);
361 writer.node(std::to_string(node), attributes);
362 }
363
364 // separators as nodes : the options of an edge are the ones of its separator
365 for (const auto& edge: edges()) {
366 const auto sep = separator(edge);
367 const auto* arc = options.edge(edge.first(), edge.second());
368
369 dot::DotNodeOptions separatorOptions;
370 if (arc != nullptr) {
371 separatorOptions.bgColor = arc->color;
372 separatorOptions.label = arc->label;
373 separatorOptions.tooltip = arc->tooltip;
374 separatorOptions.attributes = arc->attributes;
375 }
376
377 auto attributes = dot::nodeAttributes(separatorStyle,
378 arc != nullptr ? &separatorOptions : nullptr,
379 expandCliqueContent(sep),
380 expandCliqueTooltip(sep));
381 dot::addDefaultAttribute(attributes, "margin", "0.02");
382 dot::addDefaultAttribute(attributes, "height", "0");
383 dot::addDefaultAttribute(attributes, "width", "0");
384 dot::addDefaultAttribute(attributes, "shape", "box");
385 dot::addDefaultAttribute(attributes, "fontsize", std::to_string(style.separatorFontSize));
386 dot::addDefaultAttribute(attributes, "fontcolor", style.separatorFgColor);
387 dot::addDefaultAttribute(attributes, "fillcolor", style.separatorBgColor);
388 writer.node(separatorId(edge), attributes);
389 }
390
391 // edges now as c1--sep--c2
392 for (const auto& edge: edges()) {
393 dot::DotAttributes link;
394 const auto* arc = options.edge(edge.first(), edge.second());
395 if (arc != nullptr && arc->width.has_value())
396 link.push_back({"penwidth", dot::DotWriter::number(*arc->width)});
397
398 writer.edge(std::to_string(edge.first()), separatorId(edge), link);
399 writer.edge(separatorId(edge), std::to_string(edge.second()), link);
400 }
401
402 return writer.str();
403 }
404
405 std::string CliqueGraph::mapToDot() const {
406 const auto style = dot::JunctionTreeDotStyle::read();
407 return mapToDot(style.mapCliqueScale,
408 style.mapSepScale,
409 style.mapEdgeLen,
410 style.cliqueBgColor,
411 style.separatorBgColor);
412 }
413
414 std::string CliqueGraph::mapToDot(double scaleClique,
415 double scaleSep,
416 double lenEdge,
417 std::string_view colorClique,
418 std::string_view colorSep) const {
419 const auto style = dot::JunctionTreeDotStyle::read();
420
421 dot::DotWriter writer(false);
422 writer.graphAttributes(
423 {{"bgcolor", "transparent"}, {"layout", "neato"}, {"size", style.mapSize}});
424 writer.nodeDefaults(
425 {{"shape", "point"},
426 {"style", "filled"},
427 {"fillcolor", std::string(colorClique.empty() ? style.cliqueBgColor : colorClique)}});
428 writer.edgeDefaults({{"len", dot::DotWriter::number(lenEdge)}, {"color", style.arcColor}});
429
430 // cliques as nodes
431 for (const auto node: nodes()) {
432 const auto& clik = clique(node);
433 writer.node(std::to_string(node),
434 {{"tooltip", expandCliqueTooltip(clik)},
435 {"width", dotSize(scaleClique * double(clik.size()))}});
436 }
437
438 writer.nodeDefaults(
439 {{"shape", "square"},
440 {"style", "filled"},
441 {"fillcolor", std::string(colorSep.empty() ? style.separatorBgColor : colorSep)},
442 {"label", ""}});
443
444 // separators as nodes and edges
445 for (const auto& edge: edges()) {
446 const auto sep = clique(edge.first()) * clique(edge.second());
447 writer.node(separatorId(edge),
448 {{"tooltip", expandCliqueTooltip(sep)},
449 {"width", dotSize(scaleSep * double(sep.size()))}});
450 writer.edge(std::to_string(edge.first()), separatorId(edge));
451 writer.edge(separatorId(edge), std::to_string(edge.second()));
452 }
453
454 return writer.str();
455 }
456
458
459 std::ostream& operator<<(std::ostream& stream, const CliqueGraph& graph) {
460 stream << graph.toString();
461 return stream;
462 }
463
464} /* namespace gum */
465
466#endif /* DOXYGEN_SHOULD_SKIP_THIS */
CliqueGraph(Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
basic constructor: creates an empty clique graph
Class for node sets in graph.
Exception : the element we looked for cannot be found.
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
void erase(const Key &k)
Erases an element from the set.
Definition set_tpl.h:553
Base class for undirected graphs.
Definition undiGraph.h:134
Basic class for all graphs of cliques (join trees, etc).
inline source of basic clique graphs
The statements common to the graphs drawn with graphviz : preamble, attributes of nodes and arcs.
#define GUM_ERROR(type, msg)
Definition exceptions.h:76
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
GUM_SHARED_PUBLIC bool contains(std::string_view s, std::string_view needle)
true if needle in s
std::optional< std::vector< NodeId > > undirectedPath(const G &g, NodeId n1, NodeId n2)
Shortest undirected path from n1 to n2 (BFS).
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
STL namespace.
GUM_SHARED_PUBLIC std::ostream & operator<<(std::ostream &s, const gum::Variable &LDRV)
for friendly displaying the content of the variable