Basic graph of cliques. More...

#include <cliqueGraph.h>

Inheritance diagram for gum::CliqueGraph:

Collaboration diagram for gum::CliqueGraph:

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

Public Types
using	EdgeIterator = EdgeSetIterator
using	NodeIterator = NodeGraphPartIterator
using	NodeConstIterator = NodeGraphPartIterator
using	NodeIteratorSafe = NodeGraphPartIteratorSafe
using	NodeConstIteratorSafe = NodeGraphPartIteratorSafe

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
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
	CliqueGraph (const CliqueGraph &from)
	copy constructor
virtual	~CliqueGraph ()
	destructor
Accessors/Modifiers
virtual void	addEdge (NodeId first, NodeId second)
	inserts a new edge between two cliques
virtual void	eraseEdge (const Edge &edge)
	removes an edge (and its separator) from the clique graph
virtual void	clearEdges ()
	removes all edges and their separators
NodeId	addNode (const NodeSet &clique)
	adds a new clique to the graph
virtual NodeId	addNode ()
	adds a new clique to the graph
virtual void	addNodeWithId (const NodeId id, const NodeSet &clique)
	try to add a new clique to the graph
virtual void	addNodeWithId (const NodeId id)
	try to add a new clique to the graph
virtual void	eraseNode (const NodeId node)
	removes a given clique from the clique graph
virtual void	clear ()
	removes all the cliques and separators from the graph (as well as their adjacent edges)
const NodeSet &	clique (const NodeId idClique) const
	returns the set of nodes included into a given clique
NodeId	container (const NodeId idNode) const
	returns the id of a clique containing the node the id of which is in argument
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
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
virtual void	eraseFromClique (const NodeId clique_id, const NodeId node_id)
	remove a node from a clique
const NodeSet &	separator (const Edge &edge) const
	returns the separator included in a given edge
const NodeSet &	separator (const NodeId clique1, const NodeId clique) const
	returns the separator included in an edge specified by its extremities
std::vector< NodeId >	containerPath (const NodeId node1, const NodeId node2) const
	returns a path from a clique containing node1 to a clique containing node2
bool	hasRunningIntersection () const
	indicates whether the running intersection property holds
bool	isJoinTree () const
	indicates whether the graph is a join tree
virtual std::string	toString () const
	friendly displays the content of the CliqueGraph
virtual std::string	toDot () const
	friendly displays the content of the CliqueGraph in DOT format
virtual std::string	mapToDot (double scaleClique, double scaleSep, double lenEdge, const std::string &colorClique="burlywood", const std::string &colorSep="palegreen") const
	friendly displays the content of the map of the CliqueGraph in DOT format
Operators
CliqueGraph &	operator= (const CliqueGraph &from)
	copy operator
bool	operator== (const CliqueGraph &from) const
	checks whether two clique graphs are equal
Operators
bool	operator== (const UndiGraph &g) const
	tests whether two UndiGraphs are identical (same nodes, same edges)
bool	operator!= (const UndiGraph &g) const
	tests whether two UndiGraphs are different
Operators
bool	operator== (const EdgeGraphPart &p) const
	tests whether two EdgeGraphParts contain the same edges
Accessors/Modifiers
bool	hasUndirectedCycle () const
	checks whether the graph contains cycles
virtual UndiGraph	partialUndiGraph (NodeSet nodes)
	returns the partial graph formed by the nodes given in parameter
NodeProperty< NodeId >	nodes2ConnectedComponent () const
	returns a property {node:id of connected component}
Accessors/Modifiers
bool	existsEdge (const Edge &edge) const
	indicates whether a given edge exists
bool	existsEdge (NodeId n1, NodeId n2) const
	indicates whether a given edge exists
bool	emptyEdges () const
	indicates wether the EdgeGraphPart contains any edge
Size	sizeEdges () const
	indicates the number of edges stored within the EdgeGraphPart
const EdgeSet &	edges () const
	returns the set of edges stored within the EdgeGraphPart
const NodeSet &	neighbours (NodeId id) const
	returns the set of node neighbours to a given node
void	eraseNeighbours (NodeId id)
	erase all the edges adjacent to a given node
void	unvirtualizedEraseNeighbours (NodeId id)
	same function as eraseNeighbours but without any virtual call to an erase
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))
template<typename VAL>
EdgeProperty< VAL >	edgesProperty (const VAL &val, 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)
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))
std::vector< NodeId >	undirectedPath (NodeId node1, NodeId node2) const
	returns a possible path from node1 to node2 in the edge set
bool	hasUndirectedPath (NodeId n1, NodeId n2) const
	return true if n1 and n2 are connected (by an undirected path) in the graph.
bool	hasUndirectedPath (NodeId n1, NodeId n2, const NodeSet &except) const
	return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.
bool	hasUndirectedPath (const NodeSet &n1, const NodeSet &n2, const NodeSet &except) const
	return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.
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
std::vector< NodeId >	addNodes (Size n)
	insert n nodes
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))

Static Public Member Functions
Constructors / Destructors
static UndiGraph	completeGraph (int n)
	create a complete UndiGraph with n nodes

Public Attributes
Signaler2< NodeId, NodeId >	onEdgeAdded
Signaler2< NodeId, NodeId >	onEdgeDeleted
Signaler1< NodeId >	onNodeAdded
Signaler1< NodeId >	onNodeDeleted

Private Member Functions
void	_updateSeparators_ (const NodeId clique1)
	function used to update the separators when a clique is modified
bool	_runningIntersectionDFS_ (const NodeId clique, const NodeId from, _RunningIntersect_ &infos_DFS) const
	function used for the computation of the running intersection property
void	_checkNeighbours_ (NodeId id)
	when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set entry to neighbours[id]
void	_clearEdges_ ()

Private Attributes
NodeProperty< NodeSet >	_cliques_
	the set of nodes contained into the cliques
EdgeProperty< NodeSet >	_separators_
	the set of nodes contained into the separators
EdgeSet	_edges_
	the set of all the edges contained within the EdgeGraphPart
NodeProperty< NodeSet * >	_neighbours_
	for each node, the set of its adjacent edges

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 extremities of the edge.

Definition at line 77 of file cliqueGraph.h.

Member Typedef Documentation

◆ EdgeIterator

using gum::EdgeGraphPart::EdgeIterator = EdgeSetIterator

inherited

Definition at line 96 of file edgeGraphPart.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

◆ CliqueGraph() [1/2]

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_size	the size of the hash table used to store all the nodes
nodes_resize_policy	the resizing policy of this hash table
edges_size	the size of the hash table used to store all the edges
edges_resize_policy	the resizing policy of this hash table

References gum::HashTableConst::default_size.

Referenced by CliqueGraph(), operator=(), and operator==().

Here is the caller graph for this function:

◆ CliqueGraph() [2/2]

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

copy constructor

Parameters

from	the CliqueGraph that will be copied into this

References CliqueGraph().

Here is the call graph for this function:

◆ ~CliqueGraph()

virtual gum::CliqueGraph::~CliqueGraph ( )

virtual

destructor

Member Function Documentation

◆ _checkNeighbours_()

INLINE void gum::EdgeGraphPart::_checkNeighbours_ ( NodeId id )

privateinherited

when the EdgeGraphPart contains no edge adjacent to a given node, this function adds an empty set entry to neighbours[id]

Parameters

id	the node whose neighbours[id] is checked

Definition at line 67 of file edgeGraphPart_inl.h.

                                                        {
    if (!_neighbours_.exists(id)) { _neighbours_.insert(id, new NodeSet); }
  }

References _neighbours_.

Referenced by addEdge().

Here is the caller graph for this function:

◆ _clearEdges_()

void gum::EdgeGraphPart::_clearEdges_ ( )

privateinherited

Definition at line 88 of file edgeGraphPart.cpp.

                                   {
    for (const auto& elt: _neighbours_)
      delete elt.second;
 
    _neighbours_.clear();
 
    if (onEdgeDeleted.hasListener()) {
      EdgeSet tmp = _edges_;
      _edges_.clear();
 
      for (const auto& edge: tmp)
        GUM_EMIT2(onEdgeDeleted, edge.first(), edge.second());
    } else {
      _edges_.clear();
    }
  }

References _edges_, _neighbours_, GUM_EMIT2, and onEdgeDeleted.

Referenced by ~EdgeGraphPart(), and clearEdges().

Here is the caller graph for this function:

◆ _runningIntersectionDFS_()

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

References clique().

Here is the call graph for this function:

◆ _updateSeparators_()

void gum::CliqueGraph::_updateSeparators_ ( const NodeId clique1 )

private

function used to update the separators when a clique is modified

◆ addEdge()

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

virtual

inserts a new edge between two cliques

Parameters

first	the id of one extremity of the new edge to be inserted
second	the 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

InvalidNode if first and/or second do not belong to the graph nodes

Reimplemented from gum::EdgeGraphPart.

Referenced by gum::BinaryJoinTreeConverterDefault::_convertClique_().

Here is the caller graph for this function:

◆ addNode() [1/2]

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.

◆ addNode() [2/2]

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

adds a new clique to the graph

Returns: the id chosen for the new clique

References clique().

Referenced by gum::BinaryJoinTreeConverterDefault::_convertClique_().

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

n	the number of nodes to add

Returns: the vector of chosen ids

Definition at line 276 of file nodeGraphPart_inl.h.

                                                           {
    std::vector< NodeId > v;
    v.reserve(N);
    for (Idx i = 0; i < N; i++)
      v.push_back(this->addNode());
    return v;
  }

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

Here is the caller graph for this function:

◆ addNodeWithId() [1/2]

virtual void gum::CliqueGraph::addNodeWithId ( const NodeId id )

virtual

try to add a new clique to the graph

Exceptions

DuplicateElement exception is thrown if the id of the clique already exists within the clique graph

Reimplemented from gum::NodeGraphPart.

◆ addNodeWithId() [2/2]

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

virtual

try to add a new clique to the graph

Exceptions

DuplicateElement exception is thrown if the id of the clique already exists within the clique graph

References clique().

Here is the call graph for this function:

◆ addToClique()

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

NotFound	exception is thrown if clique_id does not exist
DuplicateElement	exception is thrown if clique_id set already contains the node

◆ 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())

gum::NodeGraphPart::nodes
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
Definition nodeGraphPart_inl.h:368

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.

                                                {
    NodeSet son(sizeNodes());
 
    if (!empty()) {
      for (NodeId n = 0; n < _boundVal_; ++n) {
        if (!_inHoles_(n)) son.insert(n);
      }
    }
 
    return son;
  }

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.

                                                                   {
    NodeGraphPartIterator it(*this);
    it.validate_();   // stop the iterator at the first not-in-holes
    return it;
  }

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.

                                                                  {
    NodeGraphPartIteratorSafe it(*this);
    it.validate_();   // stop the iterator at the first not-in-holes
    return it;
  }

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:

◆ clear()

virtual void gum::CliqueGraph::clear ( )

virtual

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

Reimplemented from gum::NodeGraphPart.

◆ clearEdges()

virtual void gum::CliqueGraph::clearEdges ( )

virtual

removes all edges and their separators

Reimplemented from gum::EdgeGraphPart.

◆ 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:

◆ clique()

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

returns the set of nodes included into a given clique

Exceptions

NotFound exception is raised if the clique does not belong to the clique graph

Referenced by _runningIntersectionDFS_(), addNode(), addNodeWithId(), gum::BarrenNodesFinder::barrenNodes(), gum::Triangulation::maxLog10CliqueDomainSize(), and separator().

Here is the caller graph for this function:

◆ completeGraph()

UndiGraph gum::UndiGraph::completeGraph ( int n )

staticinherited

create a complete UndiGraph with n nodes

Parameters

n int

Returns: the complete UndiGraph

Definition at line 60 of file undiGraph.cpp.

                                          {
    UndiGraph g;
    g.addNodes(n);
 
    for (int j = 0; j < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        g.addEdge(j, k);
      }
    }
    return g;
  }

References UndiGraph(), addEdge(), and gum::NodeGraphPart::addNodes().

Here is the call graph for this function:

◆ container()

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 priori information about which clique could contain idNode. As a consequence, it searches the cliques until it finds one that actually contains idNode.

Exceptions

NotFound exception is thrown if no clique contains idNode

◆ containerPath()

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

NotFound such path cannot be found

◆ edges()

INLINE const EdgeSet & gum::EdgeGraphPart::edges ( ) const

inherited

returns the set of edges stored within the EdgeGraphPart

Definition at line 59 of file edgeGraphPart_inl.h.

59{ return _edges_; }

References _edges_.

Referenced by gum::EssentialGraph::_buildEssentialGraph_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::BarrenNodesFinder::barrenNodes(), gum::learning::Miic::initiation_(), gum::learning::SimpleMiic::initiation_(), gum::PDAG::moralGraph(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::MeekRules::propagateToCPDAG(), and gum::learning::IBNLearner::setPossibleSkeleton().

Here is the caller graph for this function:

◆ edgesProperty() [1/2]

template<typename VAL>

EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty	(	const VAL &	val,
		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

a	the default value assigned to each edge in the returned Property
size	an 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.

◆ edgesProperty() [2/2]

template<typename VAL>

EdgeProperty< VAL > gum::EdgeGraphPart::edgesProperty	(	VAL(*	f )(const Edge &),
		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

f	a function assigning a VAL to any edge
size	an 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.

◆ 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:

◆ emptyEdges()

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

inherited

indicates wether the EdgeGraphPart contains any edge

Definition at line 55 of file edgeGraphPart_inl.h.

55{ return _edges_.empty(); }

References _edges_.

◆ 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.

                                                                        {
    return _endIteratorSafe_;
  }

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.

                                                                                {
    return _endIteratorSafe_;
  }

References _endIteratorSafe_, and NodeGraphPartIteratorSafe.

Here is the call graph for this function:

◆ eraseEdge()

virtual void gum::CliqueGraph::eraseEdge ( const Edge & edge )

virtual

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

Parameters

edge	the 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::BinaryJoinTreeConverterDefault::_convertClique_().

Here is the caller graph for this function:

◆ eraseFromClique()

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

NotFound exception is thrown if clique_id does not exist

◆ eraseNeighbours()

INLINE void gum::EdgeGraphPart::eraseNeighbours ( NodeId id )

inherited

erase all the edges adjacent to a given node

Parameters

id	the 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 101 of file edgeGraphPart_inl.h.

                                                      {
    if (_neighbours_.exists(id)) {
      const NodeSet& set = *(_neighbours_[id]);
 
      for (auto iter = set.beginSafe(); iter != set.endSafe();
           ++iter) {   // safe iterator needed here
        // warning: use this erases so that you actually use the virtualized
        // edge removal function
        eraseEdge(Edge(*iter, id));
      }
    }
  }

References _neighbours_, gum::Set< Key >::beginSafe(), gum::Set< Key >::endSafe(), and eraseEdge().

Here is the call graph for this function:

◆ eraseNode()

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::NodeGraphPart.

◆ 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:

◆ existsEdge() [1/2]

INLINE bool gum::EdgeGraphPart::existsEdge ( const Edge & edge ) const

inherited

indicates whether a given edge exists

Parameters

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

Definition at line 61 of file edgeGraphPart_inl.h.

61{ return _edges_.contains(edge); }

References _edges_.

Referenced by gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::EssentialGraph::_strongly_protected_(), gum::StaticTriangulation::_triangulate_(), eraseEdge(), gum::learning::Miic::orientationMiic_(), gum::learning::SimpleMiic::orientationMiic_(), gum::learning::Miic::unshieldedTriples_(), gum::learning::SimpleMiic::unshieldedTriples_(), gum::learning::Miic::unshieldedTriplesMiic_(), and gum::learning::SimpleMiic::unshieldedTriplesMiic_().

Here is the caller graph for this function:

◆ existsEdge() [2/2]

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

inherited

indicates whether a given edge exists

Parameters

n1	the id of one extremity of the edge we test the existence in the EdgeGraphPart
n2	the id of the other extremity of the edge we test the existence in the EdgeGraphPart

Definition at line 63 of file edgeGraphPart_inl.h.

                                                                         {
    return _neighbours_.exists(first) && _neighbours_[first]->exists(second);
  }

References _neighbours_.

◆ 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.

                                                               {
    if (node >= _boundVal_) return false;
 
    return (!_inHoles_(node));
  }

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:

◆ hasRunningIntersection()

bool gum::CliqueGraph::hasRunningIntersection ( ) const

indicates whether the running intersection property holds

The function works properly even if the graph contains cycles.

◆ hasUndirectedCycle()

bool gum::UndiGraph::hasUndirectedCycle ( ) const

inherited

checks whether the graph contains cycles

Definition at line 90 of file undiGraph.cpp.

                                           {
    List< std::pair< NodeId, NodeId > > open_nodes;
    NodeProperty< bool >                examined_nodes = nodesPropertyFromVal(false);
    std::pair< NodeId, NodeId >         thePair;
    NodeId                              current, from_current;
 
    for (const auto node: nodes()) {
      // check if the node has already been examined (if this is not the case,
      // this means that we are on a new connected component)
      if (!examined_nodes[node]) {
        // indicates that we are examining a new node
        examined_nodes[node] = true;
 
        // check recursively all the nodes of node's connected component
        thePair.first  = node;
        thePair.second = node;
        open_nodes.insert(thePair);
 
        while (!open_nodes.empty()) {
          // get a node to propagate
          thePair = open_nodes.front();
          open_nodes.popFront();
 
          current      = thePair.first;
          from_current = thePair.second;
 
          // check the neighbours
          for (const auto new_node: neighbours(current))
 
            // avoid to check the node we are coming from
            if (new_node != from_current) {
              if (examined_nodes[new_node]) return true;
              else {
                examined_nodes[new_node] = true;
                thePair.first            = new_node;
                thePair.second           = current;
                open_nodes.insert(thePair);
              }
            }
        }
      }
    }
 
    return false;
  }

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

Here is the call graph for this function:

◆ hasUndirectedPath() [1/3]

bool gum::EdgeGraphPart::hasUndirectedPath	(	const NodeSet &	n1,
		const NodeSet &	n2,
		const NodeSet &	except ) const

inherited

return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.

Parameters

n1	NodeSet
n2	NodeSet
except	NodeSet

Returns: bool

Definition at line 222 of file edgeGraphPart.cpp.

                                                                     {
    NodeSet visited;
    NodeSet temp;
 
    for (auto n: n1)
      temp.insert(n);
 
    while (!temp.empty()) {
      NodeId current = *(temp.begin());
      if (n2.contains(current)) return true;
      temp.erase(current);
      visited.insert(current);
      for (auto next: neighbours(current)) {
        if (!temp.contains(next) && !visited.contains(next) && !except.contains(next))
          temp.insert(next);
      }
    }
    return false;
  }

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

Here is the call graph for this function:

◆ hasUndirectedPath() [2/3]

bool gum::EdgeGraphPart::hasUndirectedPath	(	NodeId	n1,
		NodeId	n2 ) const

inherited

return true if n1 and n2 are connected (by an undirected path) in the graph.

Parameters

n1	NodeId
n2	NodeId

Returns: bool

Definition at line 185 of file edgeGraphPart.cpp.

                                                                  {
    NodeSet visited;
    NodeSet temp;
 
    temp.insert(n1);
    while (!temp.empty()) {
      NodeId current = *(temp.begin());
      if (current == n2) return true;
      temp.erase(current);
      visited.insert(current);
      for (auto next: neighbours(current)) {
        if (!temp.contains(next) && !visited.contains(next)) temp.insert(next);
      }
    }
    return false;
  }

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

Referenced by gum::UGmodel::isIndependent(), and gum::UGmodel::isIndependent().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hasUndirectedPath() [3/3]

bool gum::EdgeGraphPart::hasUndirectedPath	(	NodeId	n1,
		NodeId	n2,
		const NodeSet &	except ) const

inherited

return true if n1 and n2 are connected (by an undirected path not using the nodes of except) in the graph.

Parameters

n1	NodeId
n2	NodeId
except	NodeSet

Warning: n1 in except has no repercussion. However n2 in except naturally leads to 'false'

Returns: bool

Definition at line 202 of file edgeGraphPart.cpp.

                                                                                               {
    NodeSet visited;
    NodeSet temp;
 
    if (except.contains(n2)) return false;
 
    temp.insert(n1);
    while (!temp.empty()) {
      NodeId current = *(temp.begin());
      if (current == n2) return true;
      temp.erase(current);
      visited.insert(current);
      for (auto next: neighbours(current)) {
        if (!temp.contains(next) && !visited.contains(next) && !except.contains(next))
          temp.insert(next);
      }
    }
    return false;
  }

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

Here is the call graph for this function:

◆ isJoinTree()

bool gum::CliqueGraph::isJoinTree ( ) const

indicates whether the graph is a join tree

◆ listMapEdges()

template<typename VAL>

List< VAL > gum::EdgeGraphPart::listMapEdges ( VAL(* f )(const Edge &) ) 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

f	a function assigning a VAL to any edge

◆ 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

f	a 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:

◆ mapToDot()

virtual std::string gum::CliqueGraph::mapToDot	(	double	scaleClique,
		double	scaleSep,
		double	lenEdge,
		const std::string &	colorClique = "burlywood",
		const std::string &	colorSep = "palegreen" ) const

virtual

friendly displays the content of the map of the CliqueGraph in DOT format

◆ neighbours()

INLINE const NodeSet & gum::EdgeGraphPart::neighbours ( NodeId id ) const

inherited

returns the set of node neighbours to a given node

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

Parameters

id	the node to which the edges are adjacent

Definition at line 96 of file edgeGraphPart_inl.h.

                                                                 {
    if (_neighbours_.exists(id)) return *(_neighbours_[id]);
    else return emptyNodeSet;
  }

References _neighbours_, and gum::emptyNodeSet.

Referenced by gum::MeekRules::_applyMeekRules_(), gum::BinaryJoinTreeConverterDefault::_convertClique_(), gum::BinaryJoinTreeConverterDefault::_convertConnectedComponent_(), gum::MeekRules::_critereMinParents_(), gum::BinaryJoinTreeConverterDefault::_markConnectedComponent_(), gum::MeekRules::_propagatesOrientationInChainOfRemainingEdges_(), gum::prm::StructuredInference< GUM_SCALAR >::_removeBarrenNodes_(), gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_(), gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_(), gum::StaticTriangulation::_triangulate_(), gum::MixedGraph::boundary(), gum::MixedGraph::chainComponent(), gum::MixedGraph::hasMixedOrientedPath(), gum::PDAG::hasMixedReallyOrientedPath(), gum::UndiGraph::hasUndirectedCycle(), hasUndirectedPath(), hasUndirectedPath(), hasUndirectedPath(), gum::learning::SimpleMiic::learnPDAG(), gum::learning::SimpleMiic::learnStructure(), gum::MixedGraph::mixedOrientedPath(), gum::MixedGraph::mixedUnorientedPath(), gum::PDAG::moralGraph(), gum::UndiGraph::nodes2ConnectedComponent(), gum::UndiGraph::partialUndiGraph(), gum::learning::SimpleMiic::propagatesOrientationInChainOfRemainingEdges_(), gum::learning::SimpleMiic::propagatesRemainingOrientableEdges_(), gum::rec_ancestral(), gum::rec_hasMixedReallyOrientedPath(), gum::MixedGraph::toDot(), gum::PDAG::toDot(), gum::UndiGraph::toDot(), undirectedPath(), gum::learning::Miic::unshieldedTriples_(), gum::learning::SimpleMiic::unshieldedTriples_(), gum::learning::Miic::unshieldedTriplesMiic_(), and gum::learning::SimpleMiic::unshieldedTriplesMiic_().

◆ 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::CliqueGraph::addNode
virtual NodeId addNode()
adds a new clique to the graph

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.

                                                {
    NodeId next = 0;
 
    // return the first hole if holes exist
    if (_holes_ && (!_holes_->empty())) next = *(_holes_->begin());
    else   // in other case
      next = _boundVal_;
 
    return next;
  }

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.

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

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:

◆ nodes2ConnectedComponent()

NodeProperty< NodeId > gum::UndiGraph::nodes2ConnectedComponent ( ) const

inherited

returns a property {node:id of connected component}

Definition at line 184 of file undiGraph.cpp.

                                                                   {
    NodeProperty< NodeId > res;
 
    NodeId numCC = 0;
    for (const auto node: nodes()) {
      if (res.exists(node)) continue;
      NodeSet nodes{node};
      while (!nodes.empty()) {
        auto actual = *(nodes.begin());
        nodes.erase(actual);
        res.insert(actual, numCC);
        for (const auto nei: neighbours(actual)) {
          if (!res.exists(nei))
            if (!nodes.exists(nei)) nodes.insert(nei);
        }
      }
      numCC += 1;
    }
 
    return res;
  }

References gum::HashTable< Key, Val >::exists(), gum::HashTable< Key, Val >::insert(), gum::EdgeGraphPart::neighbours(), and gum::NodeGraphPart::nodes().

Here is the call 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

f	a function assigning a VAL to any node
size	an 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

a	the default value assigned to each edge in the returned Property
size	an 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!=() [1/2]

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

inherited

check whether two NodeGraphParts contain different nodes

Parameters

p	the 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!=() [2/2]

INLINE bool gum::UndiGraph::operator!= ( const UndiGraph & g ) const

inherited

tests whether two UndiGraphs are different

Parameters

g	the UndiGraph with which "this" is compared

Definition at line 90 of file undiGraph_inl.h.

90{ return !operator==(p); }

gum::UndiGraph::operator==

bool operator==(const UndiGraph &g) const

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

Definition undiGraph_inl.h:86

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

Here is the call graph for this function:

◆ operator=()

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

copy operator

References CliqueGraph().

Here is the call graph for this function:

◆ operator==() [1/4]

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

checks whether two clique graphs are equal

References CliqueGraph().

Here is the call graph for this function:

◆ operator==() [2/4]

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

inherited

tests whether two EdgeGraphParts contain the same edges

Parameters

p	the EdgeGraphPart that we compare with this

Definition at line 125 of file edgeGraphPart_inl.h.

                                                                  {
    return _edges_ == p._edges_;
  }

References EdgeGraphPart(), and _edges_.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator==() [3/4]

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

inherited

check whether two NodeGraphParts contain the same nodes

Parameters

p	the NodeGraphPart to be compared with "this"

Definition at line 343 of file nodeGraphPart_inl.h.

                                                                  {
    if (_boundVal_ != p._boundVal_) return false;
 
    if (_holes_)
      if (p._holes_) return (*_holes_ == *p._holes_);
      else return false;
    else if (p._holes_) return false;
 
    return true;
  }

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:

◆ operator==() [4/4]

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

inherited

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

Parameters

g	the UndiGraph with which "this" is compared

Definition at line 86 of file undiGraph_inl.h.

                                                          {
    return EdgeGraphPart::operator==(p) && NodeGraphPart::operator==(p);
  }

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

Referenced by operator!=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ partialUndiGraph()

UndiGraph gum::UndiGraph::partialUndiGraph ( NodeSet nodes )

virtualinherited

returns the partial graph formed by the nodes given in parameter

Definition at line 171 of file undiGraph.cpp.

                                                     {
    UndiGraph partialGraph;
 
    for (const auto node: nodes) {
      partialGraph.addNodeWithId(node);
 
      for (const auto nei: neighbours(node))
        if (nodes.contains(nei) && partialGraph.existsNode(nei)) partialGraph.addEdge(node, nei);
    }
 
    return partialGraph;
  }

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

Here is the call graph for this function:

◆ 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

s	the NodeGraphPart to be copied

Definition at line 83 of file nodeGraphPart.cpp.

                                                          {
    clear();   // "virtual" flush of the nodes set
    _holes_size_          = s._holes_size_;
    _holes_resize_policy_ = s._holes_resize_policy_;
 
    if (s._holes_) _holes_ = new NodeSet(*s._holes_);
 
    _boundVal_ = s._boundVal_;
 
    _updateEndIteratorSafe_();
  }

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:

◆ separator() [1/2]

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

returns the separator included in a given edge

Exceptions

NotFound exception is thrown if the edge does not belong to the clique graph

Referenced by gum::BinaryJoinTreeConverterDefault::_convertClique_(), and gum::BarrenNodesFinder::barrenNodes().

Here is the caller graph for this function:

◆ separator() [2/2]

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

returns the separator included in an edge specified by its extremities

Exceptions

NotFound exception is thrown if the edge does not belong to the clique graph

References clique().

Here is the call graph for this function:

◆ setClique()

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

NotFound exception is thrown if idClique is not a clique of the clique graph

◆ 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:

◆ sizeEdges()

INLINE Size gum::EdgeGraphPart::sizeEdges ( ) const

inherited

indicates the number of edges stored within the EdgeGraphPart

Definition at line 57 of file edgeGraphPart_inl.h.

57{ return _edges_.size(); }

References _edges_.

◆ 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.

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

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()

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

virtual

friendly displays the content of the CliqueGraph in DOT format

Reimplemented from gum::UndiGraph.

◆ toString()

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

virtual

friendly displays the content of the CliqueGraph

Reimplemented from gum::NodeGraphPart.

◆ undirectedPath()

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

inherited

returns a possible path from node1 to node2 in the edge set

Parameters

node1	the id from which the path begins
node2	the id to which the path ends

Exceptions

NotFound exception is raised if no path can be found between the two nodes

Definition at line 145 of file edgeGraphPart.cpp.

                                                                              {
    // not recursive version => use a FIFO for simulating the recursion
    List< NodeId > nodeFIFO;
    nodeFIFO.pushBack(n2);
 
    // mark[node] = predecessor if visited, else mark[node] does not exist
    NodeProperty< NodeId > mark;
    mark.insert(n2, n2);
 
    NodeId current;
 
    while (!nodeFIFO.empty()) {
      current = nodeFIFO.front();
      nodeFIFO.popFront();
 
      // check the neighbour
      for (const auto new_one: neighbours(current)) {
        if (mark.exists(new_one))   // if this node is already marked, stop
          continue;
 
        mark.insert(new_one, current);
 
        if (new_one == n1) {
          std::vector< NodeId > v;
 
          for (current = n1; current != n2; current = mark[current])
            v.push_back(current);
 
          v.push_back(n2);
 
          return v;
        }
 
        nodeFIFO.pushBack(new_one);
      }
    }
 
    GUM_ERROR(NotFound, "no path found")
  }

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

Here is the call graph for this function:

◆ unvirtualizedEraseNeighbours()

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

inherited

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

Parameters

id	the node whose ingoing arcs will be removed

Definition at line 114 of file edgeGraphPart_inl.h.

                                                                   {
    if (_neighbours_.exists(id)) {
      const NodeSet& set = *(_neighbours_[id]);
 
      for (auto iter = set.beginSafe(); iter != set.endSafe();
           ++iter) {   // safe iterator needed here
        EdgeGraphPart::eraseEdge(Edge(*iter, id));
      }
    }
  }

References _neighbours_, gum::Set< Key >::beginSafe(), gum::Set< Key >::endSafe(), and eraseEdge().

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

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ _cliques_

NodeProperty< NodeSet > gum::CliqueGraph::_cliques_

private

the set of nodes contained into the cliques

Definition at line 266 of file cliqueGraph.h.

◆ _edges_

EdgeSet gum::EdgeGraphPart::_edges_

privateinherited

the set of all the edges contained within the EdgeGraphPart

Definition at line 266 of file edgeGraphPart.h.

Referenced by EdgeGraphPart(), EdgeGraphPart(), _clearEdges_(), addEdge(), edges(), emptyEdges(), eraseEdge(), existsEdge(), operator=(), operator==(), sizeEdges(), and toString().

◆ _neighbours_

NodeProperty< NodeSet* > gum::EdgeGraphPart::_neighbours_

privateinherited

for each node, the set of its adjacent edges

Definition at line 269 of file edgeGraphPart.h.

Referenced by EdgeGraphPart(), _checkNeighbours_(), _clearEdges_(), addEdge(), eraseEdge(), eraseNeighbours(), existsEdge(), neighbours(), operator=(), and unvirtualizedEraseNeighbours().

◆ _separators_

EdgeProperty< NodeSet > gum::CliqueGraph::_separators_

private

the set of nodes contained into the separators

Definition at line 269 of file cliqueGraph.h.

◆ onEdgeAdded

Signaler2< NodeId, NodeId > gum::EdgeGraphPart::onEdgeAdded

inherited

Definition at line 98 of file edgeGraphPart.h.

Referenced by EdgeGraphPart(), addEdge(), and operator=().

◆ onEdgeDeleted

Signaler2< NodeId, NodeId > gum::EdgeGraphPart::onEdgeDeleted

inherited

Definition at line 99 of file edgeGraphPart.h.

Referenced by _clearEdges_(), and eraseEdge().

◆ 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 file:

agrum/base/graphs/cliqueGraph.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ EdgeIterator

◆ node_const_iterator

◆ node_const_iterator_safe

◆ node_iterator

◆ node_iterator_safe

◆ NodeConstIterator

◆ NodeConstIteratorSafe

◆ NodeIterator

◆ NodeIteratorSafe

Constructor & Destructor Documentation

◆ CliqueGraph() [1/2]

◆ CliqueGraph() [2/2]

◆ ~CliqueGraph()

Member Function Documentation

◆ _checkNeighbours_()

◆ _clearEdges_()

◆ _runningIntersectionDFS_()

◆ _updateSeparators_()

◆ addEdge()

◆ addNode() [1/2]

◆ addNode() [2/2]

◆ addNodes()

◆ addNodeWithId() [1/2]

◆ addNodeWithId() [2/2]

◆ addToClique()

◆ asNodeSet()

◆ begin()

◆ beginSafe()

◆ bound()

◆ clear()

◆ clearEdges()

◆ clearNodes()

◆ clique()

◆ completeGraph()

◆ container()

◆ containerPath()

◆ edges()

◆ edgesProperty() [1/2]

◆ edgesProperty() [2/2]

◆ empty()

◆ emptyEdges()

◆ emptyNodes()

◆ end()

◆ endSafe()

◆ eraseEdge()

◆ eraseFromClique()

◆ eraseNeighbours()

◆ eraseNode()

◆ exists()

◆ existsEdge() [1/2]

◆ existsEdge() [2/2]

◆ existsNode()

◆ hasRunningIntersection()

◆ hasUndirectedCycle()

◆ hasUndirectedPath() [1/3]

◆ hasUndirectedPath() [2/3]

◆ hasUndirectedPath() [3/3]

◆ isJoinTree()

◆ listMapEdges()

◆ listMapNodes()

◆ mapToDot()

◆ neighbours()

◆ nextNodeId()

◆ nodes()

◆ nodes2ConnectedComponent()

◆ nodesPropertyFromFunction()

◆ nodesPropertyFromVal()

◆ operator!=() [1/2]

◆ operator!=() [2/2]

◆ operator=()

◆ operator==() [1/4]