variableElimination.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005 by Christophe GONZALES et Pierre-Henri WUILLEMIN   *
 *   {prenom.nom}_at_lip6.fr                                               *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#ifndef GUM_VARIABLE_ELIMINATION_H
#define GUM_VARIABLE_ELIMINATION_H

#include <utility>

#include <agrum/core/math/math.h>
#include <agrum/BN/algorithms/barrenNodesFinder.h>
#include <agrum/BN/inference/tools/jointTargetedInference.h>
#include <agrum/BN/inference/tools/relevantPotentialsFinderType.h>
#include <agrum/agrum.h>
#include <agrum/graphs/algorithms/triangulations/defaultTriangulation.h>

namespace gum {


  // the function used to combine two tables
  template < typename GUM_SCALAR >
  INLINE static Potential< GUM_SCALAR >*
     VENewmultiPotential(const Potential< GUM_SCALAR >& t1,
                         const Potential< GUM_SCALAR >& t2) {
    return new Potential< GUM_SCALAR >(t1 * t2);
  }

  // the function used to combine two tables
  template < typename GUM_SCALAR >
  INLINE static Potential< GUM_SCALAR >*
     VENewprojPotential(const Potential< GUM_SCALAR >&        t1,
                        const Set< const DiscreteVariable* >& del_vars) {
    return new Potential< GUM_SCALAR >(t1.margSumOut(del_vars));
  }


  template < typename GUM_SCALAR >
  class VariableElimination : public JointTargetedInference< GUM_SCALAR > {
    public:
    // ############################################################################
    // ############################################################################

    explicit VariableElimination(
       const IBayesNet< GUM_SCALAR >* BN,
       RelevantPotentialsFinderType   relevant_type =
          RelevantPotentialsFinderType::DSEP_BAYESBALL_POTENTIALS,
       FindBarrenNodesType = FindBarrenNodesType::FIND_BARREN_NODES);

    VariableElimination(const VariableElimination< GUM_SCALAR >&) = delete;

    VariableElimination< GUM_SCALAR >&
       operator=(const VariableElimination< GUM_SCALAR >&) = delete;

    ~VariableElimination() final;



    // ############################################################################
    // ############################################################################

    void setTriangulation(const Triangulation& new_triangulation);


    void setRelevantPotentialsFinderType(RelevantPotentialsFinderType type);


    void setFindBarrenNodesType(FindBarrenNodesType type);

    const JunctionTree* junctionTree(NodeId id);



    protected:
    void _onStateChanged() final{};

    void _onEvidenceAdded(const NodeId id, bool isHardEvidence) final;

    void _onEvidenceErased(const NodeId id, bool isHardEvidence) final;

    void _onAllEvidenceErased(bool contains_hard_evidence) final;

    void _onEvidenceChanged(const NodeId id, bool hasChangedSoftHard) final;


    void _onMarginalTargetAdded(const NodeId id) final;


    void _onMarginalTargetErased(const NodeId id) final;

    virtual void _onBayesNetChanged(const IBayesNet< GUM_SCALAR >* bn) final;


    void _onJointTargetAdded(const NodeSet& set) final;


    void _onJointTargetErased(const NodeSet& set) final;

    void _onAllMarginalTargetsAdded() final;

    void _onAllMarginalTargetsErased() final;

    void _onAllJointTargetsErased() final;

    void _onAllTargetsErased() final;


    void _updateOutdatedBNStructure() final;


    void _updateOutdatedBNPotentials() final;


    void _makeInference() final;



    const Potential< GUM_SCALAR >& _posterior(NodeId id) final;


    const Potential< GUM_SCALAR >& _jointPosterior(const NodeSet& set) final;

    const Potential< GUM_SCALAR >&
       _jointPosterior(const NodeSet& wanted_target,
                       const NodeSet& declared_target) final;

    Potential< GUM_SCALAR >* _unnormalizedJointPosterior(NodeId id) final;

    Potential< GUM_SCALAR >* _unnormalizedJointPosterior(const NodeSet& set) final;


    private:
    typedef Set< const Potential< GUM_SCALAR >* > __PotentialSet;
    typedef SetIteratorSafe< const Potential< GUM_SCALAR >* >
       __PotentialSetIterator;


    RelevantPotentialsFinderType __find_relevant_potential_type;

    void (VariableElimination< GUM_SCALAR >::*__findRelevantPotentials)(
       Set< const Potential< GUM_SCALAR >* >& pot_list,
       Set< const DiscreteVariable* >&        kept_vars);

    FindBarrenNodesType __barren_nodes_type;

    Potential< GUM_SCALAR >* (*__projection_op)(
       const Potential< GUM_SCALAR >&,
       const Set< const DiscreteVariable* >&){VENewprojPotential};

    Potential< GUM_SCALAR >* (*__combination_op)(const Potential< GUM_SCALAR >&,
                                                 const Potential< GUM_SCALAR >&){
       VENewmultiPotential};

    Triangulation* __triangulation;


    UndiGraph __graph;

    JunctionTree* __JT{nullptr};

    HashTable< NodeId, NodeId > __node_to_clique;

    HashTable< NodeId, NodeSet > __clique_potentials;

    NodeId __targets2clique;


    Potential< GUM_SCALAR >* __target_posterior{nullptr};

    const GUM_SCALAR __1_minus_epsilon{GUM_SCALAR(1.0 - 1e-6)};


    void __createNewJT(const NodeSet& targets);

    void __setProjectionFunction(Potential< GUM_SCALAR >* (*proj)(
       const Potential< GUM_SCALAR >&, const Set< const DiscreteVariable* >&));

    void __setCombinationFunction(Potential< GUM_SCALAR >* (*comb)(
       const Potential< GUM_SCALAR >&, const Potential< GUM_SCALAR >&));

    void __findRelevantPotentialsWithdSeparation(
       __PotentialSet& pot_list, Set< const DiscreteVariable* >& kept_vars);

    void __findRelevantPotentialsWithdSeparation2(
       __PotentialSet& pot_list, Set< const DiscreteVariable* >& kept_vars);

    void __findRelevantPotentialsWithdSeparation3(
       __PotentialSet& pot_list, Set< const DiscreteVariable* >& kept_vars);

    void __findRelevantPotentialsGetAll(__PotentialSet&                 pot_list,
                                        Set< const DiscreteVariable* >& kept_vars);

    void __findRelevantPotentialsXX(__PotentialSet&                 pot_list,
                                    Set< const DiscreteVariable* >& kept_vars);

    // remove barren variables and return the newly created projected potentials
    __PotentialSet
       __removeBarrenVariables(__PotentialSet&                 pot_list,
                               Set< const DiscreteVariable* >& del_vars);

    std::pair< __PotentialSet, __PotentialSet > __collectMessage(NodeId id,
                                                                 NodeId from);

    std::pair< __PotentialSet, __PotentialSet > __NodePotentials(NodeId node);

    std::pair< __PotentialSet, __PotentialSet > __produceMessage(
       NodeId                                        from_id,
       NodeId                                        to_id,
       std::pair< __PotentialSet, __PotentialSet >&& incoming_messages);

    __PotentialSet __marginalizeOut(__PotentialSet                  pot_list,
                                    Set< const DiscreteVariable* >& del_vars,
                                    Set< const DiscreteVariable* >& kept_vars);
  };


#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
  extern template class VariableElimination< double >;
#endif


} /* namespace gum */


#include <agrum/BN/inference/variableElimination_tpl.h>


#endif /* GUM_VARIABLE_ELIMINATION_ */