incrementalTriangulation.h

Go to the documentation of this file.

/**
 *
 *   Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
 *   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/>.
 *
 */


/** @file
 * @brief Class for computing default triangulations of graphs
 *
 * @author Christophe GONZALES(@AMU) and Pierre-Henri WUILLEMIN(@LIP6)
 */

#ifndef GUM_INCREMENTAL_TRIANGULATION_H
#define GUM_INCREMENTAL_TRIANGULATION_H

#include <iostream>
#include <sstream>
#include <vector>

#include <agrum/tools/graphs/algorithms/triangulations/unconstrainedTriangulation.h>
#include <agrum/tools/graphs/cliqueGraph.h>
#include <agrum/tools/graphs/graphElements.h>

#ifndef DOXYGEN_SHOULD_SKIP_THIS
namespace gum_tests {
  class IncrementalTriangulationTestSuite;
}
#endif

namespace gum {

  /** @class IncrementalTriangulation
   * @brief Class that performs incremental triangulations
   */
  class IncrementalTriangulation: public Triangulation {
    public:
    // ############################################################################
    /// @name Constructors / Destructors
    // ############################################################################
    /// @{

    /// constructor
    /** Note that, in the graph passed in argument, the type of the edges may
     * differ from Edge. However, the junction trees and triangulated graphs
     * produced by the triangulation algorithm will all have edges of type Edge.
     */
    IncrementalTriangulation(const UnconstrainedTriangulation& triang_algo,
                             const UndiGraph*                  theGraph,
                             const NodeProperty< Size >*       modal);

    /// default constructor: initialize the triangulation with en empty graph
    IncrementalTriangulation(const UnconstrainedTriangulation& triangAlgo);

    /// copy operator
    IncrementalTriangulation(const IncrementalTriangulation& from);

    /// destructor
    ~IncrementalTriangulation();

    /// @}


    // ############################################################################
    /// @name Accessors / Modifiers
    // ############################################################################
    /// @{

    /// updates the triangulated graph using the modif list
    void updateTriangulation();

    /// adds a new node to the graph
    void addNode(const NodeId node, Size modal);

    /** @brief removes a node from the graph (the join tree may need a
     * triangulation update) */
    void eraseNode(const NodeId node);

    /** @brief adds a new edge to the graph (the join tree may need a
     * triangulation update) */
    void addEdge(const NodeId X, const NodeId Y);

    /// removes an edge from the graph (the join tree may need a
    /// retriangulation)
    void eraseEdge(const Edge& edge);

    /// returns the fill-ins added by the triangulation algorithm
    const EdgeSet& fillIns() {
      GUM_ERROR(OperationNotAllowed, "Not implemented yet");
    };

    /// returns an elimination ordering compatible with the triangulated graph
    const std::vector< NodeId >& eliminationOrder();

    /** @brief returns the number of a given node in the elimination order
     * (0 = first node eliminated) */
    Idx eliminationOrder(const NodeId);

    /// returns the triangulated graph
    const UndiGraph& triangulatedGraph() {
      GUM_ERROR(OperationNotAllowed, "Not implemented yet");
    };

    /// returns the current graph (that which is incrementally triangulated)
    const UndiGraph& graph() const;

    /// returns the elimination tree of a compatible ordering
    const CliqueGraph& eliminationTree() {
      GUM_ERROR(OperationNotAllowed, "Not implemented yet");
    };

    /// returns a junction tree corresponding to the current graph
    const CliqueGraph& junctionTree();

    /** @brief returns the Id of the clique created by the
     * elimination of a given node during the triangulation process */
    NodeId createdJunctionTreeClique(const NodeId id);

    /** @brief returns the Ids of the cliques of the junction tree created by
     * the elimination of the nodes */
    const NodeProperty< NodeId >& createdJunctionTreeCliques();

    /// returns the junction tree of the maximal prime subgraphs
    const CliqueGraph& maxPrimeSubgraphTree();

    /** @brief returns the Id of the maximal prime subgraph created by the
     * elimination of a given node during the triangulation process */
    NodeId createdMaxPrimeSubgraph(const NodeId id);

    /// sets the graph to the empty graph
    void clear();

    /// changes the current graph
    void setGraph(const UndiGraph*            theGraph,
                  const NodeProperty< Size >* domain_sizes);

    /// returns the triangulation algorithm (useful for fine tuning it)
    const UnconstrainedTriangulation& triangulationAlgo() const;

    /// @}


    // ############################################################################
    /// @name Operators
    // ############################################################################
    /// @{

    /// copy operator
    IncrementalTriangulation& operator=(const IncrementalTriangulation& from);

    /// virtual clone constructor
    virtual IncrementalTriangulation* newFactory() const final;

    /// virtual copy constructor
    virtual IncrementalTriangulation* copyFactory() const final;

    /// @}


    private:
    /// the graph that needs be triangulated
    UndiGraph graph__;

    /// the domain sizes of the nodes
    NodeProperty< Size > domain_sizes__;

    /// the junction tree computed so far
    CliqueGraph junction_tree__;

    /// the maximal prime subgraph tree
    CliqueGraph T_mpd__;

    /// for each node in graph, store the MPS containing the node
    NodeProperty< List< NodeId > > mps_of_node__;

    /// indicate for each MPS its set of cliques in the junction tree
    NodeProperty< std::vector< NodeId > > cliques_of_mps__;

    /// indicate for each clique the MPS it belongs to
    NodeProperty< NodeId > mps_of_clique__;

    /// the set of MPS affected by a new triangulation
    NodeProperty< bool > mps_affected__;

    /// the triangulation algorithm that will be used incremantally
    UnconstrainedTriangulation* triangulation__;

    /// a Boolean indicating whether the triangulation need be updated
    bool require_update__{false};

    /// a Boolean indicating wether we should update the elimination order
    bool require_elimination_order__{false};

    /// the current elimination ordering
    std::vector< NodeId > elimination_order__;

    /// the elimination order (access by NodeId)
    NodeProperty< Idx > reverse_elimination_order__;

    /// a Boolean indicating whether we should compute the createdJTCliques
    bool require_created_JT_cliques__{false};

    /// For each node, a clique that contains it
    NodeProperty< NodeId > created_JT_cliques__;

    /// mark the mps affected by the deletion of a given edge
    void markAffectedMPSsByRemoveLink__(const NodeId My,
                                        const NodeId Mz,
                                        const Edge&  edge);

    /// mark the mps affected by the insertion of a new edge
    int markAffectedMPSsByAddLink__(const NodeId My,
                                    const NodeId Mz,
                                    const NodeId X,
                                    const NodeId Y);

    /// remove a given node from the T_mpd structure
    void performRemoveNode__(const NodeId node, const NodeId My, const NodeId Mz);

    /// adds a new node to T_mpd, the graph and the clique graph
    void performAddNode__(const NodeId node);

    /// set-up the connected subgraph that needs be retriangulated
    void setUpConnectedTriangulation__(
       NodeId                     Mx,
       NodeId                     Mfrom,
       UndiGraph&                 theGraph,
       std::vector< Edge >&       notAffectedneighborClique,
       HashTable< NodeId, bool >& cliques_affected);

    /// used for computing the junction tree of the maximal prime subgraphs
    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;

    /// update the junction tree
    void updateJunctionTree__(NodeProperty< bool >& all_cliques_affected,
                              NodeSet&              new_nodes_in_junction_tree);

    /// update the max prime subgraph
    void updateMaxPrimeSubgraph__(NodeProperty< bool >& cliques_affected,
                                  const NodeSet& new_nodes_in_junction_tree);

    /// a collect algorithm to compute elimination orderings
    void collectEliminationOrder__(const NodeId          node,
                                   const NodeId          from,
                                   NodeProperty< bool >& examined,
                                   Idx&                  index);

    /// a collect algorithm to compute, for each node, one container JT's clique
    void collectJTCliques__(const NodeId          clique,
                            const NodeId          from,
                            NodeProperty< bool >& examined);

    /// checks that the incremental triangulation works properly
    bool check__();

    /// to enable testunits to use check__
    friend class gum_tests::IncrementalTriangulationTestSuite;
  };

} /* namespace gum */

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

#endif /* GUM_INCREMENTAL_TRIANGULATION_H */