incrementalTriangulation.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_INCREMENTAL_TRIANGULATION_H
#define GUM_INCREMENTAL_TRIANGULATION_H

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

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

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

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();



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

    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() {
      GUM_ERROR(OperationNotAllowed, "Not implemented yet");
    };


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

    Idx eliminationOrder(const NodeId);

    const UndiGraph& triangulatedGraph() {
      GUM_ERROR(OperationNotAllowed, "Not implemented yet");
    };

    const UndiGraph& graph() const;

    const CliqueGraph& eliminationTree() {
      GUM_ERROR(OperationNotAllowed, "Not implemented yet");
    };

    const CliqueGraph& junctionTree();

    NodeId createdJunctionTreeClique(const NodeId id);

    const NodeProperty< NodeId >& createdJunctionTreeCliques();

    const CliqueGraph& maxPrimeSubgraphTree();

    NodeId createdMaxPrimeSubgraph(const NodeId id);

    void clear();

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

    const UnconstrainedTriangulation& triangulationAlgo() const;



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

    IncrementalTriangulation& operator=(const IncrementalTriangulation& from);

    virtual IncrementalTriangulation* newFactory() const final;

    virtual IncrementalTriangulation* copyFactory() const final;



    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);

    bool __check();

    friend class gum_tests::IncrementalTriangulationTestSuite;
  };

} /* namespace gum */

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

#endif /* GUM_INCREMENTAL_TRIANGULATION_H */