incrementalTriangulation.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2026 by                                             *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *                                                                          *
 *   The aGrUM/pyAgrum library is free software; you can redistribute it    *
 *   and/or modify it under the terms of either :                           *
 *                                                                          *
 *    - 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,                              *
 *    - the MIT license (MIT),                                              *
 *    - or both in dual license, as here.                                   *
 *                                                                          *
 *   (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html)    *
 *                                                                          *
 *   This aGrUM/pyAgrum library is distributed in the hope that it will be  *
 *   useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,          *
 *   INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
 *   FOR A PARTICULAR PURPOSE  AND NONINFRINGEMENT. IN NO EVENT SHALL THE   *
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,        *
 *   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR  *
 *   OTHER DEALINGS IN THE SOFTWARE.                                        *
 *                                                                          *
 *   See LICENCES for more details.                                         *
 *                                                                          *
 *   SPDX-FileCopyrightText: Copyright 2005-2026                            *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *   SPDX-License-Identifier: LGPL-3.0-or-later OR MIT                      *
 *                                                                          *
 *   Contact  : info_at_agrum_dot_org                                       *
 *   homepage : http://agrum.gitlab.io                                      *
 *   gitlab   : https://gitlab.com/agrumery/agrum                           *
 *                                                                          *
 ****************************************************************************/
 

 
#ifndef GUM_INCREMENTAL_TRIANGULATION_H
#define GUM_INCREMENTAL_TRIANGULATION_H
 
#include <iostream>
#include <sstream>
#include <vector>
 
#include <agrum/base/graphs/algorithms/triangulations/unconstrainedTriangulation.h>
 
namespace gum {

  class IncrementalTriangulation: public Triangulation {
    public:
    // ############################################################################
    // ############################################################################


    IncrementalTriangulation(const UnconstrainedTriangulation& triang_algo,
                             const UndiGraph*                  theGraph,
                             const NodeProperty< Size >*       modal);

    IncrementalTriangulation(const UnconstrainedTriangulation& triangAlgo);

    IncrementalTriangulation(const IncrementalTriangulation& from);

    IncrementalTriangulation(IncrementalTriangulation&& from);

    ~IncrementalTriangulation() override;

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

    void updateTriangulation();

    void addNode(const NodeId node, Size modal);

    void eraseNode(const NodeId node);

    void addEdge(const NodeId X, const NodeId Y);

    void eraseEdge(const Edge& edge);

    const EdgeSet& fillIns() override;

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

    Idx eliminationOrder(const NodeId) override;

    const UndiGraph& triangulatedGraph() override;

    const UndiGraph& graph() const;

    const CliqueGraph& eliminationTree() override;

    const CliqueGraph& junctionTree() override;

    NodeId createdJunctionTreeClique(const NodeId id) override;

    const NodeProperty< NodeId >& createdJunctionTreeCliques() override;

    const CliqueGraph& maxPrimeSubgraphTree() override;

    NodeId createdMaxPrimeSubgraph(const NodeId id) override;

    void clear() override;

    void setGraph(const UndiGraph* theGraph, const NodeProperty< Size >* domain_sizes) override;

    const UnconstrainedTriangulation& triangulationAlgo() const;

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

    IncrementalTriangulation& operator=(const IncrementalTriangulation& from);

    IncrementalTriangulation& operator=(IncrementalTriangulation&& from);

    [[nodiscard]] IncrementalTriangulation* newFactory() const final;

    [[nodiscard]] IncrementalTriangulation* copyFactory() const final;

    bool checkConsistency();

 
 
    private:
    UndiGraph _graph_;

    NodeProperty< Size > _domain_sizes_;

    CliqueGraph _junction_tree_;

    CliqueGraph _T_mpd_;

    NodeProperty< List< NodeId > > _mps_of_node_;

    NodeProperty< std::vector< NodeId > > _cliques_of_mps_;

    NodeProperty< NodeId > _mps_of_clique_;

    NodeProperty< bool > _mps_affected_;

    UnconstrainedTriangulation* _triangulation_;

    bool _require_update_{false};

    bool _require_elimination_order_{false};

    std::vector< NodeId > _elimination_order_;

    NodeProperty< Idx > _reverse_elimination_order_;

    bool _require_created_JT_cliques_{false};

    NodeProperty< NodeId > _created_JT_cliques_;

    void _markAffectedMPSsByRemoveLink_(const NodeId My, const NodeId Mz, const Edge& edge);

    int _markAffectedMPSsByAddLink_(const NodeId My,
                                    const NodeId Mz,
                                    const NodeId X,
                                    const NodeId Y);

    void _performRemoveNode_(const NodeId node, const NodeId My, const NodeId Mz);

    void _performAddNode_(const NodeId node);

    void _setUpConnectedTriangulation_(NodeId                     Mx,
                                       NodeId                     Mfrom,
                                       UndiGraph&                 theGraph,
                                       std::vector< Edge >&       notAffectedneighborClique,
                                       HashTable< NodeId, bool >& cliques_affected);

    void _computeMaxPrimeMergings_(const NodeId                                node,
                                   const NodeId                                from,
                                   std::vector< std::pair< NodeId, NodeId > >& merged_cliques,
                                   NodeProperty< bool >&                       mark,
                                   const NodeSet& new_nodes_in_junction_tree) const;

    void _updateJunctionTree_(NodeProperty< bool >& all_cliques_affected,
                              NodeSet&              new_nodes_in_junction_tree);

    void _updateMaxPrimeSubgraph_(NodeProperty< bool >& cliques_affected,
                                  const NodeSet&        new_nodes_in_junction_tree);

    void _collectEliminationOrder_(const NodeId          node,
                                   const NodeId          from,
                                   NodeProperty< bool >& examined,
                                   Idx&                  index);

    void _collectJTCliques_(const NodeId clique, const NodeId from, NodeProperty< bool >& examined);
  };
 
} /* namespace gum */
 
#ifndef GUM_NO_INLINE
#  include <agrum/base/graphs/algorithms/triangulations/incrementalTriangulation_inl.h>
#endif   // GUM_NO_INLINE
 
#endif   /* GUM_INCREMENTAL_TRIANGULATION_H */