aGrUM 3.1.1
a C++ library for (probabilistic) graphical models
gum::learning::StructuralConstraintTabuList Class Reference

The class imposing a N-sized tabu list as a structural constraints for learning algorithms. More...

#include <structuralConstraintTabuList.h>

Inheritance diagram for gum::learning::StructuralConstraintTabuList:
Collaboration diagram for gum::learning::StructuralConstraintTabuList:

Public Types

using allConstraints = _ConstraintSet_< void >

Public Member Functions

Constructors / Destructors
 StructuralConstraintTabuList ()
 default constructor
 StructuralConstraintTabuList (const DiGraph &graph)
 constructor starting with a given graph
 StructuralConstraintTabuList (const StructuralConstraintTabuList &from)
 copy constructor
 StructuralConstraintTabuList (StructuralConstraintTabuList &&from) noexcept
 move constructor
virtual ~StructuralConstraintTabuList ()
 destructor
Operators
StructuralConstraintTabuListoperator= (const StructuralConstraintTabuList &from)
 copy operator
StructuralConstraintTabuListoperator= (StructuralConstraintTabuList &&from)
 move operator
Specific Accessors / Modifiers
void setTabuListSize (Size new_size)
 sets the size of the tabu list
void setGraphAlone (const DiGraph &graph)
 sets a new graph from which we will perform checkings
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 GraphChange &change) const
 checks whether the constraints enable to perform a graph change
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

Protected Types

using GraphHash = std::pair< Size, Size >
 The representation of a graph: a graph is defined by its set of arcs.

Protected Member Functions

GraphHash _hashArc_ (NodeId node1, NodeId node2) const
GraphHash _xorHashes_ (const GraphHash &hash1, const GraphHash &hash2) const
GraphHash _xorWithCurrentGraph_ (const GraphHash &hash) const

Protected Attributes

Bijection< GraphHash, Size_graph_tabuList_
 the tabu list
Size _tabuList_offset_ {0}
 the index of the oldest element
Size _tabuList_size_
 the max size of the tabu list
GraphHash _current_graph_ {0, 0}
 the current graph hash

Detailed Description

The class imposing a N-sized tabu list as a structural constraints for learning algorithms.

By default, the size of the tabu list is 2, but it can be changed by the user using method setTabuSize (). Each time you modify the graph you learn, the inverse change is put into the tabu list. For instance, if the learning algorithm adds an arc (X, Y), then the "Deletion of Arc (X,Y)" operation is inserted into the tabu list. If the operation performed is an arc (X,Y) reversal, then the "Reversal of Arc (Y,X)" operation is added to the tabu list.

Definition at line 84 of file structuralConstraintTabuList.h.

Member Typedef Documentation

◆ allConstraints

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

Definition at line 61 of file structuralConstraint.h.

◆ GraphHash

The representation of a graph: a graph is defined by its set of arcs.

More precisely, each arc is hashed and the graph is a XOR of all these hash values. To be more robust, an arc hash value is a pair of Size generated by a hash function over the pair of nodes of the arc.

Definition at line 264 of file structuralConstraintTabuList.h.

Constructor & Destructor Documentation

◆ StructuralConstraintTabuList() [1/4]

gum::learning::StructuralConstraintTabuList::StructuralConstraintTabuList ( )

default constructor

Definition at line 61 of file structuralConstraintTabuList.cpp.

61 :
64 // insert the empty graph. The difference between the _tabuList_offset_ and
65 // the max offset in _graph_tabuList_ should always be equal to _tabuList_size_
67
68 GUM_CONSTRUCTOR(StructuralConstraintTabuList);
69 }
Bijection< GraphHash, Size > _graph_tabuList_
the tabu list
#define GUM_STRUCTURAL_CONSTRAINT_TABU_LIST_DEFAULT_SIZE

References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_size_, and GUM_STRUCTURAL_CONSTRAINT_TABU_LIST_DEFAULT_SIZE.

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ StructuralConstraintTabuList() [2/4]

gum::learning::StructuralConstraintTabuList::StructuralConstraintTabuList ( const DiGraph & graph)

constructor starting with a given graph

Definition at line 72 of file structuralConstraintTabuList.cpp.

72 :
75 // compute the hash value of the diGraph
76 for (const auto& arc: graph.arcs()) {
77 const auto hash_arc = _hashArc_(arc.tail(), arc.head());
78 _current_graph_.first ^= hash_arc.first;
79 _current_graph_.second ^= hash_arc.second;
80 }
81
82 // insert the graph hash. The difference between the _tabuList_offset_ and
83 // the max offset in _graph_tabuList_ should always be equal to _tabuList_size_
85
86 GUM_CONSTRUCTOR(StructuralConstraintTabuList);
87 }
GraphHash _hashArc_(NodeId node1, NodeId node2) const

References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_size_, and GUM_STRUCTURAL_CONSTRAINT_TABU_LIST_DEFAULT_SIZE.

Here is the call graph for this function:

◆ StructuralConstraintTabuList() [3/4]

gum::learning::StructuralConstraintTabuList::StructuralConstraintTabuList ( const StructuralConstraintTabuList & from)

copy constructor

Definition at line 90 of file structuralConstraintTabuList.cpp.

91 :
92 _graph_tabuList_(from._graph_tabuList_), _tabuList_offset_(from._tabuList_offset_),
93 _tabuList_size_(from._tabuList_size_), _current_graph_(from._current_graph_) {
94 GUM_CONS_CPY(StructuralConstraintTabuList);
95 }
Size _tabuList_offset_
the index of the oldest element

References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.

Here is the call graph for this function:

◆ StructuralConstraintTabuList() [4/4]

gum::learning::StructuralConstraintTabuList::StructuralConstraintTabuList ( StructuralConstraintTabuList && from)
noexcept

move constructor

Definition at line 98 of file structuralConstraintTabuList.cpp.

99 :
100 _graph_tabuList_(std::move(from._graph_tabuList_)),
101 _tabuList_offset_(from._tabuList_offset_), _tabuList_size_(from._tabuList_size_),
102 _current_graph_(std::move(from._current_graph_)) {
103 GUM_CONS_MOV(StructuralConstraintTabuList);
104 }

References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.

Here is the call graph for this function:

◆ ~StructuralConstraintTabuList()

gum::learning::StructuralConstraintTabuList::~StructuralConstraintTabuList ( )
virtual

destructor

Definition at line 107 of file structuralConstraintTabuList.cpp.

107 {
108 GUM_DESTRUCTOR(StructuralConstraintTabuList);
109 }

References StructuralConstraintTabuList().

Here is the call graph for this function:

Member Function Documentation

◆ _hashArc_()

GraphHash gum::learning::StructuralConstraintTabuList::_hashArc_ ( NodeId node1,
NodeId node2 ) const
protected

◆ _xorHashes_()

GraphHash gum::learning::StructuralConstraintTabuList::_xorHashes_ ( const GraphHash & hash1,
const GraphHash & hash2 ) const
protected

◆ _xorWithCurrentGraph_()

GraphHash gum::learning::StructuralConstraintTabuList::_xorWithCurrentGraph_ ( const GraphHash & hash) const
protected

◆ checkArcAdditionAlone()

bool gum::learning::StructuralConstraintTabuList::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.

Referenced by checkModificationAlone().

Here is the caller graph for this function:

◆ checkArcDeletionAlone()

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

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

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

Referenced by checkModificationAlone().

Here is the caller graph for this function:

◆ checkArcReversalAlone()

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

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

an arc can be reversed if and only if it exists and arc (y,x) does not.

Referenced by checkModificationAlone().

Here is the caller graph for this function:

◆ checkArcTriangleDeletion1Alone()

bool gum::learning::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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::StructuralConstraintTabuList::checkModificationAlone ( const ArcReversal & change) const

checks whether the constraints enable to reverse an arc

an arc (x,y) can be reversed if and only if it exists and arc (y,x) does not.

◆ checkModificationAlone() [4/6]

bool gum::learning::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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. An arc can be removed if and only if the arc exists. An arc (x,y) can be reversed if and only if it exists and arc (y,x) does not.

Definition at line 171 of file structuralConstraintTabuList.cpp.

171 {
172 switch (change.type()) {
174 return checkArcAdditionAlone(change.node1(), change.node2());
175
177 return checkArcDeletionAlone(change.node1(), change.node2());
178
180 return checkArcReversalAlone(change.node1(), change.node2());
181
183 return checkArcTriangleDeletion1Alone(change.node1(), change.node2(), change.node3());
184
186 return checkArcTriangleDeletion2Alone(change.node1(), change.node2(), change.node3());
187
188 default :
189 GUM_ERROR(OperationNotAllowed,
190 "Graph change operation "
191 << change.typeAsString()
192 << "is not supported by the Tabu List structural constraint");
193 }
194 }
bool checkArcTriangleDeletion1Alone(NodeId node1, NodeId node2, NodeId node3) const
checks whether the constraints enable to apply an ArcTriangleDeletion1
bool checkArcDeletionAlone(NodeId x, NodeId y) const
checks whether the constraints enable to remove arc (x,y)
bool checkArcAdditionAlone(NodeId x, NodeId y) const
checks whether the constraints enable to add arc (x,y)
bool checkArcReversalAlone(NodeId x, NodeId y) const
checks whether the constraints enable to reverse arc (x,y)
bool checkArcTriangleDeletion2Alone(NodeId node1, NodeId node2, NodeId node3) const
checks whether the constraints enable to apply an ArcTriangleDeletion2
#define GUM_ERROR(type, msg)
Definition exceptions.h:76

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::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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
InvalidNodeexception is thrown if an arc (x,y) is added and x or y does not belong to the graph nodes

Referenced by modifyGraphAlone().

Here is the caller graph for this function:

◆ modifyGraphAlone() [2/6]

void gum::learning::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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
InvalidNodeexception is thrown if at least one extremity of the arc does not belong to the graph nodes

◆ modifyGraphAlone() [4/6]

void gum::learning::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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::StructuralConstraintTabuList::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
InvalidNodeexception is thrown if an arc (x,y) is added and x or y does not belong to the graph nodes

Definition at line 196 of file structuralConstraintTabuList.cpp.

196 {
197 switch (change.type()) {
199 modifyGraphAlone(static_cast< const ArcAddition& >(change));
200 break;
201
203 modifyGraphAlone(static_cast< const ArcDeletion& >(change));
204 break;
205
207 modifyGraphAlone(static_cast< const ArcReversal& >(change));
208 break;
209
211 modifyGraphAlone(static_cast< const ArcTriangleDeletion1& >(change));
212 break;
213
215 modifyGraphAlone(static_cast< const ArcTriangleDeletion2& >(change));
216 break;
217
218 default :
219 GUM_ERROR(OperationNotAllowed,
220 "Graph change operation "
221 << change.typeAsString()
222 << " is not supported by Tabu List structural constraint")
223 }
224 }
void modifyGraphAlone(const ArcAddition &change)
notify the constraint of a modification of the graph

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]

StructuralConstraintTabuList & gum::learning::StructuralConstraintTabuList::operator= ( const StructuralConstraintTabuList & from)

copy operator

Definition at line 113 of file structuralConstraintTabuList.cpp.

113 {
114 if (this != &from) {
115 _graph_tabuList_ = from._graph_tabuList_;
116 _tabuList_offset_ = from._tabuList_offset_;
117 _tabuList_size_ = from._tabuList_size_;
118 _current_graph_ = from._current_graph_;
119 }
120 return *this;
121 }

References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.

Here is the call graph for this function:

◆ operator=() [2/2]

StructuralConstraintTabuList & gum::learning::StructuralConstraintTabuList::operator= ( StructuralConstraintTabuList && from)

move operator

Definition at line 125 of file structuralConstraintTabuList.cpp.

125 {
126 if (this != &from) {
127 _graph_tabuList_ = std::move(from._graph_tabuList_);
128 _tabuList_offset_ = from._tabuList_offset_;
129 _tabuList_size_ = from._tabuList_size_;
130 _current_graph_ = from._current_graph_;
131 }
132 return *this;
133 }

References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.

Here is the call graph for this function:

◆ setGraphAlone()

void gum::learning::StructuralConstraintTabuList::setGraphAlone ( const DiGraph & graph)

sets a new graph from which we will perform checkings

◆ setTabuListSize()

void gum::learning::StructuralConstraintTabuList::setTabuListSize ( Size new_size)

sets the size of the tabu list

Definition at line 135 of file structuralConstraintTabuList.cpp.

135 {
136 if (new_size == _tabuList_size_) return;
137
138 if (_graph_tabuList_.size() > new_size) {
139 // here, there are more graphs than allowed by the new size.
140 // So remove the oldest elements, so that only new_size elements remain
141 while (_graph_tabuList_.size() > new_size) {
144 }
145 } else {
146 // here, we should keep all the elements in _graph_tabuList_ but we must
147 // ensure that the difference between the max offset in _graph_tabuList_ and
148 // _tabuList_offset_ is equal to new_size
149 if (_tabuList_offset_ + _tabuList_size_ >= new_size) {
150 // we can modify _tabuList_offset_ so that the aforementioned difference
151 // is now equal to new_size
153 } else {
154 // basically, we should add _tabuList_size_ - new_size to _tabuList_offset_,
155 // except that the value of _tabuList_offset_ would be strictly negative,
156 // which is impossible for an attribute of type Size. Hence, here, instead
157 // of changing _tabuList_offset_, we will add (new_size - _tabuList_size_)
158 // to all the offsets in the tabu list
159 const Size delta = new_size - _tabuList_size_;
160 Bijection< GraphHash, Size > new_tabuList(2 * new_size);
161 for (auto iter = _graph_tabuList_.begin(); iter != _graph_tabuList_.end(); ++iter) {
162 new_tabuList.emplace(iter.first(), iter.second() + delta);
163 }
164 _graph_tabuList_ = std::move(new_tabuList);
165 }
166 }
167
168 _tabuList_size_ = new_size;
169 }
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74

References _graph_tabuList_, _tabuList_offset_, _tabuList_size_, and gum::BijectionImplementation< T1, T2, std::is_scalar< T1 >::value &&std::is_scalar< T2 >::value >::emplace().

Here is the call graph for this function:

Member Data Documentation

◆ _current_graph_

GraphHash gum::learning::StructuralConstraintTabuList::_current_graph_ {0, 0}
protected

◆ _graph_tabuList_

Bijection< GraphHash, Size > gum::learning::StructuralConstraintTabuList::_graph_tabuList_
protected

◆ _tabuList_offset_

Size gum::learning::StructuralConstraintTabuList::_tabuList_offset_ {0}
protected

the index of the oldest element

Definition at line 270 of file structuralConstraintTabuList.h.

270{0};

Referenced by StructuralConstraintTabuList(), StructuralConstraintTabuList(), operator=(), operator=(), and setTabuListSize().

◆ _tabuList_size_

Size gum::learning::StructuralConstraintTabuList::_tabuList_size_
protected

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