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:

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

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

Classes
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...
class	Change
	the base class indicating the possible changes More...

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 61 of file DAGCycleDetector.h.

Member Enumeration Documentation

ChangeType

enum gum::DAGCycleDetector::ChangeType

strong

Enumerator
ARC_ADDITION
ARC_DELETION
ARC_REVERSAL

Definition at line 64 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 226 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ GUM_CONSTRUCTOR(DAGCycleDetector); }

Here is the call graph for this function:

DAGCycleDetector() [2/3]

INLINE gum::DAGCycleDetector::DAGCycleDetector

(

const DAGCycleDetector &

from

)

copy constructor

Definition at line 229 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

DAGCycleDetector() [3/3]

INLINE gum::DAGCycleDetector::DAGCycleDetector

(

DAGCycleDetector &&

from

)

move constructor

Definition at line 235 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

~DAGCycleDetector()

INLINE gum::DAGCycleDetector::~DAGCycleDetector

(

)

destructor

Definition at line 242 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ GUM_DESTRUCTOR(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 284 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 298 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 314 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 299 of file DAGCycleDetector.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 335 of file DAGCycleDetector.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 268 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 278 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 114 of file DAGCycleDetector.cpp.

References gum::Set< Key, Alloc >::emplace().

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

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 273 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 339 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                             {
    return !operator==(from);
  }

Here is the call graph for this function:

operator=() [1/2]

INLINE DAGCycleDetector & gum::DAGCycleDetector::operator=

(

const DAGCycleDetector &

from

)

copy operator

Definition at line 246 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

    return *this;
  }

Here is the call graph for this function:

operator=() [2/2]

INLINE DAGCycleDetector & gum::DAGCycleDetector::operator=

(

DAGCycleDetector &&

from

)

move operator

Definition at line 257 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

    return *this;
  }

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 333 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 323 of file DAGCycleDetector_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

    eraseArc(tail, head);
    addArc(head, tail);
  }

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 45 of file DAGCycleDetector.cpp.

References gum::Set< Key, Alloc >::emplace().

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

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 324 of file DAGCycleDetector.h.

_dag_

DiGraph gum::DAGCycleDetector::_dag_

private

the initial dag from which modifications are applied

Definition at line 320 of file DAGCycleDetector.h.

_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 328 of file DAGCycleDetector.h.

---

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

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