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

	IncrementalTriangulation (const UnconstrainedTriangulation &triangAlgo)
	default constructor: initialize the triangulation with en empty graph More...

	IncrementalTriangulation (const IncrementalTriangulation &from)
	copy operator More...

	~IncrementalTriangulation ()
	destructor More...

Accessors / Modifiers
void	updateTriangulation ()
	updates the triangulated graph using the modif list More...

void	addNode (const NodeId node, Size modal)
	adds a new node to the graph More...

void	eraseNode (const NodeId node)
	removes a node from the graph (the join tree may need a triangulation update) More...

void	addEdge (const NodeId X, const NodeId Y)
	adds a new edge to the graph (the join tree may need a triangulation update) More...

void	eraseEdge (const Edge &edge)
	removes an edge from the graph (the join tree may need a retriangulation) More...

const EdgeSet &	fillIns ()
	returns the fill-ins added by the triangulation algorithm More...

const std::vector< NodeId > &	eliminationOrder ()
	returns an elimination ordering compatible with the triangulated graph More...

Idx	eliminationOrder (const NodeId)
	returns the number of a given node in the elimination order (0 = first node eliminated) More...

const UndiGraph &	triangulatedGraph ()
	returns the triangulated graph More...

const UndiGraph &	graph () const
	returns the current graph (that which is incrementally triangulated) More...

const CliqueGraph &	eliminationTree ()
	returns the elimination tree of a compatible ordering More...

const CliqueGraph &	junctionTree ()
	returns a junction tree corresponding to the current graph More...

NodeId	createdJunctionTreeClique (const NodeId id)
	returns the Id of the clique created by the elimination of a given node during the triangulation process More...

const NodeProperty< NodeId > &	createdJunctionTreeCliques ()
	returns the Ids of the cliques of the junction tree created by the elimination of the nodes More...

const CliqueGraph &	maxPrimeSubgraphTree ()
	returns the junction tree of the maximal prime subgraphs More...

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

void	clear ()
	sets the graph to the empty graph More...

void	setGraph (const UndiGraph theGraph, const NodeProperty< Size > domain_sizes)
	changes the current graph More...

const UnconstrainedTriangulation &	triangulationAlgo () const
	returns the triangulation algorithm (useful for fine tuning it) More...

Operators
IncrementalTriangulation &	operator= (const IncrementalTriangulation &from)
	copy operator More...

virtual IncrementalTriangulation *	newFactory () const final
	virtual clone constructor More...

virtual IncrementalTriangulation *	copyFactory () const final
	virtual copy constructor More...

Accessors / Modifiers
double	maxLog10CliqueDomainSize ()
	returns the max of log10DomainSize of the cliques in the junction tree. More...

const NodeProperty< Size > *	domainSizes () const
	returns the domain sizes of the variables of the graph to be triangulated More...

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

Friends
class	gum_tests::IncrementalTriangulationTestSuite
	to enable testunits to use __check More...

Detailed Description

Class that performs incremental triangulations.

Definition at line 51 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.

◆ 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

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

◆ 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

Todo:: : why not a Sequence? because we need its content to be non-constant

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 125 of file incrementalTriangulation.h.

References GUM_ERROR.

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

◆ 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 103 of file incrementalTriangulation.h.

References GUM_ERROR.

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

◆ 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 70 of file triangulation.cpp.

References gum::Triangulation::_domain_sizes, and gum::Triangulation::junctionTree().

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

                                                  {
     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;
   }

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.

◆ operator=()

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

copy operator

◆ 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 117 of file incrementalTriangulation.h.

References GUM_ERROR.

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

◆ 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

Friends And Related Function Documentation

◆ gum_tests::IncrementalTriangulationTestSuite

friend class gum_tests::IncrementalTriangulationTestSuite

friend

to enable testunits to use __check

Definition at line 279 of file incrementalTriangulation.h.

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 194 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 221 of file incrementalTriangulation.h.

◆ __domain_sizes

NodeProperty< Size > gum::IncrementalTriangulation::__domain_sizes

private

the domain sizes of the nodes

Definition at line 182 of file incrementalTriangulation.h.

◆ __elimination_order

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

private

the current elimination ordering

Definition at line 212 of file incrementalTriangulation.h.

◆ __graph

UndiGraph gum::IncrementalTriangulation::__graph

private

the graph that needs be triangulated

Definition at line 179 of file incrementalTriangulation.h.

◆ __junction_tree

CliqueGraph gum::IncrementalTriangulation::__junction_tree

private

the junction tree computed so far

Definition at line 185 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 200 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 197 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 191 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 218 of file incrementalTriangulation.h.

◆ __require_elimination_order

bool gum::IncrementalTriangulation::__require_elimination_order {false}

private

a Boolean indicating wether we should update the elimination order

Definition at line 209 of file incrementalTriangulation.h.

◆ __require_update

bool gum::IncrementalTriangulation::__require_update {false}

private

a Boolean indicating whether the triangulation need be updated

Definition at line 206 of file incrementalTriangulation.h.

◆ __reverse_elimination_order

NodeProperty< Idx > gum::IncrementalTriangulation::__reverse_elimination_order

private

the elimination order (access by NodeId)

Definition at line 215 of file incrementalTriangulation.h.

◆ __T_mpd

CliqueGraph gum::IncrementalTriangulation::__T_mpd

private

the maximal prime subgraph tree

Definition at line 188 of file incrementalTriangulation.h.

◆ __triangulation

UnconstrainedTriangulation* gum::IncrementalTriangulation::__triangulation

private

the triangulation algorithm that will be used incremantally

Definition at line 203 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 152 of file triangulation.h.

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

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

agrum/graphs/algorithms/triangulations/incrementalTriangulation.h

Public Member Functions

Protected 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 Function 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