defaultEliminationSequenceStrategy.h File Reference

Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org. More...

#include <agrum/agrum.h>
#include <agrum/tools/graphs/algorithms/simplicialSet.h>
#include <agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/unconstrainedEliminationSequenceStrategy.h>
#include <agrum/tools/graphs/graphElements.h>

Include dependency graph for defaultEliminationSequenceStrategy.h:

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

Go to the source code of this file.

Classes
class	gum::DefaultEliminationSequenceStrategy
	An efficient unconstrained elimination sequence algorithm. More...

Namespaces
	gum
	Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.

Detailed Description

Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.

This library is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see http://www.gnu.org/licenses/. An efficient unconstrained elimination sequence algorithm

Class DefaultEliminationSequenceStrategy implements an unconstrained elimination sequence algorithm (that is, there is no external constraint on the possible elimination ordering). 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 defaultEliminationSequenceStrategy.h.