aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
PDAG.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
52
53#ifdef GUM_NO_INLINE
55#endif // GUM_NO_INLINE
56
57namespace gum {
58
59 // diamond structure require to explicitly initialize NodeGraphPart
60 PDAG::PDAG(Size nodes_size,
61 bool nodes_resize_policy,
62 Size arcs_size,
63 bool arcs_resize_policy,
64 Size edges_size,
65 bool edges_resize_policy) :
66 NodeGraphPart(nodes_size, nodes_resize_policy), MixedGraph(nodes_size,
67 nodes_resize_policy,
68 arcs_size,
69 arcs_resize_policy,
70 edges_size,
71 edges_resize_policy) {
72 GUM_CONSTRUCTOR(PDAG);
73 }
74
75 PDAG::PDAG(const UndiGraph& g) : NodeGraphPart(g), MixedGraph(g) { GUM_CONSTRUCTOR(PDAG); }
76
77 PDAG::PDAG(const DAG& g) : NodeGraphPart(g), MixedGraph(g) { GUM_CONSTRUCTOR(PDAG); }
78
79 PDAG::PDAG(const MixedGraph& g) : NodeGraphPart(g), MixedGraph(g) { GUM_CONS_CPY(PDAG); }
80
81 PDAG::PDAG(const PDAG& g) : NodeGraphPart(g), MixedGraph(g) { GUM_CONS_CPY(PDAG); }
82
83 PDAG::PDAG(PDAG&& g) : NodeGraphPart(std::move(g)), MixedGraph(std::move(g)) {
84 GUM_CONS_MOV(PDAG);
85 }
86
87 PDAG::~PDAG() { GUM_DESTRUCTOR(PDAG); }
88
89 UndiGraph PDAG::moralGraph() const { return graph::moralGraph(*this); }
90
92 NodeSet& marked,
93 NodeId node,
94 NodeId goal,
95 bool alreadyOriented) {
96 if (node == goal) return alreadyOriented;
97 if (marked.contains(node)) return false;
98 marked.insert(node);
99 for (const auto nod: gr.children(node))
100 if (rec_hasMixedReallyOrientedPath(gr, marked, nod, goal, true)) return true;
101 for (const auto nod: gr.neighbours(node))
102 if (rec_hasMixedReallyOrientedPath(gr, marked, nod, goal, alreadyOriented)) return true;
103 return false;
104 }
105
107 if (n1 == n2) return false;
108 NodeSet marked; // marked as already explored
109 for (const auto nod: this->children(n1))
110 if (rec_hasMixedReallyOrientedPath(*this, marked, nod, n2, true)) return true;
111
112 for (const auto nod: this->neighbours(n1))
113 if (rec_hasMixedReallyOrientedPath(*this, marked, nod, n2, false)) return true;
114
115 return false;
116 }
117
121
122 bool PDAG::cSeparation(NodeId X, NodeId Y, const NodeSet& Z) const {
123 return graph::cSeparated(*this, X, Y, Z);
124 }
125
126 bool PDAG::cSeparation(const NodeSet& X, const NodeSet& Y, const NodeSet& Z) const {
127 return graph::cSeparated(*this, X, Y, Z);
128 }
129
130 std::string PDAG::toDot() const { return toDot(dot::DotOptions()); }
131
132 std::string PDAG::toDot(const dot::DotOptions& options) const {
133 const auto style = dot::DotStyle::read();
134 dot::DotWriter writer(true);
135 dot::writePreamble(writer, style, options);
136
137 // the nodes without undirected edge, then one cluster for each chain component
138 NodeSet treatedNodes;
139 for (const auto node: nodes()) {
140 if (neighbours(node).empty()) {
141 writeDotNode(writer, style, options, node);
142 treatedNodes.insert(node);
143 }
144 }
145
146 int cluster = 0;
147 for (const auto node: nodes()) {
148 if (treatedNodes.exists(node)) continue;
149 writer.beginSubgraph("cluster_" + std::to_string(cluster++),
150 {{"style", "filled"}, {"color", "#F5F5F5"}, {"rank", "same"}});
151 for (const auto cc: chainComponent(node)) {
152 writeDotNode(writer, style, options, cc);
153 treatedNodes.insert(cc);
154 }
155 writer.endSubgraph();
156 }
157
158 for (const auto& arc: arcs())
159 writer.edge(arc.tail(), arc.head(), dot::arcAttributes(options.arc(arc.tail(), arc.head())));
160
161 for (const auto& edge: edges()) {
162 auto attributes = dot::arcAttributes(options.edge(edge.first(), edge.second()));
163 attributes.insert(attributes.begin(), {"dir", "none"});
164 writer.edge(edge.first(), edge.second(), attributes);
165 }
166
167 return writer.str();
168 }
169
170} /* namespace gum */
Base classes for partially directed acyclic graphs.
Inline implementation of Base classes for directed acylic graphs.
d-Separation and c-Separation tests for aGrUM graphs.
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 ...
const ArcSet & arcs() const
returns the set of arcs stored within the ArcGraphPart
Base class for dag.
Definition DAG.h:121
const EdgeSet & edges() const
returns the set of edges stored within the EdgeGraphPart
const NodeSet & neighbours(NodeId id) const
returns the set of node neighbours to a given node
NodeSet chainComponent(NodeId node) const
returns the set of nodes reachable by undirected path
MixedGraph(Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size arcs_size=HashTableConst::default_size, bool arcs_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
Class for node sets in graph.
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
bool empty() const
alias for emptyNodes
void writeDotNode(dot::DotWriter &writer, const dot::DotStyle &style, const dot::DotOptions &options, NodeId id) const
writes a node in the dot language, with the label "(id) name" if it is named and the colors given by ...
Base class for partially directed acyclic graphs.
Definition PDAG.h:134
std::string toDot() const override
to friendly display mixed graph in DOT format
Definition PDAG.cpp:130
UndiGraph moralizedAncestralGraph(const NodeSet &nodes) const
build a UndiGraph by moralizing the Ancestral Graph of a set of Nodes
Definition PDAG.cpp:118
PDAG(Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size arcs_size=HashTableConst::default_size, bool arcs_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
Definition PDAG.cpp:60
UndiGraph moralGraph() const
build a UndiGraph by moralizing the PDAG
Definition PDAG.cpp:89
~PDAG() override
destructor
Definition PDAG.cpp:87
bool hasMixedReallyOrientedPath(NodeId n1, NodeId n2) const
returns true if a mixed edge/directed arc path from node1 to node2 in the arc/edge set exists with at...
Definition PDAG.cpp:106
bool cSeparation(NodeId X, NodeId Y, const NodeSet &Z) const
check if node X and node Y are independent given nodes Z (in the sense of c-separation)
Definition PDAG.cpp:122
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition set_tpl.h:468
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition set_tpl.h:504
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
Base class for undirected graphs.
Definition undiGraph.h:134
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),...
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).
void endSubgraph()
Closes the last subgraph that is open.
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 beginSubgraph(std::string_view name, const DotAttributes &attributes={})
Opens a subgraph : subgraph "name" { key="value"; ... .
The statements common to the graphs drawn with graphviz : preamble, attributes of nodes and arcs.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74
Size NodeId
Type for node ids.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Moralization algorithms for aGrUM directed and mixed graphs.
void writePreamble(DotWriter &writer, const DotStyle &style, const DotOptions &options, std::string_view defaultLabel)
Writes the beginning of a graph, as pyAgrum displays it.
DotAttributes arcAttributes(const DotArcOptions *options)
The attributes of an arc or an edge given by the options : color, penwidth, label,...
bool cSeparated(const G &g, NodeId X, NodeId Y, const NodeSet &Z)
Returns true iff X and Y are c-separated by Z in g.
UndiGraph moralizedAncestralGraph(const G &g, const NodeSet &query)
Returns the moralized ancestral graph of query in g.
UndiGraph moralGraph(const G &g)
Returns the moral graph of g.
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
bool rec_hasMixedReallyOrientedPath(const PDAG &gr, NodeSet &marked, NodeId node, NodeId goal, bool alreadyOriented)
Definition PDAG.cpp:91
STL namespace.
static DotStyle read()
the style of the graphs of the section notebook
Definition dotStyle.cpp:89