gum::learning::StructuralConstraintDAG Class Reference

The base class for structural constraints imposed by DAGs. More...

#include <structuralConstraintDAG.h>

Inheritance diagram for gum::learning::StructuralConstraintDAG:

Collaboration diagram for gum::learning::StructuralConstraintDAG:

Public Types
using	allConstraints = _ConstraintSet_< void >

Public Member Functions
Constructors / Destructors
	StructuralConstraintDAG ()
	default constructor
	StructuralConstraintDAG (Size nb_nodes)
	constructor starting with an empty graph with a given number of nodes
	StructuralConstraintDAG (const DAG &graph)
	constructor starting with a given graph
	StructuralConstraintDAG (const StructuralConstraintDAG &from)
	copy constructor
	StructuralConstraintDAG (StructuralConstraintDAG &&from) noexcept
	move constructor
virtual	~StructuralConstraintDAG ()
	destructor
Operators
StructuralConstraintDAG &	operator= (const StructuralConstraintDAG &from)
	copy operator
StructuralConstraintDAG &	operator= (StructuralConstraintDAG &&from)
	move operator
Specific Accessors / Modifiers
void	setGraphAlone (const DiGraph &graph)
	sets a new graph from which we will perform checking
void	setGraphAlone (Size nb_nodes)
	sets a new empty graph from which we will perform checking
void	modifyGraphAlone (const ArcAddition &change)
	notify the constraint of a modification of the graph
void	modifyGraphAlone (const ArcDeletion &change)
	notify the constraint of a modification of the graph
void	modifyGraphAlone (const ArcReversal &change)
	notify the constraint of a modification of the graph
void	modifyGraphAlone (const ArcTriangleDeletion1 &change)
	notify the constraint of a modification of the graph
void	modifyGraphAlone (const ArcTriangleDeletion2 &change)
	notify the constraint of a modification of the graph
void	modifyGraphAlone (const GraphChange &change)
	notify the constraint of a modification of the graph
bool	isAlwaysInvalidAlone (const GraphChange &change) const
	indicates whether a change will always violate the constraint
bool	checkArcAdditionAlone (NodeId x, NodeId y) const
	checks whether the constraints enable to add arc (x,y)
bool	checkArcDeletionAlone (NodeId x, NodeId y) const
	checks whether the constraints enable to remove arc (x,y)
bool	checkArcReversalAlone (NodeId x, NodeId y) const
	checks whether the constraints enable to reverse arc (x,y)
bool	checkArcTriangleDeletion1Alone (NodeId node1, NodeId node2, NodeId node3) const
	checks whether the constraints enable to apply an ArcTriangleDeletion1
bool	checkArcTriangleDeletion2Alone (NodeId node1, NodeId node2, NodeId node3) const
	checks whether the constraints enable to apply an ArcTriangleDeletion2
bool	checkModificationAlone (const ArcAddition &change) const
	checks whether the constraints enable to add an arc
bool	checkModificationAlone (const ArcDeletion &change) const
	checks whether the constraints enable to remove an arc
bool	checkModificationAlone (const ArcReversal &change) const
	checks whether the constraints enable to reverse an arc
bool	checkModificationAlone (const ArcTriangleDeletion1 &change) const
	checks whether the constraints enable to apply an ArcTriangleDeletion1
bool	checkModificationAlone (const ArcTriangleDeletion2 &change) const
	checks whether the constraints enable to apply an ArcTriangleDeletion2
bool	checkModificationAlone (const GraphChange &change) const
	checks whether the constraints enable to perform a graph change
void	setGraph (const DAG &graph)
	sets a new graph from which we will perform checking
void	setGraph (Size nb_nodes)
	sets a new empty graph from which we will perform checking

Private Member Functions
void	_lock_ () const
	the method to lock a critical region in order to modify graph
void	_unlock_ () const
	the methode to release a critical region used to modify graph

Private Attributes
DiGraph	_graph_
std::atomic_flag	_lock_flag_ = ATOMIC_FLAG_INIT

Detailed Description

The base class for structural constraints imposed by DAGs.

This base should always be a virtual parents of the structural constraints classes. This will allow to combine different constraints into a single class

Definition at line 69 of file structuralConstraintDAG.h.

Member Typedef Documentation

allConstraints

using gum::learning::StructuralConstraintEmpty::allConstraints = _ConstraintSet_< void >

inherited

Definition at line 61 of file structuralConstraint.h.

Constructor & Destructor Documentation

StructuralConstraintDAG() [1/5]

gum::learning::StructuralConstraintDAG::StructuralConstraintDAG

(

)

default constructor

Definition at line 59 of file structuralConstraintDAG.cpp.

{ GUM_CONSTRUCTOR(StructuralConstraintDAG); }

References StructuralConstraintDAG().

Referenced by StructuralConstraintDAG(), StructuralConstraintDAG(), StructuralConstraintDAG(), StructuralConstraintDAG(), StructuralConstraintDAG(), ~StructuralConstraintDAG(), operator=(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

StructuralConstraintDAG() [2/5]

gum::learning::StructuralConstraintDAG::StructuralConstraintDAG

(

Size

nb_nodes

)

constructor starting with an empty graph with a given number of nodes

Definition at line 62 of file structuralConstraintDAG.cpp.

                                                                  {
      setGraph(nb_nodes);
      GUM_CONSTRUCTOR(StructuralConstraintDAG);
    }

References StructuralConstraintDAG(), and setGraph().

Here is the call graph for this function:

StructuralConstraintDAG() [3/5]

gum::learning::StructuralConstraintDAG::StructuralConstraintDAG

(

const DAG &

graph

)

constructor starting with a given graph

Definition at line 68 of file structuralConstraintDAG.cpp.

                                                                     {
      setGraph(graph);
      GUM_CONSTRUCTOR(StructuralConstraintDAG);
    }

References StructuralConstraintDAG(), and setGraph().

Here is the call graph for this function:

StructuralConstraintDAG() [4/5]

gum::learning::StructuralConstraintDAG::StructuralConstraintDAG

(

const StructuralConstraintDAG &

from

)

copy constructor

Definition at line 74 of file structuralConstraintDAG.cpp.

                                                                                        :
        _graph_(from._graph_) {
      GUM_CONS_CPY(StructuralConstraintDAG);
    }

References StructuralConstraintDAG(), and _graph_.

Here is the call graph for this function:

StructuralConstraintDAG() [5/5]

gum::learning::StructuralConstraintDAG::StructuralConstraintDAG ( StructuralConstraintDAG && from )

noexcept

move constructor

Definition at line 80 of file structuralConstraintDAG.cpp.

                                                                                            :
        _graph_(std::move(from._graph_)) {
      GUM_CONS_MOV(StructuralConstraintDAG);
    }

References StructuralConstraintDAG(), and _graph_.

Here is the call graph for this function:

~StructuralConstraintDAG()

gum::learning::StructuralConstraintDAG::~StructuralConstraintDAG ( )

virtual

destructor

Definition at line 86 of file structuralConstraintDAG.cpp.

{ GUM_DESTRUCTOR(StructuralConstraintDAG); }

References StructuralConstraintDAG().

Here is the call graph for this function:

Member Function Documentation

_lock_()

void gum::learning::StructuralConstraintDAG::_lock_ ( ) const

private

the method to lock a critical region in order to modify graph

_unlock_()

void gum::learning::StructuralConstraintDAG::_unlock_ ( ) const

private

the methode to release a critical region used to modify graph

checkArcAdditionAlone()

bool gum::learning::StructuralConstraintDAG::checkArcAdditionAlone	(	NodeId	x,
		NodeId	y ) const

checks whether the constraints enable to add arc (x,y)

an arc can be added if and only if its extremal nodes belong to the graph and the arc does not already exist and would not create a cycle

Referenced by checkModificationAlone().

Here is the caller graph for this function:

checkArcDeletionAlone()

bool gum::learning::StructuralConstraintDAG::checkArcDeletionAlone	(	NodeId	x,
		NodeId	y ) const

checks whether the constraints enable to remove arc (x,y)

Referenced by checkModificationAlone().

Here is the caller graph for this function:

checkArcReversalAlone()

bool gum::learning::StructuralConstraintDAG::checkArcReversalAlone	(	NodeId	x,
		NodeId	y ) const

checks whether the constraints enable to reverse arc (x,y)

An arc (x,y) can be reversed if and only if it exists and, after deleting it, the addition of arc (y,x) does not induce a directed cycle.

Referenced by checkModificationAlone().

Here is the caller graph for this function:

checkArcTriangleDeletion1Alone()

bool gum::learning::StructuralConstraintDAG::checkArcTriangleDeletion1Alone	(	NodeId	node1,
		NodeId	node2,
		NodeId	node3 ) const

checks whether the constraints enable to apply an ArcTriangleDeletion1

An arc triangle deletion1 substitutes triangle node1 -> node2 -> node3 + node1 -> node3 into v-structure node2 -> node1 <- node3

Referenced by checkModificationAlone().

Here is the caller graph for this function:

checkArcTriangleDeletion2Alone()

bool gum::learning::StructuralConstraintDAG::checkArcTriangleDeletion2Alone	(	NodeId	node1,
		NodeId	node2,
		NodeId	node3 ) const

checks whether the constraints enable to apply an ArcTriangleDeletion2

An arc triangle deletion1 substitutes triangle node1 -> node2 -> node3 + node1 -> node3 into v-structure node1 -> node2 <- node3

Referenced by checkModificationAlone().

Here is the caller graph for this function:

checkModificationAlone() [1/6]

bool gum::learning::StructuralConstraintDAG::checkModificationAlone

(

const ArcAddition &

change

)

const

checks whether the constraints enable to add an arc

an arc can be added if and only if its extremal nodes belong to the graph and the arc does not already exist.

checkModificationAlone() [2/6]

bool gum::learning::StructuralConstraintDAG::checkModificationAlone

(

const ArcDeletion &

change

)

const

checks whether the constraints enable to remove an arc

an arc can be removed if and only if the arc exists.

checkModificationAlone() [3/6]

bool gum::learning::StructuralConstraintDAG::checkModificationAlone

(

const ArcReversal &

change

)

const

checks whether the constraints enable to reverse an arc

An arc can be reversed if, after deleting arc (x,y), the addition of arc (y,x) does not induce a directed cycle.

checkModificationAlone() [4/6]

bool gum::learning::StructuralConstraintDAG::checkModificationAlone

(

const ArcTriangleDeletion1 &

change

)

const

checks whether the constraints enable to apply an ArcTriangleDeletion1

An arc triangle deletion1 substitutes triangle node1 -> node2 -> node3 + node1 -> node3 into v-structure node2 -> node1 <- node3

checkModificationAlone() [5/6]

bool gum::learning::StructuralConstraintDAG::checkModificationAlone

(

const ArcTriangleDeletion2 &

change

)

const

checks whether the constraints enable to apply an ArcTriangleDeletion2

An arc triangle deletion1 substitutes triangle node1 -> node2 -> node3 + node1 -> node3 into v-structure node1 -> node2 <- node3

checkModificationAlone() [6/6]

bool gum::learning::StructuralConstraintDAG::checkModificationAlone

(

const GraphChange &

change

)

const

checks whether the constraints enable to perform a graph change

an arc can be added if and only if its extremal nodes belong to the graph and the arc does not already exist and would not create a cycle. An arc can be removed if and only if the arc exists. An arc can be reversed if, after deleting arc (x,y), the addition of arc (y,x) does not induce a directed cycle.

Definition at line 120 of file structuralConstraintDAG.cpp.

                                                                                        {
      switch (change.type()) {
        case GraphChangeType::ARC_ADDITION :
          return checkArcAdditionAlone(change.node1(), change.node2());
 
        case GraphChangeType::ARC_DELETION :
          return checkArcDeletionAlone(change.node1(), change.node2());
 
        case GraphChangeType::ARC_REVERSAL :
          return checkArcReversalAlone(change.node1(), change.node2());
 
        case GraphChangeType::ARC_TRIANGLE_DELETION1 :
          return checkArcTriangleDeletion1Alone(change.node1(), change.node2(), change.node3());
 
        case GraphChangeType::ARC_TRIANGLE_DELETION2 :
          return checkArcTriangleDeletion2Alone(change.node1(), change.node2(), change.node3());
 
        default :
          GUM_ERROR(OperationNotAllowed,
                    "Graph change operation "
                        << change.typeAsString()
                        << "is not supported by the DAG structural constraint");
      }
    }

References gum::learning::ARC_ADDITION, gum::learning::ARC_DELETION, gum::learning::ARC_REVERSAL, gum::learning::ARC_TRIANGLE_DELETION1, gum::learning::ARC_TRIANGLE_DELETION2, checkArcAdditionAlone(), checkArcDeletionAlone(), checkArcReversalAlone(), checkArcTriangleDeletion1Alone(), checkArcTriangleDeletion2Alone(), GUM_ERROR, gum::learning::GraphChange::node1(), gum::learning::GraphChange::node2(), gum::learning::GraphChange::node3(), gum::learning::GraphChange::type(), and gum::learning::GraphChange::typeAsString().

Here is the call graph for this function:

isAlwaysInvalidAlone()

bool gum::learning::StructuralConstraintDAG::isAlwaysInvalidAlone

(

const GraphChange &

change

)

const

indicates whether a change will always violate the constraint

Some learning algorithms need examine several times whether a given graph change can be applied. For instance, the first time arc (X,Y) addition is considered, the learning algorithm may discard this change because it violates the structural constraint (e.g., if the latter enforces a DAG structure, this arc addition might induce a directed cycle), but, later on, other arc removal may induce that the arc addition is now possible. Such change is thus not always invalid. Conversely, there are changes that can be discarded once and for all. For instance, in a 2TBN structure, it is always impossible to add a backward-time arc. Such graph changes are always invalid and are therefore tagged as such by the isAlwaysInvalid method.

modifyGraphAlone() [1/6]

void gum::learning::StructuralConstraintDAG::modifyGraphAlone

(

const ArcAddition &

change

)

notify the constraint of a modification of the graph

Warning

If an already existing arc is added nothing is done. In particular, no exception is raised.

Exceptions

InvalidNode	exception is thrown if an arc (x,y) is added and x or y does not belong to the graph nodes
InvalidDirectedCycle	exception is thrown if any (directed) cycle is created by the arc addition.

Referenced by modifyGraphAlone().

Here is the caller graph for this function:

modifyGraphAlone() [2/6]

void gum::learning::StructuralConstraintDAG::modifyGraphAlone

(

const ArcDeletion &

change

)

notify the constraint of a modification of the graph

Warning

If a nonexisting arc is removed, nothing is done. In particular, no exception is raised.

modifyGraphAlone() [3/6]

void gum::learning::StructuralConstraintDAG::modifyGraphAlone

(

const ArcReversal &

change

)

notify the constraint of a modification of the graph

Warning

If an already existing arc is added, or if a nonexisting arc is removed, nothing is done. In particular, no exception is raised.

Exceptions

InvalidNode	exception is thrown if at least one extremity of the arc does not belong to the graph nodes
InvalidDirectedCycle	exception is thrown if any (directed) cycle is created by the arc reversal.

modifyGraphAlone() [4/6]

void gum::learning::StructuralConstraintDAG::modifyGraphAlone

(

const ArcTriangleDeletion1 &

change

)

notify the constraint of a modification of the graph

An arc triangle deletion1 substitutes triangle node1 -> node2 -> node3 + node1 -> node3 into v-structure node2 -> node1 <- node3

modifyGraphAlone() [5/6]

void gum::learning::StructuralConstraintDAG::modifyGraphAlone

(

const ArcTriangleDeletion2 &

change

)

notify the constraint of a modification of the graph

An arc triangle deletion1 substitutes triangle node1 -> node2 -> node3 + node1 -> node3 into v-structure node1 -> node2 <- node3

modifyGraphAlone() [6/6]

void gum::learning::StructuralConstraintDAG::modifyGraphAlone

(

const GraphChange &

change

)

notify the constraint of a modification of the graph

Warning

If an already existing arc is added, or if a nonexisting arc is removed, nothing is done. In particular, no exception is raised.

Exceptions

InvalidNode	exception is thrown if an arc (x,y) is added and x or y does not belong to the graph nodes
InvalidDirectedCycle	exception is thrown if any (directed) cycle is created by an arc addition or reversal.

Definition at line 145 of file structuralConstraintDAG.cpp.

                                                                            {
      switch (change.type()) {
        case GraphChangeType::ARC_ADDITION :
          modifyGraphAlone(reinterpret_cast< const ArcAddition& >(change));
          break;
 
        case GraphChangeType::ARC_DELETION :
          modifyGraphAlone(reinterpret_cast< const ArcDeletion& >(change));
          break;
 
        case GraphChangeType::ARC_REVERSAL :
          modifyGraphAlone(reinterpret_cast< const ArcReversal& >(change));
          break;
 
        case GraphChangeType::ARC_TRIANGLE_DELETION1 :
          modifyGraphAlone(reinterpret_cast< const ArcTriangleDeletion1& >(change));
          break;
 
        case GraphChangeType::ARC_TRIANGLE_DELETION2 :
          modifyGraphAlone(reinterpret_cast< const ArcTriangleDeletion2& >(change));
          break;
 
        default :
          GUM_ERROR(OperationNotAllowed,
                    "Graph change operation "
                        << change.typeAsString()
                        << " is not supported by the DAG structural constraints")
      }
    }

References gum::learning::ARC_ADDITION, gum::learning::ARC_DELETION, gum::learning::ARC_REVERSAL, gum::learning::ARC_TRIANGLE_DELETION1, gum::learning::ARC_TRIANGLE_DELETION2, GUM_ERROR, modifyGraphAlone(), gum::learning::GraphChange::type(), and gum::learning::GraphChange::typeAsString().

Here is the call graph for this function:

operator=() [1/2]

StructuralConstraintDAG & gum::learning::StructuralConstraintDAG::operator=

(

const StructuralConstraintDAG &

from

)

copy operator

Definition at line 90 of file structuralConstraintDAG.cpp.

                                                                            {
      if (this != &from) { _graph_ = from._graph_; }
      return *this;
    }

References StructuralConstraintDAG(), and _graph_.

Here is the call graph for this function:

operator=() [2/2]

StructuralConstraintDAG & gum::learning::StructuralConstraintDAG::operator=

(

StructuralConstraintDAG &&

from

)

move operator

Definition at line 96 of file structuralConstraintDAG.cpp.

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

References StructuralConstraintDAG(), and _graph_.

Here is the call graph for this function:

setGraph() [1/2]

void gum::learning::StructuralConstraintDAG::setGraph

(

const DAG &

graph

)

sets a new graph from which we will perform checking

Referenced by StructuralConstraintDAG(), and StructuralConstraintDAG().

Here is the caller graph for this function:

setGraph() [2/2]

void gum::learning::StructuralConstraintDAG::setGraph

(

Size

nb_nodes

)

sets a new empty graph from which we will perform checking

setGraphAlone() [1/2]

void gum::learning::StructuralConstraintDAG::setGraphAlone

(

const DiGraph &

graph

)

sets a new graph from which we will perform checking

Definition at line 101 of file structuralConstraintDAG.cpp.

                                                                    {
      // check that the digraph contains no directed cycle
      DiGraph g;
 
      for (auto node: graph)
        g.addNodeWithId(node);
 
      for (auto& arc: graph.arcs()) {
        if (graph::hasDirectedPath(g, arc.head(), arc.tail())) {
          GUM_ERROR(InvalidDirectedCycle,
                    "Graphs with directed cycles cannot be passed to StructuralConstraintDAG");
        }
        g.addArc(arc.tail(), arc.head());
      }
 
      // ok, here, there is no directed cycle
      _graph_ = std::move(g);
    }

References _graph_, gum::DiGraph::addArc(), gum::NodeGraphPart::addNodeWithId(), GUM_ERROR, and gum::graph::hasDirectedPath().

Here is the call graph for this function:

setGraphAlone() [2/2]

void gum::learning::StructuralConstraintDAG::setGraphAlone

(

Size

nb_nodes

)

sets a new empty graph from which we will perform checking

Member Data Documentation

_graph_

DiGraph gum::learning::StructuralConstraintDAG::_graph_

mutableprivate

Definition at line 268 of file structuralConstraintDAG.h.

Referenced by StructuralConstraintDAG(), StructuralConstraintDAG(), operator=(), operator=(), and setGraphAlone().

_lock_flag_

std::atomic_flag gum::learning::StructuralConstraintDAG::_lock_flag_ = ATOMIC_FLAG_INIT

mutableprivate

Definition at line 277 of file structuralConstraintDAG.h.

---

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

• agrum/BN/learning/constraints/structuralConstraintDAG.h
• agrum/BN/learning/constraints/structuralConstraintDAG.cpp