cliqueGraph.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_CLIQUE_GRAPH_H
#define GUM_CLIQUE_GRAPH_H
 
#include <iostream>
 
#include <agrum/agrum.h>
 
#include <agrum/base/graphs/undiGraph.h>
 
namespace gum {
  /* ===========================================================================
   */
  /* ===                           GRAPHS OF CLIQUES                         ===
   */
  /* ===========================================================================
   */
  /* ===========================================================================
   */
 
  class CliqueGraph: public UndiGraph {
    public:
    // ############################################################################
    // ############################################################################


 
    explicit CliqueGraph(Size nodes_size          = HashTableConst::default_size,
                         bool nodes_resize_policy = true,
                         Size edges_size          = HashTableConst::default_size,
                         bool edges_resize_policy = true);


 
    CliqueGraph(const CliqueGraph& from);

    CliqueGraph(CliqueGraph&& from);

 
    ~CliqueGraph() override;

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


    void addEdge(NodeId first, NodeId second) override;


 
    void eraseEdge(const Edge& edge) override;

 
    void clearEdges() override;


    NodeId addNode(const NodeSet& clique);
 


    NodeId addNode() override;


    void addNodeWithId(const NodeId id, const NodeSet& clique);


    void addNodeWithId(const NodeId id) override;


 
    void eraseNode(const NodeId node) override;

 
    void clear() override;


 
    const NodeSet& clique(const NodeId idClique) const;

 
    NodeId container(const NodeId idNode) const;

 
    virtual void setClique(const NodeId idClique, const NodeSet& new_clique);

 
    virtual void addToClique(const NodeId clique_id, const NodeId node_id);


 
    virtual void eraseFromClique(const NodeId clique_id, const NodeId node_id);


 
    const NodeSet& separator(const Edge& edge) const;


 
    const NodeSet& separator(const NodeId clique1, const NodeId clique) const;


 
    std::vector< NodeId > containerPath(const NodeId node1, const NodeId node2) const;


 
    bool hasRunningIntersection() const;

 
    bool isJoinTree() const;

 
    std::string toString() const override;

 
    std::string toDot() const override;

 
    virtual std::string mapToDot(double           scaleClique,
                                 double           scaleSep,
                                 double           lenEdge,
                                 std::string_view colorClique = "burlywood",
                                 std::string_view colorSep    = "palegreen") const;

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

 
    CliqueGraph& operator=(const CliqueGraph& from);

 
    CliqueGraph& operator=(CliqueGraph&& from);
 

 
    bool operator==(const CliqueGraph& from) const;

 
    private:
    NodeProperty< NodeSet > _cliques_;

    EdgeProperty< NodeSet > _separators_;

 
    void _updateSeparators_(const NodeId clique1);

 
    struct _RunningIntersect_ {
      NodeSet visited_cliques;


      NodeSet nodes_other_components;

      NodeSet nodes_DFS_forbidden;

      NodeSet nodes_DFS_seen;

      NodeProperty< NodeSet > cliques_DFS_chain;
    };

 
    bool _runningIntersectionDFS_(const NodeId        clique,
                                  const NodeId        from,
                                  _RunningIntersect_& infos_DFS) const;
  };

  using JunctionTree = CliqueGraph;

  using JoinTree = CliqueGraph;

 
  std::ostream& operator<<(std::ostream&, const CliqueGraph&);
 
} /* namespace gum */
 
#ifndef GUM_NO_INLINE
#  include <agrum/base/graphs/cliqueGraph_inl.h>
#endif   // GU%_NO_INLINE
 
#endif   /* GUM_CLIQUE_GRAPH_H */