![]() |
aGrUM 3.1.1
a C++ library for (probabilistic) graphical models
|
The class imposing a N-sized tabu list as a structural constraints for learning algorithms. More...
#include <structuralConstraintTabuList.h>
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 | |
| StructuralConstraintTabuList & | operator= (const StructuralConstraintTabuList &from) |
| copy operator | |
| StructuralConstraintTabuList & | operator= (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 | |
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.
|
inherited |
Definition at line 61 of file structuralConstraint.h.
|
protected |
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.
| gum::learning::StructuralConstraintTabuList::StructuralConstraintTabuList | ( | ) |
default constructor
Definition at line 61 of file structuralConstraintTabuList.cpp.
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=().
| gum::learning::StructuralConstraintTabuList::StructuralConstraintTabuList | ( | const DiGraph & | graph | ) |
constructor starting with a given graph
Definition at line 72 of file structuralConstraintTabuList.cpp.
References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_size_, and GUM_STRUCTURAL_CONSTRAINT_TABU_LIST_DEFAULT_SIZE.
| gum::learning::StructuralConstraintTabuList::StructuralConstraintTabuList | ( | const StructuralConstraintTabuList & | from | ) |
copy constructor
Definition at line 90 of file structuralConstraintTabuList.cpp.
References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.
|
noexcept |
move constructor
Definition at line 98 of file structuralConstraintTabuList.cpp.
References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.
|
virtual |
destructor
Definition at line 107 of file structuralConstraintTabuList.cpp.
References StructuralConstraintTabuList().
|
protected |
|
protected |
|
protected |
| 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().
| 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().
| 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().
| 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().
| 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().
| 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.
| 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.
| 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.
| 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
| 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
| 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.
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().
| 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.
| void gum::learning::StructuralConstraintTabuList::modifyGraphAlone | ( | const ArcAddition & | change | ) |
notify the constraint of a modification of the graph
| InvalidNode | exception is thrown if an arc (x,y) is added and x or y does not belong to the graph nodes |
Referenced by modifyGraphAlone().
| void gum::learning::StructuralConstraintTabuList::modifyGraphAlone | ( | const ArcDeletion & | change | ) |
notify the constraint of a modification of the graph
| void gum::learning::StructuralConstraintTabuList::modifyGraphAlone | ( | const ArcReversal & | change | ) |
notify the constraint of a modification of the graph
| InvalidNode | exception is thrown if at least one extremity of the arc does not belong to the graph nodes |
| 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
| 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
| void gum::learning::StructuralConstraintTabuList::modifyGraphAlone | ( | const GraphChange & | change | ) |
notify the constraint of a modification of the graph
| InvalidNode | exception 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.
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().
| StructuralConstraintTabuList & gum::learning::StructuralConstraintTabuList::operator= | ( | const StructuralConstraintTabuList & | from | ) |
copy operator
Definition at line 113 of file structuralConstraintTabuList.cpp.
References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.
| StructuralConstraintTabuList & gum::learning::StructuralConstraintTabuList::operator= | ( | StructuralConstraintTabuList && | from | ) |
move operator
Definition at line 125 of file structuralConstraintTabuList.cpp.
References StructuralConstraintTabuList(), _current_graph_, _graph_tabuList_, _tabuList_offset_, and _tabuList_size_.
| void gum::learning::StructuralConstraintTabuList::setGraphAlone | ( | const DiGraph & | graph | ) |
sets a new graph from which we will perform checkings
| void gum::learning::StructuralConstraintTabuList::setTabuListSize | ( | Size | new_size | ) |
sets the size of the tabu list
Definition at line 135 of file structuralConstraintTabuList.cpp.
References _graph_tabuList_, _tabuList_offset_, _tabuList_size_, and gum::BijectionImplementation< T1, T2, std::is_scalar< T1 >::value &&std::is_scalar< T2 >::value >::emplace().
|
protected |
the current graph hash
Definition at line 276 of file structuralConstraintTabuList.h.
Referenced by StructuralConstraintTabuList(), StructuralConstraintTabuList(), StructuralConstraintTabuList(), StructuralConstraintTabuList(), operator=(), and operator=().
|
protected |
the tabu list
Definition at line 267 of file structuralConstraintTabuList.h.
Referenced by StructuralConstraintTabuList(), StructuralConstraintTabuList(), StructuralConstraintTabuList(), StructuralConstraintTabuList(), operator=(), operator=(), and setTabuListSize().
|
protected |
the index of the oldest element
Definition at line 270 of file structuralConstraintTabuList.h.
Referenced by StructuralConstraintTabuList(), StructuralConstraintTabuList(), operator=(), operator=(), and setTabuListSize().
|
protected |
the max size of the tabu list
Definition at line 273 of file structuralConstraintTabuList.h.
Referenced by StructuralConstraintTabuList(), StructuralConstraintTabuList(), StructuralConstraintTabuList(), StructuralConstraintTabuList(), operator=(), operator=(), and setTabuListSize().