aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
cliqueGraph.h
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#ifndef GUM_CLIQUE_GRAPH_H
48#define GUM_CLIQUE_GRAPH_H
49
50#include <iostream>
51
52#include <agrum/agrum.h>
53
55
56namespace gum {
57
58 namespace dot {
59 class DotOptions;
60 } // namespace dot
61
62 /* ===========================================================================
63 */
64 /* === GRAPHS OF CLIQUES ===
65 */
66 /* ===========================================================================
67 */
79 /* ===========================================================================
80 */
81
82 class GUM_SHARED_PUBLIC CliqueGraph: public UndiGraph {
83 public:
84 // ############################################################################
86 // ############################################################################
88
90
94
96 bool nodes_resize_policy = true,
98 bool edges_resize_policy = true);
99
101
102
104
107
109
110 ~CliqueGraph() override;
111
113
114 // ############################################################################
116 // ############################################################################
118
120
128 void addEdge(NodeId first, NodeId second) override;
129
131
134
135 void eraseEdge(const Edge& edge) override;
136
138
139 void clearEdges() override;
140
142
144
145
147
148 NodeId addNode() override;
149
151
153 void addNodeWithId(const NodeId id, const NodeSet& clique);
154
156
158 void addNodeWithId(const NodeId id) override;
159
161
163
164 void eraseNode(const NodeId node) override;
165
168
169 void clear() override;
170
172
174
175 const NodeSet& clique(const NodeId idClique) const;
176
185
186 NodeId container(const NodeId idNode) const;
187
192
193 virtual void setClique(const NodeId idClique, const NodeSet& new_clique);
194
201
202 virtual void addToClique(const NodeId clique_id, const NodeId node_id);
203
205
208
209 virtual void eraseFromClique(const NodeId clique_id, const NodeId node_id);
210
212
214
215 const NodeSet& separator(const Edge& edge) const;
216
218
220
221 const NodeSet& separator(const NodeId clique1, const NodeId clique) const;
222
225
226
227 std::vector< NodeId > containerPath(const NodeId node1, const NodeId node2) const;
228
230
231
233
235
236 bool isJoinTree() const;
237
239
240 std::string toString() const override;
241
243
244 std::string toDot() const override;
245
248
254 std::string toDot(const dot::DotOptions& options) const override;
255
258 std::string mapToDot() const;
259
261
263 virtual std::string mapToDot(double scaleClique,
264 double scaleSep,
265 double lenEdge,
266 std::string_view colorClique = "",
267 std::string_view colorSep = "") const;
268
270
271 // ############################################################################
273 // ############################################################################
275
277
279
281
283
284
286
287 bool operator==(const CliqueGraph& from) const;
288
290
291 private:
294
297
299
300 void _updateSeparators_(const NodeId clique1);
301
303
342
344
346 const NodeId from,
347 _RunningIntersect_& infos_DFS) const;
348 };
349
354
358
360
361 GUM_SHARED_PUBLIC std::ostream& operator<<(std::ostream&, const CliqueGraph&);
362
363} /* namespace gum */
364
365#ifndef GUM_NO_INLINE
367#endif // GU%_NO_INLINE
368
369#endif /* GUM_CLIQUE_GRAPH_H */
Basic graph of cliques.
Definition cliqueGraph.h:82
std::string toString() const override
friendly displays the content of the CliqueGraph
const NodeSet & separator(const Edge &edge) const
returns the separator included in a given edge
CliqueGraph(const CliqueGraph &from)
copy constructor
const NodeSet & separator(const NodeId clique1, const NodeId clique) const
returns the separator included in an edge specified by its extremities
void eraseNode(const NodeId node) override
removes a given clique from the clique graph
bool hasRunningIntersection() const
indicates whether the running intersection property holds
void _updateSeparators_(const NodeId clique1)
function used to update the separators when a clique is modified
void addNodeWithId(const NodeId id, const NodeSet &clique)
try to add a new clique to the graph
void addEdge(NodeId first, NodeId second) override
inserts a new edge between two cliques
virtual void eraseFromClique(const NodeId clique_id, const NodeId node_id)
remove a node from a clique
void clearEdges() override
removes all edges and their separators
NodeId addNode(const NodeSet &clique)
adds a new clique to the graph
std::string toDot() const override
friendly displays the content of the CliqueGraph in DOT format
virtual void setClique(const NodeId idClique, const NodeSet &new_clique)
changes the set of nodes included into a given clique and returns the new set
void addNodeWithId(const NodeId id) override
try to add a new clique to the graph
CliqueGraph & operator=(CliqueGraph &&from)
move operator
void eraseEdge(const Edge &edge) override
removes an edge (and its separator) from the clique graph
virtual void addToClique(const NodeId clique_id, const NodeId node_id)
changes the set of nodes included into a given clique and returns the new set
CliqueGraph(CliqueGraph &&from)
move constructor
bool _runningIntersectionDFS_(const NodeId clique, const NodeId from, _RunningIntersect_ &infos_DFS) const
function used for the computation of the running intersection property
std::string mapToDot() const
friendly displays the content of the map of the CliqueGraph in DOT format, with the values of the con...
void clear() override
removes all the cliques and separators from the graph (as well as their adjacent edges)
NodeId container(const NodeId idNode) const
returns the id of a clique containing the node the id of which is in argument
EdgeProperty< NodeSet > _separators_
the set of nodes contained into the separators
std::string toDot(const dot::DotOptions &options) const override
friendly displays the content of the CliqueGraph in DOT format, with the options given by the caller
bool operator==(const CliqueGraph &from) const
checks whether two clique graphs are equal
~CliqueGraph() override
destructor
NodeId addNode() override
adds a new clique to the graph
virtual std::string mapToDot(double scaleClique, double scaleSep, double lenEdge, std::string_view colorClique="", std::string_view colorSep="") const
friendly displays the content of the map of the CliqueGraph in DOT format
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
NodeProperty< NodeSet > _cliques_
the set of nodes contained into the cliques
const NodeSet & clique(const NodeId idClique) const
returns the set of nodes included into a given clique
std::vector< NodeId > containerPath(const NodeId node1, const NodeId node2) const
returns a path from a clique containing node1 to a clique containing node2
CliqueGraph & operator=(const CliqueGraph &from)
copy operator
bool isJoinTree() const
indicates whether the graph is a join tree
The base class for all undirected edges.
UndiGraph(Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
Definition undiGraph.cpp:74
The options given to a toDot(const DotOptions&).
Definition dotOptions.h:110
inline source of basic clique graphs
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74
Size NodeId
Type for node ids.
HashTable< Edge, VAL > EdgeProperty
Property on graph elements.
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
std::ostream & operator<<(std::ostream &stream, const AVLTree< Val, Cmp > &tree)
display the content of a tree
CliqueGraph JoinTree
a join tree is a clique graph satisfying the running intersection property (but some cliques may be i...
CliqueGraph JunctionTree
a junction tree is a clique graph satisfying the running intersection property and such that no cliqu...
structure used for the computation of the running intersection property
NodeSet nodes_DFS_seen
set of the nodes examined during the current DFS
NodeSet nodes_other_components
structure indicating the nodes that belong to other connected components
NodeSet nodes_DFS_forbidden
the nodes that are currently forbidden by separators in the DFS
NodeSet visited_cliques
structure indicating for each clique whether it has been examined by a DFS (Depth First Search)
NodeProperty< NodeSet > cliques_DFS_chain
for each clique, the list of its nodes that require accessing the clique through a chain
static constexpr Size default_size
The default number of slots in hashtables.
Definition hashTable.h:102
Base classes for undirected graphs.