aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
junctionTreeRoots.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
48
49#include <cmath>
50#include <utility>
51
53
54namespace gum {
55
57 const GraphicalModel& model,
58 const NodeSet& preferred) {
59 // for each connected component, the best clique so far with its key: (not preferred, log of
60 // its domain size). The lexicographic order puts the preferred cliques first, then the smallest
61 using Key = std::pair< bool, double >;
62
63 const auto components = jt.connectedComponents();
65
66 for (const auto clique: jt.nodes()) {
67 double log_dom_size = 0.0;
68 for (const auto node: jt.clique(clique))
69 log_dom_size += std::log(static_cast< double >(model.variable(node).domainSize()));
70 const Key key{!preferred.contains(clique), log_dom_size};
71
72 const NodeId component = components[clique];
73 if (auto current = best.tryGet(component)) {
74 if (key < current->first) *current = {key, clique};
75 } else {
76 best.insert(component, {key, clique});
77 }
78 }
79
80 NodeSet roots;
81 for (const auto& elt: best)
82 roots.insert(elt.second.second);
83 return roots;
84 }
85
86} // namespace gum
const NodeSet & clique(const NodeId idClique) const
returns the set of nodes included into a given clique
virtual Size domainSize() const =0
Virtual base class for probabilistic graphical models.
virtual const DiscreteVariable & variable(NodeId id) const =0
Returns a constant reference over a variable given it's node id.
The class for generic Hash Tables.
Definition hashTable.h:640
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
optional_ref< Val > tryGet(const Key &key)
Returns a pointer to the value associated with a given key, or nullptr if the key does not exist.
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition set_tpl.h:468
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
NodeProperty< NodeId > connectedComponents() const
returns a property {node:id of weakly connected component}
Size NodeId
Type for node ids.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Selection of the roots of the connected components of a junction tree.
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
NodeSet junctionTreeRoots(const JunctionTree &jt, const GraphicalModel &model, const NodeSet &preferred)
Returns one root for each connected component of a junction tree.
CliqueGraph JunctionTree
a junction tree is a clique graph satisfying the running intersection property and such that no cliqu...