gum::PartialOrderedTriangulation Class Reference

class for graph triangulations for which we enforce a given partial ordering on the nodes eliminations, that is, the set of all the nodes is divided into several subsets. More...

#include <partialOrderedTriangulation.h>

Inheritance diagram for gum::PartialOrderedTriangulation:

Collaboration diagram for gum::PartialOrderedTriangulation:

Public Member Functions
Constructors / Destructors
	PartialOrderedTriangulation (const PartialOrderedEliminationSequenceStrategy &elimSeq=DefaultPartialOrderedEliminationSequenceStrategy(), const JunctionTreeStrategy &JTStrategy=DefaultJunctionTreeStrategy(), bool minimality=false)
	default constructor More...
	PartialOrderedTriangulation (const UndiGraph *graph, const NodeProperty< Size > *domsizes, const List< NodeSet > *partial_order, const PartialOrderedEliminationSequenceStrategy &elimSeq=DefaultPartialOrderedEliminationSequenceStrategy(), const JunctionTreeStrategy &JTStrategy=DefaultJunctionTreeStrategy(), bool minimality=false)
	constructor with a given graph More...
	PartialOrderedTriangulation (const PartialOrderedTriangulation &from)
	copy constructor More...
	PartialOrderedTriangulation (PartialOrderedTriangulation &&from)
	move constructor More...
virtual PartialOrderedTriangulation *	newFactory () const
	returns a fresh triangulation (over an empty graph) of the same type as the current object More...
virtual PartialOrderedTriangulation *	copyFactory () const final
	virtual copy constructor More...
virtual	~PartialOrderedTriangulation ()
	destructor More...
Accessors / Modifiers
virtual void	setGraph (const UndiGraph *graph, const NodeProperty< Size > *domsizes) final
	initialize the triangulation data structures for a new graph More...
virtual void	setPartialOrder (const List< NodeSet > *partial_order) final
	sets the elimination sequence's partial order (only a reference is stored) More...
Accessors / Modifiers
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 index of a given node in the elimination order (0 = first node eliminated) More...
const NodeProperty< NodeId > &	reverseEliminationOrder ()
	returns a table indicating, for each node, at which step it was deleted by the triangulation process More...
const UndiGraph &	triangulatedGraph ()
	returns the triangulated graph More...
const CliqueGraph &	eliminationTree ()
	returns the elimination tree of a compatible ordering More...
const CliqueGraph &	junctionTree ()
	returns a compatible junction tree More...
NodeId	createdJunctionTreeClique (const NodeId id)
	returns the Id of the clique of the junction tree 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 a junction tree of 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 ()
	reinitialize the graph to be triangulated to an empty graph More...
void	setMinimalRequirement (bool)
	sets/unset the minimality requirement More...
virtual bool	isMinimalityRequired () const final
	indicates wether minimality is required More...
void	setFillIns (bool)
	sets/unsets the record of the fill-ins in the standard triangulation procedure More...
const UndiGraph *	originalGraph () const
	returns the graph to be triangulated More...
EliminationSequenceStrategy &	eliminationSequenceStrategy () const
	returns the elimination sequence strategy used by the triangulation More...
JunctionTreeStrategy &	junctionTreeStrategy () const
	returns the junction tree strategy used by the triangulation 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 List< NodeSet > *	_partial_order_ {nullptr}
	the partial ordering to apply to eliminate nodes More...
EliminationSequenceStrategy *	elimination_sequence_strategy_ {nullptr}
	the elimination sequence strategy used by the triangulation More...
JunctionTreeStrategy *	junction_tree_strategy_ {nullptr}
	the junction tree strategy used by the triangulation More...
const NodeProperty< Size > *	domain_sizes_ {nullptr}
	the domain sizes of the variables/nodes of the graph More...

Protected Member Functions
virtual void	initTriangulation_ (UndiGraph &graph) final
	the function called to initialize the triangulation process More...

Detailed Description

class for graph triangulations for which we enforce a given partial ordering on the nodes eliminations, that is, the set of all the nodes is divided into several subsets.

Within each subset, any ordering can be chosen. But all the nodes of the first subset must be eliminated before the nodes of the second, which must be eliminated before those of the third subset, and so on.

Definition at line 53 of file partialOrderedTriangulation.h.

Constructor & Destructor Documentation

PartialOrderedTriangulation() [1/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation	(	const PartialOrderedEliminationSequenceStrategy &	elimSeq = DefaultPartialOrderedEliminationSequenceStrategy(),
		const JunctionTreeStrategy &	JTStrategy = DefaultJunctionTreeStrategy(),
		bool	minimality = false
	)

default constructor

Parameters

elimSeq	the elimination sequence used to triangulate the graph
JTStrategy	the junction tree strategy used to create junction trees
minimality	a Boolean indicating whether we should enforce that the triangulation is minimal w.r.t. inclusion

Definition at line 36 of file partialOrderedTriangulation.cpp.

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

                                                                  :
      StaticTriangulation(elimSeq, JTStrategy, minimality) {
    // for debugging purposes
    GUM_CONSTRUCTOR(PartialOrderedTriangulation);
  }

Here is the call graph for this function:

PartialOrderedTriangulation() [2/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation	(	const UndiGraph *	graph,
		const NodeProperty< Size > *	domsizes,
		const List< NodeSet > *	partial_order,
		const PartialOrderedEliminationSequenceStrategy &	elimSeq = DefaultPartialOrderedEliminationSequenceStrategy(),
		const JunctionTreeStrategy &	JTStrategy = DefaultJunctionTreeStrategy(),
		bool	minimality = false
	)

constructor with a given 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
partial_order	the list of the subsets constituting the partial ordering
elimSeq	the elimination sequence used to triangulate the graph
JTStrategy	the junction tree strategy used to create junction trees
minimality	a Boolean indicating whether we should enforce that the triangulation is minimal w.r.t. inclusion

Warning

Note that we allow dom_sizes 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

note that, by aGrUM's rule, the graph, the domain sizes and the partial ordering are not copied but only referenced by the triangulation algorithm.

Definition at line 46 of file partialOrderedTriangulation.cpp.

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

                                                                  :
      StaticTriangulation(theGraph, dom, elimSeq, JTStrategy, minimality),
      _partial_order_(partial_order) {
    static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_)
       ->setPartialOrder(_partial_order_);

    // for debugging purposes
    GUM_CONSTRUCTOR(PartialOrderedTriangulation);
  }

Here is the call graph for this function:

PartialOrderedTriangulation() [3/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation

(

const PartialOrderedTriangulation &

from

)

copy constructor

Definition at line 63 of file partialOrderedTriangulation.cpp.

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

                                              :
      StaticTriangulation(from),
      _partial_order_(from._partial_order_) {
    // for debugging purposes
    GUM_CONS_CPY(PartialOrderedTriangulation);
  }

Here is the call graph for this function:

PartialOrderedTriangulation() [4/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation

(

PartialOrderedTriangulation &&

from

)

move constructor

Definition at line 72 of file partialOrderedTriangulation.cpp.

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

                                                                                             :
      StaticTriangulation(std::move(from)), _partial_order_(from._partial_order_) {
    // for debugging purposes
    GUM_CONS_MOV(PartialOrderedTriangulation);
  }

Here is the call graph for this function:

~PartialOrderedTriangulation()

gum::PartialOrderedTriangulation::~PartialOrderedTriangulation ( )

virtual

destructor

Definition at line 92 of file partialOrderedTriangulation.cpp.

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

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

Here is the call graph for this function:

Member Function Documentation

clear()

void gum::StaticTriangulation::clear ( )

virtualinherited

reinitialize the graph to be triangulated to an empty graph

Implements gum::Triangulation.

Definition at line 154 of file staticTriangulation.cpp.

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

                                  {
    // clear the factories
    elimination_sequence_strategy_->clear();
    junction_tree_strategy_->clear();

    // remove the current graphs
    _original_graph_ = nullptr;
    _junction_tree_  = nullptr;
    _triangulated_graph_.clear();
    _elim_tree_.clear();
    _max_prime_junction_tree_.clear();
    _elim_cliques_.clear();
    _node_2_max_prime_clique_.clear();

    // remove all fill-ins and orderings
    _fill_ins_.clear();
    _added_fill_ins_.clear();
    _elim_order_.clear();
    _reverse_elim_order_.clear();

    // indicates that the junction tree, the max prime tree, etc, are updated
    _has_triangulation_           = true;
    _has_triangulated_graph_      = true;
    _has_elimination_tree_        = true;
    _has_junction_tree_           = true;
    _has_max_prime_junction_tree_ = true;
    _has_fill_ins_                = true;
  }

Here is the call graph for this function:

copyFactory()

PartialOrderedTriangulation * gum::PartialOrderedTriangulation::copyFactory ( ) const

finalvirtual

virtual copy constructor

Implements gum::StaticTriangulation.

Definition at line 87 of file partialOrderedTriangulation.cpp.

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

                                                                              {
    return new PartialOrderedTriangulation(*this);
  }

Here is the call graph for this function:

createdJunctionTreeClique()

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

virtualinherited

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

Implements gum::Triangulation.

createdJunctionTreeCliques()

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

virtualinherited

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

Implements gum::Triangulation.

createdMaxPrimeSubgraph()

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

virtualinherited

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::StaticTriangulation::eliminationOrder ( )

virtualinherited

returns an elimination ordering compatible with the triangulated graph

Implements gum::Triangulation.

eliminationOrder() [2/2]

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

virtualinherited

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

Implements gum::Triangulation.

eliminationSequenceStrategy()

EliminationSequenceStrategy& gum::StaticTriangulation::eliminationSequenceStrategy ( ) const

inherited

returns the elimination sequence strategy used by the triangulation

eliminationTree()

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

virtualinherited

returns the elimination tree of a compatible ordering

Implements gum::Triangulation.

fillIns()

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

virtualinherited

returns the fill-ins added by the triangulation algorithm

Implements gum::Triangulation.

Definition at line 653 of file staticTriangulation.cpp.

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

                                              {
    // if we did not compute the triangulation yet, do it and commpute
    // the fill-ins at the same time
    if (!_has_triangulation_) {
      bool want_fill_ins = _we_want_fill_ins_;
      _we_want_fill_ins_ = true;
      _triangulate_();
      _we_want_fill_ins_ = want_fill_ins;
      _has_fill_ins_     = true;
    }

    // here, we already computed a triangulation and we already computed
    // the fill-ins, so return them
    if (_has_fill_ins_) {
      if (elimination_sequence_strategy_->providesFillIns())
        return elimination_sequence_strategy_->fillIns();
      else
        return _fill_ins_;
    } else {
      // ok, here, we shall compute the fill-ins as they were not precomputed
      if (!_original_graph_) return _fill_ins_;

      // just in case, be sure that the junction tree has been constructed
      if (!_has_junction_tree_) junctionTree();

      for (const auto clik_id: _junction_tree_->nodes()) {
        // for each clique, add the edges necessary to make it complete
        const NodeSet&        clique = _junction_tree_->clique(clik_id);
        std::vector< NodeId > clique_nodes(clique.size());
        unsigned int          i = 0;

        for (const auto node: clique) {
          clique_nodes[i] = node;
          i += 1;
        }

        for (i = 0; i < clique_nodes.size(); ++i) {
          for (unsigned int j = i + 1; j < clique_nodes.size(); ++j) {
            Edge edge(clique_nodes[i], clique_nodes[j]);

            if (!_original_graph_->existsEdge(edge)) {
              try {
                _fill_ins_.insert(edge);
              } catch (DuplicateElement&) {}
            }
          }
        }
      }

      return _fill_ins_;
    }
  }

Here is the call graph for this function:

initTriangulation_()

void gum::PartialOrderedTriangulation::initTriangulation_ ( UndiGraph &  graph )

finalprotectedvirtual

the function called to initialize the triangulation process

This function is called when the triangulation process starts and is used to initialize the elimination sequence strategy. Actually, the graph that is modified by the triangulation algorithm is a copy of the original graph, and this copy need be known by the elimination sequence strategy. initTriangulation_ is used to transmit this knowledge to the elimination sequence (through method setGraph of the elimination sequence class).

Parameters

graph

the very graph that is triangulated (this is a copy of original_graph_)

Reimplemented from gum::StaticTriangulation.

Definition at line 113 of file partialOrderedTriangulation.cpp.

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

                                                                       {
    PartialOrderedEliminationSequenceStrategy* elim
       = static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_);
    elim->setGraph(&graph, domain_sizes_);
    elim->setPartialOrder(_partial_order_);
  }

Here is the call graph for this function:

isMinimalityRequired()

virtual bool gum::StaticTriangulation::isMinimalityRequired ( ) const

finalvirtualinherited

indicates wether minimality is required

junctionTree()

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

virtualinherited

returns a compatible junction tree

Implements gum::Triangulation.

junctionTreeStrategy()

JunctionTreeStrategy& gum::StaticTriangulation::junctionTreeStrategy ( ) const

inherited

returns the junction tree strategy used by the 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::StaticTriangulation::maxPrimeSubgraphTree ( )

virtualinherited

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.

Implements gum::Triangulation.

newFactory()

PartialOrderedTriangulation * gum::PartialOrderedTriangulation::newFactory ( ) const

virtual

returns a fresh triangulation (over an empty graph) of the same type as the current object

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

Implements gum::StaticTriangulation.

Definition at line 79 of file partialOrderedTriangulation.cpp.

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

                                                                             {
    return new PartialOrderedTriangulation(
       static_cast< const PartialOrderedEliminationSequenceStrategy& >(
          *elimination_sequence_strategy_),
       *junction_tree_strategy_);
  }

Here is the call graph for this function:

operator=()

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

private

forbid copy operator

originalGraph()

const UndiGraph* gum::StaticTriangulation::originalGraph ( ) const

inherited

returns the graph to be triangulated

Warning

if we have not set yet a graph, then originalGraph () will return a nullptr.

reverseEliminationOrder()

const NodeProperty< NodeId >& gum::StaticTriangulation::reverseEliminationOrder ( )

inherited

returns a table indicating, for each node, at which step it was deleted by the triangulation process

setFillIns()

void gum::StaticTriangulation::setFillIns ( bool  )

inherited

sets/unsets the record of the fill-ins in the standard triangulation procedure

setGraph()

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

finalvirtual

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
sequence	the order in which the nodes should be eliminated

Warning

note that, by aGrUM's rule, the graph and the domain sizes are not notcopied but only referenced by the triangulation algorithm.

Reimplemented from gum::StaticTriangulation.

Definition at line 98 of file partialOrderedTriangulation.cpp.

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

                                                                                   {
    StaticTriangulation::setGraph(graph, domsizes);
    static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_)
       ->setPartialOrder(_partial_order_);
  }

Here is the call graph for this function:

setMinimalRequirement()

void gum::StaticTriangulation::setMinimalRequirement ( bool  )

inherited

sets/unset the minimality requirement

setPartialOrder()

void gum::PartialOrderedTriangulation::setPartialOrder ( const List< NodeSet > *  partial_order )

finalvirtual

sets the elimination sequence's partial order (only a reference is stored)

sets the sequence of elimination

The elimination sequence is kept outside this class for efficiency reasons.

Definition at line 106 of file partialOrderedTriangulation.cpp.

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

                                                                                        {
    _partial_order_ = partial_order;
    static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_)
       ->setPartialOrder(_partial_order_);
  }

Here is the call graph for this function:

triangulatedGraph()

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

virtualinherited

returns the triangulated graph

Implements gum::Triangulation.

Definition at line 466 of file staticTriangulation.cpp.

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

                                                          {
    if (!_has_triangulation_) _triangulate_();

    // if we did not construct the triangulated graph during the triangulation,
    // that is, we just constructed the junction tree, we shall construct it now
    if (!_has_triangulated_graph_) {
      // just in case, be sure that the junction tree has been constructed
      if (!_has_junction_tree_) junctionTree();

      // copy the original graph
      _triangulated_graph_ = *_original_graph_;

      for (const auto clik_id: *_junction_tree_) {
        // for each clique, add the edges necessary to make it complete
        const NodeSet&        clique = _junction_tree_->clique(clik_id);
        std::vector< NodeId > clique_nodes(clique.size());
        unsigned int          i = 0;

        for (const auto node: clique) {
          clique_nodes[i] = node;
          i += 1;
        }

        for (i = 0; i < clique_nodes.size(); ++i) {
          for (unsigned int j = i + 1; j < clique_nodes.size(); ++j) {
            try {
              _triangulated_graph_.addEdge(clique_nodes[i], clique_nodes[j]);
            } catch (DuplicateElement&) {}
          }
        }
      }

      _has_triangulated_graph_ = true;
    }

    return _triangulated_graph_;
  }

Here is the call graph for this function:

Member Data Documentation

_partial_order_

const List< NodeSet >* gum::PartialOrderedTriangulation::_partial_order_ {nullptr}

protected

the partial ordering to apply to eliminate nodes

Definition at line 159 of file partialOrderedTriangulation.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.

elimination_sequence_strategy_

EliminationSequenceStrategy* gum::StaticTriangulation::elimination_sequence_strategy_ {nullptr}

protectedinherited

the elimination sequence strategy used by the triangulation

Definition at line 229 of file staticTriangulation.h.

junction_tree_strategy_

JunctionTreeStrategy* gum::StaticTriangulation::junction_tree_strategy_ {nullptr}

protectedinherited

the junction tree strategy used by the triangulation

Definition at line 232 of file staticTriangulation.h.

---

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

• agrum/tools/graphs/algorithms/triangulations/partialOrderedTriangulation.h
• agrum/tools/graphs/algorithms/triangulations/partialOrderedTriangulation.cpp