aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
diGraph.h
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#ifndef GUM_DIGRAPH_H
48#define GUM_DIGRAPH_H
49
50#include <iostream>
51#include <optional>
52#include <sstream>
53#include <utility>
54
55#include <agrum/agrum.h>
56
61
62namespace gum {
63
64 namespace dot {
65 class DotOptions;
66 } // namespace dot
67
68 /* ===========================================================================
69 */
70 /* === BASE CLASS FOR MANIPULATING ALL DIRECTED GRAPHS ===
71 */
72 /* ===========================================================================
73 */
134 /* ===========================================================================
135 */
136 class GUM_SHARED_PUBLIC DiGraph: public virtual NodeGraphPart, public ArcGraphPart {
137 public:
138 // ############################################################################
140 // ############################################################################
142
144
148 explicit DiGraph(Size nodes_size = HashTableConst::default_size,
149 bool nodes_resize_policy = true,
151 bool arcs_resize_policy = true);
152
154
155 DiGraph(const DiGraph& g);
156
158 DiGraph(DiGraph&& g);
159
161 ~DiGraph() override;
162
168 static DiGraph completeGraph(int n);
169
171
172 // ############################################################################
174 // ############################################################################
176
178
179 DiGraph& operator=(const DiGraph& g);
180
183
185
186 // not virtual : it is a feature !!! :)
187 bool operator==(const DiGraph& g) const;
188
190
191 // not virtual : it is a feature !!! :)
192 // bool operator!=(const DiGraph& g) const;
193
195
196 // ############################################################################
198 // ############################################################################
200
202
207 void addArc(const NodeId tail, const NodeId head) override;
208
210
213 void eraseNode(const NodeId id) override;
214
216 void clear() override;
217
219 std::string toString() const override;
220
222
224 virtual std::string toDot() const;
225
228 virtual std::string toDot(const dot::DotOptions& options) const;
229
237
247 bool hasDirectedPath(NodeId from, NodeId to) const;
248
250 std::optional< std::vector< NodeId > > directedPath(NodeId node1, NodeId node2) const;
251
254 std::optional< std::vector< NodeId > > directedUnorientedPath(NodeId node1, NodeId node2) const;
255
257 NodeSet ancestors(NodeId id) const;
258
260 NodeSet descendants(NodeId id) const;
261
263 NodeSet family(NodeId id) const;
264
266 NodeSet family(const NodeSet& ids) const;
267
270 };
271
273 GUM_SHARED_PUBLIC std::ostream& operator<<(std::ostream&, const DiGraph&);
274
275} /* namespace gum */
276
278
279#ifndef GUM_NO_INLINE
281#endif // GU%_NO_INLINE
282
283#endif /* GUM_DIGRAPH_H */
ArcGraphPart(Size arcs_size=HashTableConst::default_size, bool arcs_resize_policy=true)
default constructor
Base class for all oriented graphs.
Definition diGraph.h:136
NodeSet ancestors(NodeId id) const
returns the set of all ancestors of id (nodes from which id is reachable)
NodeSet family(NodeId id) const
returns { id } ∪ parents(id)
bool hasDirectedPath(NodeId from, NodeId to) const
checks whether there exists a directed path from from to to
Definition diGraph.cpp:114
std::optional< std::vector< NodeId > > directedPath(NodeId node1, NodeId node2) const
returns a directed path from node1 to node2, or std::nullopt if none
static DiGraph completeGraph(int n)
Build a complete DiGraph with n nodes.
Definition diGraph.cpp:59
virtual std::string toDot() const
to friendly display the content of the graph in the DOT syntax
Definition diGraph.cpp:94
DiGraph & operator=(const DiGraph &g)
copy operator
Definition diGraph_inl.h:72
void clear() override
removes all the nodes and arcs from the graph
Definition diGraph_inl.h:67
void addArc(const NodeId tail, const NodeId head) override
insert a new arc into the directed graph
Definition diGraph_inl.h:59
NodeProperty< NodeId > connectedComponents() const
returns a property {node:id of weakly connected component}
DiGraph(Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size arcs_size=HashTableConst::default_size, bool arcs_resize_policy=true)
default constructor
Definition diGraph.cpp:71
void eraseNode(const NodeId id) override
remove a node and its adjacent arcs from the graph
Definition diGraph_inl.h:93
Sequence< NodeId > topologicalOrder() const
Build and return a topological order.
bool operator==(const DiGraph &g) const
tests whether two DiGraphs are identical (same nodes, same arcs)
NodeSet descendants(NodeId id) const
returns the set of all descendants of id (nodes reachable from id)
std::optional< std::vector< NodeId > > directedUnorientedPath(NodeId node1, NodeId node2) const
returns a shortest path from node1 to node2 ignoring arc orientation, or std::nullopt if none
std::string toString() const override
to friendly display the content of the graph
Definition diGraph.cpp:87
NodeGraphPart(Size holes_size=HashTableConst::default_size, bool holes_resize_policy=true)
default constructor
The options given to a toDot(const DotOptions&).
Definition dotOptions.h:110
Concept for directed graphs (arcs with parents/children).
Inline implementation of Base classes for oriented graphs.
C++20 concepts for aGrUM graph interfaces.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74
Size NodeId
Type for node ids.
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
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
Base node set class for graphs.
Header file of gum::Sequence, a class for storing (ordered) sequences of objects.
static constexpr Size default_size
The default number of slots in hashtables.
Definition hashTable.h:102