Class that performs incremental triangulations. More...

#include <incrementalTriangulation.h>

Inheritance diagram for gum::IncrementalTriangulation:

Collaboration diagram for gum::IncrementalTriangulation:

Public Member Functions
Constructors / Destructors
	IncrementalTriangulation (const UnconstrainedTriangulation &triang_algo, const UndiGraph theGraph, const NodeProperty< Size > modal)
	constructor
	IncrementalTriangulation (const UnconstrainedTriangulation &triangAlgo)
	default constructor: initialize the triangulation with en empty graph
	IncrementalTriangulation (const IncrementalTriangulation &from)
	copy operator
	~IncrementalTriangulation ()
	destructor
Accessors / Modifiers
void	updateTriangulation ()
	updates the triangulated graph using the modif list
void	addNode (const NodeId node, Size modal)
	adds a new node to the graph
void	eraseNode (const NodeId node)
	removes a node from the graph (the join tree may need a triangulation update)
void	addEdge (const NodeId X, const NodeId Y)
	adds a new edge to the graph (the join tree may need a triangulation update)
void	eraseEdge (const Edge &edge)
	removes an edge from the graph (the join tree may need a retriangulation)
const EdgeSet &	fillIns ()
	returns the fill-ins added by the triangulation algorithm
const std::vector< NodeId > &	eliminationOrder ()
	returns an elimination ordering compatible with the triangulated graph
Idx	eliminationOrder (const NodeId)
	returns the number of a given node in the elimination order (0 = first node eliminated)
const UndiGraph &	triangulatedGraph ()
	returns the triangulated graph
const UndiGraph &	graph () const
	returns the current graph (that which is incrementally triangulated)
const CliqueGraph &	eliminationTree ()
	returns the elimination tree of a compatible ordering
const CliqueGraph &	junctionTree ()
	returns a junction tree corresponding to the current graph
NodeId	createdJunctionTreeClique (const NodeId id)
	returns the Id of the clique created by the elimination of a given node during the triangulation process
const NodeProperty< NodeId > &	createdJunctionTreeCliques ()
	returns the Ids of the cliques of the junction tree created by the elimination of the nodes
const CliqueGraph &	maxPrimeSubgraphTree ()
	returns the junction tree of the maximal prime subgraphs
NodeId	createdMaxPrimeSubgraph (const NodeId id)
	returns the Id of the maximal prime subgraph created by the elimination of a given node during the triangulation process
void	clear ()
	sets the graph to the empty graph
void	setGraph (const UndiGraph theGraph, const NodeProperty< Size > domain_sizes)
	changes the current graph
const UnconstrainedTriangulation &	triangulationAlgo () const
	returns the triangulation algorithm (useful for fine tuning it)
Operators
IncrementalTriangulation &	operator= (const IncrementalTriangulation &from)
	copy operator
virtual IncrementalTriangulation *	newFactory () const final
	virtual clone constructor
virtual IncrementalTriangulation *	copyFactory () const final
	virtual copy constructor
Accessors / Modifiers
double	maxLog10CliqueDomainSize ()
	returns the max of log10DomainSize of the cliques in the junction tree.
const NodeProperty< Size > *	domainSizes () const
	returns the domain sizes of the variables of the graph to be triangulated

Protected Attributes
const NodeProperty< Size > *	domain_sizes_ {nullptr}
	the domain sizes of the variables/nodes of the graph

Private Member Functions
void	_markAffectedMPSsByRemoveLink_ (const NodeId My, const NodeId Mz, const Edge &edge)
	mark the mps affected by the deletion of a given edge
int	_markAffectedMPSsByAddLink_ (const NodeId My, const NodeId Mz, const NodeId X, const NodeId Y)
	mark the mps affected by the insertion of a new edge
void	_performRemoveNode_ (const NodeId node, const NodeId My, const NodeId Mz)
	remove a given node from the T_mpd structure
void	_performAddNode_ (const NodeId node)
	adds a new node to T_mpd, the graph and the clique graph
void	_setUpConnectedTriangulation_ (NodeId Mx, NodeId Mfrom, UndiGraph &theGraph, std::vector< Edge > &notAffectedneighborClique, HashTable< NodeId, bool > &cliques_affected)
	set-up the connected subgraph that needs be retriangulated
void	_computeMaxPrimeMergings_ (const NodeId node, const NodeId from, std::vector< std::pair< NodeId, NodeId > > &merged_cliques, NodeProperty< bool > &mark, const NodeSet &new_nodes_in_junction_tree) const
	used for computing the junction tree of the maximal prime subgraphs
void	_updateJunctionTree_ (NodeProperty< bool > &all_cliques_affected, NodeSet &new_nodes_in_junction_tree)
	update the junction tree
void	_updateMaxPrimeSubgraph_ (NodeProperty< bool > &cliques_affected, const NodeSet &new_nodes_in_junction_tree)
	update the max prime subgraph
void	_collectEliminationOrder_ (const NodeId node, const NodeId from, NodeProperty< bool > &examined, Idx &index)
	a collect algorithm to compute elimination orderings
void	_collectJTCliques_ (const NodeId clique, const NodeId from, NodeProperty< bool > &examined)
	a collect algorithm to compute, for each node, one container JT's clique
bool	_check_ ()
	checks that the incremental triangulation works properly

Private Attributes
UndiGraph	_graph_
	the graph that needs be triangulated
NodeProperty< Size >	_domain_sizes_
	the domain sizes of the nodes
CliqueGraph	_junction_tree_
	the junction tree computed so far
CliqueGraph	_T_mpd_
	the maximal prime subgraph tree
NodeProperty< List< NodeId > >	_mps_of_node_
	for each node in graph, store the MPS containing the node
NodeProperty< std::vector< NodeId > >	_cliques_of_mps_
	indicate for each MPS its set of cliques in the junction tree
NodeProperty< NodeId >	_mps_of_clique_
	indicate for each clique the MPS it belongs to
NodeProperty< bool >	_mps_affected_
	the set of MPS affected by a new triangulation
UnconstrainedTriangulation *	_triangulation_
	the triangulation algorithm that will be used incremantally
bool	_require_update_ {false}
	a Boolean indicating whether the triangulation need be updated
bool	_require_elimination_order_ {false}
	a Boolean indicating wether we should update the elimination order
std::vector< NodeId >	_elimination_order_
	the current elimination ordering
NodeProperty< Idx >	_reverse_elimination_order_
	the elimination order (access by NodeId)
bool	_require_created_JT_cliques_ {false}
	a Boolean indicating whether we should compute the createdJTCliques
NodeProperty< NodeId >	_created_JT_cliques_
	For each node, a clique that contains it.

Friends
class	gum_tests::IncrementalTriangulationTestSuite
	to enable testunits to use check

Detailed Description

Class that performs incremental triangulations.

Definition at line 68 of file incrementalTriangulation.h.

Constructor & Destructor Documentation

◆ IncrementalTriangulation() [1/3]

gum::IncrementalTriangulation::IncrementalTriangulation	(	const UnconstrainedTriangulation &	triang_algo,
		const UndiGraph *	theGraph,
		const NodeProperty< Size > *	modal )

constructor

Note that, in the graph passed in argument, the type of the edges may differ from Edge. However, the junction trees and triangulated graphs produced by the triangulation algorithm will all have edges of type Edge.

Referenced by IncrementalTriangulation(), copyFactory(), newFactory(), and operator=().

Here is the caller graph for this function:

◆ IncrementalTriangulation() [2/3]

gum::IncrementalTriangulation::IncrementalTriangulation ( const UnconstrainedTriangulation & triangAlgo )

default constructor: initialize the triangulation with en empty graph

◆ IncrementalTriangulation() [3/3]

gum::IncrementalTriangulation::IncrementalTriangulation ( const IncrementalTriangulation & from )

copy operator

References IncrementalTriangulation().

Here is the call graph for this function:

◆ ~IncrementalTriangulation()

gum::IncrementalTriangulation::~IncrementalTriangulation ( )

destructor

Member Function Documentation

◆ _check_()

bool gum::IncrementalTriangulation::_check_ ( )

private

checks that the incremental triangulation works properly

◆ _collectEliminationOrder_()

void gum::IncrementalTriangulation::_collectEliminationOrder_	(	const NodeId	node,
		const NodeId	from,
		NodeProperty< bool > &	examined,
		Idx &	index )

private

a collect algorithm to compute elimination orderings

◆ _collectJTCliques_()

void gum::IncrementalTriangulation::_collectJTCliques_	(	const NodeId	clique,
		const NodeId	from,
		NodeProperty< bool > &	examined )

private

a collect algorithm to compute, for each node, one container JT's clique

◆ _computeMaxPrimeMergings_()

void gum::IncrementalTriangulation::_computeMaxPrimeMergings_	(	const NodeId	node,
		const NodeId	from,
		std::vector< std::pair< NodeId, NodeId > > &	merged_cliques,
		NodeProperty< bool > &	mark,
		const NodeSet &	new_nodes_in_junction_tree ) const

private

used for computing the junction tree of the maximal prime subgraphs

◆ _markAffectedMPSsByAddLink_()

int gum::IncrementalTriangulation::_markAffectedMPSsByAddLink_	(	const NodeId	My,
		const NodeId	Mz,
		const NodeId	X,
		const NodeId	Y )

private

mark the mps affected by the insertion of a new edge

◆ _markAffectedMPSsByRemoveLink_()

void gum::IncrementalTriangulation::_markAffectedMPSsByRemoveLink_	(	const NodeId	My,
		const NodeId	Mz,
		const Edge &	edge )

private

mark the mps affected by the deletion of a given edge

◆ _performAddNode_()

void gum::IncrementalTriangulation::_performAddNode_ ( const NodeId node )

private

adds a new node to T_mpd, the graph and the clique graph

◆ _performRemoveNode_()

void gum::IncrementalTriangulation::_performRemoveNode_	(	const NodeId	node,
		const NodeId	My,
		const NodeId	Mz )

private

remove a given node from the T_mpd structure

◆ _setUpConnectedTriangulation_()

void gum::IncrementalTriangulation::_setUpConnectedTriangulation_	(	NodeId	Mx,
		NodeId	Mfrom,
		UndiGraph &	theGraph,
		std::vector< Edge > &	notAffectedneighborClique,
		HashTable< NodeId, bool > &	cliques_affected )

private

set-up the connected subgraph that needs be retriangulated

◆ _updateJunctionTree_()

void gum::IncrementalTriangulation::_updateJunctionTree_	(	NodeProperty< bool > &	all_cliques_affected,
		NodeSet &	new_nodes_in_junction_tree )

private

update the junction tree

◆ _updateMaxPrimeSubgraph_()

void gum::IncrementalTriangulation::_updateMaxPrimeSubgraph_	(	NodeProperty< bool > &	cliques_affected,
		const NodeSet &	new_nodes_in_junction_tree )

private

update the max prime subgraph

◆ addEdge()

void gum::IncrementalTriangulation::addEdge	(	const NodeId	X,
		const NodeId	Y )

adds a new edge to the graph (the join tree may need a triangulation update)

◆ addNode()

void gum::IncrementalTriangulation::addNode	(	const NodeId	node,
		Size	modal )

adds a new node to the graph

◆ clear()

void gum::IncrementalTriangulation::clear ( )

virtual

sets the graph to the empty graph

Implements gum::Triangulation.

◆ copyFactory()

virtual IncrementalTriangulation * gum::IncrementalTriangulation::copyFactory ( ) const

finalvirtual

virtual copy constructor

Implements gum::Triangulation.

References IncrementalTriangulation(), and copyFactory().

Referenced by copyFactory().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ createdJunctionTreeClique()

NodeId gum::IncrementalTriangulation::createdJunctionTreeClique ( const NodeId id )

virtual

returns the Id of the clique created by the elimination of a given node during the triangulation process

Implements gum::Triangulation.

◆ createdJunctionTreeCliques()

const NodeProperty< NodeId > & gum::IncrementalTriangulation::createdJunctionTreeCliques ( )

virtual

returns the Ids of the cliques of the junction tree created by the elimination of the nodes

Implements gum::Triangulation.

◆ createdMaxPrimeSubgraph()

NodeId gum::IncrementalTriangulation::createdMaxPrimeSubgraph ( const NodeId id )

virtual

returns the Id of the maximal prime subgraph created by the elimination of a given node during the triangulation process

Implements gum::Triangulation.

◆ domainSizes()

const NodeProperty< Size > * gum::Triangulation::domainSizes ( ) const

inherited

returns the domain sizes of the variables of the graph to be triangulated

◆ eliminationOrder() [1/2]

const std::vector< NodeId > & gum::IncrementalTriangulation::eliminationOrder ( )

virtual

returns an elimination ordering compatible with the triangulated graph

Implements gum::Triangulation.

◆ eliminationOrder() [2/2]

Idx gum::IncrementalTriangulation::eliminationOrder ( const NodeId )

virtual

returns the number of a given node in the elimination order (0 = first node eliminated)

Implements gum::Triangulation.

◆ eliminationTree()

const CliqueGraph & gum::IncrementalTriangulation::eliminationTree ( )

inlinevirtual

returns the elimination tree of a compatible ordering

Implements gum::Triangulation.

Definition at line 136 of file incrementalTriangulation.h.

136{ GUM_ERROR(OperationNotAllowed, "Not implemented yet") }

GUM_ERROR

#define GUM_ERROR(type, msg)

Definition exceptions.h:72

References GUM_ERROR.

◆ eraseEdge()

void gum::IncrementalTriangulation::eraseEdge ( const Edge & edge )

removes an edge from the graph (the join tree may need a retriangulation)

◆ eraseNode()

void gum::IncrementalTriangulation::eraseNode ( const NodeId node )

removes a node from the graph (the join tree may need a triangulation update)

◆ fillIns()

const EdgeSet & gum::IncrementalTriangulation::fillIns ( )

inlinevirtual

returns the fill-ins added by the triangulation algorithm

Implements gum::Triangulation.

Definition at line 120 of file incrementalTriangulation.h.

120{ GUM_ERROR(OperationNotAllowed, "Not implemented yet") }

References GUM_ERROR.

◆ graph()

const UndiGraph & gum::IncrementalTriangulation::graph ( ) const

returns the current graph (that which is incrementally triangulated)

◆ junctionTree()

const CliqueGraph & gum::IncrementalTriangulation::junctionTree ( )

virtual

returns a junction tree corresponding to the current graph

Implements gum::Triangulation.

◆ maxLog10CliqueDomainSize()

double gum::Triangulation::maxLog10CliqueDomainSize ( )

inherited

returns the max of log10DomainSize of the cliques in the junction tree.

This is usefull for instance to estimate the complexity (both in space and in time) of the inference that will use the junction tree.

This method is not 'const' since it can be called before building any junction tree and hence it needs to build it...

Definition at line 86 of file triangulation.cpp.

                                                 {
    double              res = 0.0;
    double              dSize;
    const JunctionTree& jt = junctionTree();   // here, the fact that we get
    // a junction tree ensures that domain_sizes_ is different from nullptr
 
    for (const NodeId cl: jt) {
      dSize = 0.0;
 
      for (const auto node: jt.clique(cl))
        dSize += std::log10((*domain_sizes_)[node]);
 
      if (res < dSize) res = dSize;
    }
 
    return res;
  }

References gum::CliqueGraph::clique(), domain_sizes_, and junctionTree().

Referenced by gum::MaxInducedWidthMCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::_checkConditions_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ maxPrimeSubgraphTree()

const CliqueGraph & gum::IncrementalTriangulation::maxPrimeSubgraphTree ( )

virtual

returns the junction tree of the maximal prime subgraphs

Implements gum::Triangulation.

◆ newFactory()

virtual IncrementalTriangulation * gum::IncrementalTriangulation::newFactory ( ) const

finalvirtual

virtual clone constructor

Implements gum::Triangulation.

References IncrementalTriangulation().

Here is the call graph for this function:

◆ operator=()

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

copy operator

References IncrementalTriangulation().

Here is the call graph for this function:

◆ setGraph()

void gum::IncrementalTriangulation::setGraph	(	const UndiGraph *	theGraph,
		const NodeProperty< Size > *	domain_sizes )

virtual

changes the current graph

Implements gum::Triangulation.

◆ triangulatedGraph()

const UndiGraph & gum::IncrementalTriangulation::triangulatedGraph ( )

inlinevirtual

returns the triangulated graph

Implements gum::Triangulation.

Definition at line 130 of file incrementalTriangulation.h.

130{ GUM_ERROR(OperationNotAllowed, "Not implemented yet") }

References GUM_ERROR.

◆ triangulationAlgo()

const UnconstrainedTriangulation & gum::IncrementalTriangulation::triangulationAlgo ( ) const

returns the triangulation algorithm (useful for fine tuning it)

◆ updateTriangulation()

void gum::IncrementalTriangulation::updateTriangulation ( )

updates the triangulated graph using the modif list

◆ gum_tests::IncrementalTriangulationTestSuite

friend class gum_tests::IncrementalTriangulationTestSuite

friend

to enable testunits to use check

Definition at line 281 of file incrementalTriangulation.h.

References gum_tests::IncrementalTriangulationTestSuite.

Referenced by gum_tests::IncrementalTriangulationTestSuite.

Member Data Documentation

◆ _cliques_of_mps_

NodeProperty< std::vector< NodeId > > gum::IncrementalTriangulation::_cliques_of_mps_

private

indicate for each MPS its set of cliques in the junction tree

Definition at line 202 of file incrementalTriangulation.h.

◆ _created_JT_cliques_

NodeProperty< NodeId > gum::IncrementalTriangulation::_created_JT_cliques_

private

For each node, a clique that contains it.

Definition at line 229 of file incrementalTriangulation.h.

◆ _domain_sizes_

NodeProperty< Size > gum::IncrementalTriangulation::_domain_sizes_

private

the domain sizes of the nodes

Definition at line 190 of file incrementalTriangulation.h.

◆ _elimination_order_

std::vector< NodeId > gum::IncrementalTriangulation::_elimination_order_

private

the current elimination ordering

Definition at line 220 of file incrementalTriangulation.h.

◆ _graph_

UndiGraph gum::IncrementalTriangulation::_graph_

private

the graph that needs be triangulated

Definition at line 187 of file incrementalTriangulation.h.

◆ _junction_tree_

CliqueGraph gum::IncrementalTriangulation::_junction_tree_

private

the junction tree computed so far

Definition at line 193 of file incrementalTriangulation.h.

◆ _mps_affected_

NodeProperty< bool > gum::IncrementalTriangulation::_mps_affected_

private

the set of MPS affected by a new triangulation

Definition at line 208 of file incrementalTriangulation.h.

◆ _mps_of_clique_

NodeProperty< NodeId > gum::IncrementalTriangulation::_mps_of_clique_

private

indicate for each clique the MPS it belongs to

Definition at line 205 of file incrementalTriangulation.h.

◆ _mps_of_node_

NodeProperty< List< NodeId > > gum::IncrementalTriangulation::_mps_of_node_

private

for each node in graph, store the MPS containing the node

Definition at line 199 of file incrementalTriangulation.h.

◆ _require_created_JT_cliques_

bool gum::IncrementalTriangulation::_require_created_JT_cliques_ {false}

private

a Boolean indicating whether we should compute the createdJTCliques

Definition at line 226 of file incrementalTriangulation.h.

226{false};

◆ _require_elimination_order_

bool gum::IncrementalTriangulation::_require_elimination_order_ {false}

private

a Boolean indicating wether we should update the elimination order

Definition at line 217 of file incrementalTriangulation.h.

217{false};

◆ _require_update_

bool gum::IncrementalTriangulation::_require_update_ {false}

private

a Boolean indicating whether the triangulation need be updated

Definition at line 214 of file incrementalTriangulation.h.

214{false};

◆ _reverse_elimination_order_

NodeProperty< Idx > gum::IncrementalTriangulation::_reverse_elimination_order_

private

the elimination order (access by NodeId)

Definition at line 223 of file incrementalTriangulation.h.

◆ _T_mpd_

CliqueGraph gum::IncrementalTriangulation::_T_mpd_

private

the maximal prime subgraph tree

Definition at line 196 of file incrementalTriangulation.h.

◆ _triangulation_

UnconstrainedTriangulation* gum::IncrementalTriangulation::_triangulation_

private

the triangulation algorithm that will be used incremantally

Definition at line 211 of file incrementalTriangulation.h.

◆ domain_sizes_

const NodeProperty< Size >* gum::Triangulation::domain_sizes_ {nullptr}

protectedinherited

the domain sizes of the variables/nodes of the graph

Definition at line 170 of file triangulation.h.

170{nullptr};

Referenced by Triangulation(), Triangulation(), Triangulation(), gum::OrderedTriangulation::initTriangulation_(), gum::PartialOrderedTriangulation::initTriangulation_(), gum::StaticTriangulation::initTriangulation_(), maxLog10CliqueDomainSize(), and gum::StaticTriangulation::setGraph().

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

agrum/base/graphs/algorithms/triangulations/incrementalTriangulation.h

Public Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ IncrementalTriangulation() [1/3]

◆ IncrementalTriangulation() [2/3]

◆ IncrementalTriangulation() [3/3]

◆ ~IncrementalTriangulation()

Member Function Documentation

◆ _check_()

◆ _collectEliminationOrder_()

◆ _collectJTCliques_()

◆ _computeMaxPrimeMergings_()

◆ _markAffectedMPSsByAddLink_()

◆ _markAffectedMPSsByRemoveLink_()

◆ _performAddNode_()

◆ _performRemoveNode_()

◆ _setUpConnectedTriangulation_()

◆ _updateJunctionTree_()

◆ _updateMaxPrimeSubgraph_()

◆ addEdge()

◆ addNode()

◆ clear()

◆ copyFactory()

◆ createdJunctionTreeClique()

◆ createdJunctionTreeCliques()

◆ createdMaxPrimeSubgraph()

◆ domainSizes()

◆ eliminationOrder() [1/2]

◆ eliminationOrder() [2/2]

◆ eliminationTree()

◆ eraseEdge()

◆ eraseNode()

◆ fillIns()

◆ graph()

◆ junctionTree()

◆ maxLog10CliqueDomainSize()

◆ maxPrimeSubgraphTree()

◆ newFactory()

◆ operator=()

◆ setGraph()

◆ triangulatedGraph()

◆ triangulationAlgo()

◆ updateTriangulation()

Friends And Related Symbol Documentation

◆ gum_tests::IncrementalTriangulationTestSuite

Member Data Documentation

◆ _cliques_of_mps_

◆ _created_JT_cliques_

◆ _domain_sizes_

◆ _elimination_order_

◆ _graph_

◆ _junction_tree_

◆ _mps_affected_

◆ _mps_of_clique_

◆ _mps_of_node_

◆ _require_created_JT_cliques_

◆ _require_elimination_order_

◆ _require_update_

◆ _reverse_elimination_order_

◆ _T_mpd_

◆ _triangulation_

◆ domain_sizes_