aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
undiGraph.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_UNDIGRAPH_H
48#define GUM_UNDIGRAPH_H
49
50#include <iostream>
51#include <optional>
52#include <utility>
53
54#include <agrum/agrum.h>
55
59
60namespace gum {
61
62 namespace dot {
63 class DotOptions;
64 } // namespace dot
65
66 /* ===========================================================================
67 */
68 /* === BASE CLASS FOR MANIPULATING ALL UNDIRECTED GRAPHS ===
69 */
70 /* ===========================================================================
71 */
131 /* ===========================================================================
132 */
133
134 class GUM_SHARED_PUBLIC UndiGraph: public virtual NodeGraphPart, public EdgeGraphPart {
135 public:
136 // ############################################################################
138 // ############################################################################
140
142
146 explicit UndiGraph(Size nodes_size = HashTableConst::default_size,
147 bool nodes_resize_policy = true,
149 bool edges_resize_policy = true);
150
152
153 UndiGraph(const UndiGraph& g);
154
156 UndiGraph(UndiGraph&& g);
157
159 ~UndiGraph() override;
160
166 static UndiGraph completeGraph(int n);
167
169
170 // ############################################################################
172 // ############################################################################
174
176
177 UndiGraph& operator=(const UndiGraph& g);
178
181
183
184 // not virtual : it is a feature !!! :)
185 bool operator==(const UndiGraph& g) const;
186
188 // ############################################################################
190 // ############################################################################
192
194
201 void addEdge(NodeId first, NodeId second) override;
202
204
207 void eraseNode(NodeId id) override;
208
210 void clear() override;
211
213 std::string toString() const override;
214
216 virtual std::string toDot() const;
217
219 virtual std::string toDot(const dot::DotOptions& options) const;
220
222 bool hasUndirectedCycle() const;
223
226
229
232
234 std::optional< std::vector< NodeId > > undirectedPath(NodeId node1, NodeId node2) const;
235
237 bool hasUndirectedPath(NodeId n1, NodeId n2) const;
238
240
241 bool hasUndirectedPath(NodeId n1, NodeId n2, const NodeSet& except) const;
242
244 bool hasUndirectedPath(const NodeSet& n1, const NodeSet& n2, const NodeSet& except) const;
245
247 };
248
250 GUM_SHARED_PUBLIC std::ostream& operator<<(std::ostream&, const UndiGraph&);
251
252} /* namespace gum */
253
255
256#ifndef GUM_NO_INLINE
258#endif // GU%_NO_INLINE
259
260#endif /* GUM_UNDIGRAPH_H */
EdgeGraphPart(Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
default constructor
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
NodeGraphPart(Size holes_size=HashTableConst::default_size, bool holes_resize_policy=true)
default constructor
Base class for undirected graphs.
Definition undiGraph.h:134
bool operator==(const UndiGraph &g) const
tests whether two UndiGraphs are identical (same nodes, same edges)
UndiGraph & operator=(const UndiGraph &g)
copy operator
void clear() override
removes all the nodes and edges from the graph
NodeProperty< NodeId > chainComponents() const
returns a property {node:id of chain component} (edges only)
virtual std::string toDot() const
to friendly display graph in DOT format
static UndiGraph completeGraph(int n)
create a complete UndiGraph with n nodes
Definition undiGraph.cpp:62
void addEdge(NodeId first, NodeId second) override
insert a new edge into the undirected graph
bool hasUndirectedPath(NodeId n1, NodeId n2) const
returns true if n1 and n2 are connected by an undirected path
bool hasUndirectedCycle() const
checks whether the graph contains cycles
NodeProperty< NodeId > connectedComponents() const
returns a property {node:id of weakly connected component}
std::string toString() const override
to friendly display the content of the graph
Definition undiGraph.cpp:96
std::optional< std::vector< NodeId > > undirectedPath(NodeId node1, NodeId node2) const
returns a shortest undirected path from node1 to node2, or std::nullopt if none
virtual UndiGraph partialUndiGraph(NodeSet nodes)
returns the partial graph formed by the nodes given in parameter
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
Concept for undirected graphs (edges with neighbours).
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.
static constexpr Size default_size
The default number of slots in hashtables.
Definition hashTable.h:102
Inline implementation of Base classes for undirected graphs.