gum::DAGCycleDetector Class Reference

A class for detecting directed cycles in DAGs when trying to apply many changes to the graph. More...

#include <DAGCycleDetector.h>

Collaboration diagram for gum::DAGCycleDetector:

Classes
class	Change
	the base class indicating the possible changes More...
class	ArcAdd
	the class to indicate that we wish to add a new arc More...
class	ArcDel
	the class to indicate that we wish to remove an arc More...
class	ArcReverse
	the class to indicate that we wish to reverse an arc More...

Public Types
enum class	ChangeType { ARC_ADDITION , ARC_DELETION , ARC_REVERSAL }

Public Member Functions
Constructors / Destructors
	DAGCycleDetector () noexcept
	default constructor
	DAGCycleDetector (const DAGCycleDetector &from)
	copy constructor
	DAGCycleDetector (DAGCycleDetector &&from)
	move constructor
	~DAGCycleDetector ()
	destructor
Operators
DAGCycleDetector &	operator= (const DAGCycleDetector &from)
	copy operator
DAGCycleDetector &	operator= (DAGCycleDetector &&from)
	move operator
bool	operator== (const DAGCycleDetector &from) const
	check the equality between two DAGCycleDetectors
bool	operator!= (const DAGCycleDetector &from) const
	check the inequality between two DAGCycleDetectors
Accessors/Modifiers
void	setDAG (const DAG &dag)
	sets the initial DAG from which changes shall be applied
void	addArc (NodeId x, NodeId y)
	adds a new arc to the current DAG
void	eraseArc (NodeId x, NodeId y)
	removes an arc from the current DAG
void	reverseArc (NodeId x, NodeId y)
	reverses an arc from the DAG
bool	hasCycleFromAddition (NodeId x, NodeId y) const noexcept
	indicates whether an arc addition would create a cycle
bool	hasCycleFromReversal (NodeId x, NodeId y) const noexcept
	indicates wether an arc reversal would create a cycle
bool	hasCycleFromDeletion (NodeId x, NodeId y) const noexcept
	indicates whether an arc deletion would create a cycle
bool	hasCycleFromModifications (const std::vector< Change > &modifs) const
	indicates whether a set of modifications would create a cycle

Private Member Functions
void	_addWeightedSet_ (NodeProperty< Size > &nodeset, const NodeProperty< Size > &set_to_add, Size multiplier) const
	adds a weighted nodeset to another (weights are added)
void	_delWeightedSet_ (NodeProperty< Size > &nodeset, const NodeProperty< Size > &set_to_del, Size multiplier) const
	removes a weighted nodeset from another (weights are subtracted)
void	_restrictWeightedSet_ (NodeProperty< Size > &result_set, const NodeProperty< Size > &set_to_restrict, const NodeSet &extrmities) const
	put into a weighted nodeset the nodes of another weighted set that belong to a set of arc extremities

Private Attributes
DiGraph	_dag_
	the initial dag from which modifications are applied
NodeProperty< NodeProperty< Size > >	_ancestors_
	the set of ancestors of each node in the dag
NodeProperty< NodeProperty< Size > >	_descendants_
	the set of descendants of each node in the dag

Detailed Description

A class for detecting directed cycles in DAGs when trying to apply many changes to the graph.

When trying to assess whether multiple changes applied to a given DAG would induce cycles, use class DAGCycleDetector instead of trying to apply the modifications to the DAG itself and check whether and exception is raised: the class is designed to be fast for such modifications. However, the number of modifications checked should be higher than at least 3 for this class to be competitive.

Definition at line 81 of file DAGCycleDetector.h.

Member Enumeration Documentation

ChangeType

enum class gum::DAGCycleDetector::ChangeType

strong

Enumerator
ARC_ADDITION
ARC_DELETION
ARC_REVERSAL

Definition at line 84 of file DAGCycleDetector.h.

{ ARC_ADDITION, ARC_DELETION, ARC_REVERSAL };

Constructor & Destructor Documentation

DAGCycleDetector() [1/3]

INLINE gum::DAGCycleDetector::DAGCycleDetector ( )

noexcept

default constructor

Definition at line 245 of file DAGCycleDetector_inl.h.

{ GUM_CONSTRUCTOR(DAGCycleDetector); }

References DAGCycleDetector().

Referenced by DAGCycleDetector(), DAGCycleDetector(), DAGCycleDetector(), ~DAGCycleDetector(), operator!=(), operator=(), operator=(), and operator==().

Here is the call graph for this function:

Here is the caller graph for this function:

DAGCycleDetector() [2/3]

INLINE gum::DAGCycleDetector::DAGCycleDetector

(

const DAGCycleDetector &

from

)

copy constructor

Definition at line 248 of file DAGCycleDetector_inl.h.

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

References DAGCycleDetector(), _ancestors_, _dag_, and _descendants_.

Here is the call graph for this function:

DAGCycleDetector() [3/3]

INLINE gum::DAGCycleDetector::DAGCycleDetector

(

DAGCycleDetector &&

from

)

move constructor

Definition at line 254 of file DAGCycleDetector_inl.h.

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

References DAGCycleDetector(), _ancestors_, _dag_, and _descendants_.

Here is the call graph for this function:

~DAGCycleDetector()

INLINE gum::DAGCycleDetector::~DAGCycleDetector

(

)

destructor

Definition at line 261 of file DAGCycleDetector_inl.h.

{ GUM_DESTRUCTOR(DAGCycleDetector); }

References DAGCycleDetector().

Here is the call graph for this function:

Member Function Documentation

_addWeightedSet_()

INLINE void gum::DAGCycleDetector::_addWeightedSet_ ( NodeProperty< Size > & nodeset, const NodeProperty< Size > & set_to_add, Size multiplier ) const

private

adds a weighted nodeset to another (weights are added)

adds a nodeset to another (nodes are weighted, so weights are added)

Definition at line 303 of file DAGCycleDetector_inl.h.

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

References gum::HashTable< Key, Val >::cbegin(), gum::HashTable< Key, Val >::cend(), gum::HashTable< Key, Val >::exists(), and gum::HashTable< Key, Val >::insert().

Referenced by addArc(), hasCycleFromModifications(), and setDAG().

Here is the call graph for this function:

Here is the caller graph for this function:

_delWeightedSet_()

INLINE void gum::DAGCycleDetector::_delWeightedSet_ ( NodeProperty< Size > & nodeset, const NodeProperty< Size > & set_to_del, Size multiplier ) const

private

removes a weighted nodeset from another (weights are subtracted)

Definition at line 317 of file DAGCycleDetector_inl.h.

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

References gum::HashTable< Key, Val >::cbegin(), gum::HashTable< Key, Val >::cend(), gum::HashTable< Key, Val >::erase(), and gum::HashTable< Key, Val >::exists().

Referenced by eraseArc(), and hasCycleFromModifications().

Here is the call graph for this function:

Here is the caller graph for this function:

_restrictWeightedSet_()

INLINE void gum::DAGCycleDetector::_restrictWeightedSet_ ( NodeProperty< Size > & result_set, const NodeProperty< Size > & set_to_restrict, const NodeSet & extrmities ) const

private

put into a weighted nodeset the nodes of another weighted set that belong to a set of arc extremities

Definition at line 333 of file DAGCycleDetector_inl.h.

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

References gum::HashTable< Key, Val >::cbegin(), gum::HashTable< Key, Val >::cend(), gum::Set< Key >::exists(), and gum::HashTable< Key, Val >::insert().

Referenced by hasCycleFromModifications().

Here is the call graph for this function:

Here is the caller graph for this function:

addArc()

void gum::DAGCycleDetector::addArc	(	NodeId	x,
		NodeId	y )

adds a new arc to the current DAG

worst case complexity: O(h^2) where h is the height of the DAG

Exceptions

InvalidDirectedCycle

if the arc would create a cycle in the dag

Definition at line 310 of file DAGCycleDetector.cpp.

                                                        {
    // check that the arc does not already exist
    if (_dag_.existsArc(tail, head)) return;
 
    // check that the arc would not create a cycle
    if (hasCycleFromAddition(tail, head)) {
      GUM_ERROR(InvalidDirectedCycle, "the arc would create a directed into a DAG")
    }
 
    _dag_.addArc(tail, head);
 
    // now we apply the addition of the arc as done in method
    // hasCycleFromModifications
    const NodeProperty< Size >& anc_tail  = _ancestors_[tail];
    const NodeProperty< Size >& desc_head = _descendants_[head];
 
    // update the set of ancestors
    NodeProperty< Size > set_to_add = anc_tail;
    set_to_add.insert(tail, 1);
    _addWeightedSet_(_ancestors_[head], set_to_add, 1);
 
    for (auto iter = desc_head.cbegin(); iter != desc_head.cend(); ++iter) {
      _addWeightedSet_(_ancestors_[iter.key()], set_to_add, _ancestors_[iter.key()][head]);
    }
 
    // update the set of descendants
    set_to_add = desc_head;
    set_to_add.insert(head, 1);
    _addWeightedSet_(_descendants_[tail], set_to_add, 1);
 
    for (auto iter = anc_tail.cbegin(); iter != anc_tail.cend(); ++iter) {
      _addWeightedSet_(_descendants_[iter.key()], set_to_add, _descendants_[iter.key()][tail]);
    }
  }

References _addWeightedSet_(), _ancestors_, _dag_, _descendants_, gum::HashTable< Key, Val >::cbegin(), gum::HashTable< Key, Val >::cend(), GUM_ERROR, hasCycleFromAddition(), and gum::HashTable< Key, Val >::insert().

Referenced by reverseArc().

Here is the call graph for this function:

Here is the caller graph for this function:

eraseArc()

void gum::DAGCycleDetector::eraseArc	(	NodeId	x,
		NodeId	y )

removes an arc from the current DAG

worst case complexity: O(h^2) where h is the height of the DAG

Definition at line 346 of file DAGCycleDetector.cpp.

                                                          {
    // check that the arc exists
    if (!_dag_.existsArc(tail, head)) return;
 
    _dag_.eraseArc(Arc(tail, head));
 
    // we apply the deletion of the arc as done in method
    // hasCycleFromModifications
    const NodeProperty< Size >& anc_tail  = _ancestors_[tail];
    const NodeProperty< Size >& desc_head = _descendants_[head];
 
    // update the set of descendants
    NodeProperty< Size > set_to_del = desc_head;
    set_to_del.insert(head, 1);
    _delWeightedSet_(_descendants_[tail], set_to_del, 1);
 
    for (auto iter = anc_tail.cbegin(); iter != anc_tail.cend(); ++iter) {
      _delWeightedSet_(_descendants_[iter.key()], set_to_del, _descendants_[iter.key()][tail]);
    }
 
    // update the set of ancestors
    set_to_del = anc_tail;
    set_to_del.insert(tail, 1);
    _delWeightedSet_(_ancestors_[head], set_to_del, 1);
 
    for (auto iter = desc_head.cbegin(); iter != desc_head.cend(); ++iter) {
      _delWeightedSet_(_ancestors_[iter.key()], set_to_del, _ancestors_[iter.key()][head]);
    }
  }

References _ancestors_, _dag_, _delWeightedSet_(), _descendants_, gum::HashTable< Key, Val >::cbegin(), gum::HashTable< Key, Val >::cend(), and gum::HashTable< Key, Val >::insert().

Referenced by reverseArc().

Here is the call graph for this function:

Here is the caller graph for this function:

hasCycleFromAddition()

INLINE bool gum::DAGCycleDetector::hasCycleFromAddition ( NodeId x, NodeId y ) const

noexcept

indicates whether an arc addition would create a cycle

worst case complexity: O(1)

Definition at line 287 of file DAGCycleDetector_inl.h.

                                                                                      {
    return _descendants_[y].exists(x);
  }

References _descendants_.

Referenced by addArc().

Here is the caller graph for this function:

hasCycleFromDeletion()

INLINE bool gum::DAGCycleDetector::hasCycleFromDeletion ( NodeId x, NodeId y ) const

noexcept

indicates whether an arc deletion would create a cycle

worst case complexity: O(1)

Definition at line 297 of file DAGCycleDetector_inl.h.

                                                                                      {
    return false;
  }

hasCycleFromModifications()

bool gum::DAGCycleDetector::hasCycleFromModifications

(

const std::vector< Change > &

modifs

)

const

indicates whether a set of modifications would create a cycle

the Boolean returned corresponds to the existence (or not) of a cycle on the graph resulting from the whole sequence of modifications. This means, for instance, that if, among modifs, there exists an arc (X,Y) addition involving a cycle but also the same arc (X,Y) deletion, the final graph obtained does not contains a cycle (due to the deletion) and the method will thus return false.

Definition at line 134 of file DAGCycleDetector.cpp.

                                                                                          {
    // first, we separate deletions and insertions (reversals are cut into
    // a deletion + an insertion) and we check that no insertion also exists
    // as a deletion (if so, we remove both operations). In addition, if
    // we try to add an arc (X,X) we return that it induces a cycle
    HashTable< Arc, Size > deletions(Size(modifs.size()));
    HashTable< Arc, Size > additions(Size(modifs.size()));
 
    for (const auto& modif: modifs) {
      Arc arc(modif.tail(), modif.head());
 
      switch (modif.type()) {
        case ChangeType::ARC_DELETION :
          if (deletions.exists(arc)) ++deletions[arc];
          else deletions.insert(arc, 1);
 
          break;
 
        case ChangeType::ARC_ADDITION :
          if (modif.tail() == modif.head()) return true;
 
          if (additions.exists(arc)) ++additions[arc];
          else additions.insert(arc, 1);
 
          break;
 
        case ChangeType::ARC_REVERSAL :
          if (deletions.exists(arc)) ++deletions[arc];
          else deletions.insert(arc, 1);
 
          arc = Arc(modif.head(), modif.tail());
 
          if (additions.exists(arc)) ++additions[arc];
          else additions.insert(arc, 1);
 
          break;
 
        default : GUM_ERROR(OperationNotAllowed, "undefined change type")
      }
    }
 
    for (auto iter = additions.beginSafe();   // safe iterator needed here
         iter != additions.endSafe();
         ++iter) {
      if (deletions.exists(iter.key())) {
        Size& nb_del = deletions[iter.key()];
        Size& nb_add = iter.val();
 
        if (nb_del > nb_add) {
          additions.erase(iter);
          nb_del -= nb_add;
        } else if (nb_del < nb_add) {
          deletions.erase(iter.key());
          nb_add -= nb_del;
        } else {
          deletions.erase(iter.key());
          additions.erase(iter);
        }
      }
    }
 
    // get the set of nodes involved in the modifications
    NodeSet extremities;
 
    for (const auto& modif: modifs) {
      extremities.insert(modif.tail());
      extremities.insert(modif.head());
    }
 
    // we now retrieve the set of ancestors and descendants of all the
    // extremities of the arcs involved in the modifications. We also
    // keep track of all the children and parents of these nodes
    NodeProperty< NodeProperty< Size > > ancestors, descendants;
 
    for (const auto& modif: modifs) {
      if (!ancestors.exists(modif.tail())) {
        NodeProperty< Size >& anc = ancestors.insert(modif.tail(), NodeProperty< Size >()).second;
        _restrictWeightedSet_(anc, _ancestors_[modif.tail()], extremities);
 
        NodeProperty< Size >& desc
            = descendants.insert(modif.tail(), NodeProperty< Size >()).second;
        _restrictWeightedSet_(desc, _descendants_[modif.tail()], extremities);
      }
 
      if (!ancestors.exists(modif.head())) {
        NodeProperty< Size >& anc = ancestors.insert(modif.head(), NodeProperty< Size >()).second;
        _restrictWeightedSet_(anc, _ancestors_[modif.head()], extremities);
 
        NodeProperty< Size >& desc
            = descendants.insert(modif.head(), NodeProperty< Size >()).second;
        _restrictWeightedSet_(desc, _descendants_[modif.head()], extremities);
      }
    }
 
    // we apply all the suppressions:
    // assume that the modif concerns arc (X,Y). Then, after removing
    // arc (X,Y), the sets of descendants of the nodes T in
    // ( X + ancestors (X) ) are updated by subtracting the number of paths
    // leading to Y and its set of descendants. These numbers are equal to
    // the numbers found in descendants[X] * the numbers of paths leading
    // to X, i.e., descendants[T][X].
    // By symmetry, the set of ancestors of nodes T in ( Y + descendants (Y) )
    // are
    // updated by subtracting the number of paths leading to X and its
    // ancestors.
    for (auto iter = deletions.cbegin(); iter != deletions.cend(); ++iter) {
      const Arc&                  arc       = iter.key();
      const NodeId                tail      = arc.tail();
      const NodeProperty< Size >& anc_tail  = ancestors[tail];
      const NodeId                head      = arc.head();
      const NodeProperty< Size >& desc_head = descendants[head];
 
      // update the set of descendants
      NodeProperty< Size > set_to_del = desc_head;
      set_to_del.insert(head, 1);
      _delWeightedSet_(descendants[tail], set_to_del, 1);
 
      for (auto iter = anc_tail.cbegin(); iter != anc_tail.cend(); ++iter) {
        _delWeightedSet_(descendants[iter.key()], set_to_del, descendants[iter.key()][tail]);
      }
 
      // update the set of ancestors
      set_to_del = anc_tail;
      set_to_del.insert(tail, 1);
      _delWeightedSet_(ancestors[head], set_to_del, 1);
 
      for (auto iter = desc_head.cbegin(); iter != desc_head.cend(); ++iter) {
        _delWeightedSet_(ancestors[iter.key()], set_to_del, ancestors[iter.key()][head]);
      }
    }
 
    // now we apply all the additions of arcs (including the additions after
    // arc reversals). After adding arc (X,Y), the set of ancestors T of Y and
    // its
    // descendants shall be updated by adding the number of paths leading to
    // X and its ancestors, i.e., ancestors[X] * the number of paths leading
    // to Y, i.e., ancestors[T][Y]. Similarly, the set of descendants of X and
    // its
    // ancestors should be updated by adding the number of paths leading to Y
    // and
    // its descendants. Finally, an arc (X,Y) can be added if and
    // only if Y does not belong to the ancestor set of X
    for (auto iter = additions.cbegin(); iter != additions.cend(); ++iter) {
      const Arc& arc  = iter.key();
      NodeId     tail = arc.tail();
      NodeId     head = arc.head();
 
      const NodeProperty< Size >& anc_tail = ancestors[tail];
 
      if (anc_tail.exists(head)) { return true; }
 
      const NodeProperty< Size >& desc_head = descendants[head];
 
      // update the set of ancestors
      NodeProperty< Size > set_to_add = anc_tail;
      set_to_add.insert(tail, 1);
      _addWeightedSet_(ancestors[head], set_to_add, 1);
 
      for (auto iter = desc_head.cbegin(); iter != desc_head.cend(); ++iter) {
        _addWeightedSet_(ancestors[iter.key()], set_to_add, ancestors[iter.key()][head]);
      }
 
      // update the set of descendants
      set_to_add = desc_head;
      set_to_add.insert(head, 1);
      _addWeightedSet_(descendants[tail], set_to_add, 1);
 
      for (auto iter = anc_tail.cbegin(); iter != anc_tail.cend(); ++iter) {
        _addWeightedSet_(descendants[iter.key()], set_to_add, descendants[iter.key()][tail]);
      }
    }
 
    return false;
  }

References _addWeightedSet_(), _ancestors_, _delWeightedSet_(), _descendants_, _restrictWeightedSet_(), ARC_ADDITION, ARC_DELETION, ARC_REVERSAL, gum::HashTable< Key, Val >::beginSafe(), gum::HashTable< Key, Val >::cbegin(), gum::HashTable< Key, Val >::cend(), gum::HashTable< Key, Val >::endSafe(), gum::HashTable< Key, Val >::erase(), gum::HashTable< Key, Val >::exists(), GUM_ERROR, gum::Arc::head(), gum::HashTable< Key, Val >::insert(), gum::Set< Key >::insert(), and gum::Arc::tail().

Here is the call graph for this function:

hasCycleFromReversal()

INLINE bool gum::DAGCycleDetector::hasCycleFromReversal ( NodeId x, NodeId y ) const

noexcept

indicates wether an arc reversal would create a cycle

worst case complexity: O(1)

Definition at line 292 of file DAGCycleDetector_inl.h.

                                                                                      {
    return (_ancestors_[y][x] > 1);
  }

References _ancestors_.

Referenced by reverseArc().

Here is the caller graph for this function:

operator!=()

INLINE bool gum::DAGCycleDetector::operator!=

(

const DAGCycleDetector &

from

)

const

check the inequality between two DAGCycleDetectors

used essentally for debugging purposes

Definition at line 358 of file DAGCycleDetector_inl.h.

                                                                           {
    return !operator==(from);
  }

References DAGCycleDetector(), and operator==().

Here is the call graph for this function:

operator=() [1/2]

INLINE DAGCycleDetector & gum::DAGCycleDetector::operator=

(

const DAGCycleDetector &

from

)

copy operator

Definition at line 265 of file DAGCycleDetector_inl.h.

                                                                          {
    if (this != &from) {
      _dag_         = from._dag_;
      _ancestors_   = from._ancestors_;
      _descendants_ = from._descendants_;
    }
 
    return *this;
  }

References DAGCycleDetector(), _ancestors_, _dag_, and _descendants_.

Here is the call graph for this function:

operator=() [2/2]

INLINE DAGCycleDetector & gum::DAGCycleDetector::operator=

(

DAGCycleDetector &&

from

)

move operator

Definition at line 276 of file DAGCycleDetector_inl.h.

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

References DAGCycleDetector(), _ancestors_, _dag_, and _descendants_.

Here is the call graph for this function:

operator==()

INLINE bool gum::DAGCycleDetector::operator==

(

const DAGCycleDetector &

from

)

const

check the equality between two DAGCycleDetectors

used essentally for debugging purposes

Definition at line 352 of file DAGCycleDetector_inl.h.

                                                                           {
    return (   //(  _dagmodel_ == from. _dagmodel_ ) &&
        (_ancestors_ == from._ancestors_) && (_descendants_ == from._descendants_));
  }

References DAGCycleDetector(), _ancestors_, and _descendants_.

Referenced by operator!=().

Here is the call graph for this function:

Here is the caller graph for this function:

reverseArc()

INLINE void gum::DAGCycleDetector::reverseArc	(	NodeId	x,
		NodeId	y )

reverses an arc from the DAG

worst case complexity: O(h^2) where h is the height of the DAG

Exceptions

InvalidDirectedCycle

if the arc reversal would create a cycle in the dag

Definition at line 342 of file DAGCycleDetector_inl.h.

                                                                   {
    if (hasCycleFromReversal(tail, head)) {
      GUM_ERROR(InvalidDirectedCycle, "the arc would create a directed into a DAG")
    }
 
    eraseArc(tail, head);
    addArc(head, tail);
  }

References addArc(), eraseArc(), GUM_ERROR, and hasCycleFromReversal().

Here is the call graph for this function:

setDAG()

void gum::DAGCycleDetector::setDAG

(

const DAG &

dag

)

sets the initial DAG from which changes shall be applied

Definition at line 65 of file DAGCycleDetector.cpp.

                                              {
    // sets the dag
    _dag_ = dag;
 
    // get the set of roots and leaves of the dag
    List< NodeId >       roots, leaves;
    NodeProperty< Size > nb_parents, nb_children;
 
    for (const auto node: dag) {
      Size nb_ch = dag.children(node).size();
      nb_children.insert(node, nb_ch);
 
      if (!nb_ch) leaves.insert(node);
 
      Size nb_pa = dag.parents(node).size();
      nb_parents.insert(node, nb_pa);
 
      if (!nb_pa) roots.insert(node);
    }
 
    // recompute the set of ancestors
    NodeProperty< Size > empty_set;
    _ancestors_.clear();
 
    for (NodeId node: dag) {
      _ancestors_.insert(node, empty_set);
    }
 
    while (!roots.empty()) {
      // get a node and update the ancestors of its children
      NodeId               node           = roots.front();
      NodeProperty< Size > node_ancestors = _ancestors_[node];
      node_ancestors.insert(node, 1);
      const NodeSet& node_children = dag.children(node);
      roots.popFront();
 
      for (const auto ch: node_children) {
        _addWeightedSet_(_ancestors_[ch], node_ancestors, 1);
        --nb_parents[ch];
 
        if (!nb_parents[ch]) { roots.insert(ch); }
      }
    }
 
    // recompute the set of descendants
    _descendants_.clear();
 
    for (const auto node: dag) {
      _descendants_.insert(node, empty_set);
    }
 
    while (!leaves.empty()) {
      // get a node and update the descendants of its parents
      NodeId               node             = leaves.front();
      NodeProperty< Size > node_descendants = _descendants_[node];
      node_descendants.insert(node, 1);
      const NodeSet& node_parents = dag.parents(node);
      leaves.popFront();
 
      for (const auto pa: node_parents) {
        _addWeightedSet_(_descendants_[pa], node_descendants, 1);
        --nb_children[pa];
 
        if (!nb_children[pa]) { leaves.insert(pa); }
      }
    }
  }

References _addWeightedSet_(), _ancestors_, _dag_, _descendants_, gum::ArcGraphPart::children(), gum::List< Val >::empty(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::insert(), gum::ArcGraphPart::parents(), gum::List< Val >::popFront(), and gum::Set< Key >::size().

Here is the call graph for this function:

Member Data Documentation

_ancestors_

NodeProperty< NodeProperty< Size > > gum::DAGCycleDetector::_ancestors_

private

the set of ancestors of each node in the dag

for each ancestor, we keep track of the number of paths leading to it

Definition at line 339 of file DAGCycleDetector.h.

Referenced by DAGCycleDetector(), DAGCycleDetector(), addArc(), eraseArc(), hasCycleFromModifications(), hasCycleFromReversal(), operator=(), operator=(), operator==(), and setDAG().

_dag_

DiGraph gum::DAGCycleDetector::_dag_

private

the initial dag from which modifications are applied

Definition at line 335 of file DAGCycleDetector.h.

Referenced by DAGCycleDetector(), DAGCycleDetector(), addArc(), eraseArc(), operator=(), operator=(), and setDAG().

_descendants_

NodeProperty< NodeProperty< Size > > gum::DAGCycleDetector::_descendants_

private

the set of descendants of each node in the dag

for each ancestor, we keep track of the number of paths leading to it

Definition at line 343 of file DAGCycleDetector.h.

Referenced by DAGCycleDetector(), DAGCycleDetector(), addArc(), eraseArc(), hasCycleFromAddition(), hasCycleFromModifications(), operator=(), operator=(), operator==(), and setDAG().

---

The documentation for this class was generated from the following files:

• agrum/base/graphs/algorithms/DAGCycleDetector.h
• agrum/base/graphs/algorithms/DAGCycleDetector.cpp
• agrum/base/graphs/algorithms/DAGCycleDetector_inl.h