aGrUM
3.3.2
a C++ library for (probabilistic) graphical models
Toggle main menu visibility
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
52
#include <
agrum/base/graphicalModels/inference/junctionTreeRoots.h
>
53
54
namespace
gum
{
55
56
NodeSet
junctionTreeRoots
(
const
JunctionTree
& jt,
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
();
64
HashTable< NodeId, std::pair< Key, NodeId >
> best;
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
gum::CliqueGraph::clique
const NodeSet & clique(const NodeId idClique) const
returns the set of nodes included into a given clique
gum::DiscreteVariable::domainSize
virtual Size domainSize() const =0
gum::GraphicalModel
Virtual base class for probabilistic graphical models.
Definition
graphicalModel.h:64
gum::GraphicalModel::variable
virtual const DiscreteVariable & variable(NodeId id) const =0
Returns a constant reference over a variable given it's node id.
gum::HashTable
The class for generic Hash Tables.
Definition
hashTable.h:640
gum::HashTable::insert
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
Definition
hashTable_tpl.h:754
gum::HashTable::tryGet
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.
Definition
hashTable_tpl.h:605
gum::NodeGraphPart::nodes
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
Definition
nodeGraphPart_inl.h:379
gum::Set::contains
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition
set_tpl.h:468
gum::Set::insert
void insert(const Key &k)
Inserts a new element into the set.
Definition
set_tpl.h:510
gum::UndiGraph::connectedComponents
NodeProperty< NodeId > connectedComponents() const
returns a property {node:id of weakly connected component}
Definition
undiGraph_inl.h:127
gum::NodeId
Size NodeId
Type for node ids.
Definition
graphElements.h:117
gum::NodeSet
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Definition
graphElements.h:392
junctionTreeRoots.h
Selection of the roots of the connected components of a junction tree.
gum
gum is the global namespace for all aGrUM entities
Definition
agrum.h:46
gum::junctionTreeRoots
NodeSet junctionTreeRoots(const JunctionTree &jt, const GraphicalModel &model, const NodeSet &preferred)
Returns one root for each connected component of a junction tree.
Definition
junctionTreeRoots.cpp:56
gum::JunctionTree
CliqueGraph JunctionTree
a junction tree is a clique graph satisfying the running intersection property and such that no cliqu...
Definition
cliqueGraph.h:353
aGrUM
3.3.2
© PHW&CG&others - 2022
DoXyGeN 1.18.0