aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
essentialGraph.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
51
52#ifdef GUM_NO_INLINE
54#endif // GU%_NO_INLINE
55
56namespace gum {
58
60
65
67 if (&g != this) {
70 }
71 return *this;
72 }
73
75
77 MixedGraph mg; // during the process, the graph may not be a PDAG
78 _pdag_.clear();
79 if (_dagmodel_ == nullptr) return;
80
81 for (const auto& node: _dagmodel_->nodes()) {
82 mg.addNodeWithId(node);
84 }
85 for (const auto& arc: _dagmodel_->arcs()) {
86 mg.addArc(arc.tail(), arc.head());
87 }
88
89 std::vector< Arc > v;
90 do {
91 v.clear();
92 for (const auto x: _dagmodel_->topologicalOrder())
93 for (const auto y: mg.children(x))
94 if (!_strongly_protected_(mg, x, y)) v.emplace_back(x, y);
95
96 for (const auto& arc: v) {
97 mg.eraseArc(arc);
98 mg.addEdge(arc.tail(), arc.head());
99 }
100 } while (!v.empty());
101
102 for (const auto& arc: mg.arcs()) {
103 _pdag_.addArc(arc.tail(), arc.head());
104 }
105 for (const auto& edge: mg.edges()) {
106 _pdag_.addEdge(edge.first(), edge.second());
107 }
108
109 for (auto id: _pdag_)
110 _pdag_.setName(id, _dagmodel_->variable(id).name());
111 }
112
116
118 // testing a->b from
119 // A Characterization of Markov Equivalence Classes for Acyclic Digraphs (2001)
120 // Steen A. Andersson, David Madigan, and Michael D. Perlman*
121
122 // condition (a)
123 for (const auto& c: mg.parents(a)) {
124 if (!mg.existsArc(c, b)) { return true; }
125 }
126
127
128 for (const auto& c: mg.parents(b)) {
129 if (c == a) { continue; }
130 // condition (c)
131 if (mg.existsArc(a, c)) { return true; }
132
133 // condition (b) knowing that a can not be a parent of c (condition below)
134 if (!mg.existsEdge(a, c) && !mg.existsArc(c, a)) { return true; }
135 }
136
137 // condition (d)
138 bool oneFound = false;
139 for (const auto& c: mg.parents(b)) {
140 if (c == a) { continue; }
141 // condition (d)
142 if (mg.existsEdge(c, a)) {
143 if (oneFound) { // this is the second found
144 return true;
145 }
146 oneFound = true;
147 }
148 }
149
150 return false;
151 }
152
153 std::string EssentialGraph::toDot() const { return toDot(dot::DotOptions()); }
154
155 std::string EssentialGraph::toDot(const dot::DotOptions& options) const {
156 const auto style = dot::DotStyle::read();
157 dot::DotWriter writer(true);
158 dot::writePreamble(writer, style, options);
159
160 if (_dagmodel_ != nullptr) {
161 for (const auto node: _pdag_.nodes()) {
162 const auto& name = _dagmodel_->variable(node).name();
163 writer.node(node,
165 options.node(node),
166 name,
167 "(" + std::to_string(node) + ") " + name));
168 }
169
170 for (const auto& edge: _pdag_.edges()) {
171 auto attributes = dot::arcAttributes(options.edge(edge.first(), edge.second()));
172 attributes.insert(attributes.begin(), {"dir", "none"});
173 writer.edge(edge.first(), edge.second(), attributes);
174 }
175
176 // the arcs which are in every DAG of the equivalence class are in red
177 for (const auto& arc: _pdag_.arcs()) {
178 auto attributes = dot::arcAttributes(options.arc(arc.tail(), arc.head()));
179 dot::addDefaultAttribute(attributes, "color", "red");
180 writer.edge(arc.tail(), arc.head(), attributes);
181 }
182 }
183
184 return writer.str();
185 }
186
188 UndiGraph skel;
189 for (const auto& n: nodes())
190 skel.addNodeWithId(n);
191 for (const auto& edge: edges())
192 skel.addEdge(edge.first(), edge.second());
193 for (const auto& arc: arcs())
194 skel.addEdge(arc.tail(), arc.head());
195 if (_dagmodel_ != nullptr)
196 for (auto id: skel)
197 skel.setName(id, _dagmodel_->variable(id).name());
198 return skel;
199 }
200} // namespace gum
bool existsArc(const Arc &arc) const
indicates whether a given arc exists
const NodeSet & parents(NodeId id) const
returns the set of nodes with arc ingoing to a given node
NodeSet children(const NodeSet &ids) const
returns the set of nodes which consists in the node and its parents returns the set of children of a ...
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
const ArcSet & arcs() const
returns the set of arcs stored within the ArcGraphPart
Virtual base class for PGMs using a DAG.
Definition DAGmodel.h:64
const ArcSet & arcs() const
return true if the arc tail->head exists in the DAGmodel
Sequence< NodeId > topologicalOrder() const
The topological order stays the same as long as no variable or arcs are added or erased src the topol...
const NodeGraphPart & nodes() const final
Returns a named copy of the internal DAG: each node id is assigned the name of the corresponding vari...
void addArc(const NodeId tail, const NodeId head) override
insert a new arc into the directed graph
Definition diGraph_inl.h:59
const DiscreteVariable & variable(NodeId id) const override
Returns a constant reference over a variable given its node id.
const EdgeSet & edges() const
returns the set of edges stored within the EdgeGraphPart
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
const ArcSet & arcs() const
wrapping MixedGraph::arcs()
const DAGmodel * _dagmodel_
UndiGraph skeleton() const
const NodeGraphPart & nodes() const
wrapping MixedGraph::nodes()
EssentialGraph & operator=(const EssentialGraph &g)
bool _strongly_protected_(NodeId a, NodeId b) const
EssentialGraph()=default
std::string toDot() const
const EdgeSet & edges() const
wrapping MixedGraph::edges()
Base class for mixed graphs.
Definition mixedGraph.h:150
void clear() override
removes all the nodes, arcs and edges from the graph
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
void setName(NodeId id, const std::string &name)
sets the name of node id
virtual void addNodeWithId(const NodeId id)
try to insert a node with the given id
Base class for partially directed acyclic graphs.
Definition PDAG.h:134
void addEdge(NodeId first, NodeId second) final
insert a new edge into the partially directed graph
Definition PDAG_inl.h:93
void addArc(NodeId tail, NodeId head) final
insert a new arc into the directed graph
Definition PDAG_inl.h:75
Base class for undirected graphs.
Definition undiGraph.h:134
void addEdge(NodeId first, NodeId second) override
insert a new edge into the undirected graph
const std::string & name() const
returns the name of the variable
The options given to a toDot(const DotOptions&).
Definition dotOptions.h:110
const DotArcOptions * arc(Size tail, Size head) const
the options of the arc from tail to head, or nullptr if none was given for it
const DotArcOptions * edge(Size a, Size b) const
the options of the undirected edge between a and b, given for (a, b) or for (b, a),...
const DotNodeOptions * node(Size node) const
the options of a node, or nullptr if none was given for it
Writes a graph in the dot language, statement after statement, in the order of the calls.
Definition dotWriter.h:100
void edge(std::string_view from, std::string_view to, const DotAttributes &attributes={})
an edge from from to to (-> in a directed graph, -- in an undirected one).
std::string str() const
The graph written so far, closed. It can be called at any moment, and the writer can be used after.
void node(std::string_view id, const DotAttributes &attributes={})
a node, whose identifier is id (quoted).
The statements common to the graphs drawn with graphviz : preamble, attributes of nodes and arcs.
Class building the essential Graph from a DAGmodel.
Inline implementation of the class building the essential Graph from a DAGmodel.
Size NodeId
Type for node ids.
DotAttributes nodeAttributes(const DotStyle &style, const DotNodeOptions *options, std::string_view defaultLabel, std::string_view defaultTooltip)
The attributes of a node : its label and tooltip, and its colors if the options give some.
void writePreamble(DotWriter &writer, const DotStyle &style, const DotOptions &options, std::string_view defaultLabel)
Writes the beginning of a graph, as pyAgrum displays it.
void addDefaultAttribute(DotAttributes &attributes, std::string_view key, std::string_view value)
Adds an attribute at the beginning of the list, unless the list already gives a value for this key : ...
DotAttributes arcAttributes(const DotArcOptions *options)
The attributes of an arc or an edge given by the options : color, penwidth, label,...
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
static DotStyle read()
the style of the graphs of the section notebook
Definition dotStyle.cpp:89