DAGCycleDetector_inl.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2025 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-2025                            *
 *       - 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                           *
 *                                                                          *
 ****************************************************************************/
#pragma once

 
namespace gum {
 
  /* ===========================================================================
   */
  // CHANGES
  /* ===========================================================================
   */
 
  // default constructor
  INLINE DAGCycleDetector::Change::Change(ChangeType type, NodeId tail, NodeId head) noexcept :
      _type_{type}, _tail_{tail}, _head_{head} {
    GUM_CONSTRUCTOR(DAGCycleDetector::Change);
  }
 
  // copy constructor
  INLINE DAGCycleDetector::Change::Change(const DAGCycleDetector::Change& from) noexcept :
      _type_{from._type_}, _tail_{from._tail_}, _head_{from._head_} {
    GUM_CONS_CPY(DAGCycleDetector::Change);
  }
 
  // move constructor
  INLINE DAGCycleDetector::Change::Change(DAGCycleDetector::Change&& from) noexcept :
      _type_{from._type_}, _tail_{from._tail_}, _head_{from._head_} {
    GUM_CONS_MOV(DAGCycleDetector::Change);
  }
 
  // destructor
  INLINE DAGCycleDetector::Change::~Change() noexcept { GUM_DESTRUCTOR(DAGCycleDetector::Change); }
 
  // copy operator
  INLINE DAGCycleDetector::Change&
         DAGCycleDetector::Change::operator=(const DAGCycleDetector::Change& from) noexcept {
    _type_ = from._type_;
    _tail_ = from._tail_;
    _head_ = from._head_;
    return *this;
  }
 
  // move operator
  INLINE DAGCycleDetector::Change&
         DAGCycleDetector::Change::operator=(DAGCycleDetector::Change&& from) noexcept {
    _type_ = from._type_;
    _tail_ = from._tail_;
    _head_ = from._head_;
    return *this;
  }

  INLINE DAGCycleDetector::ChangeType DAGCycleDetector::Change::type() const noexcept {
    return _type_;
  }

  INLINE NodeId DAGCycleDetector::Change::tail() const noexcept { return _tail_; }

  INLINE NodeId DAGCycleDetector::Change::head() const noexcept { return _head_; }
 
  /* ===========================================================================
   */
  // ArcAdd
  /* ===========================================================================
   */

  INLINE DAGCycleDetector::ArcAdd::ArcAdd(NodeId tail, NodeId head) noexcept :
      DAGCycleDetector::Change(DAGCycleDetector::ChangeType::ARC_ADDITION, tail, head) {
    GUM_CONSTRUCTOR(DAGCycleDetector::ArcAdd);
  }

  INLINE DAGCycleDetector::ArcAdd::ArcAdd(const DAGCycleDetector::ArcAdd& from) noexcept :
      DAGCycleDetector::Change(from.type(), from.tail(), from.head()) {
    GUM_CONS_CPY(DAGCycleDetector::ArcAdd);
  }

  INLINE DAGCycleDetector::ArcAdd::ArcAdd(DAGCycleDetector::ArcAdd&& from) noexcept :
      DAGCycleDetector::Change(std::move(from.type()),
                               std::move(from.tail()),
                               std::move(from.head())) {
    GUM_CONS_MOV(DAGCycleDetector::ArcAdd);
  }

  INLINE DAGCycleDetector::ArcAdd::~ArcAdd() noexcept { GUM_DESTRUCTOR(DAGCycleDetector::ArcAdd); }

  INLINE DAGCycleDetector::ArcAdd&
         DAGCycleDetector::ArcAdd::operator=(const DAGCycleDetector::ArcAdd& from) noexcept {
    DAGCycleDetector::Change::operator=(from);
    return *this;
  }

  INLINE DAGCycleDetector::ArcAdd&
         DAGCycleDetector::ArcAdd::operator=(DAGCycleDetector::ArcAdd&& from) noexcept {
    DAGCycleDetector::Change::operator=(std::move(from));
    return *this;
  }
 
  /* ===========================================================================
   */
  // ArcDel
  /* ===========================================================================
   */

  INLINE DAGCycleDetector::ArcDel::ArcDel(NodeId tail, NodeId head) noexcept :
      DAGCycleDetector::Change(DAGCycleDetector::ChangeType::ARC_DELETION, tail, head) {
    GUM_CONSTRUCTOR(DAGCycleDetector::ArcDel);
  }

  INLINE DAGCycleDetector::ArcDel::ArcDel(const DAGCycleDetector::ArcDel& from) noexcept :
      DAGCycleDetector::Change(from.type(), from.tail(), from.head()) {
    GUM_CONS_CPY(DAGCycleDetector::ArcDel);
  }

  INLINE DAGCycleDetector::ArcDel::ArcDel(DAGCycleDetector::ArcDel&& from) noexcept :
      DAGCycleDetector::Change(std::move(from.type()),
                               std::move(from.tail()),
                               std::move(from.head())) {
    GUM_CONS_MOV(DAGCycleDetector::ArcDel);
  }

  INLINE DAGCycleDetector::ArcDel::~ArcDel() noexcept { GUM_DESTRUCTOR(DAGCycleDetector::ArcDel); }

  INLINE DAGCycleDetector::ArcDel&
         DAGCycleDetector::ArcDel::operator=(const DAGCycleDetector::ArcDel& from) noexcept {
    DAGCycleDetector::Change::operator=(from);
    return *this;
  }

  INLINE DAGCycleDetector::ArcDel&
         DAGCycleDetector::ArcDel::operator=(DAGCycleDetector::ArcDel&& from) noexcept {
    DAGCycleDetector::Change::operator=(std::move(from));
    return *this;
  }
 
  /* ===========================================================================
   */
  // ArcReverse
  /* ===========================================================================
   */

  INLINE DAGCycleDetector::ArcReverse::ArcReverse(NodeId tail, NodeId head) noexcept :
      DAGCycleDetector::Change(DAGCycleDetector::ChangeType::ARC_REVERSAL, tail, head) {
    GUM_CONSTRUCTOR(DAGCycleDetector::ArcReverse);
  }

  INLINE DAGCycleDetector::ArcReverse::ArcReverse(const DAGCycleDetector::ArcReverse& from) noexcept
      : DAGCycleDetector::Change(from.type(), from.tail(), from.head()) {
    GUM_CONS_CPY(DAGCycleDetector::ArcReverse);
  }

  INLINE DAGCycleDetector::ArcReverse::ArcReverse(DAGCycleDetector::ArcReverse&& from) noexcept :
      DAGCycleDetector::Change(std::move(from.type()),
                               std::move(from.tail()),
                               std::move(from.head())) {
    GUM_CONS_MOV(DAGCycleDetector::ArcReverse);
  }

  INLINE DAGCycleDetector::ArcReverse::~ArcReverse() noexcept {
    GUM_DESTRUCTOR(DAGCycleDetector::ArcReverse);
  }

  INLINE DAGCycleDetector::ArcReverse&
      DAGCycleDetector::ArcReverse::operator=(const DAGCycleDetector::ArcReverse& from) noexcept {
    DAGCycleDetector::Change::operator=(from);
    return *this;
  }

  INLINE DAGCycleDetector::ArcReverse&
         DAGCycleDetector::ArcReverse::operator=(DAGCycleDetector::ArcReverse&& from) noexcept {
    DAGCycleDetector::Change::operator=(std::move(from));
    return *this;
  }
 
  /* ===========================================================================
   */
  // DAGCycleDetector
  /* ===========================================================================
   */

  INLINE DAGCycleDetector::DAGCycleDetector() noexcept { GUM_CONSTRUCTOR(DAGCycleDetector); }

  INLINE DAGCycleDetector::DAGCycleDetector(const DAGCycleDetector& from) :
      _dag_(from._dag_), _ancestors_(from._ancestors_), _descendants_(from._descendants_) {
    GUM_CONS_CPY(DAGCycleDetector);
  }

  INLINE DAGCycleDetector::DAGCycleDetector(DAGCycleDetector&& from) :
      _dag_(std::move(from._dag_)), _ancestors_(std::move(from._ancestors_)),
      _descendants_(std::move(from._descendants_)) {
    GUM_CONS_MOV(DAGCycleDetector);
  }

  INLINE DAGCycleDetector::~DAGCycleDetector() { GUM_DESTRUCTOR(DAGCycleDetector); }

  INLINE
  DAGCycleDetector& DAGCycleDetector::operator=(const DAGCycleDetector& from) {
    if (this != &from) {
      _dag_         = from._dag_;
      _ancestors_   = from._ancestors_;
      _descendants_ = from._descendants_;
    }
 
    return *this;
  }

  INLINE DAGCycleDetector& DAGCycleDetector::operator=(DAGCycleDetector&& from) {
    if (this != &from) {
      _dag_         = std::move(from._dag_);
      _ancestors_   = std::move(from._ancestors_);
      _descendants_ = std::move(from._descendants_);
    }
 
    return *this;
  }

  INLINE bool DAGCycleDetector::hasCycleFromAddition(NodeId x, NodeId y) const noexcept {
    return _descendants_[y].exists(x);
  }

  INLINE bool DAGCycleDetector::hasCycleFromReversal(NodeId x, NodeId y) const noexcept {
    return (_ancestors_[y][x] > 1);
  }

  INLINE bool DAGCycleDetector::hasCycleFromDeletion(NodeId x, NodeId y) const noexcept {
    return false;
  }

  INLINE
  void DAGCycleDetector::_addWeightedSet_(NodeProperty< Size >&       nodeset,
                                          const NodeProperty< Size >& set_to_add,
                                          Size                        multiplier) const {
    for (auto iter = set_to_add.cbegin(); iter != set_to_add.cend(); ++iter) {
      if (nodeset.exists(iter.key())) {
        nodeset[iter.key()] += iter.val() * multiplier;
      } else {
        nodeset.insert(iter.key(), iter.val() * multiplier);
      }
    }
  }

  INLINE
  void DAGCycleDetector::_delWeightedSet_(NodeProperty< Size >&       nodeset,
                                          const NodeProperty< Size >& set_to_del,
                                          Size                        multiplier) const {
    for (auto iter = set_to_del.cbegin(); iter != set_to_del.cend(); ++iter) {
      if (nodeset.exists(iter.key())) {
        Size& weight = nodeset[iter.key()];
        weight -= iter.val() * multiplier;
 
        if (!weight) { nodeset.erase(iter.key()); }
      }
    }
  }

  INLINE
  void DAGCycleDetector::_restrictWeightedSet_(NodeProperty< Size >&       result_set,
                                               const NodeProperty< Size >& set_to_restrict,
                                               const NodeSet&              extremities) const {
    for (auto iter = set_to_restrict.cbegin(); iter != set_to_restrict.cend(); ++iter) {
      if (extremities.exists(iter.key())) { result_set.insert(iter.key(), iter.val()); }
    }
  }

  INLINE void DAGCycleDetector::reverseArc(NodeId tail, NodeId head) {
    if (hasCycleFromReversal(tail, head)) {
      GUM_ERROR(InvalidDirectedCycle, "the arc would create a directed into a DAG")
    }
 
    eraseArc(tail, head);
    addArc(head, tail);
  }

  INLINE bool DAGCycleDetector::operator==(const DAGCycleDetector& from) const {
    return (   //(  _dagmodel_ == from. _dagmodel_ ) &&
        (_ancestors_ == from._ancestors_) && (_descendants_ == from._descendants_));
  }

  INLINE bool DAGCycleDetector::operator!=(const DAGCycleDetector& from) const {
    return !operator==(from);
  }
 
} /* namespace gum */