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 50 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

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

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

GUM_ERROR

#define GUM_ERROR(type, msg)

Definition: exceptions.h:51

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

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

GUM_ERROR

#define GUM_ERROR(type, msg)

Definition: exceptions.h:51

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

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

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

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

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

GUM_ERROR

#define GUM_ERROR(type, msg)

Definition: exceptions.h:51

◆ 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 263 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 184 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 211 of file incrementalTriangulation.h.

◆ _domain_sizes_

NodeProperty< Size > gum::IncrementalTriangulation::_domain_sizes_

private

the domain sizes of the nodes

Definition at line 172 of file incrementalTriangulation.h.

◆ _elimination_order_

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

private

the current elimination ordering

Definition at line 202 of file incrementalTriangulation.h.

◆ _graph_

UndiGraph gum::IncrementalTriangulation::_graph_

private

the graph that needs be triangulated

Definition at line 169 of file incrementalTriangulation.h.

◆ _junction_tree_

CliqueGraph gum::IncrementalTriangulation::_junction_tree_

private

the junction tree computed so far

Definition at line 175 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 190 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 187 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 181 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 208 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 199 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 196 of file incrementalTriangulation.h.

◆ _reverse_elimination_order_

NodeProperty< Idx > gum::IncrementalTriangulation::_reverse_elimination_order_

private

the elimination order (access by NodeId)

Definition at line 205 of file incrementalTriangulation.h.

◆ _T_mpd_

CliqueGraph gum::IncrementalTriangulation::_T_mpd_

private

the maximal prime subgraph tree

Definition at line 178 of file incrementalTriangulation.h.

◆ _triangulation_

UnconstrainedTriangulation* gum::IncrementalTriangulation::_triangulation_

private

the triangulation algorithm that will be used incremantally

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

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

agrum/tools/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_