aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
PAG.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
47#include <sstream>
48
51
52namespace gum {
53
54 // ##########################################################################
55 // Constructors / Destructors
56 // ##########################################################################
57
58 PAG::PAG() { GUM_CONSTRUCTOR(PAG); }
59
60 PAG::PAG(const PAG& other) : NodeGraphPart(other), UndiGraph(other), marks_(other.marks_) {
61 GUM_CONS_CPY(PAG);
62 }
63
64 PAG::PAG(PAG&& other) noexcept :
65 NodeGraphPart(std::move(other)), UndiGraph(std::move(other)),
66 marks_(std::move(other.marks_)) {
67 GUM_CONS_MOV(PAG);
68 }
69
70 PAG::~PAG() { GUM_DESTRUCTOR(PAG); }
71
72 PAG& PAG::operator=(const PAG& other) {
73 if (this != &other) {
75 marks_ = other.marks_;
76 }
77 return *this;
78 }
79
80 PAG& PAG::operator=(PAG&& other) noexcept {
81 if (this != &other) {
82 UndiGraph::operator=(std::move(other));
83 marks_ = std::move(other.marks_);
84 }
85 return *this;
86 }
87
88 // ##########################################################################
89 // Edge operations
90 // ##########################################################################
91
93
94 void PAG::addEdge(NodeId x, NodeId y, EdgeMark markAtX, EdgeMark markAtY) {
95 if (existsEdge(x, y)) { return; }
97 // marks_[Arc(x,y)] = mark at y; marks_[Arc(y,x)] = mark at x
98 marks_.insert(Arc(x, y), markAtY);
99 marks_.insert(Arc(y, x), markAtX);
100 }
101
102 void PAG::eraseEdge(const Edge& e) {
103 if (!existsEdge(e)) { return; }
104 if (marks_.exists(Arc(e.first(), e.second()))) { marks_.erase(Arc(e.first(), e.second())); }
105 if (marks_.exists(Arc(e.second(), e.first()))) { marks_.erase(Arc(e.second(), e.first())); }
107 }
108
110 marks_.clear();
112 }
113
115 if (existsNode(id)) {
116 // unvirtualizedEraseNeighbours (called by UndiGraph::eraseNode) bypasses
117 // PAG::eraseEdge, so we clean marks manually before delegating
118 for (const NodeId nb: neighbours(id)) {
119 if (marks_.exists(Arc(id, nb))) { marks_.erase(Arc(id, nb)); }
120 if (marks_.exists(Arc(nb, id))) { marks_.erase(Arc(nb, id)); }
121 }
122 }
124 }
125
126 void PAG::clear() {
127 marks_.clear();
129 }
130
131 // ##########################################################################
132 // Mark accessors
133 // ##########################################################################
134
135 EdgeMark PAG::markAt(NodeId src, NodeId dst) const { return marks_[Arc(src, dst)]; }
136
137 void PAG::setMarkAt(NodeId src, NodeId dst, EdgeMark m) { marks_.set(Arc(src, dst), m); }
138
139 // ##########################################################################
140 // Predicates
141 // ##########################################################################
142
143 bool PAG::isArrowhead(NodeId src, NodeId dst) const {
144 return markAt(src, dst) == EdgeMark::Arrowhead;
145 }
146
147 bool PAG::isTail(NodeId src, NodeId dst) const { return markAt(src, dst) == EdgeMark::Tail; }
148
149 bool PAG::isCircle(NodeId src, NodeId dst) const { return markAt(src, dst) == EdgeMark::Circle; }
150
152 // Tail at x (from y's perspective) and Arrowhead at y (from x's perspective)
153 return isTail(y, x) && isArrowhead(x, y);
154 }
155
156 bool PAG::isBidirected(NodeId x, NodeId y) const {
157 return isArrowhead(x, y) && isArrowhead(y, x);
158 }
159
161 // z is a definite collider on x-z-y iff both endpoints at z are Arrowhead
162 return isArrowhead(x, z) && isArrowhead(y, z);
163 }
164
165 // ##########################################################################
166 // Bulk operations
167 // ##########################################################################
168
170 for (const Edge& e: edges()) {
171 setMarkAt(e.first(), e.second(), m);
172 setMarkAt(e.second(), e.first(), m);
173 }
174 }
175
176 // ##########################################################################
177 // Conversion / display
178 // ##########################################################################
179
181 MixedGraph g;
182 for (const NodeId n: nodes()) {
183 g.addNodeWithId(n);
184 }
185
186 for (const Edge& e: edges()) {
187 const NodeId x = e.first();
188 const NodeId y = e.second();
189 const bool xArrow = isArrowhead(y, x); // arrowhead at x-endpoint
190 const bool yArrow = isArrowhead(x, y); // arrowhead at y-endpoint
191 if (xArrow && yArrow) {
192 g.addArc(x, y);
193 g.addArc(y, x);
194 } else if (yArrow) {
195 g.addArc(x, y);
196 } else if (xArrow) {
197 g.addArc(y, x);
198 } else {
199 g.addEdge(x, y);
200 }
201 }
202 return g;
203 }
204
205 namespace {
206 char markChar(EdgeMark m) {
207 switch (m) {
208 case EdgeMark::Circle : return 'o';
209 case EdgeMark::Tail : return '-';
210 case EdgeMark::Arrowhead : return '>';
211 }
212 return '?';
213 }
214 } // namespace
215
216 std::string PAG::toString() const {
217 std::ostringstream s;
218 s << std::format("PAG{{nodes: {}, edges: [", NodeGraphPart::toString());
219 bool first = true;
220 for (const Edge& e: edges()) {
221 if (!first) { s << ", "; }
222 first = false;
223 const NodeId x = e.first();
224 const NodeId y = e.second();
225 s << std::format("{} {}--{} {}", x, markChar(markAt(y, x)), markChar(markAt(x, y)), y);
226 }
227 s << "]}";
228 return s.str();
229 }
230
231 std::string PAG::toDot() const { return toDot(dot::DotOptions()); }
232
233 std::string PAG::toDot(const dot::DotOptions& options) const {
234 const auto style = dot::DotStyle::read();
235 dot::DotWriter writer(true);
236 dot::writePreamble(writer, style, options);
237 writeDotNodes(writer, style, options);
238
239 for (const Edge& e: edges()) {
240 const NodeId x = e.first();
241 const NodeId y = e.second();
242 const bool xArrow = isArrowhead(y, x);
243 const bool yArrow = isArrowhead(x, y);
244 const bool xCircle = isCircle(y, x);
245 const bool yCircle = isCircle(x, y);
246
247 const std::string arrowhead = yArrow ? "normal" : (yCircle ? "odot" : "none");
248 const std::string arrowtail = xArrow ? "normal" : (xCircle ? "odot" : "none");
249
250 auto attributes = dot::arcAttributes(options.edge(x, y));
251 attributes.insert(attributes.begin(),
252 {{"dir", "both"}, {"arrowhead", arrowhead}, {"arrowtail", arrowtail}});
253 writer.edge(x, y, attributes);
254 }
255
256 return writer.str();
257 }
258
259 std::ostream& operator<<(std::ostream& stream, const PAG& g) {
260 stream << g.toString();
261 return stream;
262 }
263
264} /* namespace gum */
Partial Ancestral Graph (PAG) — graph type for FCI output.
The base class for all directed edges.
Arc(NodeId tail, NodeId head)
basic constructor. Creates tail -> head.
void addArc(const NodeId tail, const NodeId head) override
insert a new arc into the directed graph
Definition diGraph_inl.h:59
virtual void eraseEdge(const Edge &edge)
removes an edge from the EdgeGraphPart
const EdgeSet & edges() const
returns the set of edges stored within the EdgeGraphPart
virtual void clearEdges()
removes all the edges from the EdgeGraphPart
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
const NodeSet & neighbours(NodeId id) const
returns the set of node neighbours to a given node
The base class for all undirected edges.
GUM_NODISCARD NodeId first() const
returns one extremal node ID (whichever one it is is unspecified)
GUM_NODISCARD NodeId second() const
returns the node ID of the other extremal node ID
Base class for mixed graphs.
Definition mixedGraph.h:150
Class for node sets in graph.
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
void writeDotNodes(dot::DotWriter &writer, const dot::DotStyle &style, const dot::DotOptions &options) const
writes the nodes in the dot language, see writeDotNode()
virtual std::string toString() const
a function to display the set of nodes
NodeGraphPart(Size holes_size=HashTableConst::default_size, bool holes_resize_policy=true)
default constructor
bool existsNode(const NodeId id) const
returns true iff the NodeGraphPart contains the given nodeId
virtual void addNodeWithId(const NodeId id)
try to insert a node with the given id
Partial Ancestral Graph: undirected topology with endpoint marks.
Definition PAG.h:94
bool isCircle(NodeId src, NodeId dst) const
true if mark at dst (from src) is Circle
Definition PAG.cpp:149
bool isBidirected(NodeId x, NodeId y) const
true if edge x-y is bidirected x↔y (Arrowhead on both endpoints)
Definition PAG.cpp:156
bool isDefCollider(NodeId x, NodeId z, NodeId y) const
true if z is a definite collider on path x-z-y (Arrowhead at z from both sides)
Definition PAG.cpp:160
PAG & operator=(const PAG &)
Definition PAG.cpp:72
void clear() override
remove all nodes, edges, and marks
Definition PAG.cpp:126
void reorientAllWith(EdgeMark m)
set all endpoint marks to m (used between FCI phases to reset to Circle)
Definition PAG.cpp:169
PAG()
Definition PAG.cpp:58
ArcProperty< EdgeMark > marks_
marks_[Arc(x,y)] = mark at y-endpoint of edge x-y
Definition PAG.h:202
void addEdge(NodeId x, NodeId y) override
add edge with Circle-Circle marks
Definition PAG.cpp:92
void setMarkAt(NodeId src, NodeId dst, EdgeMark m)
set mark at dst-endpoint when traversing from src
Definition PAG.cpp:137
bool isTail(NodeId src, NodeId dst) const
true if mark at dst (from src) is Tail
Definition PAG.cpp:147
void eraseEdge(const Edge &e) override
remove edge and its two mark entries
Definition PAG.cpp:102
EdgeMark markAt(NodeId src, NodeId dst) const
mark at dst-endpoint when traversing from src
Definition PAG.cpp:135
std::string toDot() const override
approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; ...
Definition PAG.cpp:231
void clearEdges() override
clear all edges (and their marks)
Definition PAG.cpp:109
bool isArrowhead(NodeId src, NodeId dst) const
true if mark at dst (from src) is Arrowhead
Definition PAG.cpp:143
~PAG() override
Definition PAG.cpp:70
MixedGraph toMixedGraph() const
approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; ...
Definition PAG.cpp:180
bool isDefinitelyDirected(NodeId x, NodeId y) const
true if edge x-y is definitely directed x→y (Tail@x, Arrowhead@y)
Definition PAG.cpp:151
void eraseNode(NodeId id) override
remove node and clean up marks for all its adjacent edges
Definition PAG.cpp:114
std::string toString() const override
approximate conversion for learnDAG/learnPDAG: Tail-Arrowhead → arc; Arrowhead-Arrowhead → two arcs; ...
Definition PAG.cpp:216
UndiGraph & operator=(const UndiGraph &g)
copy operator
void clear() override
removes all the nodes and edges from the graph
void addEdge(NodeId first, NodeId second) override
insert a new edge into the undirected graph
void eraseNode(NodeId id) override
remove a node and its adjacent edges from the graph
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
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).
The statements common to the graphs drawn with graphviz : preamble, attributes of nodes and arcs.
Size NodeId
Type for node ids.
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,...
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
EdgeMark
Endpoint marks used in PAG edges.
Definition PAG.h:69
@ Arrowhead
Definition PAG.h:69
static DotStyle read()
the style of the graphs of the section notebook
Definition dotStyle.cpp:89