aGrUM  0.13.2
gum::CliqueGraph Class Reference

Basic graph of cliques. More...

#include <cliqueGraph.h>

+ Inheritance diagram for gum::CliqueGraph:
+ Collaboration diagram for gum::CliqueGraph:

Public Attributes

Signaler1< NodeIdonNodeAdded
 
Signaler1< NodeIdonNodeDeleted
 
Signaler2< NodeId, NodeIdonEdgeAdded
 
Signaler2< NodeId, NodeIdonEdgeDeleted
 

Public Member Functions

Constructors / Destructors
 CliqueGraph (Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
 basic constructor: creates an empty clique graph More...
 
 CliqueGraph (const CliqueGraph &from)
 copy constructor More...
 
virtual ~CliqueGraph ()
 destructor More...
 
Accessors/Modifiers
virtual void addEdge (const NodeId first, const NodeId second)
 inserts a new edge between two cliques More...
 
virtual void eraseEdge (const Edge &edge)
 removes an edge (and its separator) from the clique graph More...
 
virtual void clearEdges ()
 removes all edges and their separators More...
 
NodeId addNode (const NodeSet &clique)
 adds a new clique to the graph More...
 
virtual NodeId addNode ()
 adds a new clique to the graph More...
 
virtual void addNode (const NodeId id, const NodeSet &clique)
 try to add a new clique to the graph More...
 
virtual void addNode (const NodeId id)
 try to add a new clique to the graph More...
 
virtual void eraseNode (const NodeId node)
 removes a given clique from the clique graph More...
 
virtual void clear ()
 removes all the cliques and separators from the graph (as well as their adjacent edges) More...
 
const NodeSetclique (const NodeId idClique) const
 returns the set of nodes included into a given clique More...
 
NodeId container (const NodeId idNode) const
 returns the id of a clique containing the node the id of which is in argument More...
 
virtual void setClique (const NodeId idClique, const NodeSet &new_clique)
 changes the set of nodes included into a given clique and returns the new set More...
 
virtual void addToClique (const NodeId clique_id, const NodeId node_id)
 changes the set of nodes included into a given clique and returns the new set More...
 
virtual void eraseFromClique (const NodeId clique_id, const NodeId node_id)
 remove a node from a clique More...
 
const NodeSetseparator (const Edge &edge) const
 returns the separator included in a given edge More...
 
const NodeSetseparator (const NodeId clique1, const NodeId clique) const
 returns the separator included in an edge specified by its extremities More...
 
std::vector< NodeIdcontainerPath (const NodeId node1, const NodeId node2) const
 returns a path from a clique containing node1 to a clique containing node2 More...
 
bool hasRunningIntersection () const
 indicates whether the running intersection property holds More...
 
bool isJoinTree () const
 indicates whether the graph is a join tree More...
 
virtual const std::string toString () const
 friendly displays the content of the CliqueGraph More...
 
virtual const std::string toDot () const
 friendly displays the content of the CliqueGraph in DOT format More...
 
Operators
CliqueGraphoperator= (const CliqueGraph &from)
 copy operator More...
 
bool operator!= (const CliqueGraph &from) const
 checks whether two clique graphs are different More...
 
bool operator== (const CliqueGraph &from) const
 checks whether two clique graphs are equal More...
 
Operators
bool operator== (const UndiGraph &g) const
 tests whether two UndiGraphs are identical (same nodes, same edges) More...
 
bool operator!= (const UndiGraph &g) const
 tests whether two UndiGraphs are different More...
 
Operators
bool operator== (const NodeGraphPart &p) const
 check whether two NodeGraphParts contain the same nodes More...
 
bool operator!= (const NodeGraphPart &p) const
 check whether two NodeGraphParts contain different nodes More...
 
Operators
bool operator== (const EdgeGraphPart &p) const
 tests whether two EdgeGraphParts contain the same edges More...
 
bool operator!= (const EdgeGraphPart &p) const
 tests whether two EdgeGraphParts contain different edges More...
 
Accessors/Modifiers
bool hasUndirectedCycle () const
 checks whether the graph contains cycles More...
 
virtual UndiGraph partialUndiGraph (NodeSet nodesSet)
 returns the partial graph formed by the nodes given in parameter More...
 
Accessors/Modifiers
void populateNodes (const NodeGraphPart &s)
 populateNodes clears *this and fills it with the same nodes as "s" More...
 
template<typename T >
void populateNodesFromProperty (const NodeProperty< T > &h)
 populateNodesFromProperty clears *this and fills it with the keys of "h" More...
 
NodeId nextNodeId () const
 returns a new node id, not yet used by any node More...
 
std::vector< NodeIdaddNodes (Size n)
 insert n nodes More...
 
virtual void addNodeWithId (const NodeId id)
 try to insert a node with the given id More...
 
bool existsNode (const NodeId id) const
 returns true iff the NodeGraphPart contains the given nodeId More...
 
bool exists (const NodeId id) const
 alias for existsNode More...
 
bool emptyNodes () const
 indicates whether there exists nodes in the NodeGraphPart More...
 
bool empty () const
 alias for emptyNodes More...
 
virtual void clearNodes ()
 remove all the nodes from the NodeGraphPart More...
 
Size sizeNodes () const
 returns the number of nodes in the NodeGraphPart More...
 
Size size () const
 alias for sizeNodes More...
 
NodeId bound () const
 returns a number n such that all node ids are strictly lower than n More...
 
NodeSet asNodeSet () const
 returns a copy of the set of nodes represented by the NodeGraphPart More...
 
const NodeGraphPartnodes () const
 return *this as a NodeGraphPart More...
 
node_iterator_safe beginSafe () const
 a begin iterator to parse the set of nodes contained in the NodeGraphPart More...
 
const node_iterator_safeendSafe () const noexcept
 the end iterator to parse the set of nodes contained in the NodeGraphPart More...
 
node_iterator begin () const noexcept
 a begin iterator to parse the set of nodes contained in the NodeGraphPart More...
 
const node_iteratorend () const noexcept
 the end iterator to parse the set of nodes contained in the NodeGraphPart More...
 
template<typename VAL >
NodeProperty< VAL > nodesProperty (VAL(*f)(const NodeId &), Size size=0) const
 a method to create a HashTable with key:NodeId and value:VAL More...
 
template<typename VAL >
NodeProperty< VAL > nodesProperty (const VAL &a, Size size=0) const
 a method to create a hashMap with key:NodeId and value:VAL More...
 
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)) More...
 
Accessors/Modifiers
bool existsEdge (const Edge &edge) const
 indicates whether a given edge exists More...
 
bool existsEdge (const NodeId n1, const NodeId n2) const
 indicates whether a given edge exists More...
 
bool emptyEdges () const
 indicates wether the EdgeGraphPart contains any edge More...
 
Size sizeEdges () const
 indicates the number of edges stored within the EdgeGraphPart More...
 
const EdgeSetedges () const
 returns the set of edges stored within the EdgeGraphPart More...
 
const NodeSetneighbours (const NodeId id) const
 returns the set of edges adjacent to a given node More...
 
void eraseNeighbours (const NodeId id)
 erase all the edges adjacent to a given node More...
 
void unvirtualizedEraseNeighbours (const NodeId id)
 same function as eraseNeighbours but without any virtual call to an erase More...
 
template<typename VAL >
EdgeProperty< VAL > edgesProperty (VAL(*f)(const Edge &), Size size=0) const
 a method to create a hashMap of VAL from a set of edges (using for every edge, say x, the VAL f(x)) More...
 
template<typename VAL >
EdgeProperty< VAL > edgesProperty (const VAL &a, Size size=0) const
 a method to create a hashMap of VAL from a set of edges (using for every edge, say x, the VAL a) More...
 
template<typename VAL >
List< VAL > listMapEdges (VAL(*f)(const Edge &)) const
 a method to create a list of VAL from a set of edges (using for every edge, say x, the VAL f(x)) More...
 
const std::vector< NodeIdundirectedPath (const NodeId node1, const NodeId node2) const
 returns a possible path from node1 to node2 in the edge set More...
 

Public Types

typedef NodeGraphPartIterator NodeIterator
 
typedef NodeGraphPartIterator NodeConstIterator
 
typedef NodeGraphPartIteratorSafe NodeIteratorSafe
 
typedef NodeGraphPartIteratorSafe NodeConstIteratorSafe
 
typedef EdgeSetIterator EdgeIterator
 
using node_iterator = NodeGraphPartIterator
 types for STL compliance More...
 
using node_const_iterator = NodeGraphPartIterator
 types for STL compliance More...
 
using node_iterator_safe = NodeGraphPartIteratorSafe
 types for STL compliance More...
 
using node_const_iterator_safe = NodeGraphPartIteratorSafe
 types for STL compliance More...
 

Classes

struct  __RunningIntersect
 structure used for the computation of the running intersection property More...
 

Detailed Description

Basic graph of cliques.

A CliqueGraph is an undirected graph the nodes of which are Cliques, i.e., sets of NodeIds. Cliques are linked by Edges. These edges contain separators that are actually the intersection of the two Cliques at the extermities of the edge.

Definition at line 55 of file cliqueGraph.h.

Member Typedef Documentation

Definition at line 74 of file edgeGraphPart.h.

types for STL compliance

Definition at line 258 of file nodeGraphPart.h.

types for STL compliance

Definition at line 260 of file nodeGraphPart.h.

types for STL compliance

Definition at line 257 of file nodeGraphPart.h.

types for STL compliance

Definition at line 259 of file nodeGraphPart.h.

Definition at line 267 of file nodeGraphPart.h.

Definition at line 266 of file nodeGraphPart.h.

Constructor & Destructor Documentation

gum::CliqueGraph::CliqueGraph ( Size  nodes_size = HashTableConst::default_size,
bool  nodes_resize_policy = true,
Size  edges_size = HashTableConst::default_size,
bool  edges_resize_policy = true 
)
explicit

basic constructor: creates an empty clique graph

Parameters
nodes_sizethe size of the hash table used to store all the nodes
nodes_resize_policythe resizing policy of this hash table
edges_sizethe size of the hash table used to store all the edges
edges_resize_policythe resizing policy of this hash table
gum::CliqueGraph::CliqueGraph ( const CliqueGraph from)

copy constructor

Parameters
fromthe CliqueGraph that will be copied into this
virtual gum::CliqueGraph::~CliqueGraph ( )
virtual

destructor

Member Function Documentation

bool gum::CliqueGraph::__runningIntersectionDFS ( const NodeId  clique,
const NodeId  from,
__RunningIntersect infos_DFS 
) const
private

function used for the computation of the running intersection property

void gum::CliqueGraph::__updateSeparators ( const NodeId  clique1)
private

function used to update the separators when a clique is modified

virtual void gum::CliqueGraph::addEdge ( const NodeId  first,
const NodeId  second 
)
virtual

inserts a new edge between two cliques

Parameters
firstthe id of one extremity of the new edge to be inserted
secondthe id of the other extremity of the new edge to be inserted
Warning
if the edge already exists, nothing is done. In particular, no exception is raised.
Exceptions
InvalidNodeif first and/or second do not belong to the graph nodes

Reimplemented from gum::UndiGraph.

Referenced by gum::StaticTriangulation::__computeEliminationTree(), gum::DefaultJunctionTreeStrategy::__computeJunctionTree(), gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), and gum::BinaryJoinTreeConverterDefault::__convertClique().

+ Here is the caller graph for this function:

NodeId gum::CliqueGraph::addNode ( const NodeSet clique)

adds a new clique to the graph

Returns
the id chosen for the new clique

Referenced by gum::StaticTriangulation::__computeEliminationTree(), gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), and gum::BinaryJoinTreeConverterDefault::__convertClique().

+ Here is the caller graph for this function:

virtual NodeId gum::CliqueGraph::addNode ( )
virtual

adds a new clique to the graph

Returns
the id chosen for the new clique

Reimplemented from gum::NodeGraphPart.

virtual void gum::CliqueGraph::addNode ( const NodeId  id,
const NodeSet clique 
)
virtual

try to add a new clique to the graph

Exceptions
DuplicateElementexception is thrown if the id of the clique already exists within the clique graph
virtual void gum::CliqueGraph::addNode ( const NodeId  id)
virtual

try to add a new clique to the graph

Exceptions
DuplicateElementexception is thrown if the id of the clique already exists within the clique graph
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 265 of file nodeGraphPart_inl.h.

265  {
266  std::vector< NodeId > v;
267  v.reserve(N);
268  for (Idx i = 0; i < N; i++)
269  v.push_back(this->addNode());
270  return v;
271  }
unsigned long Idx
Type for indexes.
Definition: types.h:43
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

Definition at line 126 of file nodeGraphPart.cpp.

References gum::NodeGraphPart::__boundVal, gum::NodeGraphPart::__eraseHole(), gum::NodeGraphPart::__holes, gum::NodeGraphPart::__inHoles(), gum::NodeGraphPart::__updateEndIteratorSafe(), GUM_EMIT1, GUM_ERROR, gum::Set< Key, Alloc >::insert(), and gum::NodeGraphPart::onNodeAdded.

Referenced by gum::prm::PRMClass< GUM_SCALAR >::__addCastDescendants(), gum::prm::PRMInterface< GUM_SCALAR >::__addCastDescendants(), gum::EssentialGraph::__buildEssentialGraph(), gum::MarkovBlanket::__buildMarkovBlanket(), gum::SpanningForestPrim::__computeInAComponent(), gum::prm::PRMClass< GUM_SCALAR >::__implementInterfaces(), gum::prm::PRMInterface< GUM_SCALAR >::__inheritInterface(), gum::learning::genericBNLearner::__learnDAG(), gum::prm::PRMInterface< GUM_SCALAR >::__overloadAttribute(), gum::prm::PRMClass< GUM_SCALAR >::__overloadAttribute(), gum::learning::genericBNLearner::__prepare_miic_3off2(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::InfluenceDiagram< GUM_SCALAR >::_addNode(), gum::InfluenceDiagram< GUM_SCALAR >::_moralGraph(), gum::prm::PRMInterface< GUM_SCALAR >::add(), gum::prm::PRMClass< GUM_SCALAR >::add(), gum::BayesNet< GUM_SCALAR >::add(), gum::prm::gspan::Pattern::addNodeWithLabel(), gum::prm::StructuredInference< GUM_SCALAR >::CData::CData(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::prm::PRMClass< GUM_SCALAR >::inheritAggregates(), gum::prm::PRMClass< GUM_SCALAR >::inheritAttributes(), gum::prm::PRMClass< GUM_SCALAR >::inheritParameters(), gum::prm::PRMClass< GUM_SCALAR >::inheritReferenceSlots(), gum::prm::PRMClass< GUM_SCALAR >::inheritSlotChains(), gum::BayesNetFragment< GUM_SCALAR >::installNode(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::InterfaceGraph(), gum::learning::Miic::learnStructure(), gum::UndiGraph::partialUndiGraph(), and gum::learning::StructuralConstraintDAG::StructuralConstraintDAG().

126  {
127  if (id >= __boundVal) {
128  if (id > __boundVal) { // we have to add holes
129  if (!__holes) __holes = new NodeSet();
130 
131  for (NodeId i = __boundVal; i < id; ++i)
132  __holes->insert(i);
133  }
134 
135  __boundVal = id + 1;
136 
138  } else {
139  if (__inHoles(id)) { // we fill a hole
140  __eraseHole(id);
141  } else {
142  GUM_ERROR(DuplicateElement, "Id " << id << " is already used");
143  }
144  }
145 
146  GUM_EMIT1(onNodeAdded, id);
147  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
#define GUM_EMIT1(signal, arg1)
Definition: signaler1.h:40
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
bool __inHoles(NodeId id) const
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
void __updateEndIteratorSafe()
updating endIterator (always at __max+1)
Signaler1< NodeId > onNodeAdded
void __eraseHole(NodeId id)
to delete hole.
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

virtual void gum::CliqueGraph::addToClique ( const NodeId  clique_id,
const NodeId  node_id 
)
virtual

changes the set of nodes included into a given clique and returns the new set

Exceptions
NotFoundexception is thrown if clique_id does not exist
DuplicateElementexception is thrown if clique_id set already contains the node

Referenced by gum::StaticTriangulation::__computeMaxPrimeJunctionTree().

+ Here is the caller graph for this function:

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())
as this is faster and consumes much less memory.

Definition at line 355 of file nodeGraphPart_inl.h.

References gum::Set< Key, Alloc >::insert().

Referenced by gum::InfluenceDiagram< GUM_SCALAR >::getPartialTemporalOrder().

355  {
356  NodeSet son(sizeNodes());
357 
358  if (!empty()) {
359  for (NodeId n = 0; n < __boundVal; ++n) {
360  if (!__inHoles(n)) son.insert(n);
361  }
362  }
363 
364  return son;
365  }
Size sizeNodes() const
returns the number of nodes in the NodeGraphPart
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
bool __inHoles(NodeId id) const
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
bool empty() const
alias for emptyNodes

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

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

Definition at line 327 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::_validate().

Referenced by gum::prm::gspan::DFSTree< GUM_SCALAR >::parent(), and gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot().

327  {
328  NodeGraphPartIterator it(*this);
329  it._validate(); // stop the iterator at the first not-in-holes
330  return it;
331  }
friend class NodeGraphPartIterator

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

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

Definition at line 313 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::_validate().

313  {
314  NodeGraphPartIteratorSafe it(*this);
315  it._validate(); // stop the iterator at the first not-in-holes
316  return it;
317  }
friend class NodeGraphPartIteratorSafe

+ Here is the call graph for this function:

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

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

Definition at line 302 of file nodeGraphPart_inl.h.

Referenced by gum::NodeGraphPart::__clearNodes(), gum::StaticTriangulation::__computeEliminationTree(), gum::NodeGraphPartIterator::_setPos(), and gum::NodeGraphPartIterator::_validate().

302 { return __boundVal; }
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart

+ Here is the caller graph for this function:

virtual void gum::CliqueGraph::clear ( )
virtual

removes all the cliques and separators from the graph (as well as their adjacent edges)

Reimplemented from gum::UndiGraph.

Referenced by gum::StaticTriangulation::__computeEliminationTree(), gum::DefaultJunctionTreeStrategy::clear(), and gum::StaticTriangulation::clear().

+ Here is the caller graph for this function:

virtual void gum::CliqueGraph::clearEdges ( )
virtual

removes all edges and their separators

Reimplemented from gum::EdgeGraphPart.

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

remove all the nodes from the NodeGraphPart

Definition at line 304 of file nodeGraphPart_inl.h.

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

304 { __clearNodes(); }
void __clearNodes()
code for clearing nodes (called twice)

+ Here is the caller graph for this function:

const NodeSet& gum::CliqueGraph::clique ( const NodeId  idClique) const

returns the set of nodes included into a given clique

Exceptions
NotFoundexception is raised if the clique does not belong to the clique graph

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree(), gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), gum::BarrenNodesFinder::barrenNodes(), and gum::StaticTriangulation::fillIns().

+ Here is the caller graph for this function:

NodeId gum::CliqueGraph::container ( const NodeId  idNode) const

returns the id of a clique containing the node the id of which is in argument

Warning
note that this method is time consuming as the clique graph does not contain a priori information about which clique could contain idNode. As a consequence, it searches the cliques until it finds one that actually contains idNode.
Exceptions
NotFoundexception is thrown if no clique contains idNode
std::vector< NodeId > gum::CliqueGraph::containerPath ( const NodeId  node1,
const NodeId  node2 
) const

returns a path from a clique containing node1 to a clique containing node2

Exceptions
NotFoundsuch path cannot be found
INLINE const EdgeSet & gum::EdgeGraphPart::edges ( ) const
inherited

returns the set of edges stored within the EdgeGraphPart

Definition at line 36 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__edges.

Referenced by gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), gum::learning::Miic::_initiation(), gum::BarrenNodesFinder::barrenNodes(), gum::EssentialGraph::edges(), and gum::SpanningForestPrim::edgesInSpanningForest().

36 { return __edges; }
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

+ Here is the caller graph for this function:

template<typename VAL >
EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty ( VAL(*)(const Edge &)  f,
Size  size = 0 
) const
inherited

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

Parameters
fa function assigning a VAL to any edge
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 edges. If you do not specify this parameter, the method will assign it for you.

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree().

+ Here is the caller graph for this function:

template<typename VAL >
EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty ( const VAL &  a,
Size  size = 0 
) const
inherited

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

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 edges. If you do not specify this parameter, the method will assign it for you.
INLINE bool gum::NodeGraphPart::empty ( ) const
inherited

alias for emptyNodes

Definition at line 300 of file nodeGraphPart_inl.h.

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

300 { return emptyNodes(); }
bool emptyNodes() const
indicates whether there exists nodes in the NodeGraphPart

+ Here is the caller graph for this function:

INLINE bool gum::EdgeGraphPart::emptyEdges ( ) const
inherited

indicates wether the EdgeGraphPart contains any edge

Definition at line 32 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__edges, and gum::Set< Key, Alloc >::empty().

32 { return __edges.empty(); }
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

+ Here is the call graph for this function:

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

indicates whether there exists nodes in the NodeGraphPart

Definition at line 298 of file nodeGraphPart_inl.h.

298 { return (sizeNodes() == 0); }
Size sizeNodes() const
returns the number of nodes in the NodeGraphPart
INLINE const NodeGraphPartIterator & gum::NodeGraphPart::end ( ) const
noexceptinherited

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

Definition at line 333 of file nodeGraphPart_inl.h.

Referenced by gum::MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >::toDot().

333  {
334  return __endIteratorSafe;
335  }
NodeGraphPartIteratorSafe __endIteratorSafe
the end iterator (used to speed-up parsings of the NodeGraphPart)

+ Here is the caller graph for this function:

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

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

Definition at line 323 of file nodeGraphPart_inl.h.

323  {
324  return __endIteratorSafe;
325  }
NodeGraphPartIteratorSafe __endIteratorSafe
the end iterator (used to speed-up parsings of the NodeGraphPart)
virtual void gum::CliqueGraph::eraseEdge ( const Edge edge)
virtual

removes an edge (and its separator) from the clique graph

Parameters
edgethe edge to be removed
Warning
if the edge does not exist, nothing is done. In particular, no exception is thrown.

Reimplemented from gum::EdgeGraphPart.

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree(), and gum::BinaryJoinTreeConverterDefault::__convertClique().

+ Here is the caller graph for this function:

virtual void gum::CliqueGraph::eraseFromClique ( const NodeId  clique_id,
const NodeId  node_id 
)
virtual

remove a node from a clique

If node_id cannot be found in the clique set, then the function does nothing. In particular, it does not throw any exception.

Exceptions
NotFoundexception is thrown if clique_id does not exist
INLINE void gum::EdgeGraphPart::eraseNeighbours ( const NodeId  id)
inherited

erase all the edges adjacent to a given node

Parameters
idthe node the adjacent edges of which will be removed
Warning
if no edge is adjacent to id, nothing is done. In particular, no exception is thrown.
although this method is not virtual, it calls method eraseEdge( const Edge& edge ) and, as such, has a "virtual" behaviour

Definition at line 80 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__neighbours, gum::EdgeGraphPart::eraseEdge(), and gum::EdgeGraphPart::neighbours().

80  {
81  if (__neighbours.exists(id)) {
82  const NodeSet& set = neighbours(id);
83 
84  for (auto iter = set.beginSafe(); iter != set.endSafe();
85  ++iter) { // safe iterator needed here
86  // warning: use this erase so that you actually use the virtualized
87  // edge removal function
88  eraseEdge(Edge(*iter, id));
89  }
90  }
91  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeProperty< NodeSet * > __neighbours
for each node, the set of its adjacent edges
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
virtual void eraseEdge(const Edge &edge)
removes an edge from the EdgeGraphPart

+ Here is the call graph for this function:

virtual void gum::CliqueGraph::eraseNode ( const NodeId  node)
virtual

removes a given clique from the clique graph

If the CliqueGraph does not contain the node, then nothing is done. In particular, no exception is raised.

Reimplemented from gum::UndiGraph.

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree().

+ Here is the caller graph for this function:

INLINE bool gum::NodeGraphPart::exists ( const NodeId  id) const
inherited
INLINE bool gum::EdgeGraphPart::existsEdge ( const Edge edge) const
inherited

indicates whether a given edge exists

Parameters
edgethe edge we test whether or not it belongs to the EdgeGraphPart

Definition at line 38 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__edges, and gum::Set< Key, Alloc >::contains().

Referenced by gum::StaticTriangulation::__computeMaxPrimeMergings(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::EssentialGraph::__strongly_protected(), gum::StaticTriangulation::__triangulate(), gum::learning::Miic::_orientation_3off2(), gum::learning::Miic::_orientation_miic(), gum::EdgeGraphPart::eraseEdge(), gum::StaticTriangulation::fillIns(), and gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::InterfaceGraph().

38  {
39  return __edges.contains(edge);
40  }
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:581
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

INLINE bool gum::EdgeGraphPart::existsEdge ( const NodeId  n1,
const NodeId  n2 
) const
inherited

indicates whether a given edge exists

Parameters
n1the id of one extremity of the edge we test the existence in the EdgeGraphPart
n2the id of the other extremity of the edge we test the existence in the EdgeGraphPart

Definition at line 42 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__neighbours.

43  {
44  return __neighbours.exists(first) && __neighbours[first]->exists(second);
45  }
NodeProperty< NodeSet * > __neighbours
for each node, the set of its adjacent edges
INLINE bool gum::NodeGraphPart::existsNode ( const NodeId  id) const
inherited
bool gum::CliqueGraph::hasRunningIntersection ( ) const

indicates whether the running intersection property holds

The function works properly even if the graph contains cycles.

bool gum::UndiGraph::hasUndirectedCycle ( ) const
inherited

checks whether the graph contains cycles

Definition at line 52 of file undiGraph.cpp.

References gum::List< Val, Alloc >::empty(), gum::List< Val, Alloc >::front(), gum::List< Val, Alloc >::insert(), gum::EdgeGraphPart::neighbours(), gum::NodeGraphPart::nodes(), gum::NodeGraphPart::nodesProperty(), and gum::List< Val, Alloc >::popFront().

52  {
53  List< std::pair< NodeId, NodeId > > open_nodes;
54  NodeProperty< bool > examined_nodes = nodesProperty(false);
55  std::pair< NodeId, NodeId > thePair;
56  NodeId current, from_current;
57 
58  for (const auto node : nodes()) {
59  // check if the node has already been examined (if this is not the case,
60  // this means that we are on a new connected component)
61  if (!examined_nodes[node]) {
62  // indicates that we are examining a new node
63  examined_nodes[node] = true;
64 
65  // check recursively all the nodes of node's connected component
66  thePair.first = node;
67  thePair.second = node;
68  open_nodes.insert(thePair);
69 
70  while (!open_nodes.empty()) {
71  // get a node to propagate
72  thePair = open_nodes.front();
73  open_nodes.popFront();
74 
75  current = thePair.first;
76  from_current = thePair.second;
77 
78  // check the neighbours
79  for (const auto new_node : neighbours(current))
80 
81  // avoid to check the node we are coming from
82  if (new_node != from_current) {
83  if (examined_nodes[new_node])
84  return true;
85  else {
86  examined_nodes[new_node] = true;
87  thePair.first = new_node;
88  thePair.second = current;
89  open_nodes.insert(thePair);
90  }
91  }
92  }
93  }
94  }
95 
96  return false;
97  }
NodeProperty< VAL > nodesProperty(VAL(*f)(const NodeId &), Size size=0) const
a method to create a HashTable with key:NodeId and value:VAL
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart

+ Here is the call graph for this function:

bool gum::CliqueGraph::isJoinTree ( ) const

indicates whether the graph is a join tree

template<typename VAL >
List< VAL > gum::EdgeGraphPart::listMapEdges ( VAL(*)(const Edge &)  f) const
inherited

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

Parameters
fa function assigning a VAL to any edge
template<typename VAL >
List< VAL > gum::NodeGraphPart::listMapNodes ( VAL(*)(const NodeId &)  f) 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
INLINE const NodeSet & gum::EdgeGraphPart::neighbours ( const NodeId  id) const
inherited

returns the set of edges adjacent to a given node

Note that the set of edges returned may be empty if no edge within the EdgeGraphPart is adjacent the given node.

Parameters
idthe node to which the edges are adjacent

Definition at line 75 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__checkNeighbours(), and gum::EdgeGraphPart::__neighbours.

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree(), gum::StaticTriangulation::__computeMaxPrimeMergings(), gum::BinaryJoinTreeConverterDefault::__convertClique(), gum::BinaryJoinTreeConverterDefault::__convertConnectedComponent(), gum::SpanningForestPrim::__exploreNode(), gum::prm::gspan::DFSTree< GUM_SCALAR >::__initialiaze_root(), gum::BinaryJoinTreeConverterDefault::__markConnectedComponent(), gum::prm::StructuredInference< GUM_SCALAR >::__removeBarrenNodes(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::EssentialGraph::__strongly_protected(), gum::StaticTriangulation::__triangulate(), gum::learning::Miic::_propagatesHead(), gum::EdgeGraphPart::eraseNeighbours(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::UndiGraph::hasUndirectedCycle(), gum::learning::Miic::learnStructure(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::EssentialGraph::neighbours(), gum::prm::gspan::DFSTree< GUM_SCALAR >::NeighborDegreeSort::operator()(), gum::UndiGraph::partialUndiGraph(), gum::EssentialGraph::toDot(), gum::UndiGraph::toDot(), gum::MixedGraph::toDot(), gum::EdgeGraphPart::undirectedPath(), and gum::EdgeGraphPart::unvirtualizedEraseNeighbours().

75  {
77  return *(__neighbours[id]);
78  }
void __checkNeighbours(const NodeId id) const
when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set ent...
NodeProperty< NodeSet * > __neighbours
for each node, the set of its adjacent edges

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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);
is basically not thread safe !!
Returns
a node id not yet used by any node within the NodeGraphPart

Definition at line 223 of file nodeGraphPart_inl.h.

Referenced by gum::InfluenceDiagram< GUM_SCALAR >::_addNode(), and gum::BayesNet< GUM_SCALAR >::add().

223  {
224  NodeId next = 0;
225 
226  // return the first hole if holes exist
227  if (__holes && (!__holes->empty()))
228  next = *(__holes->begin());
229  else // in other case
230  next = __boundVal;
231 
232  return next;
233  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
iterator begin() const
The usual unsafe begin iterator to parse the set.
Definition: set_tpl.h:517

+ Here is the caller graph for this function:

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

return *this as a NodeGraphPart

Definition at line 367 of file nodeGraphPart_inl.h.

Referenced by gum::MarkovBlanket::__buildMarkovBlanket(), gum::SpanningForestPrim::__compute(), gum::StaticTriangulation::__computeMaxPrimeJunctionTree(), gum::prm::LayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::ClusteredLayerGenerator< GUM_SCALAR >::__generateClassDag(), gum::prm::GSpan< GUM_SCALAR >::__sortPatterns(), gum::credal::CNMonteCarloSampling< GUM_SCALAR, BNInferenceEngine >::__threadUpdate(), gum::InfluenceDiagram< GUM_SCALAR >::_moralGraph(), gum::InfluenceDiagram< GUM_SCALAR >::_removeTables(), gum::prm::StructuredInference< GUM_SCALAR >::CData::CData(), gum::StaticTriangulation::fillIns(), gum::InfluenceDiagram< GUM_SCALAR >::getDecisionGraph(), gum::prm::gspan::DFSTree< GUM_SCALAR >::growPattern(), gum::UndiGraph::hasUndirectedCycle(), gum::MarkovBlanket::nodes(), gum::EssentialGraph::nodes(), gum::prm::gspan::Pattern::nodes(), gum::MarkovBlanket::toDot(), gum::EssentialGraph::toDot(), gum::InfluenceDiagram< GUM_SCALAR >::toDot(), gum::UndiGraph::toDot(), gum::DiGraph::toDot(), and gum::MixedGraph::toDot().

367  {
368  return *(static_cast< const NodeGraphPart* >(this));
369  }
NodeGraphPart(Size holes_size=HashTableConst::default_size, bool holes_resize_policy=true)
default constructor

+ Here is the caller graph for this function:

template<typename VAL >
NodeProperty< VAL > gum::NodeGraphPart::nodesProperty ( VAL(*)(const NodeId &)  f,
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.

Referenced by gum::InfluenceDiagram< GUM_SCALAR >::_getChildrenDecision(), gum::BarrenNodesFinder::barrenNodes(), gum::BinaryJoinTreeConverterDefault::convert(), gum::InfluenceDiagram< GUM_SCALAR >::existsPathBetween(), and gum::UndiGraph::hasUndirectedCycle().

+ Here is the caller graph for this function:

template<typename VAL >
NodeProperty< VAL > gum::NodeGraphPart::nodesProperty ( 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.
INLINE bool gum::EdgeGraphPart::operator!= ( const EdgeGraphPart p) const
inherited

tests whether two EdgeGraphParts contain different edges

Parameters
pthe EdgeGraphPart that we compare with this

Definition at line 108 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__edges.

108  {
109  return __edges != p.__edges;
110  }
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart
INLINE bool gum::UndiGraph::operator!= ( const UndiGraph g) const
inherited

tests whether two UndiGraphs are different

Parameters
gthe UndiGraph with which "this" is compared

Definition at line 67 of file undiGraph_inl.h.

References gum::UndiGraph::operator==().

67  {
68  return !operator==(p);
69  }
bool operator==(const UndiGraph &g) const
tests whether two UndiGraphs are identical (same nodes, same edges)
Definition: undiGraph_inl.h:63

+ Here is the call graph for this function:

bool gum::CliqueGraph::operator!= ( const CliqueGraph from) const

checks whether two clique graphs are different

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 351 of file nodeGraphPart_inl.h.

References gum::NodeGraphPartIterator::operator==().

351  {
352  return !operator==(p);
353  }
bool operator==(const NodeGraphPart &p) const
check whether two NodeGraphParts contain the same nodes

+ Here is the call graph for this function:

CliqueGraph& gum::CliqueGraph::operator= ( const CliqueGraph from)

copy operator

INLINE bool gum::EdgeGraphPart::operator== ( const EdgeGraphPart p) const
inherited

tests whether two EdgeGraphParts contain the same edges

Parameters
pthe EdgeGraphPart that we compare with this

Definition at line 104 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__edges.

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

104  {
105  return __edges == p.__edges;
106  }
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

+ Here is the caller graph for this function:

INLINE bool gum::UndiGraph::operator== ( const UndiGraph g) const
inherited

tests whether two UndiGraphs are identical (same nodes, same edges)

Parameters
gthe UndiGraph with which "this" is compared

Definition at line 63 of file undiGraph_inl.h.

References gum::EdgeGraphPart::operator==(), and gum::NodeGraphPart::operator==().

Referenced by gum::UndiGraph::operator!=().

63  {
65  }
bool operator==(const EdgeGraphPart &p) const
tests whether two EdgeGraphParts contain the same edges
bool operator==(const NodeGraphPart &p) const
check whether two NodeGraphParts contain the same nodes

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool gum::CliqueGraph::operator== ( const CliqueGraph from) const

checks whether two clique graphs are equal

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 337 of file nodeGraphPart_inl.h.

References gum::NodeGraphPart::__boundVal, and gum::NodeGraphPart::__holes.

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

337  {
338  if (__boundVal != p.__boundVal) return false;
339 
340  if (__holes)
341  if (p.__holes)
342  return (*__holes == *p.__holes);
343  else
344  return false;
345  else if (p.__holes)
346  return false;
347 
348  return true;
349  }
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart

+ Here is the caller graph for this function:

UndiGraph gum::UndiGraph::partialUndiGraph ( NodeSet  nodesSet)
virtualinherited

returns the partial graph formed by the nodes given in parameter

Definition at line 136 of file undiGraph.cpp.

References gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::NodeGraphPart::existsNode(), and gum::EdgeGraphPart::neighbours().

136  {
137  UndiGraph partialGraph;
138 
139  for (const auto node : nodesSet) {
140  partialGraph.addNodeWithId(node);
141 
142  for (const auto nei : neighbours(node))
143  if (nodesSet.contains(nei) && partialGraph.existsNode(nei))
144  partialGraph.addEdge(node, nei);
145  }
146 
147  return partialGraph;
148  }
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
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:37

+ Here is the call graph for this function:

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 61 of file nodeGraphPart.cpp.

References gum::NodeGraphPart::__boundVal, gum::NodeGraphPart::__holes, gum::NodeGraphPart::__holes_resize_policy, gum::NodeGraphPart::__holes_size, gum::NodeGraphPart::__updateEndIteratorSafe(), and gum::NodeGraphPart::clear().

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

61  {
62  clear(); // "virtual" flush of the nodes set
63  __holes_size = s.__holes_size;
64  __holes_resize_policy = s.__holes_resize_policy;
65 
66  if (s.__holes) __holes = new NodeSet(*s.__holes);
67 
68  __boundVal = s.__boundVal;
69 
71  }
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
bool __holes_resize_policy
value for __holes configuration
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
Size __holes_size
value for __holes configuration
void __updateEndIteratorSafe()
updating endIterator (always at __max+1)
virtual void clear()
alias for clearNodes

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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.

const NodeSet& gum::CliqueGraph::separator ( const Edge edge) const

returns the separator included in a given edge

Exceptions
NotFoundexception is thrown if the edge does not belong to the clique graph

Referenced by gum::StaticTriangulation::__computeMaxPrimeMergings(), gum::BinaryJoinTreeConverterDefault::__convertClique(), and gum::BarrenNodesFinder::barrenNodes().

+ Here is the caller graph for this function:

const NodeSet& gum::CliqueGraph::separator ( const NodeId  clique1,
const NodeId  clique 
) const

returns the separator included in an edge specified by its extremities

Exceptions
NotFoundexception is thrown if the edge does not belong to the clique graph
virtual void gum::CliqueGraph::setClique ( const NodeId  idClique,
const NodeSet new_clique 
)
virtual

changes the set of nodes included into a given clique and returns the new set

Exceptions
NotFoundexception is thrown if idClique is not a clique of the clique graph
INLINE Size gum::EdgeGraphPart::sizeEdges ( ) const
inherited

indicates the number of edges stored within the EdgeGraphPart

Definition at line 34 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__edges, and gum::Set< Key, Alloc >::size().

Referenced by gum::EssentialGraph::sizeEdges().

34 { return __edges.size(); }
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701
EdgeSet __edges
the set of all the edges contained within the EdgeGraphPart

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

returns the number of nodes in the NodeGraphPart

Definition at line 274 of file nodeGraphPart_inl.h.

Referenced by gum::BinaryJoinTreeConverterDefault::__markConnectedComponent(), gum::BarrenNodesFinder::barrenNodes(), gum::BinaryJoinTreeConverterDefault::convert(), gum::EliminationSequenceStrategy::setGraph(), gum::MarkovBlanket::sizeNodes(), and gum::EssentialGraph::sizeNodes().

274  {
275  return (__holes) ? (__boundVal - __holes->size()) : __boundVal;
276  }
NodeSet * __holes
the set of nodes not contained in the NodeGraphPart in the interval 1..__max
NodeId __boundVal
the id below which NodeIds may belong to the NodeGraphPart
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701

+ Here is the caller graph for this function:

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

friendly displays the content of the CliqueGraph in DOT format

Reimplemented from gum::UndiGraph.

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

friendly displays the content of the CliqueGraph

Reimplemented from gum::UndiGraph.

const std::vector< NodeId > gum::EdgeGraphPart::undirectedPath ( const NodeId  node1,
const NodeId  node2 
) const
inherited

returns a possible path from node1 to node2 in the edge 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 124 of file edgeGraphPart.cpp.

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

124  {
125  // not recursive version => use a FIFO for simulating the recursion
126  List< NodeId > nodeFIFO;
127  nodeFIFO.pushBack(n2);
128 
129  // mark[node] = predecessor if visited, else mark[node] does not exist
130  NodeProperty< NodeId > mark;
131  mark.insert(n2, n2);
132 
133  NodeId current;
134 
135  while (!nodeFIFO.empty()) {
136  current = nodeFIFO.front();
137  nodeFIFO.popFront();
138 
139  // check the neighbour
140  for (const auto new_one : neighbours(current)) {
141  if (mark.exists(new_one)) // if this node is already marked, stop
142  continue;
143 
144  mark.insert(new_one, current);
145 
146  if (new_one == n1) {
147  std::vector< NodeId > v;
148 
149  for (current = n1; current != n2; current = mark[current])
150  v.push_back(current);
151 
152  v.push_back(n2);
153 
154  return v;
155  }
156 
157  nodeFIFO.pushBack(new_one);
158  }
159  }
160 
161  GUM_ERROR(NotFound, "no path found");
162  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

INLINE void gum::EdgeGraphPart::unvirtualizedEraseNeighbours ( const NodeId  id)
inherited

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

Parameters
idthe node whose ingoing arcs will be removed

Definition at line 93 of file edgeGraphPart_inl.h.

References gum::EdgeGraphPart::__neighbours, gum::EdgeGraphPart::eraseEdge(), and gum::EdgeGraphPart::neighbours().

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

93  {
94  if (__neighbours.exists(id)) {
95  const NodeSet& set = neighbours(id);
96 
97  for (auto iter = set.beginSafe(); iter != set.endSafe();
98  ++iter) { // safe iterator needed here
99  EdgeGraphPart::eraseEdge(Edge(*iter, id));
100  }
101  }
102  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeProperty< NodeSet * > __neighbours
for each node, the set of its adjacent edges
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
virtual void eraseEdge(const Edge &edge)
removes an edge from the EdgeGraphPart

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

NodeProperty< NodeSet > gum::CliqueGraph::__cliques
private

the set of nodes contained into the cliques

Definition at line 239 of file cliqueGraph.h.

EdgeProperty< NodeSet > gum::CliqueGraph::__separators
private

the set of nodes contained into the separators

Definition at line 242 of file cliqueGraph.h.

Signaler2< NodeId, NodeId > gum::EdgeGraphPart::onEdgeAdded
inherited
Signaler2< NodeId, NodeId > gum::EdgeGraphPart::onEdgeDeleted
inherited
Signaler1< NodeId > gum::NodeGraphPart::onNodeAdded
inherited

Definition at line 271 of file nodeGraphPart.h.

Referenced by gum::NodeGraphPart::addNodeWithId().

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

Definition at line 272 of file nodeGraphPart.h.

Referenced by gum::NodeGraphPart::__clearNodes().


The documentation for this class was generated from the following file: