Interface for all the triangulation methods. More...

#include <triangulation.h>

Inheritance diagram for gum::Triangulation:

Collaboration diagram for gum::Triangulation:

Public Member Functions
Constructors / Destructors
virtual Triangulation *	newFactory () const =0
	returns a fresh triangulation of the same type as the current object but with an empty graph More...

virtual Triangulation *	copyFactory () const =0
	virtual copy constructor More...

virtual	~Triangulation ()
	destructor More...

Accessors / Modifiers
virtual void	setGraph (const UndiGraph graph, const NodeProperty< Size > domsizes)=0
	initialize the triangulation data structures for a new graph More...

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

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

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

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

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

virtual const CliqueGraph &	junctionTree ()=0
	returns a compatible junction tree More...

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

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

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

virtual const CliqueGraph &	maxPrimeSubgraphTree ()=0
	returns a junction tree of maximal prime subgraphs More...

virtual NodeId	createdMaxPrimeSubgraph (const NodeId id)=0
	returns the Id of the maximal prime subgraph created by the elimination of a given node during the triangulation process More...

virtual void	clear ()=0
	reinitialize the graph to be triangulated to an empty graph 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...

Protected Member Functions
	Triangulation ()
	default constructor More...

	Triangulation (const NodeProperty< Size > *domsizes)
	constructor with a domain size specified More...

	Triangulation (const Triangulation &)
	prevent copy constructor except when using newFactory More...

	Triangulation (Triangulation &&)
	prevent move constructor except when used by children More...

Detailed Description

Interface for all the triangulation methods.

Definition at line 46 of file triangulation.h.

Constructor & Destructor Documentation

◆ ~Triangulation()

gum::Triangulation::~Triangulation ( )

virtual

destructor

Definition at line 49 of file triangulation.cpp.

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

                                 {   // for debugging purposes
     GUM_DESTRUCTOR(Triangulation);
   }

Here is the call graph for this function:

◆ Triangulation() [1/4]

gum::Triangulation::Triangulation ( )

protected

default constructor

Definition at line 39 of file triangulation.cpp.

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

                                {   // for debugging purposes
     GUM_CONSTRUCTOR(Triangulation);
   }

Here is the call graph for this function:

◆ Triangulation() [2/4]

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

protected

constructor with a domain size specified

Warning: note that, by aGrUM's rule, domsizes is not copied but only referenced by the triangulation algorithm.

Definition at line 44 of file triangulation.cpp.

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

                                                                    : domain_sizes_(domsizes) {
     GUM_CONSTRUCTOR(Triangulation);
   }

Here is the call graph for this function:

◆ Triangulation() [3/4]

gum::Triangulation::Triangulation ( const Triangulation & from )

protected

prevent copy constructor except when using newFactory

Definition at line 54 of file triangulation.cpp.

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

                                                         : domain_sizes_(from.domain_sizes_) {
     GUM_CONS_CPY(Triangulation);
   }

Here is the call graph for this function:

◆ Triangulation() [4/4]

gum::Triangulation::Triangulation ( Triangulation && from )

protected

prevent move constructor except when used by children

Definition at line 59 of file triangulation.cpp.

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

                                                    : domain_sizes_(from.domain_sizes_) {
     GUM_CONS_MOV(Triangulation);
   }

Here is the call graph for this function:

Member Function Documentation

◆ clear()

virtual void gum::Triangulation::clear ( )

pure virtual

reinitialize the graph to be triangulated to an empty graph

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ copyFactory()

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

pure virtual

virtual copy constructor

note that we return a pointer as it enables subclasses to return pointers to their types, not Triangulation pointers. See item 25 of the more effective C++.

Implemented in gum::IncrementalTriangulation, gum::PartialOrderedTriangulation, gum::OrderedTriangulation, gum::DefaultTriangulation, gum::StaticTriangulation, and gum::UnconstrainedTriangulation.

◆ createdJunctionTreeClique()

virtual NodeId gum::Triangulation::createdJunctionTreeClique ( const NodeId id )

pure virtual

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

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ createdJunctionTreeCliques()

virtual const NodeProperty< NodeId >& gum::Triangulation::createdJunctionTreeCliques ( )

pure virtual

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

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ createdMaxPrimeSubgraph()

virtual NodeId gum::Triangulation::createdMaxPrimeSubgraph ( const NodeId id )

pure virtual

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

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ domainSizes()

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

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

◆ eliminationOrder() [1/2]

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

pure virtual

returns an elimination ordering compatible with the triangulated graph

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ eliminationOrder() [2/2]

virtual Idx gum::Triangulation::eliminationOrder ( const NodeId )

pure virtual

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

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ eliminationTree()

virtual const CliqueGraph& gum::Triangulation::eliminationTree ( )

pure virtual

returns the elimination tree of a compatible ordering

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ fillIns()

virtual const EdgeSet& gum::Triangulation::fillIns ( )

pure virtual

returns the fill-ins added by the triangulation algorithm

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ junctionTree()

virtual const CliqueGraph& gum::Triangulation::junctionTree ( )

pure virtual

returns a compatible junction tree

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ maxLog10CliqueDomainSize()

double gum::Triangulation::maxLog10CliqueDomainSize ( )

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

virtual const CliqueGraph& gum::Triangulation::maxPrimeSubgraphTree ( )

pure virtual

returns a junction tree of maximal prime subgraphs

Warning: Actually, the cliques of the junction tree are guarranteed to be maximal prime subgraph of the original graph that was triangulated only if the triangulation performed is minimal (in the sense that removing any edge in the triangulated graph results in a nontriangulated graph). This can be ensured by requiring minimality of the triangulation.

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

◆ newFactory()

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

pure virtual

returns a fresh triangulation of the same type as the current object but with an empty graph

note that we return a pointer as it enables subclasses to return pointers to their types, not Triangulation pointers. See item 25 of the more effective C++.

Implemented in gum::IncrementalTriangulation, gum::PartialOrderedTriangulation, gum::OrderedTriangulation, gum::DefaultTriangulation, gum::StaticTriangulation, and gum::UnconstrainedTriangulation.

◆ operator=()

Triangulation& gum::Triangulation::operator= ( const Triangulation & )

private

prevent copy operator

◆ setGraph()

virtual void gum::Triangulation::setGraph	(	const UndiGraph *	graph,
		const NodeProperty< Size > *	domsizes
	)

pure virtual

initialize the triangulation data structures for a new graph

Parameters

graph	the graph to be triangulated, i.e., the nodes of which will be eliminated
domsizes	the domain sizes of the nodes to be eliminated

Warning: Note that we allow domsizes to be defined over nodes/variables that do not belong to graph. These sizes will simply be ignored. However, it is compulsory that all the nodes of graph belong to dom_sizes; the graph is not copied but only referenced by the elimination sequence algorithm.

Implemented in gum::IncrementalTriangulation, gum::PartialOrderedTriangulation, gum::OrderedTriangulation, and gum::StaticTriangulation.

◆ triangulatedGraph()

virtual const UndiGraph& gum::Triangulation::triangulatedGraph ( )

pure virtual

returns the triangulated graph

Implemented in gum::IncrementalTriangulation, and gum::StaticTriangulation.

Member Data Documentation

◆ domain_sizes_

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

protected

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

agrum/tools/graphs/algorithms/triangulations/triangulation.h
agrum/tools/graphs/algorithms/triangulations/triangulation.cpp

Public Member Functions

Protected Attributes

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ~Triangulation()

◆ Triangulation() [1/4]

◆ Triangulation() [2/4]

◆ Triangulation() [3/4]

◆ Triangulation() [4/4]

Member Function Documentation

◆ clear()

◆ copyFactory()

◆ createdJunctionTreeClique()

◆ createdJunctionTreeCliques()

◆ createdMaxPrimeSubgraph()

◆ domainSizes()

◆ eliminationOrder() [1/2]

◆ eliminationOrder() [2/2]

◆ eliminationTree()

◆ fillIns()

◆ junctionTree()

◆ maxLog10CliqueDomainSize()

◆ maxPrimeSubgraphTree()

◆ newFactory()

◆ operator=()

◆ setGraph()

◆ triangulatedGraph()

Member Data Documentation

◆ domain_sizes_