staticTriangulation.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005 by Christophe GONZALES and 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_STATIC_TRIANGULATION_H
#define GUM_STATIC_TRIANGULATION_H

#include <vector>

#include <agrum/agrum.h>

#include <agrum/graphs/algorithms/triangulations/eliminationStrategies/eliminationSequenceStrategy.h>
#include <agrum/graphs/algorithms/triangulations/junctionTreeStrategies/junctionTreeStrategy.h>
#include <agrum/graphs/algorithms/triangulations/triangulation.h>
#include <agrum/graphs/cliqueGraph.h>


namespace gum {


  class StaticTriangulation : public Triangulation {
    public:
    // ############################################################################
    // ############################################################################

    virtual StaticTriangulation* newFactory() const = 0;


    virtual StaticTriangulation* copyFactory() const = 0;

    virtual ~StaticTriangulation();



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


    virtual void setGraph(const UndiGraph*            graph,
                          const NodeProperty< Size >* domsizes);

    const EdgeSet& fillIns();

    const std::vector< NodeId >& eliminationOrder();

    Idx eliminationOrder(const NodeId);

    const NodeProperty< NodeId >& reverseEliminationOrder();

    const UndiGraph& triangulatedGraph();

    const CliqueGraph& eliminationTree();

    const CliqueGraph& junctionTree();

    NodeId createdJunctionTreeClique(const NodeId id);

    const NodeProperty< NodeId >& createdJunctionTreeCliques();


    const CliqueGraph& maxPrimeSubgraphTree();

    NodeId createdMaxPrimeSubgraph(const NodeId id);

    void clear();

    void setMinimalRequirement(bool);

    virtual bool isMinimalityRequired() const final;

    void setFillIns(bool);


    const UndiGraph* originalGraph() const;

    EliminationSequenceStrategy& eliminationSequenceStrategy() const;

    JunctionTreeStrategy& junctionTreeStrategy() const;



    protected:
    // ############################################################################
    // ############################################################################


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


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

    StaticTriangulation(const StaticTriangulation&);

    StaticTriangulation(StaticTriangulation&&);



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


    virtual void _initTriangulation(UndiGraph& graph);



    EliminationSequenceStrategy* _elimination_sequence_strategy{nullptr};

    JunctionTreeStrategy* _junction_tree_strategy{nullptr};


    private:
    const UndiGraph* __original_graph{nullptr};

    UndiGraph __triangulated_graph;

    EdgeSet __fill_ins;

    std::vector< NodeId > __elim_order;

    NodeProperty< NodeId > __reverse_elim_order;

    NodeProperty< NodeSet > __elim_cliques;

    CliqueGraph __elim_tree;


    const CliqueGraph* __junction_tree{nullptr};

    CliqueGraph __max_prime_junction_tree;

    NodeProperty< NodeId > __node_2_max_prime_clique;

    bool __has_triangulation{false};

    bool __has_triangulated_graph{false};

    bool __has_elimination_tree{false};

    bool __has_junction_tree{false};

    bool __has_max_prime_junction_tree{false};

    bool __has_fill_ins{false};

    bool __minimality_required{false};

    std::vector< EdgeSet > __added_fill_ins;

    bool __we_want_fill_ins{false};

    // ===========================================================================

    void __triangulate();

    void __computeEliminationTree();

    void __computeMaxPrimeJunctionTree();

    void __computeRecursiveThinning();

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

    StaticTriangulation& operator=(const StaticTriangulation&);
  };

} /* namespace gum */

#ifndef GUM_NO_INLINE
#  include <agrum/graphs/algorithms/triangulations/staticTriangulation_inl.h>
#endif   // GUM_NO_INLINE

#endif /* GUM_STATIC_TRIANGULATION_H */