defaultPartialOrderedEliminationSequenceStrategy.h File Reference

An Elimination sequence algorithm that imposes a given partial ordering on the nodes elimination sequence. More...

#include <agrum/core/priorityQueue.h>
#include <agrum/graphs/algorithms/simplicialSet.h>
#include <agrum/graphs/algorithms/triangulations/eliminationStrategies/partialOrderedEliminationSequenceStrategy.h>
#include <agrum/graphs/graphElements.h>

Include dependency graph for defaultPartialOrderedEliminationSequenceStrategy.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	gum::DefaultPartialOrderedEliminationSequenceStrategy
	An Elimination sequence algorithm that imposes a given partial ordering on the nodes elimination sequence. More...

Namespaces
	gum
	gum is the global namespace for all aGrUM entities

Detailed Description

An Elimination sequence algorithm that imposes a given partial ordering on the nodes elimination sequence.

Class DefaultPartialOrderedEliminationSequenceStrategy implements an elimination sequence algorithm that satisfies a partial ordering, that is, the set of all the nodes is divided into several subsets. 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. Within a subset, the ordering is determined as follows:

the nodes that are simplicial (i.e., those that already form a clique with

their neighbors) are eliminated first

then the nodes that are almost simplicial (i.e. if we remove one of their

neighbors, they become simplicial) and that create small cliques, are eliminated (see Bodlaender's safe reductions)

the quasi simplicial nodes (i.e., the nodes that do not require many

fill-ins to create cliques) that would create small cliques, are eliminated

finally, the heuristic proposed by Kjaerulff(90) is used to compute the

last nodes to be eliminated.

Author

Christophe GONZALES and Pierre-Henri WUILLEMIN

Definition in file defaultPartialOrderedEliminationSequenceStrategy.h.