gum::StaticTriangulation Class Reference

base class for all non-incremental triangulation methods More...

#include <staticTriangulation.h>

Inheritance diagram for gum::StaticTriangulation:

Collaboration diagram for gum::StaticTriangulation:

Public Member Functions
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
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...

Constructors / Destructors
virtual StaticTriangulation *	newFactory () const =0
	returns a fresh triangulation of the same type as the current object but over an empty graph More...
virtual StaticTriangulation *	copyFactory () const =0
	virtual copy constructor More...
virtual	~StaticTriangulation ()
	destructor More...
	StaticTriangulation (const EliminationSequenceStrategy &elimSeq, const JunctionTreeStrategy &JTStrategy, bool minimality=false)
	default constructor: without any graph More...
	StaticTriangulation (const UndiGraph *graph, const NodeProperty< Size > *dom_sizes, const EliminationSequenceStrategy &elimSeq, const JunctionTreeStrategy &JTStrategy, bool minimality=false)
	constructor with a given graph More...
	StaticTriangulation (const StaticTriangulation &)
	forbid copy constructor except in newfactory More...
	StaticTriangulation (StaticTriangulation &&)
	forbid move constructor except in children's constructors More...

Accessors / Modifiers
virtual void	setGraph (const UndiGraph *graph, const NodeProperty< Size > *domsizes)
	initialize the triangulation data structures for a new graph 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 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...
virtual void	_initTriangulation (UndiGraph &graph)
	the function called to initialize the triangulation process More...

Detailed Description

base class for all non-incremental triangulation methods

Definition at line 47 of file staticTriangulation.h.

Constructor & Destructor Documentation

~StaticTriangulation()

gum::StaticTriangulation::~StaticTriangulation ( )

virtual

destructor

Definition at line 150 of file staticTriangulation.cpp.

References _elimination_sequence_strategy, and _junction_tree_strategy.

                                            {
    // for debugging purposes
    GUM_DESTRUCTOR(StaticTriangulation);

    delete _elimination_sequence_strategy;
    delete _junction_tree_strategy;

    // no need to deallocate __original_graph nor __junction_tree because
    // they are not owned by the static triangulation class
  }

StaticTriangulation() [1/4]

gum::StaticTriangulation::StaticTriangulation ( const EliminationSequenceStrategy &  elimSeq, const JunctionTreeStrategy &  JTStrategy, bool  minimality = false  )

protected

default constructor: without any graph

Parameters

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

Definition at line 66 of file staticTriangulation.cpp.

References _junction_tree_strategy, and gum::JunctionTreeStrategy::setTriangulation().

                                                    :
      _elimination_sequence_strategy(elimSeq.newFactory()),
      _junction_tree_strategy(JTStrategy.newFactory()),
      __minimality_required(minimality) {
    // for debugging purposes
    GUM_CONSTRUCTOR(StaticTriangulation);

    // register the triangulation to its junction tree strategy
    _junction_tree_strategy->setTriangulation(this);
  }

Here is the call graph for this function:

StaticTriangulation() [2/4]

gum::StaticTriangulation::StaticTriangulation ( const UndiGraph *  graph, const NodeProperty< Size > *  dom_sizes, const EliminationSequenceStrategy &  elimSeq, const JunctionTreeStrategy &  JTStrategy, bool  minimality = false  )

protected

constructor with a given graph

Parameters

graph	the graph to be triangulated, i.e., the nodes of which will be eliminated
dom_sizes	the domain sizes of the nodes to be eliminated
elimSeq	the elimination sequence used to triangulate the graph
JTStrategy	the junction tree strategy used to create junction trees

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

Parameters

minimality

a Boolean indicating whether we should enforce that the triangulation is minimal w.r.t. inclusion

Warning

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

Definition at line 38 of file staticTriangulation.cpp.

References __added_fill_ins, __elim_cliques, __elim_order, __node_2_max_prime_clique, __reverse_elim_order, _junction_tree_strategy, gum::JunctionTreeStrategy::setTriangulation(), and gum::NodeGraphPart::size().

                                                    :
      Triangulation(domsizes),
      _elimination_sequence_strategy(elimSeq.newFactory()),
      _junction_tree_strategy(JTStrategy.newFactory()), __original_graph(theGraph),
      __minimality_required(minimality) {
    // for debugging purposes
    GUM_CONSTRUCTOR(StaticTriangulation);

    // if the graph is not empty, resize several structures in order to speed-up
    // their fillings.
    if (theGraph != nullptr) {
      __elim_order.resize(theGraph->size());
      __reverse_elim_order.resize(theGraph->size());
      __elim_cliques.resize(theGraph->size());
      __node_2_max_prime_clique.resize(theGraph->size());
      __added_fill_ins.resize(theGraph->size());
    }

    // register the triangulation to its junction tree strategy
    _junction_tree_strategy->setTriangulation(this);
  }

Here is the call graph for this function:

StaticTriangulation() [3/4]

gum::StaticTriangulation::StaticTriangulation ( const StaticTriangulation &  from )

protected

forbid copy constructor except in newfactory

Definition at line 81 of file staticTriangulation.cpp.

References __junction_tree, _elimination_sequence_strategy, _junction_tree_strategy, gum::JunctionTreeStrategy::copyFactory(), gum::EliminationSequenceStrategy::copyFactory(), and gum::JunctionTreeStrategy::junctionTree().

                                                                          :
      Triangulation(from), __original_graph(from.__original_graph),
      __triangulated_graph(from.__triangulated_graph), __fill_ins(from.__fill_ins),
      __elim_order(from.__elim_order),
      __reverse_elim_order(from.__reverse_elim_order),
      __elim_cliques(from.__elim_cliques), __elim_tree(from.__elim_tree),
      __max_prime_junction_tree(from.__max_prime_junction_tree),
      __node_2_max_prime_clique(from.__node_2_max_prime_clique),
      __has_triangulation(from.__has_triangulation),
      __has_triangulated_graph(from.__has_triangulated_graph),
      __has_elimination_tree(from.__has_elimination_tree),
      __has_junction_tree(from.__has_junction_tree),
      __has_max_prime_junction_tree(from.__has_max_prime_junction_tree),
      __has_fill_ins(from.__has_fill_ins),
      __minimality_required(from.__minimality_required),
      __added_fill_ins(from.__added_fill_ins),
      __we_want_fill_ins(from.__we_want_fill_ins) {
    // copy the strategies
    _elimination_sequence_strategy =
       from._elimination_sequence_strategy->copyFactory();
    _junction_tree_strategy = from._junction_tree_strategy->copyFactory(this);

    // if from has a junction tree, copy it
    if (from.__junction_tree != nullptr) {
      __junction_tree = &(_junction_tree_strategy->junctionTree());
    }

    // for debugging purposes
    GUM_CONS_CPY(StaticTriangulation);
  }

Here is the call graph for this function:

StaticTriangulation() [4/4]

gum::StaticTriangulation::StaticTriangulation ( StaticTriangulation &&  from )

protected

forbid move constructor except in children's constructors

Definition at line 113 of file staticTriangulation.cpp.

References __junction_tree, _junction_tree_strategy, gum::JunctionTreeStrategy::junctionTree(), and gum::JunctionTreeStrategy::moveTriangulation().

                                                                     :
      Triangulation(std::move(from)),
      _elimination_sequence_strategy(from._elimination_sequence_strategy),
      _junction_tree_strategy(from._junction_tree_strategy),
      __original_graph(from.__original_graph),
      __triangulated_graph(std::move(from.__triangulated_graph)),
      __fill_ins(std::move(from.__fill_ins)),
      __elim_order(std::move(from.__elim_order)),
      __reverse_elim_order(std::move(from.__reverse_elim_order)),
      __elim_cliques(std::move(from.__elim_cliques)),
      __elim_tree(std::move(from.__elim_tree)),
      __max_prime_junction_tree(std::move(from.__max_prime_junction_tree)),
      __node_2_max_prime_clique(std::move(from.__node_2_max_prime_clique)),
      __has_triangulation(from.__has_triangulation),
      __has_triangulated_graph(from.__has_triangulated_graph),
      __has_elimination_tree(from.__has_elimination_tree),
      __has_junction_tree(from.__has_junction_tree),
      __has_max_prime_junction_tree(from.__has_max_prime_junction_tree),
      __has_fill_ins(from.__has_fill_ins),
      __minimality_required(from.__minimality_required),
      __added_fill_ins(std::move(from.__added_fill_ins)),
      __we_want_fill_ins(from.__we_want_fill_ins) {
    // move the factories contained in from
    from._elimination_sequence_strategy = new DefaultEliminationSequenceStrategy;
    from._junction_tree_strategy = new DefaultJunctionTreeStrategy;
    _junction_tree_strategy->moveTriangulation(this);

    // if from has a junction tree, copy it
    if (from.__junction_tree != nullptr) {
      __junction_tree = &(_junction_tree_strategy->junctionTree());
    }

    // for debugging purposes
    GUM_CONS_MOV(StaticTriangulation);
  }

Here is the call graph for this function:

Member Function Documentation

__computeEliminationTree()

void gum::StaticTriangulation::__computeEliminationTree ( )

private

returns an elimination tree from a triangulated graph

Definition at line 334 of file staticTriangulation.cpp.

References __elim_cliques, __elim_order, __elim_tree, __has_elimination_tree, __has_triangulation, __original_graph, __reverse_elim_order, __triangulate(), gum::CliqueGraph::addEdge(), gum::CliqueGraph::addNode(), gum::NodeGraphPart::bound(), and gum::CliqueGraph::clear().

                                                     {
    // if there already exists an elimination tree, no need to compute it again
    if (__has_elimination_tree) return;

    // if the graph is not triangulated, triangulate it
    if (!__has_triangulation) __triangulate();

    // create the nodes of the elimination tree
    __elim_tree.clear();

    Size size = Size(__elim_order.size());
    for (NodeId i = NodeId(0); i < size; ++i)
      __elim_tree.addNode(i, __elim_cliques[__elim_order[i]]);

    // create the edges of the elimination tree: join a node to the one in
    // its clique that is eliminated first
    for (NodeId i = NodeId(0); i < size; ++i) {
      NodeId         clique_i_creator = __elim_order[i];
      const NodeSet& list_of_nodes = __elim_cliques[clique_i_creator];
      Idx            child = __original_graph->bound() + 1;

      for (const auto node : list_of_nodes) {
        Idx it_elim_step = __reverse_elim_order[node];

        if ((node != clique_i_creator) && (child > it_elim_step))
          child = it_elim_step;
      }

      if (child <= __original_graph->bound()) {
        // WARNING: here, we assume that the nodes of the elimination tree are
        // indexed from 0 to n-1
        __elim_tree.addEdge(i, child);
      }
    }

    __has_elimination_tree = true;
  }

Here is the call graph for this function:

__computeMaxPrimeJunctionTree()

void gum::StaticTriangulation::__computeMaxPrimeJunctionTree ( )

private

computes the junction tree of the maximal prime subgraphs

Definition at line 407 of file staticTriangulation.cpp.

References __computeMaxPrimeMergings(), __has_junction_tree, __has_max_prime_junction_tree, __junction_tree, __max_prime_junction_tree, __node_2_max_prime_clique, _junction_tree_strategy, gum::CliqueGraph::addEdge(), gum::CliqueGraph::addNode(), gum::CliqueGraph::addToClique(), gum::CliqueGraph::clique(), gum::Set< Key, Alloc >::contains(), gum::JunctionTreeStrategy::createdCliques(), gum::EdgeGraphPart::edges(), gum::HashTable< Key, Val, Alloc >::insert(), junctionTree(), gum::NodeGraphPart::nodes(), and gum::NodeGraphPart::size().

                                                          {
    // if there already exists a max prime junction tree, no need
    // to recompute it
    if (__has_max_prime_junction_tree) return;

    // if there is no junction tree, create it
    if (!__has_junction_tree) junctionTree();

    // the maximal prime subgraph join tree is created by aggregation of some
    // cliques. More precisely, when the separator between 2 cliques is not
    // complete in the original graph, then the two cliques must be merged.
    // Create a hashtable indicating which clique has been absorbed by some
    // other
    // clique.
    NodeProperty< NodeId > T_mpd_cliques(__junction_tree->size());

    for (const auto clik : __junction_tree->nodes())
      T_mpd_cliques.insert(clik, clik);

    // parse all the separators of the junction tree and test those that are not
    // complete in the orginal graph
    std::vector< Arc > merged_cliques;

    NodeSet mark;

    for (const auto clik : __junction_tree->nodes())
      if (!mark.contains(clik))
        __computeMaxPrimeMergings(clik, clik, merged_cliques, mark);

    // compute the transitive closure of merged_cliques. This one will contain
    // pairs (X,Y) indicating that clique X must be merged with clique Y.
    // Actually clique X will be inserted into clique Y.
    for (unsigned int i = 0; i < merged_cliques.size(); ++i) {
      T_mpd_cliques[merged_cliques[i].tail()] =
         T_mpd_cliques[merged_cliques[i].head()];
    }

    // now we can create the max prime junction tree. First, create the cliques
    for (const auto& elt : T_mpd_cliques)
      if (elt.first == elt.second)
        __max_prime_junction_tree.addNode(elt.second,
                                          __junction_tree->clique(elt.second));

    // add to the cliques previously created the nodes of the cliques that were
    // merged into them
    for (const auto& elt : T_mpd_cliques)
      if (elt.first != elt.second)
        for (const auto node : __junction_tree->clique(elt.first)) {
          try {
            __max_prime_junction_tree.addToClique(elt.second, node);
          } catch (DuplicateElement&) {}
        }

    // add the edges to the graph
    for (const auto& edge : __junction_tree->edges()) {
      NodeId node1 = T_mpd_cliques[edge.first()];
      NodeId node2 = T_mpd_cliques[edge.second()];

      if (node1 != node2) {
        try {
          __max_prime_junction_tree.addEdge(node1, node2);
        } catch (DuplicateElement&) {}
      }
    }

    // compute for each node which clique of the max prime junction tree was
    // created by the elimination of the node
    const NodeProperty< NodeId >& node_2_junction_clique =
       _junction_tree_strategy->createdCliques();

    for (const auto& elt : node_2_junction_clique)
      __node_2_max_prime_clique.insert(elt.first, T_mpd_cliques[elt.second]);

    __has_max_prime_junction_tree = true;
  }

Here is the call graph for this function:

__computeMaxPrimeMergings()

void gum::StaticTriangulation::__computeMaxPrimeMergings ( const NodeId  node, const NodeId  from, std::vector< Arc > &  merged_cliques, NodeSet &  mark  ) const

private

used for computing the junction tree of the maximal prime subgraphs

Definition at line 373 of file staticTriangulation.cpp.

References __junction_tree, __original_graph, gum::Set< Key, Alloc >::begin(), gum::Set< Key, Alloc >::end(), gum::EdgeGraphPart::existsEdge(), gum::EdgeGraphPart::neighbours(), and gum::CliqueGraph::separator().

Referenced by __computeMaxPrimeJunctionTree().

                                     {
    mark << node;

    for (const auto other_node : __junction_tree->neighbours(node))
      if (other_node != from) {
        const NodeSet& separator = __junction_tree->separator(node, other_node);
        // check that the separator between node and other_node is complete
        bool complete = true;

        for (auto iter_sep1 = separator.begin();
             iter_sep1 != separator.end() && complete;
             ++iter_sep1) {
          auto iter_sep2 = iter_sep1;

          for (++iter_sep2; iter_sep2 != separator.end(); ++iter_sep2) {
            if (!__original_graph->existsEdge(*iter_sep1, *iter_sep2)) {
              complete = false;
              break;
            }
          }
        }

        // here complete indicates whether the separator is complete or not
        if (!complete) merged_cliques.push_back(Arc(other_node, node));

        __computeMaxPrimeMergings(other_node, node, merged_cliques, mark);
      }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

__computeRecursiveThinning()

void gum::StaticTriangulation::__computeRecursiveThinning ( )

private

removes redondant fill-ins and compute proper elimination cliques and order

Definition at line 192 of file staticTriangulation.cpp.

References __added_fill_ins, __elim_cliques, __elim_order, __fill_ins, __has_fill_ins, __reverse_elim_order, __triangulated_graph, gum::Set< Key, Alloc >::erase(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::insert(), gum::Set< Key, Alloc >::insert(), gum::HashTable< Key, Val, Alloc >::insert(), and gum::NodeGraphPart::size().

Referenced by __triangulate().

                                                       {
    // apply recursive thinning (fmint, see Kjaerulff (90), "triangulation of
    // graphs - algorithms giving small total state space")
    NodeId                       node1, node2;
    bool                         incomplete;
    std::vector< NodeId >        adj;
    EdgeSet                      T_prime;
    NodeProperty< unsigned int > R(__triangulated_graph.size());

    for (const auto node : __triangulated_graph)
      R.insert(node, 0);

    // the FMINT loop
    if (__added_fill_ins.size() > 0) {
      for (auto iter = __added_fill_ins.rbegin(); iter != __added_fill_ins.rend();
           ++iter) {
        if (iter->size()) {
          // here apply MINT to T_i = __added_fill_ins[i]
          EdgeSet& T = *iter;

          // compute R: by default, R is equal to all the nodes in the graph
          // when R[...] >= j (see the j in the loop below), this means that the
          // node belongs to an extremal edge in R
          for (std::size_t k = 0; k < __elim_order.size(); ++k)
            R[__elim_order[k]] =
               0;   // WARNING: do not replace R[__elim_order[k]] by

          // R[k] because the node ids may not be
          // consecutive numbers

          // apply MINT while some edges can possibly be deleted
          bool require_mint = true;

          for (unsigned int j = 0; require_mint; ++j) {
            // find T' (it is equal to the edges (v,w) of T such that
            // the intersection of adj(v,G) and adj(w,G) is complete and such
            // that
            // v and/or w belongs to an extremal node in R
            for (const auto& edge : T) {
              node1 = edge.first();
              node2 = edge.second();

              // check if at least one extremal node belongs to R
              if ((R[node1] < j) && (R[node2] < j)) continue;

              // check if the intersection of adj(v,G) and adj(w,G) is a
              // complete subgraph
              if (__triangulated_graph.neighbours(node2).size()
                  < __triangulated_graph.neighbours(node1).size()) {
                NodeId tmp = node1;
                node1 = node2;
                node2 = tmp;
              }

              incomplete = false;

              // find the nodes belonging to the intersection of adj(v,G)
              // and adj(w,G)
              for (const auto adjnode : __triangulated_graph.neighbours(node1))
                if (__triangulated_graph.existsEdge(node2, adjnode))
                  adj.push_back(adjnode);

              // check if the intersection is complete
              for (unsigned int k = 0; k < adj.size() && !incomplete; ++k) {
                for (unsigned int m = k + 1; m < adj.size(); ++m) {
                  if (!__triangulated_graph.existsEdge(adj[k], adj[m])) {
                    incomplete = true;
                    break;
                  }
                }
              }

              adj.clear();

              if (!incomplete) {
                T_prime.insert(edge);
                R[node1] = j + 1;
                R[node2] = j + 1;
              }
            }

            // compute the new value of T (i.e. T\T') and update the
            // triangulated graph
            for (const auto& edge : T_prime) {
              T.erase(edge);
              __triangulated_graph.eraseEdge(edge);

              if (__has_fill_ins) __fill_ins.erase(edge);
            }

            if (T_prime.size() == 0) require_mint = false;

            T_prime.clear();
          }
        }
      }
    }

    // here, the recursive thinning has removed all the superfluous edges.
    // Hence some cliques have been split and, as a result, the elimination
    // order has changed. We should thus compute a new perfect ordering. To
    // do so, we use a Maximal Cardinality Search: it has indeed the nice
    // property that, when the graph is already triangulated, it finds a
    // compatible order of elimination that does not require any edge addition

    // a structure storing the number of neighbours previously processed
    PriorityQueue< NodeId, unsigned int, std::greater< unsigned int > >
       numbered_neighbours(std::greater< unsigned int >(),
                           __triangulated_graph.size());

    for (Size i = 0; i < __elim_order.size(); ++i)
      numbered_neighbours.insert(__elim_order[i], 0);

    // perform the maximum cardinality search
    if (__elim_order.size() > 0) {
      for (Size i = Size(__elim_order.size()); i >= 1; --i) {
        NodeId ni = NodeId(i - 1);
        NodeId node = numbered_neighbours.pop();
        __elim_order[ni] = node;
        __reverse_elim_order[node] = ni;

        for (const auto neighbour : __triangulated_graph.neighbours(node)) {
          try {
            numbered_neighbours.setPriority(
               neighbour, 1 + numbered_neighbours.priority(neighbour));
          } catch (NotFound&) {}
        }
      }
    }

    // here the elimination order is ok. We now need to update the
    // __elim_cliques
    for (Size i = 0; i < __elim_order.size(); ++i) {
      NodeSet& cliques = __elim_cliques.insert(__elim_order[i], NodeSet()).second;
      cliques << __elim_order[i];

      for (const auto neighbour : __triangulated_graph.neighbours(__elim_order[i]))
        if (__reverse_elim_order[neighbour] > i) cliques << neighbour;
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

__triangulate()

void gum::StaticTriangulation::__triangulate ( )

private

the function that performs the triangulation

Definition at line 551 of file staticTriangulation.cpp.

References __added_fill_ins, __computeRecursiveThinning(), __elim_cliques, __elim_order, __fill_ins, __has_fill_ins, __has_triangulated_graph, __has_triangulation, __minimality_required, __original_graph, __reverse_elim_order, __triangulated_graph, __we_want_fill_ins, _elimination_sequence_strategy, _initTriangulation(), gum::UndiGraph::addEdge(), gum::EliminationSequenceStrategy::askFillIns(), gum::Set< Key, Alloc >::begin(), gum::EliminationSequenceStrategy::eliminationUpdate(), gum::Set< Key, Alloc >::end(), gum::UndiGraph::eraseNode(), gum::EdgeGraphPart::existsEdge(), gum::Set< Key, Alloc >::insert(), gum::EdgeGraphPart::neighbours(), gum::EliminationSequenceStrategy::nextNodeToEliminate(), gum::EliminationSequenceStrategy::providesFillIns(), gum::EliminationSequenceStrategy::providesGraphUpdate(), gum::Set< Key, Alloc >::resize(), gum::NodeGraphPart::size(), and gum::Set< Key, Alloc >::size().

Referenced by __computeEliminationTree(), fillIns(), and triangulatedGraph().

                                          {
    // if the graph is already triangulated, no need to triangulate it again
    if (__has_triangulation) return;

    // copy the graph to be triangulated, so that we can modify it
    UndiGraph tmp_graph = *__original_graph;

    _initTriangulation(tmp_graph);
    _elimination_sequence_strategy->askFillIns(__we_want_fill_ins);

    // if we are to do recursive thinning, we will have to add fill-ins to the
    // triangulated graph each time we eliminate a node. Hence, we shall
    // initialize the triangulated graph by a copy of the original graph
    if (__minimality_required) {
      __triangulated_graph = *__original_graph;
      __has_triangulated_graph = true;
    }

    // perform the triangulation
    NodeId removable_node = 0;

    for (unsigned int nb_elim = 0; tmp_graph.size() != 0; ++nb_elim) {
      removable_node = _elimination_sequence_strategy->nextNodeToEliminate();

      // when minimality is not required, i.e., we won't apply recursive
      // thinning, the cliques sets can be computed
      if (!__minimality_required) {
        NodeSet& cliques = __elim_cliques.insert(removable_node, NodeSet()).second;
        cliques.resize(tmp_graph.neighbours(removable_node).size() / 2);
        cliques << removable_node;
        for (const auto clik : tmp_graph.neighbours(removable_node))
          cliques << clik;
      } else {
        // here recursive thinning will be applied, hence we need store the
        // fill-ins added by the current node removal
        EdgeSet& current_fill = __added_fill_ins[nb_elim];
        NodeId   node1, node2;

        const NodeSet& nei = tmp_graph.neighbours(removable_node);

        for (auto iter_edges1 = nei.begin(); iter_edges1 != nei.end();
             ++iter_edges1) {
          node1 = *iter_edges1;
          auto iter_edges2 = iter_edges1;

          for (++iter_edges2; iter_edges2 != nei.end(); ++iter_edges2) {
            node2 = *iter_edges2;
            Edge edge(node1, node2);

            if (!tmp_graph.existsEdge(edge)) {
              current_fill.insert(edge);
              __triangulated_graph.addEdge(node1, node2);
            }
          }
        }
      }

      // if we want fill-ins but the elimination sequence strategy does not
      // compute them, we shall compute them here
      if (__we_want_fill_ins
          && !_elimination_sequence_strategy->providesFillIns()) {
        NodeId node1, node2;

        // add edges between removable_node's neighbours in order to create
        // a clique
        const NodeSet& nei = tmp_graph.neighbours(removable_node);

        for (auto iter_edges1 = nei.begin(); iter_edges1 != nei.end();
             ++iter_edges1) {
          node1 = *iter_edges1;
          auto iter_edges2 = iter_edges1;

          for (++iter_edges2; iter_edges2 != nei.end(); ++iter_edges2) {
            node2 = *iter_edges2;
            Edge edge(node1, node2);

            if (!tmp_graph.existsEdge(edge)) { __fill_ins.insert(edge); }
          }
        }

        // delete removable_node and its adjacent edges
        tmp_graph.eraseNode(removable_node);
      }

      // inform the elimination sequence that we are actually removing
      // removable_node (this enables, for instance, to update the weights of
      // the nodes in the graph)
      _elimination_sequence_strategy->eliminationUpdate(removable_node);

      if (!_elimination_sequence_strategy->providesGraphUpdate()) {
        NodeId node1, node2;

        const NodeSet& nei = tmp_graph.neighbours(removable_node);

        for (auto iter_edges1 = nei.begin(); iter_edges1 != nei.end();
             ++iter_edges1) {
          node1 = *iter_edges1;
          auto iter_edges2 = iter_edges1;

          for (++iter_edges2; iter_edges2 != nei.end(); ++iter_edges2) {
            node2 = *iter_edges2;
            Edge edge(node1, node2);

            if (!tmp_graph.existsEdge(edge)) { tmp_graph.addEdge(node1, node2); }
          }
        }

        tmp_graph.eraseNode(removable_node);
      }

      // update the elimination order
      __elim_order[nb_elim] = removable_node;
      __reverse_elim_order.insert(removable_node, nb_elim);
    }

    // indicate whether we actually computed fill-ins
    __has_fill_ins = __we_want_fill_ins;

    // if minimality is required, remove the redondant edges
    if (__minimality_required) __computeRecursiveThinning();

    __has_triangulation = true;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

_initTriangulation()

void gum::StaticTriangulation::_initTriangulation ( UndiGraph &  graph )

protectedvirtual

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 needs 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 in gum::PartialOrderedTriangulation, and gum::OrderedTriangulation.

Definition at line 730 of file staticTriangulation.cpp.

References gum::Triangulation::_domain_sizes, _elimination_sequence_strategy, and gum::EliminationSequenceStrategy::setGraph().

Referenced by __triangulate().

                                                               {
    _elimination_sequence_strategy->setGraph(&graph, _domain_sizes);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

clear()

void gum::StaticTriangulation::clear ( )

virtual

reinitialize the graph to be triangulated to an empty graph

Implements gum::Triangulation.

Definition at line 162 of file staticTriangulation.cpp.

References __added_fill_ins, __elim_cliques, __elim_order, __elim_tree, __fill_ins, __has_elimination_tree, __has_fill_ins, __has_junction_tree, __has_max_prime_junction_tree, __has_triangulated_graph, __has_triangulation, __junction_tree, __max_prime_junction_tree, __node_2_max_prime_clique, __original_graph, __reverse_elim_order, __triangulated_graph, _elimination_sequence_strategy, _junction_tree_strategy, gum::JunctionTreeStrategy::clear(), gum::CliqueGraph::clear(), gum::EliminationSequenceStrategy::clear(), gum::UndiGraph::clear(), and gum::Set< Key, Alloc >::clear().

Referenced by setGraph().

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

Here is the caller graph for this function:

copyFactory()

virtual StaticTriangulation* gum::StaticTriangulation::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++.

Implements gum::Triangulation.

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

createdJunctionTreeClique()

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

virtual

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

virtual

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 )

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

virtual

returns an elimination ordering compatible with the triangulated graph

Implements gum::Triangulation.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::__buildReduceGraph(), gum::DefaultJunctionTreeStrategy::__computeJunctionTree(), gum::prm::SVED< GUM_SCALAR >::__eliminateNodes(), gum::prm::SVE< GUM_SCALAR >::__eliminateNodes(), gum::prm::SVED< GUM_SCALAR >::__eliminateNodesWithEvidence(), gum::prm::SVE< GUM_SCALAR >::__eliminateNodesWithEvidence(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::__elimination_cost(), gum::prm::SVE< GUM_SCALAR >::__initLiftedNodes(), gum::prm::StructuredInference< GUM_SCALAR >::__reduceAloneInstances(), and gum::prm::StructuredInference< GUM_SCALAR >::__reducePattern().

Here is the caller graph for this function:

eliminationOrder() [2/2]

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

virtual

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

Implements gum::Triangulation.

eliminationSequenceStrategy()

EliminationSequenceStrategy& gum::StaticTriangulation::eliminationSequenceStrategy

(

)

const

returns the elimination sequence strategy used by the triangulation

eliminationTree()

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

virtual

returns the elimination tree of a compatible ordering

Implements gum::Triangulation.

Referenced by gum::DefaultJunctionTreeStrategy::__computeJunctionTree().

Here is the caller graph for this function:

fillIns()

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

virtual

returns the fill-ins added by the triangulation algorithm

Implements gum::Triangulation.

Definition at line 676 of file staticTriangulation.cpp.

References __fill_ins, __has_fill_ins, __has_junction_tree, __has_triangulation, __junction_tree, __original_graph, __triangulate(), __we_want_fill_ins, _elimination_sequence_strategy, gum::CliqueGraph::clique(), gum::EdgeGraphPart::existsEdge(), gum::EliminationSequenceStrategy::fillIns(), gum::Set< Key, Alloc >::insert(), junctionTree(), gum::NodeGraphPart::nodes(), gum::EliminationSequenceStrategy::providesFillIns(), and gum::Set< Key, Alloc >::size().

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

isMinimalityRequired()

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

finalvirtual

indicates wether minimality is required

junctionTree()

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

virtual

returns a compatible junction tree

Implements gum::Triangulation.

Referenced by __computeMaxPrimeJunctionTree(), fillIns(), and triangulatedGraph().

Here is the caller graph for this function:

junctionTreeStrategy()

JunctionTreeStrategy& gum::StaticTriangulation::junctionTreeStrategy

(

)

const

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

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.

Implements gum::Triangulation.

newFactory()

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

pure virtual

returns a fresh triangulation of the same type as the current object but over 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++.

Implements gum::Triangulation.

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

operator=()

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

private

forbid copy operator

originalGraph()

const UndiGraph* gum::StaticTriangulation::originalGraph

(

)

const

returns the graph to be triangulated

Warning

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

Referenced by gum::DefaultJunctionTreeStrategy::copyFactory().

Here is the caller graph for this function:

reverseEliminationOrder()

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

(

)

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

setFillIns()

void gum::StaticTriangulation::setFillIns

(

bool

)

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

setGraph()

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

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.

Implements gum::Triangulation.

Reimplemented in gum::PartialOrderedTriangulation, and gum::OrderedTriangulation.

Definition at line 523 of file staticTriangulation.cpp.

References __added_fill_ins, __elim_cliques, __elim_order, __has_elimination_tree, __has_fill_ins, __has_junction_tree, __has_max_prime_junction_tree, __has_triangulated_graph, __has_triangulation, __node_2_max_prime_clique, __original_graph, __reverse_elim_order, gum::Triangulation::_domain_sizes, clear(), and gum::NodeGraphPart::size().

Referenced by gum::OrderedTriangulation::setGraph(), and gum::PartialOrderedTriangulation::setGraph().

                                                                           {
    // remove the old graph
    clear();

    if (graph != nullptr) {
      // prepare the size of the data for the new graph
      __elim_order.resize(graph->size());
      __reverse_elim_order.resize(graph->size());
      __elim_cliques.resize(graph->size());
      __added_fill_ins.resize(graph->size());
      __node_2_max_prime_clique.resize(graph->size());
    }

    // keep track of the variables passed in argument
    __original_graph = graph;
    _domain_sizes = domsizes;

    // indicate that no triangulation was performed for this graph
    __has_triangulation = false;
    __has_triangulated_graph = false;
    __has_elimination_tree = false;
    __has_junction_tree = false;
    __has_max_prime_junction_tree = false;
    __has_fill_ins = false;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

setMinimalRequirement()

void gum::StaticTriangulation::setMinimalRequirement

(

bool

)

sets/unset the minimality requirement

triangulatedGraph()

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

virtual

returns the triangulated graph

Implements gum::Triangulation.

Definition at line 484 of file staticTriangulation.cpp.

References __has_junction_tree, __has_triangulated_graph, __has_triangulation, __junction_tree, __original_graph, __triangulate(), __triangulated_graph, gum::UndiGraph::addEdge(), junctionTree(), and gum::Set< Key, Alloc >::size().

                                                          {
    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

__added_fill_ins

std::vector< EdgeSet > gum::StaticTriangulation::__added_fill_ins

private

a vector containing the set of fill-ins added after each node elimination (used by recursive thinning)

Definition at line 293 of file staticTriangulation.h.

Referenced by __computeRecursiveThinning(), __triangulate(), clear(), setGraph(), and StaticTriangulation().

__elim_cliques

NodeProperty< NodeSet > gum::StaticTriangulation::__elim_cliques

private

the cliques formed by the elimination of the nodes

Definition at line 251 of file staticTriangulation.h.

Referenced by __computeEliminationTree(), __computeRecursiveThinning(), __triangulate(), clear(), setGraph(), and StaticTriangulation().

__elim_order

std::vector< NodeId > gum::StaticTriangulation::__elim_order

private

the order in which nodes are eliminated by the algorithm

Definition at line 245 of file staticTriangulation.h.

Referenced by __computeEliminationTree(), __computeRecursiveThinning(), __triangulate(), clear(), setGraph(), and StaticTriangulation().

__elim_tree

CliqueGraph gum::StaticTriangulation::__elim_tree

private

the elimination tree computed by the algorithm

Definition at line 254 of file staticTriangulation.h.

Referenced by __computeEliminationTree(), and clear().

__fill_ins

EdgeSet gum::StaticTriangulation::__fill_ins

private

the fill-ins added during the whole triangulation process

Definition at line 242 of file staticTriangulation.h.

Referenced by __computeRecursiveThinning(), __triangulate(), clear(), and fillIns().

__has_elimination_tree

bool gum::StaticTriangulation::__has_elimination_tree {false}

private

a boolean indicating whether the elimination tree has been computed

Definition at line 276 of file staticTriangulation.h.

Referenced by __computeEliminationTree(), clear(), and setGraph().

__has_fill_ins

bool gum::StaticTriangulation::__has_fill_ins {false}

private

indicates whether we actually computed fill-ins

Definition at line 286 of file staticTriangulation.h.

Referenced by __computeRecursiveThinning(), __triangulate(), clear(), fillIns(), and setGraph().

__has_junction_tree

bool gum::StaticTriangulation::__has_junction_tree {false}

private

a boolean indicating whether the junction tree has been constructed

Definition at line 279 of file staticTriangulation.h.

Referenced by __computeMaxPrimeJunctionTree(), clear(), fillIns(), setGraph(), and triangulatedGraph().

__has_max_prime_junction_tree

bool gum::StaticTriangulation::__has_max_prime_junction_tree {false}

private

indicates whether a maximal prime subgraph junction tree has been constructed

Definition at line 283 of file staticTriangulation.h.

Referenced by __computeMaxPrimeJunctionTree(), clear(), and setGraph().

__has_triangulated_graph

bool gum::StaticTriangulation::__has_triangulated_graph {false}

private

a boolean indicating whether we have constructed the triangulated graph

Definition at line 273 of file staticTriangulation.h.

Referenced by __triangulate(), clear(), setGraph(), and triangulatedGraph().

__has_triangulation

bool gum::StaticTriangulation::__has_triangulation {false}

private

a boolean indicating whether we have parformed a triangulation

Definition at line 270 of file staticTriangulation.h.

Referenced by __computeEliminationTree(), __triangulate(), clear(), fillIns(), setGraph(), and triangulatedGraph().

__junction_tree

const CliqueGraph* gum::StaticTriangulation::__junction_tree {nullptr}

private

the junction tree computed by the algorithm

note that the junction tree is owned by the junctionTreeStrategy and, therefore, its deletion from memory is not handled by the static triangulation class.

Definition at line 260 of file staticTriangulation.h.

Referenced by __computeMaxPrimeJunctionTree(), __computeMaxPrimeMergings(), clear(), fillIns(), StaticTriangulation(), and triangulatedGraph().

__max_prime_junction_tree

CliqueGraph gum::StaticTriangulation::__max_prime_junction_tree

private

the maximal prime subgraph junction tree computed from the junction tree

Definition at line 263 of file staticTriangulation.h.

Referenced by __computeMaxPrimeJunctionTree(), and clear().

__minimality_required

bool gum::StaticTriangulation::__minimality_required {false}

private

indicates whether the triangulation must be minimal

Definition at line 289 of file staticTriangulation.h.

Referenced by __triangulate().

__node_2_max_prime_clique

NodeProperty< NodeId > gum::StaticTriangulation::__node_2_max_prime_clique

private

indicates which clique of the max prime junction tree was created by the elmination of a given node (the key of the table)

Definition at line 267 of file staticTriangulation.h.

Referenced by __computeMaxPrimeJunctionTree(), clear(), setGraph(), and StaticTriangulation().

__original_graph

const UndiGraph* gum::StaticTriangulation::__original_graph {nullptr}

private

a pointer to the (external) original graph (which will be triangulated)

Definition at line 236 of file staticTriangulation.h.

Referenced by __computeEliminationTree(), __computeMaxPrimeMergings(), __triangulate(), clear(), fillIns(), setGraph(), and triangulatedGraph().

__reverse_elim_order

NodeProperty< NodeId > gum::StaticTriangulation::__reverse_elim_order

private

the elimination order (access by NodeId)

Definition at line 248 of file staticTriangulation.h.

Referenced by __computeEliminationTree(), __computeRecursiveThinning(), __triangulate(), clear(), setGraph(), and StaticTriangulation().

__triangulated_graph

UndiGraph gum::StaticTriangulation::__triangulated_graph

private

the triangulated graph

Definition at line 239 of file staticTriangulation.h.

Referenced by __computeRecursiveThinning(), __triangulate(), clear(), and triangulatedGraph().

__we_want_fill_ins

bool gum::StaticTriangulation::__we_want_fill_ins {false}

private

a boolean indicating if we want fill-ins list with the standard triangulation method

Definition at line 297 of file staticTriangulation.h.

Referenced by __triangulate(), and fillIns().

_domain_sizes

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

protectedinherited

the domain sizes of the variables/nodes of the graph

Definition at line 149 of file triangulation.h.

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

_elimination_sequence_strategy

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

protected

the elimination sequence strategy used by the triangulation

Definition at line 228 of file staticTriangulation.h.

Referenced by __triangulate(), gum::OrderedTriangulation::_initTriangulation(), gum::PartialOrderedTriangulation::_initTriangulation(), _initTriangulation(), clear(), fillIns(), gum::OrderedTriangulation::newFactory(), gum::PartialOrderedTriangulation::newFactory(), gum::OrderedTriangulation::OrderedTriangulation(), gum::PartialOrderedTriangulation::PartialOrderedTriangulation(), gum::OrderedTriangulation::setGraph(), gum::PartialOrderedTriangulation::setGraph(), gum::OrderedTriangulation::setOrder(), gum::PartialOrderedTriangulation::setPartialOrder(), StaticTriangulation(), and ~StaticTriangulation().

_junction_tree_strategy

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

protected

the junction tree strategy used by the triangulation

Definition at line 231 of file staticTriangulation.h.

Referenced by __computeMaxPrimeJunctionTree(), clear(), gum::OrderedTriangulation::newFactory(), gum::PartialOrderedTriangulation::newFactory(), StaticTriangulation(), and ~StaticTriangulation().

---

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

• agrum/graphs/algorithms/triangulations/staticTriangulation.h
• agrum/graphs/algorithms/triangulations/staticTriangulation.cpp