aGrUM 2.3.2
a C++ library for (probabilistic) graphical models
gum::DiGraph Class Reference
Graph representation

Base class for all oriented graphs. More...

#include <diGraph.h>

Inheritance diagram for gum::DiGraph:
Collaboration diagram for gum::DiGraph:

Public Types

using NodeIterator = NodeGraphPartIterator
using NodeConstIterator = NodeGraphPartIterator
using NodeIteratorSafe = NodeGraphPartIteratorSafe
using NodeConstIteratorSafe = NodeGraphPartIteratorSafe
using ArcIterator = ArcSetIterator
using node_iterator = NodeGraphPartIterator
 types for STL compliance
using node_const_iterator = NodeGraphPartIterator
 types for STL compliance
using node_iterator_safe = NodeGraphPartIteratorSafe
 types for STL compliance
using node_const_iterator_safe = NodeGraphPartIteratorSafe
 types for STL compliance

Public Member Functions

bool hasDirectedPath (NodeId from, NodeId to)
 checks whether there exists a directed path from from to to
Operators
DiGraph & operator= (const DiGraph &g)
 copy operator
bool operator== (const DiGraph &g) const
 tests whether two DiGraphs are identical (same nodes, same arcs)
Accessors/Modifiers

tests whether two DiGraphs are different

Parameters
gthe DiGraph with which "this" is compared
virtual void addArc (const NodeId tail, const NodeId head)
 insert a new arc into the directed graph
virtual void eraseNode (const NodeId id)
 remove a node and its adjacent arcs from the graph
virtual void clear ()
 removes all the nodes and arcs from the graph
virtual std::string toString () const
 to friendly display the content of the graph
virtual std::string toDot () const
 to friendly display the content of the graph in the DOT syntax
Sequence< NodeId > topologicalOrder () const
 Build and return a topological order.
Operators
bool operator== (const NodeGraphPart &p) const
 check whether two NodeGraphParts contain the same nodes
bool operator!= (const NodeGraphPart &p) const
 check whether two NodeGraphParts contain different nodes
Accessors/Modifiers
void populateNodes (const NodeGraphPart &s)
 populateNodes clears *this and fills it with the same nodes as "s"
template<typename T>
void populateNodesFromProperty (const NodeProperty< T > &h)
 populateNodesFromProperty clears *this and fills it with the keys of "h"
NodeId nextNodeId () const
 returns a new node id, not yet used by any node
virtual NodeId addNode ()
 insert a new node and return its id
std::vector< NodeId > addNodes (Size n)
 insert n nodes
virtual void addNodeWithId (const NodeId id)
 try to insert a node with the given id
bool existsNode (const NodeId id) const
 returns true iff the NodeGraphPart contains the given nodeId
bool exists (const NodeId id) const
 alias for existsNode
bool emptyNodes () const
 indicates whether there exists nodes in the NodeGraphPart
bool empty () const
 alias for emptyNodes
virtual void clearNodes ()
 remove all the nodes from the NodeGraphPart
Size sizeNodes () const
 returns the number of nodes in the NodeGraphPart
Size size () const
 alias for sizeNodes
NodeId bound () const
 returns a number n such that all node ids are strictly lower than n
NodeSet asNodeSet () const
 returns a copy of the set of nodes represented by the NodeGraphPart
const NodeGraphPart & nodes () const
 return *this as a NodeGraphPart
node_iterator_safe beginSafe () const
 a begin iterator to parse the set of nodes contained in the NodeGraphPart
const node_iterator_safe & endSafe () const noexcept
 the end iterator to parse the set of nodes contained in the NodeGraphPart
node_iterator begin () const noexcept
 a begin iterator to parse the set of nodes contained in the NodeGraphPart
const node_iterator & end () const noexcept
 the end iterator to parse the set of nodes contained in the NodeGraphPart
template<typename VAL>
NodeProperty< VAL > nodesPropertyFromFunction (VAL(*f)(const NodeId &), Size size=0) const
 a method to create a HashTable with key:NodeId and value:VAL
template<typename VAL>
NodeProperty< VAL > nodesPropertyFromVal (const VAL &a, Size size=0) const
 a method to create a hashMap with key:NodeId and value:VAL
template<typename VAL>
List< VAL > listMapNodes (VAL(*f)(const NodeId &)) const
 a method to create a list of VAL from a set of nodes (using for every nodee, say x, the VAL f(x))
Operators
bool operator== (const ArcGraphPart &p) const
 tests whether two ArcGraphParts contain the same arcs
Accessors/Modifiers
virtual void eraseArc (const Arc &arc)
 removes an arc from the ArcGraphPart
bool existsArc (const Arc &arc) const
 indicates whether a given arc exists
bool existsArc (NodeId tail, NodeId head) const
 indicates whether a given arc exists
bool emptyArcs () const
 indicates wether the ArcGraphPart contains any arc
void clearArcs ()
 removes all the arcs from the ArcGraphPart
Size sizeArcs () const
 indicates the number of arcs stored within the ArcGraphPart
const ArcSet & arcs () const
 returns the set of arcs stored within the ArcGraphPart
const NodeSet & parents (NodeId id) const
 returns the set of nodes with arc ingoing to a given node
NodeSet parents (const NodeSet &ids) const
 returns the set of parents of a set of nodes
NodeSet family (NodeId id) const
 returns the set of nodes which consists in the node and its parents
NodeSet family (const NodeSet &ids) const
 returns the set of family nodes of a set of nodes
NodeSet descendants (NodeId id) const
 returns the set of nodes with directed path outgoing from a given node
NodeSet ancestors (NodeId id) const
 returns the set of nodes with directed path ingoing to a given node
NodeSet children (const NodeSet &ids) const
 returns the set of children of a set of nodes
const NodeSet & children (NodeId id) const
 returns the set of nodes with arc outgoing from a given node
void eraseParents (NodeId id)
 erase all the parents of a given node
void unvirtualizedEraseParents (NodeId id)
 same function as eraseParents but without any virtual call to an erase
void eraseChildren (NodeId id)
 removes all the children of a given node
void unvirtualizedEraseChildren (NodeId id)
 same function as eraseChildren but without any virtual call to an erase
template<typename VAL>
ArcProperty< VAL > arcsProperty (VAL(*f)(const Arc &), Size size=0) const
 a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL f(x))
template<typename VAL>
ArcProperty< VAL > arcsProperty (const VAL &a, Size size=0) const
 a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL a)
template<typename VAL>
List< VAL > listMapArcs (VAL(*f)(const Arc &)) const
 a method to create a list of VAL from a set of arcs (using for every arc, say x, the VAL f(x))
std::vector< NodeId > directedPath (NodeId node1, NodeId node2) const
 returns a directed path from node1 to node2 belonging to the set of arcs
std::vector< NodeId > directedUnorientedPath (NodeId node1, NodeId node2) const
 returns an unoriented (directed) path from node1 to node2 in the arc set

Public Attributes

Signaler1< NodeId > onNodeAdded
Signaler1< NodeId > onNodeDeleted
Signaler2< NodeId, NodeId > onArcAdded
Signaler2< NodeId, NodeId > onArcDeleted

Protected Member Functions

void eraseSetOfArcs_ (const ArcSet &set)
 a (virtualized) function to remove a given set of arcs
void unvirtualizedEraseSetOfArcs_ (const ArcSet &set)
 similar to eraseSetOfArcs_ except that it is unvirtualized

Private Member Functions

void _updateEndIteratorSafe_ ()
 updating endIterator (always at max+1)
void _clearNodes_ ()
 code for clearing nodes (called twice)
void _eraseHole_ (NodeId id)
 to delete hole.
void _addHole_ (NodeId id)
 to add a hole.
void _checkParents_ (NodeId id)
 when the ArcGraphPart contains no arc ingoing into a given node, this function adds an empty set entry to parents[id]
void _checkChildren_ (NodeId id)
 when the ArcGraphPart contains no arc outgoing from a given node, this function adds an empty set entry to children[id]
Introspection
bool _inHoles_ (NodeId id) const
Size _sizeHoles_ () const

Private Attributes

NodeSet * _holes_
 the set of nodes not contained in the NodeGraphPart in the interval 1.
Size _holes_size_
 value for holes configuration
bool _holes_resize_policy_
 value for holes configuration
NodeGraphPartIteratorSafe _endIteratorSafe_
 the end iterator (used to speed-up parsings of the NodeGraphPart)
NodeId _boundVal_
 the id below which NodeIds may belong to the NodeGraphPart
Set< Arc > _arcs_
 the set of all the arcs contained within the ArcGraphPart
NodeProperty< NodeSet * > _parents_
 for each arc, the sets of its parents
NodeProperty< NodeSet * > _children_
 for each arc, the set of its children

Constructors / Destructors

 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
 DiGraph (const DiGraph &g)
 copy constructor
virtual ~DiGraph ()
 destructor
static DiGraph completeGraph (int n)
 Build a complete DiGraph with n nodes.

Detailed Description

Base class for all oriented graphs.

This is the base class for graphs containing directed edges (so-called arcs)

Definition at line 130 of file diGraph.h.

Member Typedef Documentation

◆ ArcIterator

using gum::ArcGraphPart::ArcIterator = ArcSetIterator
inherited

Definition at line 100 of file arcGraphPart.h.

◆ node_const_iterator

using gum::NodeGraphPart::node_const_iterator = NodeGraphPartIterator
inherited

types for STL compliance

Definition at line 276 of file nodeGraphPart.h.

◆ node_const_iterator_safe

using gum::NodeGraphPart::node_const_iterator_safe = NodeGraphPartIteratorSafe
inherited

types for STL compliance

Definition at line 278 of file nodeGraphPart.h.

◆ node_iterator

using gum::NodeGraphPart::node_iterator = NodeGraphPartIterator
inherited

types for STL compliance

Definition at line 275 of file nodeGraphPart.h.

◆ node_iterator_safe

using gum::NodeGraphPart::node_iterator_safe = NodeGraphPartIteratorSafe
inherited

types for STL compliance

Definition at line 277 of file nodeGraphPart.h.

◆ NodeConstIterator

using gum::NodeGraphPart::NodeConstIterator = NodeGraphPartIterator
inherited

Definition at line 285 of file nodeGraphPart.h.

◆ NodeConstIteratorSafe

using gum::NodeGraphPart::NodeConstIteratorSafe = NodeGraphPartIteratorSafe
inherited

Definition at line 287 of file nodeGraphPart.h.

◆ NodeIterator

using gum::NodeGraphPart::NodeIterator = NodeGraphPartIterator
inherited

Definition at line 284 of file nodeGraphPart.h.

◆ NodeIteratorSafe

using gum::NodeGraphPart::NodeIteratorSafe = NodeGraphPartIteratorSafe
inherited

Definition at line 286 of file nodeGraphPart.h.

Constructor & Destructor Documentation

◆ DiGraph() [1/2]

gum::DiGraph::DiGraph ( Size nodes_size = HashTableConst::default_size,
bool nodes_resize_policy = true,
Size arcs_size = HashTableConst::default_size,
bool arcs_resize_policy = true )
explicit

default constructor

Parameters
nodes_sizethe size of the hash table used to store all the nodes
nodes_resize_policythe resizing policy of this hash table
arcs_sizethe size of the hash table used to store all the arcs
arcs_resize_policythe resizing policy of this hash table

Definition at line 69 of file diGraph.cpp.

72 :
73 NodeGraphPart(nodes_size, nodes_resize_policy), ArcGraphPart(arcs_size, arcs_resize_policy) {
74 GUM_CONSTRUCTOR(DiGraph)
75 }
gum::ArcGraphPart::ArcGraphPart
ArcGraphPart(Size arcs_size=HashTableConst::default_size, bool arcs_resize_policy=true)
default constructor
Definition arcGraphPart.cpp:58
gum::NodeGraphPart::NodeGraphPart
NodeGraphPart(Size holes_size=HashTableConst::default_size, bool holes_resize_policy=true)
default constructor
Definition nodeGraphPart.cpp:57

References gum::ArcGraphPart::ArcGraphPart(), DiGraph(), and gum::NodeGraphPart::NodeGraphPart().

Referenced by gum::DAG::DAG(), gum::DAG::DAG(), DiGraph(), DiGraph(), gum::MixedGraph::MixedGraph(), gum::MixedGraph::MixedGraph(), gum::MixedGraph::MixedGraph(), gum::MixedGraph::MixedGraph(), gum::prm::gspan::Pattern::Pattern(), gum::prm::gspan::Pattern::Pattern(), ~DiGraph(), completeGraph(), operator=(), and operator==().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ DiGraph() [2/2]

gum::DiGraph::DiGraph ( const DiGraph & g)

copy constructor

Parameters
gthe DiGraph to copy

Definition at line 77 of file diGraph.cpp.

77: NodeGraphPart(g), ArcGraphPart(g) { GUM_CONS_CPY(DiGraph) }

References gum::ArcGraphPart::ArcGraphPart(), DiGraph(), and gum::NodeGraphPart::NodeGraphPart().

Here is the call graph for this function:

◆ ~DiGraph()

gum::DiGraph::~DiGraph ( )
virtual

destructor

Definition at line 79 of file diGraph.cpp.

79{ GUM_DESTRUCTOR(DiGraph) }

References DiGraph().

Here is the call graph for this function:

Member Function Documentation

◆ _addHole_()

void gum::NodeGraphPart::_addHole_ ( NodeId id)
privateinherited

to add a hole.

Warning
id is assumed not to be already a hole

Definition at line 96 of file nodeGraphPart.cpp.

96 {
97 // we assume that the node exists
98 if (node + 1 == _boundVal_) {
99 // we remove the max : no new hole and maybe a bunch of holes to remove
100 --_boundVal_;
101
102 if (_holes_) {
103 while (_holes_->contains(_boundVal_ - 1)) {
104 // a bunch of holes to remove. We do not use inHoles for optimisation
105 // :
106 // not to repeat the test if ( _holes_) each time
107 _holes_->erase(--_boundVal_);
108 }
109
110 if (_holes_->empty()) {
111 delete _holes_;
112 _holes_ = nullptr;
113 }
114 }
115
116 _updateEndIteratorSafe_();
117 } else {
118 if (!_holes_) _holes_ = new NodeSet(_holes_size_, _holes_resize_policy_);
119
120 _holes_->insert(node);
121 }
122 }
gum::NodeGraphPart::_updateEndIteratorSafe_
void _updateEndIteratorSafe_()
updating endIterator (always at max+1)
Definition nodeGraphPart_inl.h:327
gum::NodeGraphPart::_holes_size_
Size _holes_size_
value for holes configuration
Definition nodeGraphPart.h:519
gum::NodeGraphPart::_holes_resize_policy_
bool _holes_resize_policy_
value for holes configuration
Definition nodeGraphPart.h:522
gum::NodeGraphPart::_holes_
NodeSet * _holes_
the set of nodes not contained in the NodeGraphPart in the interval 1.
Definition nodeGraphPart.h:516
gum::NodeGraphPart::_boundVal_
NodeId _boundVal_
the id below which NodeIds may belong to the NodeGraphPart
Definition nodeGraphPart.h:528
gum::NodeSet
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Definition graphElements.h:380

References _boundVal_, _holes_, _holes_resize_policy_, _holes_size_, and _updateEndIteratorSafe_().

Referenced by eraseNode(), and gum_tests::NodeGraphPartTestSuite.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _checkChildren_()

INLINE void gum::ArcGraphPart::_checkChildren_ ( NodeId id)
privateinherited

when the ArcGraphPart contains no arc outgoing from a given node, this function adds an empty set entry to children[id]

Parameters
idthe node whose children[id] is checked

Definition at line 71 of file arcGraphPart_inl.h.

71 {
72 if (!_children_.exists(id)) { _children_.insert(id, new NodeSet); }
73 }
gum::ArcGraphPart::_children_
NodeProperty< NodeSet * > _children_
for each arc, the set of its children
Definition arcGraphPart.h:322

References _children_.

Referenced by addArc().

Here is the caller graph for this function:

◆ _checkParents_()

INLINE void gum::ArcGraphPart::_checkParents_ ( NodeId id)
privateinherited

when the ArcGraphPart contains no arc ingoing into a given node, this function adds an empty set entry to parents[id]

Parameters
idthe node whose parents[id] is checked

Definition at line 67 of file arcGraphPart_inl.h.

67 {
68 if (!_parents_.exists(id)) { _parents_.insert(id, new NodeSet); }
69 }
gum::ArcGraphPart::_parents_
NodeProperty< NodeSet * > _parents_
for each arc, the sets of its parents
Definition arcGraphPart.h:319

References _parents_.

Referenced by addArc().

Here is the caller graph for this function:

◆ _clearNodes_()

void gum::NodeGraphPart::_clearNodes_ ( )
privateinherited

code for clearing nodes (called twice)

Definition at line 174 of file nodeGraphPart.cpp.

174 {
175 NodeId bound = _boundVal_;
176 _boundVal_ = 0;
177
178 if (onNodeDeleted.hasListener()) {
179 for (NodeId n = 0; n < bound; ++n) {
180 if (!_inHoles_(n)) GUM_EMIT1(onNodeDeleted, n);
181 }
182 }
183
184 _updateEndIteratorSafe_();
185
186 delete (_holes_);
187 _holes_ = nullptr;
188 }
gum::NodeGraphPart::onNodeDeleted
Signaler1< NodeId > onNodeDeleted
Definition nodeGraphPart.h:290
gum::NodeGraphPart::bound
NodeId bound() const
returns a number n such that all node ids are strictly lower than n
Definition nodeGraphPart_inl.h:310
gum::NodeGraphPart::_inHoles_
bool _inHoles_(NodeId id) const
Definition nodeGraphPart_inl.h:372
GUM_EMIT1
#define GUM_EMIT1(signal, arg1)
Definition signaler1.h:61

References _boundVal_, _holes_, _inHoles_(), _updateEndIteratorSafe_(), bound(), GUM_EMIT1, and onNodeDeleted.

Referenced by clear(), clearNodes(), and gum_tests::NodeGraphPartTestSuite.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _eraseHole_()

INLINE void gum::NodeGraphPart::_eraseHole_ ( NodeId id)
privateinherited

to delete hole.

Warning
the hole is assumed to be existing.

Definition at line 244 of file nodeGraphPart_inl.h.

244 {
245 _holes_->erase(id);
246
247 if (_holes_->empty()) {
248 delete _holes_;
249 _holes_ = nullptr;
250 }
251 }

References _holes_.

Referenced by addNode(), addNodeWithId(), and gum_tests::NodeGraphPartTestSuite.

Here is the caller graph for this function:

◆ _inHoles_()

INLINE bool gum::NodeGraphPart::_inHoles_ ( NodeId id) const
privateinherited
Returns
true if id is part of holes

Definition at line 372 of file nodeGraphPart_inl.h.

372{ return _holes_ && _holes_->contains(id); }

References _holes_.

Referenced by _clearNodes_(), addNodeWithId(), asNodeSet(), existsNode(), gum_tests::NodeGraphPartTestSuite, and toString().

Here is the caller graph for this function:

◆ _sizeHoles_()

INLINE Size gum::NodeGraphPart::_sizeHoles_ ( ) const
privateinherited
Returns
the size of holes

Definition at line 375 of file nodeGraphPart_inl.h.

375{ return _holes_ ? _holes_->size() : (Size)0; }
gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74

References _holes_.

Referenced by gum_tests::NodeGraphPartTestSuite.

Here is the caller graph for this function:

◆ _updateEndIteratorSafe_()

INLINE void gum::NodeGraphPart::_updateEndIteratorSafe_ ( )
privateinherited

updating endIterator (always at max+1)

Definition at line 327 of file nodeGraphPart_inl.h.

327{ _endIteratorSafe_.setPos_(_boundVal_); }
gum::NodeGraphPart::_endIteratorSafe_
NodeGraphPartIteratorSafe _endIteratorSafe_
the end iterator (used to speed-up parsings of the NodeGraphPart)
Definition nodeGraphPart.h:525

References _boundVal_, and _endIteratorSafe_.

Referenced by NodeGraphPart(), NodeGraphPart(), _addHole_(), _clearNodes_(), addNode(), addNodeWithId(), gum_tests::NodeGraphPartTestSuite, and populateNodes().

Here is the caller graph for this function:

◆ addArc()

INLINE void gum::DiGraph::addArc ( const NodeId tail,
const NodeId head )
virtual

insert a new arc into the directed graph

Parameters
tailthe id of the tail of the new inserted arc
headthe id of the head of the new inserted arc
Warning
if the arc already exists, nothing is done. In particular, no exception is raised.
Exceptions
InvalidNodeif head or tail does not belong to the graph nodes

Reimplemented from gum::ArcGraphPart.

Reimplemented in gum::DAG, gum::PDAG, and gum::prm::gspan::Pattern.

Definition at line 55 of file diGraph_inl.h.

55 {
56 if (!exists(head)) { GUM_ERROR(InvalidNode, "no head node : " << head) }
57
58 if (!exists(tail)) { GUM_ERROR(InvalidNode, "no tail node : " << tail) }
59
60 ArcGraphPart::addArc(tail, head);
61 }
gum::ArcGraphPart::addArc
virtual void addArc(NodeId tail, NodeId head)
insert a new arc into the ArcGraphPart
Definition arcGraphPart_inl.h:114
gum::NodeGraphPart::exists
bool exists(const NodeId id) const
alias for existsNode
Definition nodeGraphPart_inl.h:296
GUM_ERROR
#define GUM_ERROR(type, msg)
Definition exceptions.h:72

References gum::ArcGraphPart::addArc(), gum::NodeGraphPart::exists(), and GUM_ERROR.

Referenced by gum::MeekRules::_applyMeekRules_(), gum::EssentialGraph::_buildEssentialGraph_(), gum::learning::Miic::_orientingVstructureMiic_(), gum::learning::SimpleMiic::_orientingVstructureMiic_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::learning::Miic::_propagatingOrientationMiic_(), gum::learning::SimpleMiic::_propagatingOrientationMiic_(), gum::DAG::addArc(), gum::PDAG::addArc(), gum::prm::gspan::Pattern::addArc(), completeGraph(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::learning::SimpleMiic::orientationLatents_(), gum::learning::Miic::orientationMiic_(), gum::learning::SimpleMiic::orientationMiic_(), gum::learning::IBNLearner::prepareMiic_(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), and gum::learning::SimpleMiic::propagatesRemainingOrientableEdges_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ addNode()

INLINE NodeId gum::NodeGraphPart::addNode ( )
virtualinherited

insert a new node and return its id

Returns
the id chosen by the internal idFactory

Reimplemented in gum::CliqueGraph.

Definition at line 258 of file nodeGraphPart_inl.h.

258 {
259 NodeId newNode;
260
261 // fill the first hole if holes exist
262 if (_holes_ && (!_holes_->empty())) {
263 newNode = *(_holes_->begin());
264 _eraseHole_(newNode);
265 } else {
266 newNode = _boundVal_;
267 ++_boundVal_;
268 _updateEndIteratorSafe_();
269 }
270
271 GUM_EMIT1(onNodeAdded, newNode);
272
273 return newNode;
274 }
gum::NodeGraphPart::onNodeAdded
Signaler1< NodeId > onNodeAdded
Definition nodeGraphPart.h:289
gum::NodeGraphPart::_eraseHole_
void _eraseHole_(NodeId id)
to delete hole.
Definition nodeGraphPart_inl.h:244

References _boundVal_, _eraseHole_(), _holes_, _updateEndIteratorSafe_(), GUM_EMIT1, and onNodeAdded.

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_(), gum::prm::StructuredInference< GUM_SCALAR >::_addEdgesInReducedGraph_(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::StructuredInference< GUM_SCALAR >::_buildPatternGraph_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), and gum::prm::gspan::DFSTree< GUM_SCALAR >::addRoot().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ addNodes()

INLINE std::vector< NodeId > gum::NodeGraphPart::addNodes ( Size n)
inherited

insert n nodes

Parameters
nthe number of nodes to add
Returns
the vector of chosen ids

Definition at line 276 of file nodeGraphPart_inl.h.

276 {
277 std::vector< NodeId > v;
278 v.reserve(N);
279 for (Idx i = 0; i < N; i++)
280 v.push_back(this->addNode());
281 return v;
282 }
gum::Idx
Size Idx
Type for indexes.
Definition types.h:79

Referenced by gum::DiGraph::completeGraph(), and gum::UndiGraph::completeGraph().

Here is the caller graph for this function:

◆ addNodeWithId()

void gum::NodeGraphPart::addNodeWithId ( const NodeId id)
virtualinherited

try to insert a node with the given id

Warning
This method should be carefully used. Please prefer populateNodes or populateNodesFromProperty when possible
Exceptions
DuplicateElementexception if the id already exists

Reimplemented in gum::CliqueGraph.

Definition at line 151 of file nodeGraphPart.cpp.

151 {
152 if (id >= _boundVal_) {
153 if (id > _boundVal_) { // we have to add holes
154 if (!_holes_) _holes_ = new NodeSet(_holes_size_, _holes_resize_policy_);
155
156 for (NodeId i = _boundVal_; i < id; ++i)
157 _holes_->insert(i);
158 }
159
160 _boundVal_ = id + 1;
161
162 _updateEndIteratorSafe_();
163 } else {
164 if (_inHoles_(id)) { // we fill a hole
165 _eraseHole_(id);
166 } else {
167 GUM_ERROR(DuplicateElement, "Id " << id << " is already used")
168 }
169 }
170
171 GUM_EMIT1(onNodeAdded, id);
172 }

References _boundVal_, _eraseHole_(), _holes_, _holes_resize_policy_, _holes_size_, _inHoles_(), _updateEndIteratorSafe_(), GUM_EMIT1, GUM_ERROR, and onNodeAdded.

Referenced by gum::learning::StructuralConstraintDAG::StructuralConstraintDAG(), gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::learning::IBNLearner::learnDag_(), gum::learning::SimpleMiic::learnStructure(), gum::InfluenceDiagram< GUM_SCALAR >::moralGraph_(), gum::DAG::moralizedAncestralGraph(), gum::PDAG::moralizedAncestralGraph(), gum::UndiGraph::partialUndiGraph(), gum::learning::IBNLearner::prepareMiic_(), gum::MeekRules::propagateToCPDAG(), gum::MeekRules::propagateToDAG(), gum::rec_ancestral(), and gum::EssentialGraph::skeleton().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ancestors()

NodeSet gum::ArcGraphPart::ancestors ( NodeId id) const
inherited

returns the set of nodes with directed path ingoing to a given node

Note that the set of nodes returned may be empty if no path within the ArcGraphPart is ingoing to the given node.

Parameters
idthe node which is the head of a directed path with the returned nodes

Definition at line 191 of file arcGraphPart.cpp.

191 {
192 NodeSet res;
193 NodeSet tmp;
194 for (auto next: parents(id))
195 tmp.insert(next);
196
197 while (!tmp.empty()) {
198 auto current = *(tmp.begin());
199 tmp.erase(current);
200 res.insert(current);
201 for (auto next: parents(current)) {
202 if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
203 }
204 }
205 return res;
206 }
gum::Set::insert
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:539

References gum::Set< Key >::begin(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), gum::Set< Key >::insert(), and parents().

Referenced by gum::DAGmodel::ancestors().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ arcs()

INLINE const ArcSet & gum::ArcGraphPart::arcs ( ) const
inherited

returns the set of arcs stored within the ArcGraphPart

Definition at line 59 of file arcGraphPart_inl.h.

59{ return _arcs_; }
gum::ArcGraphPart::_arcs_
Set< Arc > _arcs_
the set of all the arcs contained within the ArcGraphPart
Definition arcGraphPart.h:316

References _arcs_.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::ClassBayesNet< GUM_SCALAR >::_init_(), gum::prm::gspan::Pattern::arcs(), gum::learning::SimpleMiic::learnStructure(), gum::DAG::moralGraph(), gum::PDAG::moralGraph(), gum::MeekRules::propagateToCPDAG(), gum::MeekRules::propagateToDAG(), and gum::DiGraph::toDot().

Here is the caller graph for this function:

◆ arcsProperty() [1/2]

template<typename VAL>
ArcProperty< VAL > gum::ArcGraphPart::arcsProperty ( const VAL & a,
Size size = 0 ) const
inherited

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL a)

Parameters
athe default value assigned to each arc in the returned Property
sizean optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of arcs. If you do not specify this parameter, the method will assign it for you.

◆ arcsProperty() [2/2]

template<typename VAL>
ArcProperty< VAL > gum::ArcGraphPart::arcsProperty ( VAL(* f )(const Arc &),
Size size = 0 ) const
inherited

a method to create a hashMap of VAL from a set of arcs (using for every arc, say x, the VAL f(x))

Parameters
fa function assigning a VAL to any arc
sizean optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of arcs. If you do not specify this parameter, the method will assign it for you.

◆ asNodeSet()

INLINE NodeSet gum::NodeGraphPart::asNodeSet ( ) const
inherited

returns a copy of the set of nodes represented by the NodeGraphPart

Warning
this function is o(n) where n is the number of nodes. In space and in time. Usually, when you need to parse the nodes of a NodeGraphPart, prefer using
for(const auto n : nodes())
rather than
for(const auto n : asNodeSet())
gum::NodeGraphPart::asNodeSet
NodeSet asNodeSet() const
returns a copy of the set of nodes represented by the NodeGraphPart
Definition nodeGraphPart_inl.h:356
as this is faster and consumes much less memory.

Definition at line 356 of file nodeGraphPart_inl.h.

356 {
357 NodeSet son(sizeNodes());
358
359 if (!empty()) {
360 for (NodeId n = 0; n < _boundVal_; ++n) {
361 if (!_inHoles_(n)) son.insert(n);
362 }
363 }
364
365 return son;
366 }
gum::NodeGraphPart::sizeNodes
Size sizeNodes() const
returns the number of nodes in the NodeGraphPart
Definition nodeGraphPart_inl.h:284

References _boundVal_, _inHoles_(), empty(), gum::Set< Key >::insert(), and sizeNodes().

Referenced by gum::MarginalTargetedInference< GUM_SCALAR >::MarginalTargetedInference(), gum::MarginalTargetedMRFInference< GUM_SCALAR >::MarginalTargetedMRFInference(), and gum::ImportanceSampling< GUM_SCALAR >::unsharpenBN_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ begin()

INLINE NodeGraphPartIterator gum::NodeGraphPart::begin ( ) const
noexceptinherited

a begin iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 333 of file nodeGraphPart_inl.h.

333 {
334 NodeGraphPartIterator it(*this);
335 it.validate_(); // stop the iterator at the first not-in-holes
336 return it;
337 }
gum::NodeGraphPart::NodeGraphPartIterator
friend class NodeGraphPartIterator
Definition nodeGraphPart.h:479

References NodeGraphPartIterator, and gum::NodeGraphPartIterator::validate_().

Referenced by gum::Estimator< GUM_SCALAR >::Estimator(), populateNodesFromProperty(), and gum::Estimator< GUM_SCALAR >::setFromBN().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ beginSafe()

INLINE NodeGraphPartIteratorSafe gum::NodeGraphPart::beginSafe ( ) const
inherited

a begin iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 321 of file nodeGraphPart_inl.h.

321 {
322 NodeGraphPartIteratorSafe it(*this);
323 it.validate_(); // stop the iterator at the first not-in-holes
324 return it;
325 }
gum::NodeGraphPart::NodeGraphPartIteratorSafe
friend class NodeGraphPartIteratorSafe
Definition nodeGraphPart.h:480

References NodeGraphPartIteratorSafe, and gum::NodeGraphPartIterator::validate_().

Here is the call graph for this function:

◆ bound()

INLINE NodeId gum::NodeGraphPart::bound ( ) const
inherited

returns a number n such that all node ids are strictly lower than n

Definition at line 310 of file nodeGraphPart_inl.h.

310{ return _boundVal_; }

References _boundVal_.

Referenced by _clearNodes_().

Here is the caller graph for this function:

◆ children() [1/2]

INLINE NodeSet gum::ArcGraphPart::children ( const NodeSet & ids) const
inherited

returns the set of children of a set of nodes

Definition at line 86 of file arcGraphPart_inl.h.

86 {
87 NodeSet res;
88 for (const auto node: ids)
89 res += children(node);
90 return res;
91 }
gum::ArcGraphPart::children
NodeSet children(const NodeSet &ids) const
returns the set of children of a set of nodes
Definition arcGraphPart_inl.h:86

References children().

Referenced by ArcGraphPart(), gum::prm::ClassDependencyGraph< GUM_SCALAR >::_addArcs_(), gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::gspan::Pattern::_expandCodeIsMinimal_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::DAG::_minimalCondSetVisitDn_(), gum::DAG::_minimalCondSetVisitUp_(), gum::prm::gspan::Pattern::_not_rec_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::gspan::Pattern::_rec_(), gum::BarrenNodesFinder::barrenNodes(), gum::MixedGraph::boundary(), children(), descendants(), directedUnorientedPath(), eraseChildren(), gum::DiGraph::hasDirectedPath(), gum::PDAG::hasMixedReallyOrientedPath(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::initialize_(), gum::prm::PRMClassElementContainer< double >::isInputNode(), gum::prm::gspan::Pattern::isMinimal(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::makeInferenceNodeToNeighbours_(), gum::DAG::minimalCondSet(), gum::MixedGraph::mixedUnorientedPath(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::rec_hasMixedReallyOrientedPath(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::prm::gspan::Pattern::remove(), gum::BayesBall::requisiteNodes(), gum::dSeparationAlgorithm::requisiteNodes(), gum::DAGCycleDetector::setDAG(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), and unvirtualizedEraseChildren().

Here is the call graph for this function:

◆ children() [2/2]

INLINE const NodeSet & gum::ArcGraphPart::children ( NodeId id) const
inherited

returns the set of nodes with arc outgoing from a given node

Note that the set of arcs returned may be empty if no arc within the ArcGraphPart is outgoing from the given node.

Parameters
idthe node which is the tail of the arcs returned

Definition at line 109 of file arcGraphPart_inl.h.

109 {
110 if (_children_.exists(id)) return *_children_[id];
111 else return emptyNodeSet;
112 }
gum::emptyNodeSet
const NodeSet emptyNodeSet
Some typdefs and define for shortcuts ...
Definition graphElements.h:387

References _children_, and gum::emptyNodeSet.

◆ clear()

INLINE void gum::DiGraph::clear ( )
virtual

removes all the nodes and arcs from the graph

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 63 of file diGraph_inl.h.

63 {
64 ArcGraphPart::clearArcs();
65 NodeGraphPart::clearNodes();
66 }
gum::ArcGraphPart::clearArcs
void clearArcs()
removes all the arcs from the ArcGraphPart
Definition arcGraphPart.cpp:98
gum::NodeGraphPart::clearNodes
virtual void clearNodes()
remove all the nodes from the NodeGraphPart
Definition nodeGraphPart_inl.h:312

References gum::ArcGraphPart::clearArcs(), and gum::NodeGraphPart::clearNodes().

Referenced by operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ clearArcs()

void gum::ArcGraphPart::clearArcs ( )
inherited

removes all the arcs from the ArcGraphPart

Definition at line 98 of file arcGraphPart.cpp.

98 {
99 for (const auto& elt: _parents_)
100 delete elt.second;
101
102 _parents_.clear();
103
104 for (const auto& elt: _children_)
105 delete elt.second;
106
107 _children_.clear();
108
109 // we need this copy only if at least one onArcDeleted listener exists
110 if (onArcDeleted.hasListener()) {
111 ArcSet tmp = _arcs_;
112 _arcs_.clear();
113
114 for (const auto& arc: tmp)
115 GUM_EMIT2(onArcDeleted, arc.tail(), arc.head());
116 } else {
117 _arcs_.clear();
118 }
119 }
gum::ArcGraphPart::onArcDeleted
Signaler2< NodeId, NodeId > onArcDeleted
Definition arcGraphPart.h:103
GUM_EMIT2
#define GUM_EMIT2(signal, arg1, arg2)
Definition signaler2.h:61

References _arcs_, _children_, _parents_, GUM_EMIT2, and onArcDeleted.

Referenced by ~ArcGraphPart(), gum::DiGraph::clear(), gum::MixedGraph::clear(), operator=(), and gum::MixedGraph::operator=().

Here is the caller graph for this function:

◆ clearNodes()

INLINE void gum::NodeGraphPart::clearNodes ( )
virtualinherited

remove all the nodes from the NodeGraphPart

Definition at line 312 of file nodeGraphPart_inl.h.

312{ _clearNodes_(); }
gum::NodeGraphPart::_clearNodes_
void _clearNodes_()
code for clearing nodes (called twice)
Definition nodeGraphPart.cpp:174

References _clearNodes_().

Referenced by gum::DiGraph::clear(), gum::MixedGraph::clear(), gum::UndiGraph::clear(), and gum::MixedGraph::operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ completeGraph()

DiGraph gum::DiGraph::completeGraph ( int n)
static

Build a complete DiGraph with n nodes.

Parameters
intn
Returns
the complete DiGraph

Definition at line 57 of file diGraph.cpp.

57 {
58 DiGraph g;
59 g.addNodes(n);
60
61 for (int j = 0; j < n; ++j) {
62 for (int k = j + 1; k < n; ++k) {
63 g.addArc(j, k);
64 }
65 }
66 return g;
67 }

References DiGraph(), addArc(), and gum::NodeGraphPart::addNodes().

Here is the call graph for this function:

◆ descendants()

NodeSet gum::ArcGraphPart::descendants ( NodeId id) const
inherited

returns the set of nodes with directed path outgoing from a given node

Note that the set of nodes returned may be empty if no path within the ArcGraphPart is outgoing from the given node.

Parameters
idthe node which is the tail of a directed path with the returned nodes

Definition at line 174 of file arcGraphPart.cpp.

174 {
175 NodeSet res;
176 NodeSet tmp;
177 for (auto next: children(id))
178 tmp.insert(next);
179
180 while (!tmp.empty()) {
181 auto current = *(tmp.begin());
182 tmp.erase(current);
183 res.insert(current);
184 for (auto next: children(current)) {
185 if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
186 }
187 }
188 return res;
189 }

References gum::Set< Key >::begin(), children(), gum::Set< Key >::contains(), gum::Set< Key >::empty(), gum::Set< Key >::erase(), and gum::Set< Key >::insert().

Referenced by gum::DAGmodel::descendants().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ directedPath()

std::vector< NodeId > gum::ArcGraphPart::directedPath ( NodeId node1,
NodeId node2 ) const
inherited

returns a directed path from node1 to node2 belonging to the set of arcs

Parameters
node1the id from which the path begins
node2the id to which the path ends
Exceptions
NotFoundexception is raised if no path can be found between the two nodes

Definition at line 208 of file arcGraphPart.cpp.

208 {
209 // not recursive version => use a FIFO for simulating the recursion
210 List< NodeId > nodeFIFO;
211 nodeFIFO.pushBack(n2);
212
213 // mark[node] = successor if visited, else mark[node] does not exist
214 NodeProperty< NodeId > mark;
215 mark.insert(n2, n2);
216
217 NodeId current;
218
219 while (!nodeFIFO.empty()) {
220 current = nodeFIFO.front();
221 nodeFIFO.popFront();
222
223 // check the parents
224
225 for (const auto new_one: parents(current)) {
226 if (mark.exists(new_one)) // if this node is already marked, do not
227 continue; // check it again
228
229 mark.insert(new_one, current);
230
231 if (new_one == n1) {
232 std::vector< NodeId > v;
233
234 for (current = n1; current != n2; current = mark[current])
235 v.push_back(current);
236
237 v.push_back(n2);
238
239 return v;
240 }
241
242 nodeFIFO.pushBack(new_one);
243 }
244 }
245
246 GUM_ERROR(NotFound, "no path found")
247 }
gum::HashTable::insert
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
Definition hashTable_tpl.h:665
gum::NodeProperty
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
Definition graphElements.h:395

References gum::List< Val >::empty(), gum::HashTable< Key, Val >::exists(), gum::List< Val >::front(), GUM_ERROR, gum::HashTable< Key, Val >::insert(), parents(), gum::List< Val >::popFront(), and gum::List< Val >::pushBack().

Referenced by gum::learning::SimpleMiic::orientationLatents_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ directedUnorientedPath()

std::vector< NodeId > gum::ArcGraphPart::directedUnorientedPath ( NodeId node1,
NodeId node2 ) const
inherited

returns an unoriented (directed) path from node1 to node2 in the arc set

Parameters
node1the id from which the path begins
node2the id to which the path ends
Exceptions
NotFoundexception is raised if no path can be found between the two nodes

Definition at line 249 of file arcGraphPart.cpp.

249 {
250 // not recursive version => use a FIFO for simulating the recursion
251 List< NodeId > nodeFIFO;
252 nodeFIFO.pushBack(n2);
253
254 // mark[node] = successor if visited, else mark[node] does not exist
255 NodeProperty< NodeId > mark;
256 mark.insert(n2, n2);
257
258 NodeId current;
259
260 while (!nodeFIFO.empty()) {
261 current = nodeFIFO.front();
262 nodeFIFO.popFront();
263
264 // check the parents
265 for (const auto new_one: parents(current)) {
266 if (mark.exists(new_one)) // the node has already been visited
267 continue;
268
269 mark.insert(new_one, current);
270
271 if (new_one == n1) {
272 std::vector< NodeId > v;
273
274 for (current = n1; current != n2; current = mark[current])
275 v.push_back(current);
276
277 v.push_back(n2);
278
279 return v;
280 }
281
282 nodeFIFO.pushBack(new_one);
283 }
284
285 // check the children
286 for (const auto new_one: children(current)) {
287 if (mark.exists(new_one)) // the node has already been visited
288 continue;
289
290 mark.insert(new_one, current);
291
292 if (new_one == n1) {
293 std::vector< NodeId > v;
294
295 for (current = n1; current != n2; current = mark[current])
296 v.push_back(current);
297
298 v.push_back(n2);
299
300 return v;
301 }
302
303 nodeFIFO.pushBack(new_one);
304 }
305 }
306
307 GUM_ERROR(NotFound, "no path found")
308 }

References children(), gum::List< Val >::empty(), gum::HashTable< Key, Val >::exists(), gum::List< Val >::front(), GUM_ERROR, gum::HashTable< Key, Val >::insert(), parents(), gum::List< Val >::popFront(), and gum::List< Val >::pushBack().

Here is the call graph for this function:

◆ empty()

INLINE bool gum::NodeGraphPart::empty ( ) const
inherited

alias for emptyNodes

Definition at line 308 of file nodeGraphPart_inl.h.

308{ return emptyNodes(); }
gum::NodeGraphPart::emptyNodes
bool emptyNodes() const
indicates whether there exists nodes in the NodeGraphPart
Definition nodeGraphPart_inl.h:306

References emptyNodes().

Referenced by asNodeSet(), gum::PDAG::cSeparation(), gum::DAG::dSeparation(), gum::prm::gspan::Pattern::remove(), and gum::PDAG::toDot().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ emptyArcs()

INLINE bool gum::ArcGraphPart::emptyArcs ( ) const
inherited

indicates wether the ArcGraphPart contains any arc

Definition at line 55 of file arcGraphPart_inl.h.

55{ return _arcs_.empty(); }

References _arcs_.

◆ emptyNodes()

INLINE bool gum::NodeGraphPart::emptyNodes ( ) const
inherited

indicates whether there exists nodes in the NodeGraphPart

Definition at line 306 of file nodeGraphPart_inl.h.

306{ return (sizeNodes() == 0); }

References sizeNodes().

Referenced by empty().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ end()

INLINE const NodeGraphPartIterator & gum::NodeGraphPart::end ( ) const
noexceptinherited

the end iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 339 of file nodeGraphPart_inl.h.

339 {
340 return _endIteratorSafe_;
341 }

References _endIteratorSafe_, and NodeGraphPartIterator.

Referenced by gum::Estimator< GUM_SCALAR >::Estimator(), populateNodesFromProperty(), and gum::Estimator< GUM_SCALAR >::setFromBN().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ endSafe()

INLINE const NodeGraphPartIteratorSafe & gum::NodeGraphPart::endSafe ( ) const
noexceptinherited

the end iterator to parse the set of nodes contained in the NodeGraphPart

Definition at line 329 of file nodeGraphPart_inl.h.

329 {
330 return _endIteratorSafe_;
331 }

References _endIteratorSafe_, and NodeGraphPartIteratorSafe.

Here is the call graph for this function:

◆ eraseArc()

INLINE void gum::ArcGraphPart::eraseArc ( const Arc & arc)
virtualinherited

removes an arc from the ArcGraphPart

Parameters
arcthe arc to be removed
Warning
if the arc does not exist, nothing is done. In particular, no exception is thrown. However, the signal onArcDeleted is fired only if a node is effectively removed.

Definition at line 126 of file arcGraphPart_inl.h.

126 {
127 // ASSUMING tail and head exists in _parents_ anf _children_
128 // (if not, it is an error)
129 if (existsArc(arc)) {
130 NodeId tail = arc.tail();
131 NodeId head = arc.head();
132 _parents_[head]->erase(tail);
133 _children_[tail]->erase(head);
134 _arcs_.erase(arc);
135 GUM_EMIT2(onArcDeleted, tail, head);
136 }
137 }
gum::ArcGraphPart::existsArc
bool existsArc(const Arc &arc) const
indicates whether a given arc exists
Definition arcGraphPart_inl.h:61

References _arcs_, _children_, _parents_, existsArc(), GUM_EMIT2, gum::Arc::head(), onArcDeleted, and gum::Arc::tail().

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::MeekRules::_orientDoubleHeadedArcs_(), gum::BarrenNodesFinder::barrenNodes(), eraseChildren(), eraseParents(), eraseSetOfArcs_(), gum::learning::IBNLearner::learnDag_(), gum::learning::GreedyHillClimbing::learnStructure(), gum::learning::LocalSearchWithTabuList::learnStructure(), gum::learning::SimpleMiic::learnStructure(), gum::learning::SimpleMiic::orientationLatents_(), gum::learning::Miic::orientationMiic_(), gum::learning::SimpleMiic::orientationMiic_(), gum::learning::Miic::orientDoubleHeadedArcs_(), gum::prm::gspan::Pattern::pop_back(), unvirtualizedEraseChildren(), unvirtualizedEraseParents(), and unvirtualizedEraseSetOfArcs_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ eraseChildren()

INLINE void gum::ArcGraphPart::eraseChildren ( NodeId id)
inherited

removes all the children of a given node

Parameters
idthe node all the children of which will be removed
Warning
although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseChildren
if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 158 of file arcGraphPart_inl.h.

158 {
159 if (_children_.exists(id)) {
160 const NodeSet& children = *(_children_[id]);
161
162 for (auto iter = children.beginSafe(); // safe iterator needed here
163 iter != children.endSafe();
164 ++iter) {
165 // warning: use this erase so that you actually use the virtualized
166 // arc removal function
167 eraseArc(Arc(id, *iter));
168 }
169 }
170 }

References _children_, children(), and eraseArc().

Here is the call graph for this function:

◆ eraseNode()

INLINE void gum::DiGraph::eraseNode ( const NodeId id)
virtual

remove a node and its adjacent arcs from the graph

Parameters
idthe id of the node to be removed
Warning
if the node does not exist, nothing is done. In particular, no exception is raised.

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 79 of file diGraph_inl.h.

79 {
80 // warning: to remove the arcs adjacent to id, use the unvirtualized
81 // versions
82 // of arc removals
83 ArcGraphPart::unvirtualizedEraseParents(id);
84 ArcGraphPart::unvirtualizedEraseChildren(id);
85
86 NodeGraphPart::eraseNode(id);
87 }
gum::ArcGraphPart::unvirtualizedEraseChildren
void unvirtualizedEraseChildren(NodeId id)
same function as eraseChildren but without any virtual call to an erase
Definition arcGraphPart_inl.h:189
gum::ArcGraphPart::unvirtualizedEraseParents
void unvirtualizedEraseParents(NodeId id)
same function as eraseParents but without any virtual call to an erase
Definition arcGraphPart_inl.h:177
gum::NodeGraphPart::eraseNode
virtual void eraseNode(const NodeId id)
erase the node with the given id
Definition nodeGraphPart_inl.h:298

References gum::NodeGraphPart::eraseNode(), gum::ArcGraphPart::unvirtualizedEraseChildren(), and gum::ArcGraphPart::unvirtualizedEraseParents().

Referenced by gum::BarrenNodesFinder::barrenNodes(), gum::prm::gspan::Pattern::pop_back(), and gum::prm::gspan::Pattern::remove().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ eraseParents()

INLINE void gum::ArcGraphPart::eraseParents ( NodeId id)
inherited

erase all the parents of a given node

Parameters
idthe node all the parents of which will be removed
Warning
although this method is not virtual, it calls method eraseArc( const Arc& arc ) and, as such, has a "virtual" behaviour. If you do not wish it to have this "virtual" behaviour, call instead method unvirtualizedEraseParents
if no arc is a parent of id, nothing is done. In particular, no exception is thrown.

Definition at line 144 of file arcGraphPart_inl.h.

144 {
145 if (_parents_.exists(id)) {
146 const NodeSet& parents = *(_parents_[id]);
147
148 for (auto iter = parents.beginSafe(); // safe iterator needed here
149 iter != parents.endSafe();
150 ++iter) {
151 // warning: use this erase so that you actually use the virtualized
152 // arc removal function
153 eraseArc(Arc(*iter, id));
154 }
155 }
156 }

References _parents_, eraseArc(), and parents().

Here is the call graph for this function:

◆ eraseSetOfArcs_()

INLINE void gum::ArcGraphPart::eraseSetOfArcs_ ( const ArcSet & set)
protectedinherited

a (virtualized) function to remove a given set of arcs

Warning
this function uses eraseArc, which is a virtual function. Hence the behaviour of this function is that of a virtual function

Definition at line 139 of file arcGraphPart_inl.h.

139 {
140 for (const auto& arc: set)
141 eraseArc(arc);
142 }

References eraseArc().

Here is the call graph for this function:

◆ exists()

INLINE bool gum::NodeGraphPart::exists ( const NodeId id) const
inherited

alias for existsNode

Definition at line 296 of file nodeGraphPart_inl.h.

296{ return existsNode(node); }
gum::NodeGraphPart::existsNode
bool existsNode(const NodeId id) const
returns true iff the NodeGraphPart contains the given nodeId
Definition nodeGraphPart_inl.h:290

References existsNode().

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::_removeNode_(), gum::DiGraph::addArc(), gum::prm::gspan::Pattern::addArc(), gum::UndiGraph::addEdge(), gum::prm::gspan::Pattern::exists(), gum::DiGraph::hasDirectedPath(), gum::learning::IBNLearner::learnDag_(), and gum::DAG::moralizedAncestralGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ existsArc() [1/2]

INLINE bool gum::ArcGraphPart::existsArc ( const Arc & arc) const
inherited

indicates whether a given arc exists

Parameters
arcthe arc we test whether or not it belongs to the ArcGraphPart

Definition at line 61 of file arcGraphPart_inl.h.

61{ return _arcs_.contains(arc); }

References _arcs_.

Referenced by gum::learning::Miic::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::learning::Miic::_existsNonTrivialDirectedPath_(), gum::learning::SimpleMiic::_existsNonTrivialDirectedPath_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::gspan::Pattern::_not_rec_(), gum::learning::Miic::_orientingVstructureMiic_(), gum::learning::SimpleMiic::_orientingVstructureMiic_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::gspan::Pattern::_rec_(), gum::EssentialGraph::_strongly_protected_(), eraseArc(), gum::prm::gspan::Pattern::exists(), gum::learning::SimpleMiic::orientationLatents_(), gum::learning::Miic::updateProbaTriples_(), and gum::learning::SimpleMiic::updateProbaTriples_().

Here is the caller graph for this function:

◆ existsArc() [2/2]

INLINE bool gum::ArcGraphPart::existsArc ( NodeId tail,
NodeId head ) const
inherited

indicates whether a given arc exists

Parameters
tailthe tail of the arc we test the existence in the ArcGraphPart
headthe head of the arc we test the existence in the ArcGraphPart

Definition at line 63 of file arcGraphPart_inl.h.

63 {
64 return _parents_.exists(head) && _parents_[head]->exists(tail);
65 }

References _parents_.

◆ existsNode()

INLINE bool gum::NodeGraphPart::existsNode ( const NodeId id) const
inherited

returns true iff the NodeGraphPart contains the given nodeId

Definition at line 290 of file nodeGraphPart_inl.h.

290 {
291 if (node >= _boundVal_) return false;
292
293 return (!_inHoles_(node));
294 }

References _boundVal_, and _inHoles_().

Referenced by eraseNode(), exists(), gum::PDAG::moralizedAncestralGraph(), gum::UndiGraph::partialUndiGraph(), and gum::rec_ancestral().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ family() [1/2]

INLINE NodeSet gum::ArcGraphPart::family ( const NodeSet & ids) const
inherited

returns the set of family nodes of a set of nodes

Definition at line 102 of file arcGraphPart_inl.h.

102 {
103 NodeSet res;
104 for (const auto node: ids)
105 res += family(node);
106 return res;
107 }
gum::ArcGraphPart::family
NodeSet family(NodeId id) const
returns the set of nodes which consists in the node and its parents
Definition arcGraphPart_inl.h:80

References family().

Here is the call graph for this function:

◆ family() [2/2]

INLINE NodeSet gum::ArcGraphPart::family ( NodeId id) const
inherited

returns the set of nodes which consists in the node and its parents

Note that the set of nodes returned may be empty if no path within the ArcGraphPart is outgoing from the given node.

Parameters
idthe node which is the tail of a directed path with the returned nodes

Definition at line 80 of file arcGraphPart_inl.h.

80 {
81 NodeSet res{id};
82 return res + parents(id);
83 }

References parents().

Referenced by family().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ hasDirectedPath()

bool gum::DiGraph::hasDirectedPath ( NodeId from,
NodeId to )

checks whether there exists a directed path from from to to

If from==to, this function checks if a directed cycle containing from exists.

Parameters
from
to
Returns
true if a directed path exists

Definition at line 151 of file diGraph.cpp.

151 {
152 if (!exists(from)) return false;
153
154 // not recursive version => use a FIFO for simulating the recursion
155 List< NodeId > nodeFIFO;
156 nodeFIFO.pushBack(from);
157
158 NodeSet marked;
159 marked.insert(from);
160
161 NodeId new_one;
162
163 while (!nodeFIFO.empty()) {
164 new_one = nodeFIFO.front();
165 nodeFIFO.popFront();
166
167 for (const auto chi: children(new_one)) {
168 if (chi == to) return true;
169
170 if (!marked.contains(chi)) {
171 nodeFIFO.pushBack(chi);
172 marked.insert(chi);
173 }
174 }
175 }
176
177 return false;
178 }

References gum::ArcGraphPart::children(), gum::Set< Key >::contains(), gum::List< Val >::empty(), gum::NodeGraphPart::exists(), gum::List< Val >::front(), gum::Set< Key >::insert(), gum::List< Val >::popFront(), and gum::List< Val >::pushBack().

Referenced by gum::DAG::addArc(), and gum::PDAG::addArc().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ listMapArcs()

template<typename VAL>
List< VAL > gum::ArcGraphPart::listMapArcs ( VAL(* f )(const Arc &)) const
inherited

a method to create a list of VAL from a set of arcs (using for every arc, say x, the VAL f(x))

Parameters
fa function assigning a VAL to any arc

◆ listMapNodes()

template<typename VAL>
List< VAL > gum::NodeGraphPart::listMapNodes ( VAL(* f )(const NodeId &)) const
inherited

a method to create a list of VAL from a set of nodes (using for every nodee, say x, the VAL f(x))

Parameters
fa function assigning a VAL to any node

References listMapNodes().

Referenced by listMapNodes().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ nextNodeId()

INLINE NodeId gum::NodeGraphPart::nextNodeId ( ) const
inherited

returns a new node id, not yet used by any node

Warning
a code like
id=nextNodeId();addNode(id);
gum::NodeGraphPart::nextNodeId
NodeId nextNodeId() const
returns a new node id, not yet used by any node
Definition nodeGraphPart_inl.h:232
is basically not thread safe !!
Returns
a node id not yet used by any node within the NodeGraphPart

Definition at line 232 of file nodeGraphPart_inl.h.

232 {
233 NodeId next = 0;
234
235 // return the first hole if holes exist
236 if (_holes_ && (!_holes_->empty())) next = *(_holes_->begin());
237 else // in other case
238 next = _boundVal_;
239
240 return next;
241 }

References _boundVal_, and _holes_.

◆ nodes()

INLINE const NodeGraphPart & gum::NodeGraphPart::nodes ( ) const
inherited

return *this as a NodeGraphPart

Definition at line 368 of file nodeGraphPart_inl.h.

368 {
369 return *(static_cast< const NodeGraphPart* >(this));
370 }

References NodeGraphPart().

Referenced by gum::MeekRules::_complete_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::ClassBayesNet< GUM_SCALAR >::_init_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVE< GUM_SCALAR >::_initLiftedNodes_(), gum::MeekRules::_orientDoubleHeadedArcs_(), gum::MeekRules::_propagates_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::PRMFactory< GUM_SCALAR >::addAttribute(), gum::UndiGraph::hasUndirectedCycle(), gum::DAG::moralGraph(), gum::PDAG::moralGraph(), gum::DAG::moralizedAncestralGraph(), gum::PDAG::moralizedAncestralGraph(), gum::prm::gspan::Pattern::nodes(), gum::UndiGraph::nodes2ConnectedComponent(), gum::learning::Miic::orientDoubleHeadedArcs_(), gum::UndiGraph::partialUndiGraph(), gum::learning::IBNLearner::prepareMiic_(), gum::MeekRules::propagateToDAG(), gum::DiGraph::toDot(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), and gum::UndiGraph::toDot().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ nodesPropertyFromFunction()

template<typename VAL>
NodeProperty< VAL > gum::NodeGraphPart::nodesPropertyFromFunction ( VAL(* f )(const NodeId &),
Size size = 0 ) const
inherited

a method to create a HashTable with key:NodeId and value:VAL

VAL are computed from the nodes using for all node x, VAL f(x). This method is a wrapper of the same method in HashTable.

See also
HashTable::map.
Parameters
fa function assigning a VAL to any node
sizean optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of nodes. If you do not specify this parameter, the method will assign it for you.

References nodesPropertyFromFunction(), and size().

Referenced by nodesPropertyFromFunction().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ nodesPropertyFromVal()

template<typename VAL>
NodeProperty< VAL > gum::NodeGraphPart::nodesPropertyFromVal ( const VAL & a,
Size size = 0 ) const
inherited

a method to create a hashMap with key:NodeId and value:VAL

for all nodes, the value stored is a. This method is a wrapper of the same method in HashTable.

See also
HashTable::map.
Parameters
athe default value assigned to each edge in the returned Property
sizean optional parameter enabling to fine-tune the returned Property. Roughly speaking, it is a good practice to have a size equal to half the number of nodes. If you do not specify this parameter, the method will assign it for you.

References nodesPropertyFromVal(), and size().

Referenced by gum::BinaryJoinTreeConverterDefault::convert(), gum::UndiGraph::hasUndirectedCycle(), and nodesPropertyFromVal().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ operator!=()

INLINE bool gum::NodeGraphPart::operator!= ( const NodeGraphPart & p) const
inherited

check whether two NodeGraphParts contain different nodes

Parameters
pthe NodeGraphPart to be compared with "this"

Definition at line 354 of file nodeGraphPart_inl.h.

354{ return !operator==(p); }
gum::NodeGraphPart::operator==
bool operator==(const NodeGraphPart &p) const
check whether two NodeGraphParts contain the same nodes
Definition nodeGraphPart_inl.h:343

References NodeGraphPart(), and operator==().

Here is the call graph for this function:

◆ operator=()

INLINE DiGraph & gum::DiGraph::operator= ( const DiGraph & g)

copy operator

Parameters
gthe DiGraph to copy

Definition at line 68 of file diGraph_inl.h.

68 {
69 // avoid self assigment
70 if (this != &g) {
71 DiGraph::clear();
72 NodeGraphPart::operator=(g);
73 ArcGraphPart::operator=(g);
74 }
75
76 return *this;
77 }
gum::ArcGraphPart::operator=
ArcGraphPart & operator=(const ArcGraphPart &s)
copy operator
Definition arcGraphPart.cpp:121
gum::NodeGraphPart::operator=
NodeGraphPart & operator=(const NodeGraphPart &p)
copy operator
Definition nodeGraphPart_inl.h:225

References DiGraph(), clear(), gum::ArcGraphPart::operator=(), and gum::NodeGraphPart::operator=().

Referenced by gum::DAG::operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ operator==() [1/3]

INLINE bool gum::ArcGraphPart::operator== ( const ArcGraphPart & p) const
inherited

tests whether two ArcGraphParts contain the same arcs

Parameters
pthe ArcGraphPart that we compare with this

Definition at line 201 of file arcGraphPart_inl.h.

201{ return _arcs_ == p._arcs_; }

References ArcGraphPart(), and _arcs_.

Referenced by gum::DiGraph::operator==(), and gum::MixedGraph::operator==().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ operator==() [2/3]

INLINE bool gum::DiGraph::operator== ( const DiGraph & g) const

tests whether two DiGraphs are identical (same nodes, same arcs)

Parameters
gthe DiGraph with which "this" is compared

Definition at line 89 of file diGraph_inl.h.

89 {
90 return ArcGraphPart::operator==(p) && NodeGraphPart::operator==(p);
91 }
gum::ArcGraphPart::operator==
bool operator==(const ArcGraphPart &p) const
tests whether two ArcGraphParts contain the same arcs
Definition arcGraphPart_inl.h:201

References DiGraph(), gum::ArcGraphPart::operator==(), and gum::NodeGraphPart::operator==().

Here is the call graph for this function:

◆ operator==() [3/3]

INLINE bool gum::NodeGraphPart::operator== ( const NodeGraphPart & p) const
inherited

check whether two NodeGraphParts contain the same nodes

Parameters
pthe NodeGraphPart to be compared with "this"

Definition at line 343 of file nodeGraphPart_inl.h.

343 {
344 if (_boundVal_ != p._boundVal_) return false;
345
346 if (_holes_)
347 if (p._holes_) return (*_holes_ == *p._holes_);
348 else return false;
349 else if (p._holes_) return false;
350
351 return true;
352 }

References NodeGraphPart(), _boundVal_, and _holes_.

Referenced by operator!=(), gum::DiGraph::operator==(), gum::MixedGraph::operator==(), and gum::UndiGraph::operator==().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ parents() [1/2]

INLINE NodeSet gum::ArcGraphPart::parents ( const NodeSet & ids) const
inherited

returns the set of parents of a set of nodes

Definition at line 94 of file arcGraphPart_inl.h.

94 {
95 NodeSet res;
96 for (const auto node: ids)
97 res += parents(node);
98 return res;
99 }

References parents().

Here is the call graph for this function:

◆ parents() [2/2]

INLINE const NodeSet & gum::ArcGraphPart::parents ( NodeId id) const
inherited

returns the set of nodes with arc ingoing to a given node

Note that the set of arcs returned may be empty if no arc within the ArcGraphPart is ingoing into the given node.

Parameters
idthe node toward which the arcs returned are pointing

Definition at line 75 of file arcGraphPart_inl.h.

75 {
76 if (_parents_.exists(id)) return *(_parents_[id]);
77 else return emptyNodeSet;
78 }

References _parents_, and gum::emptyNodeSet.

Referenced by gum::MeekRules::_complete_(), gum::MeekRules::_critereMinParents_(), gum::learning::Miic::_existsDirectedPath_(), gum::learning::SimpleMiic::_existsDirectedPath_(), gum::MeekRules::_existsDirectedPath_(), gum::learning::Miic::_existsNonTrivialDirectedPath_(), gum::learning::SimpleMiic::_existsNonTrivialDirectedPath_(), gum::prm::gspan::Pattern::_expandCodeIsMinimal_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClass_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClassDag_(), gum::prm::LayerGenerator< GUM_SCALAR >::_generateClasses_(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::_generateCluster_(), gum::prm::SVE< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVED< GUM_SCALAR >::_initElimOrder_(), gum::prm::SVE< GUM_SCALAR >::_initLiftedNodes_(), gum::prm::SVED< GUM_SCALAR >::_initLiftedNodes_(), gum::MeekRules::_isOrientable_(), gum::DAG::_minimalCondSetVisitDn_(), gum::DAG::_minimalCondSetVisitUp_(), gum::prm::gspan::Pattern::_not_rec_(), gum::MeekRules::_orientDoubleHeadedArcs_(), gum::MeekRules::_propagates_(), gum::learning::Miic::_propagatingOrientationMiic_(), gum::learning::SimpleMiic::_propagatingOrientationMiic_(), gum::prm::gspan::Pattern::_rec_(), gum::EssentialGraph::_strongly_protected_(), ancestors(), gum::BarrenNodesFinder::barrenNodes(), gum::MixedGraph::boundary(), directedPath(), directedUnorientedPath(), eraseParents(), family(), gum::MixedGraph::hasMixedOrientedPath(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::initialize_(), gum::prm::PRMClassElementContainer< double >::isInputNode(), gum::learning::Miic::isMaxIndegree_(), gum::prm::gspan::Pattern::isMinimal(), gum::learning::SimpleMiic::isOrientable_(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::credal::CNLoopyPropagation< GUM_SCALAR >::makeInferenceNodeToNeighbours_(), gum::DAG::minimalCondSet(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::DAG::moralGraph(), gum::PDAG::moralGraph(), gum::DAG::moralizedAncestralGraph(), gum::learning::Miic::orientDoubleHeadedArcs_(), gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), parents(), gum::rec_ancestral(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::prm::gspan::Pattern::remove(), gum::BayesBall::requisiteNodes(), gum::dSeparationAlgorithm::requisiteNodes(), gum::prm::gspan::Pattern::rightmostPath(), gum::DAGCycleDetector::setDAG(), and unvirtualizedEraseParents().

◆ populateNodes()

void gum::NodeGraphPart::populateNodes ( const NodeGraphPart & s)
inherited

populateNodes clears *this and fills it with the same nodes as "s"

populateNodes should basically be the preferred way to insert nodes with IDs not selected by the internal idFactory.

Parameters
sthe NodeGraphPart to be copied

Definition at line 83 of file nodeGraphPart.cpp.

83 {
84 clear(); // "virtual" flush of the nodes set
85 _holes_size_ = s._holes_size_;
86 _holes_resize_policy_ = s._holes_resize_policy_;
87
88 if (s._holes_) _holes_ = new NodeSet(*s._holes_);
89
90 _boundVal_ = s._boundVal_;
91
92 _updateEndIteratorSafe_();
93 }
gum::NodeGraphPart::clear
virtual void clear()
alias for clearNodes
Definition nodeGraphPart_inl.h:319

References NodeGraphPart(), _boundVal_, _holes_, _holes_resize_policy_, _holes_size_, _updateEndIteratorSafe_(), and clear().

Referenced by gum::DAG::moralGraph(), gum::PDAG::moralGraph(), and operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ populateNodesFromProperty()

template<typename T>
void gum::NodeGraphPart::populateNodesFromProperty ( const NodeProperty< T > & h)
inherited

populateNodesFromProperty clears *this and fills it with the keys of "h"

populateNodes should basically be the preferred way to insert nodes with IDs not selected by the internal idFactory.

References NodeGraphPart(), begin(), end(), and toString().

Here is the call graph for this function:

◆ size()

INLINE Size gum::NodeGraphPart::size ( ) const
inherited

alias for sizeNodes

Definition at line 288 of file nodeGraphPart_inl.h.

288{ return sizeNodes(); }

References sizeNodes().

Referenced by gum::StaticTriangulation::StaticTriangulation(), gum::prm::gspan::DFSTree< GUM_SCALAR >::_addChild_(), gum::StaticTriangulation::_triangulate_(), gum::learning::GreedyHillClimbing::learnStructure(), gum::learning::LocalSearchWithTabuList::learnStructure(), nodesPropertyFromFunction(), nodesPropertyFromVal(), gum::BayesBall::relevantTensors(), gum::dSeparationAlgorithm::relevantTensors(), gum::BayesBall::requisiteNodes(), gum::dSeparationAlgorithm::requisiteNodes(), gum::StaticTriangulation::setGraph(), gum::DAGmodel::size(), gum::prm::gspan::Pattern::size(), gum::UGmodel::size(), and gum::UndiGraph::toDot().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ sizeArcs()

INLINE Size gum::ArcGraphPart::sizeArcs ( ) const
inherited

indicates the number of arcs stored within the ArcGraphPart

Definition at line 57 of file arcGraphPart_inl.h.

57{ return _arcs_.size(); }

References _arcs_.

Referenced by gum::prm::gspan::Pattern::sizeArcs().

Here is the caller graph for this function:

◆ sizeNodes()

INLINE Size gum::NodeGraphPart::sizeNodes ( ) const
inherited

returns the number of nodes in the NodeGraphPart

Definition at line 284 of file nodeGraphPart_inl.h.

284 {
285 return (_holes_) ? (_boundVal_ - _holes_->size()) : _boundVal_;
286 }

References _boundVal_, and _holes_.

Referenced by gum::BinaryJoinTreeConverterDefault::_markConnectedComponent_(), asNodeSet(), gum::BinaryJoinTreeConverterDefault::convert(), emptyNodes(), and size().

Here is the caller graph for this function:

◆ toDot()

std::string gum::DiGraph::toDot ( ) const
virtual

to friendly display the content of the graph in the DOT syntax

Parameters
nameThe graph name in the dot syntax. Default is G.
Returns
Returns a string describing the graph in the dot syntax

Reimplemented in gum::MixedGraph, gum::PDAG, and gum::prm::gspan::Pattern.

Definition at line 88 of file diGraph.cpp.

88 {
89 std::stringstream strBuff;
90 std::string tab = " ";
91 strBuff << "digraph {" << std::endl;
92
93 for (const auto node: nodes())
94 strBuff << tab << node << ";" << std::endl;
95
96 strBuff << std::endl;
97
98 for (const auto& arc: arcs())
99 strBuff << tab << arc.tail() << " -> " << arc.head() << ";" << std::endl;
100
101 strBuff << "}" << std::endl << std::endl;
102 return strBuff.str();
103 }

References gum::ArcGraphPart::arcs(), and gum::NodeGraphPart::nodes().

Here is the call graph for this function:

◆ topologicalOrder()

Sequence< NodeId > gum::DiGraph::topologicalOrder ( ) const

Build and return a topological order.

Exceptions
InvalidDirectedCycleRaised if this DiGraph contains cycles.

Definition at line 111 of file diGraph.cpp.

111 {
112 Sequence< NodeId > topologicalOrder;
113 const auto& dag = *this;
114
115 if (dag.empty()) return topologicalOrder;
116
117 auto border = std::vector< NodeId >();
118 border.reserve(dag.size() / 2);
119 auto count = dag.nodesPropertyFromVal< Size >(0, dag.size());
120 for (const auto node: dag.nodes()) {
121 if (dag.parents(node).empty()) { border.push_back(node); }
122 count[node] = dag.parents(node).size();
123 }
124
125 if (border.empty()) {
126 GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.");
127 }
128
129 while (!border.empty()) {
130 const auto root = border.back();
131 border.pop_back();
132
133 if (topologicalOrder.exists(root)) {
134 GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.");
135 }
136 topologicalOrder.insert(root);
137
138 for (const auto child: dag.children(root)) {
139 if (count[child] == 1) { border.push_back(child); }
140 if (count[child] == 0) {
141 GUM_ERROR(InvalidDirectedCycle, "cycles prevent the creation of a topological ordering.");
142 }
143 count[child]--;
144 }
145 }
146
147 GUM_ASSERT(topologicalOrder.size() == dag.size());
148 return topologicalOrder;
149 }
gum::DiGraph::topologicalOrder
Sequence< NodeId > topologicalOrder() const
Build and return a topological order.
Definition diGraph.cpp:111

References GUM_ERROR, and topologicalOrder().

Referenced by gum::IBayesNet< double >::arcs(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), and topologicalOrder().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ toString()

std::string gum::DiGraph::toString ( ) const
virtual

to friendly display the content of the graph

Reimplemented from gum::NodeGraphPart.

Reimplemented in gum::MixedGraph.

Definition at line 81 of file diGraph.cpp.

81 {
82 std::string s = NodeGraphPart::toString();
83 s += " , ";
84 s += ArcGraphPart::toString();
85 return s;
86 }
gum::ArcGraphPart::toString
std::string toString() const
to friendly display the content of the ArcGraphPart
Definition arcGraphPart.cpp:154
gum::NodeGraphPart::toString
virtual std::string toString() const
a function to display the set of nodes
Definition nodeGraphPart.cpp:124

References gum::ArcGraphPart::toString(), and gum::NodeGraphPart::toString().

Referenced by gum::operator<<().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ unvirtualizedEraseChildren()

INLINE void gum::ArcGraphPart::unvirtualizedEraseChildren ( NodeId id)
inherited

same function as eraseChildren but without any virtual call to an erase

Parameters
idthe node whose outgoing arcs will be removed

Definition at line 189 of file arcGraphPart_inl.h.

189 {
190 if (_children_.exists(id)) {
191 const NodeSet& children = *(_children_[id]);
192
193 for (auto iter = children.beginSafe(); // safe iterator needed here
194 iter != children.endSafe();
195 ++iter) {
196 ArcGraphPart::eraseArc(Arc(id, *iter));
197 }
198 }
199 }

References _children_, children(), and eraseArc().

Referenced by gum::DiGraph::eraseNode(), and gum::MixedGraph::eraseNode().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ unvirtualizedEraseParents()

INLINE void gum::ArcGraphPart::unvirtualizedEraseParents ( NodeId id)
inherited

same function as eraseParents but without any virtual call to an erase

Parameters
idthe node whose ingoing arcs will be removed

Definition at line 177 of file arcGraphPart_inl.h.

177 {
178 if (_parents_.exists(id)) {
179 const NodeSet& parents = *(_parents_[id]);
180
181 for (auto iter = parents.beginSafe(); // safe iterator needed here
182 iter != parents.endSafe();
183 ++iter) {
184 ArcGraphPart::eraseArc(Arc(*iter, id));
185 }
186 }
187 }

References _parents_, eraseArc(), and parents().

Referenced by gum::DiGraph::eraseNode(), and gum::MixedGraph::eraseNode().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ unvirtualizedEraseSetOfArcs_()

INLINE void gum::ArcGraphPart::unvirtualizedEraseSetOfArcs_ ( const ArcSet & set)
protectedinherited

similar to eraseSetOfArcs_ except that it is unvirtualized

Warning
this function uses ArcGraphPart::eraseArc, hence, as compared with eraseSetOfArcs_, it removes the arcs without calling a virtual eraseArc

Definition at line 172 of file arcGraphPart_inl.h.

172 {
173 for (const auto& arc: set)
174 ArcGraphPart::eraseArc(arc);
175 }

References eraseArc().

Here is the call graph for this function:

Member Data Documentation

◆ _arcs_

Set< Arc > gum::ArcGraphPart::_arcs_
privateinherited

the set of all the arcs contained within the ArcGraphPart

Definition at line 316 of file arcGraphPart.h.

Referenced by ArcGraphPart(), ArcGraphPart(), addArc(), arcs(), clearArcs(), emptyArcs(), eraseArc(), existsArc(), operator=(), operator==(), sizeArcs(), and toString().

◆ _boundVal_

NodeId gum::NodeGraphPart::_boundVal_
privateinherited

the id below which NodeIds may belong to the NodeGraphPart

Definition at line 528 of file nodeGraphPart.h.

Referenced by NodeGraphPart(), NodeGraphPart(), _addHole_(), _clearNodes_(), _updateEndIteratorSafe_(), addNode(), addNodeWithId(), asNodeSet(), bound(), existsNode(), nextNodeId(), operator==(), populateNodes(), sizeNodes(), and toString().

◆ _children_

NodeProperty< NodeSet* > gum::ArcGraphPart::_children_
privateinherited

for each arc, the set of its children

Definition at line 322 of file arcGraphPart.h.

Referenced by ArcGraphPart(), _checkChildren_(), addArc(), children(), clearArcs(), eraseArc(), eraseChildren(), operator=(), and unvirtualizedEraseChildren().

◆ _endIteratorSafe_

NodeGraphPartIteratorSafe gum::NodeGraphPart::_endIteratorSafe_
privateinherited

the end iterator (used to speed-up parsings of the NodeGraphPart)

Definition at line 525 of file nodeGraphPart.h.

Referenced by NodeGraphPart(), NodeGraphPart(), _updateEndIteratorSafe_(), end(), and endSafe().

◆ _holes_

NodeSet* gum::NodeGraphPart::_holes_
privateinherited

the set of nodes not contained in the NodeGraphPart in the interval 1.

. max

Warning
holes may be nullptr.

Definition at line 516 of file nodeGraphPart.h.

Referenced by NodeGraphPart(), NodeGraphPart(), ~NodeGraphPart(), _addHole_(), _clearNodes_(), _eraseHole_(), _inHoles_(), _sizeHoles_(), addNode(), addNodeWithId(), nextNodeId(), operator==(), populateNodes(), and sizeNodes().

◆ _holes_resize_policy_

bool gum::NodeGraphPart::_holes_resize_policy_
privateinherited

value for holes configuration

Definition at line 522 of file nodeGraphPart.h.

Referenced by NodeGraphPart(), NodeGraphPart(), _addHole_(), addNodeWithId(), and populateNodes().

◆ _holes_size_

Size gum::NodeGraphPart::_holes_size_
privateinherited

value for holes configuration

Definition at line 519 of file nodeGraphPart.h.

Referenced by NodeGraphPart(), NodeGraphPart(), _addHole_(), addNodeWithId(), and populateNodes().

◆ _parents_

NodeProperty< NodeSet* > gum::ArcGraphPart::_parents_
privateinherited

for each arc, the sets of its parents

Definition at line 319 of file arcGraphPart.h.

Referenced by ArcGraphPart(), _checkParents_(), addArc(), clearArcs(), eraseArc(), eraseParents(), existsArc(), operator=(), parents(), and unvirtualizedEraseParents().

◆ onArcAdded

Signaler2< NodeId, NodeId > gum::ArcGraphPart::onArcAdded
inherited

Definition at line 102 of file arcGraphPart.h.

Referenced by ArcGraphPart(), addArc(), and operator=().

◆ onArcDeleted

Signaler2< NodeId, NodeId > gum::ArcGraphPart::onArcDeleted
inherited

Definition at line 103 of file arcGraphPart.h.

Referenced by clearArcs(), and eraseArc().

◆ onNodeAdded

Signaler1< NodeId > gum::NodeGraphPart::onNodeAdded
inherited

Definition at line 289 of file nodeGraphPart.h.

Referenced by addNode(), and addNodeWithId().

◆ onNodeDeleted

Signaler1< NodeId > gum::NodeGraphPart::onNodeDeleted
inherited

Definition at line 290 of file nodeGraphPart.h.

Referenced by _clearNodes_(), and eraseNode().

The documentation for this class was generated from the following files:
aGrUM 2.3.2

© PHW&CG&others - 2022
DoXyGeN 1.16.1