aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy > Class Template Referenceabstract

Class implementingting a function graph manager. More...

#include <multiDimFunctionGraphManager.h>

Inheritance diagram for gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >:
[legend]
Collaboration diagram for gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >:
[legend]

Public Member Functions

void clean ()
 Removes var without nodes in the diagram.

Private Attributes

MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > * _functionGraph_
 The multidimdecisiongraph supposed to be edited.

Constructors / Destructors

MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy > * MultiDimFunctionGraph ()
 This friend methods from is the only way to get an instance of a manager.
 MultiDimFunctionGraphManager (MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > *master)
 Default constructor.
virtual ~MultiDimFunctionGraphManager ()
 Class destructor.

Nodes manipulation methods.

NodeId addInternalNode_ (const DiscreteVariable *var, NodeId *sons)
 Adds an internal node.
void setRootNode (const NodeId &root)
 Sets root node of decision diagram.
NodeId addInternalNode (const DiscreteVariable *var)
 Inserts a new non terminal node in graph.
virtual NodeId addInternalNode (const DiscreteVariable *var, NodeId *sons)=0
 Inserts a new non terminal node in graph.
NodeId addInternalNode (const DiscreteVariable *var, NodeId nid)
 Inserts a new non terminal node in graph.
NodeId addTerminalNode (const GUM_ELEMENT &value)
 Adds a value to the MultiDimFunctionGraph.
void eraseNode (NodeId id, NodeId replacingId=0, bool updateParents=true)
 Erases a node from the diagram.

Manipulation methods.

void migrateNode_ (const NodeId &x, const NodeId &y)
 Remaps all arcs going to ou going from the first given node to the second node, then delete first node.
void setSon (const NodeId &node, const Idx &modality, const NodeId &sonNode)
 Sets nodes son for given modality to designated son node.
void minimizeSize ()
 Performs a sifting in search of a(local) minimal size.
void moveTo (const DiscreteVariable *x, Idx desiredPos)
 Changes var position in variable sequence.
void _adjacentSwap_ (const DiscreteVariable *x, const DiscreteVariable *y)
 Swap two adjacent variable.

Redundancy methods.

NodeId nodeRedundancyCheck_ (const DiscreteVariable *var, NodeId *sonsMap)
 Check for redundancy.
void reduce_ ()
 Ensures that every isomorphic subgraphs are merged together.
virtual void reduce ()=0
 Ensures that every isomorphic subgraphs are merged together.
NodeId _checkIsomorphism_ (const DiscreteVariable *var, NodeId *sons)
 Checks if a similar node does not already exists in the graph.
bool _isRedundant_ (const DiscreteVariable *var, NodeId *sons)
 Checks if node has the same child for every variable value.

Detailed Description

template<typename GUM_ELEMENT, template< typename > class TerminalNodePolicy>
class gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >

Class implementingting a function graph manager.

Warning
Doxygen does not like spanning command on multiple line, so we could not configure it with the correct include directive. Use the following code snippet to include this file.

This class provides methods to edit a Function Graph. Any modification on a MultiDimFunctionGraph graph must be done via this class.

This class is a singleton and its unique instance ca be accessed using the MultiDimFunctionGraph::getManager() method.

To do so :

// You can also use getTreeInstance()
auto * func_graph =
auto manager = dg->manager();
static MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > * getReducedAndOrderedInstance()
Returns a reduced and ordered instance.
Template Parameters
GUM_ELEMENTThe type of scalars stored in the multidimensional table.
TerminalNodePolicyThe terminal node policy to use.

Definition at line 97 of file multiDimFunctionGraphManager.h.

Constructor & Destructor Documentation

◆ MultiDimFunctionGraphManager()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::MultiDimFunctionGraphManager ( MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > * master)
explicitprotected

Default constructor.

You have to call MultiDimFunctionGraph::getManager() to get the instance of MultiDimFunctionGraphManager bound to your function graph.

Definition at line 61 of file multiDimFunctionGraphManager_tpl.h.

62 {
65 }
Class implementingting a function graph manager.
MultiDimFunctionGraphManager(MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > *master)
Default constructor.
MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > * _functionGraph_
The multidimdecisiongraph supposed to be edited.

References MultiDimFunctionGraphManager(), and _functionGraph_.

Referenced by MultiDimFunctionGraphManager(), gum::MultiDimFunctionGraphROManager< GUM_ELEMENT, TerminalNodePolicy >::MultiDimFunctionGraphROManager(), gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >::MultiDimFunctionGraphTreeManager(), ~MultiDimFunctionGraphManager(), minimizeSize(), and MultiDimFunctionGraph.

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

◆ ~MultiDimFunctionGraphManager()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::~MultiDimFunctionGraphManager ( )
virtual

Class destructor.

Definition at line 69 of file multiDimFunctionGraphManager_tpl.h.

References MultiDimFunctionGraphManager().

Here is the call graph for this function:

Member Function Documentation

◆ _adjacentSwap_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::_adjacentSwap_ ( const DiscreteVariable * x,
const DiscreteVariable * y )
private

Swap two adjacent variable.

Order is important here. X must precede Y before the swap (at the end Y will then precede X). Not respecting this constraint leads to unattended behaviour.

Parameters
xThe first variable to swap.
yThe second variable to swap.

Definition at line 324 of file multiDimFunctionGraphManager_tpl.h.

326 {
327 LinkedList< NodeId >* oldxNodes = _functionGraph_->_var2NodeIdMap_[x];
328 _functionGraph_->_var2NodeIdMap_[x] = new LinkedList< NodeId >();
329 LinkedList< NodeId >* oldyNodes = _functionGraph_->_var2NodeIdMap_[y];
330 _functionGraph_->_var2NodeIdMap_[y] = new LinkedList< NodeId >();
331
332
333 InternalNode* currentOldXNode = nullptr;
334 NodeId* currentNewXNodeSons = nullptr;
335 Idx indx = 0;
336
337 NodeId* currentNewYNodeSons = nullptr;
339 Idx indy = 0;
340
341 while (oldxNodes->list()) {
342 // Recuperating a node associated to variables x
343 currentOldXNode = _functionGraph_->_internalNodeMap_[oldxNodes->list()->element()];
344
345 // Creating a new node associated to variable y
347
348 // Now the graph needs to be remap by inserting nodes bound to x
349 // for each values assumed by y
350 for (indy = 0; indy < y->domainSize(); ++indy) {
351 // Creating a new node bound to x that will be the son of the node
352 // tied to y for the current value assumed by y
354
355 // Iterating on the different values taht x can assumed to do the remap
356 for (indx = 0; indx < x->domainSize(); ++indx) {
358 if (!_functionGraph_->isTerminalNode(currentOldXNode->son(indx))
359 && _functionGraph_->node(currentOldXNode->son(indx))->nodeVar() == y)
361 = _functionGraph_->node(currentOldXNode->son(indx))->son(indy);
362 }
363
364 // Inserting the new node bound to x
366 }
367
368 // Replacing old node x by new node y
371 migrateNode_(oldxNodes->list()->element(), currentNewYNodeId);
372 SOA_DEALLOCATE(currentNewYNodeSons, y->domainSize() * sizeof(NodeId));
373 } else {
375 if (currentNewYNodeId != 0) {
376 migrateNode_(oldxNodes->list()->element(), currentNewYNodeId);
377 SOA_DEALLOCATE(currentNewYNodeSons, y->domainSize() * sizeof(NodeId));
378 } else {
379 // Updating the sons (they must not consider old x as their parent)
380 for (Idx i = 0; i < currentOldXNode->nodeVar()->domainSize(); ++i) {
381 if (_functionGraph_->_internalNodeMap_.exists(currentOldXNode->son(i))) {
382 _functionGraph_->_internalNodeMap_[currentOldXNode->son(i)]->removeParent(
383 oldxNodes->list()->element(),
384 i);
385 }
386 }
387 // Reaffecting old node x internal attributes to correct new one
389 // Updating new sons (they must consider the node as a parent)
390 for (Idx i = 0; i < currentOldXNode->nodeVar()->domainSize(); ++i) {
391 if (_functionGraph_->_internalNodeMap_.exists(currentNewYNodeSons[i])) {
392 _functionGraph_->_internalNodeMap_[currentNewYNodeSons[i]]->addParent(
393 oldxNodes->list()->element(),
394 i);
395 }
396 }
397
398 _functionGraph_->_var2NodeIdMap_[y]->addLink(oldxNodes->list()->element());
399 }
400 }
401
402 oldxNodes->searchAndRemoveLink(oldxNodes->list()->element());
403 }
404 delete oldxNodes;
405
406 while (oldyNodes->list()) {
407 NodeId curId = oldyNodes->list()->element();
408 if (_functionGraph_->_internalNodeMap_[curId]->parents() == nullptr) {
409 for (Idx i = 0; i < _functionGraph_->_internalNodeMap_[curId]->nodeVar()->domainSize(); ++i)
410 if (_functionGraph_->_internalNodeMap_.exists(
411 _functionGraph_->_internalNodeMap_[curId]->son(i)))
412 _functionGraph_->_internalNodeMap_[_functionGraph_->_internalNodeMap_[curId]->son(i)]
413 ->removeParent(curId, i);
414 delete _functionGraph_->_internalNodeMap_[curId];
415 _functionGraph_->_internalNodeMap_.erase(curId);
416 _functionGraph_->_model_.eraseNode(curId);
417 } else {
418 _functionGraph_->_var2NodeIdMap_[y]->addLink(curId);
419 }
420 oldyNodes->searchAndRemoveLink(curId);
421 }
422 delete oldyNodes;
423 }
static NodeId * allocateNodeSons(const DiscreteVariable *v)
Allocates a table of nodeid of the size given in parameter.
NodeId nodeRedundancyCheck_(const DiscreteVariable *var, NodeId *sonsMap)
Check for redundancy.
bool _isRedundant_(const DiscreteVariable *var, NodeId *sons)
Checks if node has the same child for every variable value.
void migrateNode_(const NodeId &x, const NodeId &y)
Remaps all arcs going to ou going from the first given node to the second node, then delete first nod...
NodeId _checkIsomorphism_(const DiscreteVariable *var, NodeId *sons)
Checks if a similar node does not already exists in the graph.

References _adjacentSwap_(), and _functionGraph_.

Referenced by _adjacentSwap_(), and addInternalNode().

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

◆ _checkIsomorphism_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
NodeId gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::_checkIsomorphism_ ( const DiscreteVariable * var,
NodeId * sons )
private

Checks if a similar node does not already exists in the graph.

Tow nodes are similar if for every value assumed by the associated variable, these two nodes have the same children.

Warning
This will not free sons.
Parameters
varThe node to check for.
sonsThe node sons.
Returns
Returns the node id if found, 0 otherwhise.

Definition at line 475 of file multiDimFunctionGraphManager_tpl.h.

477 {
478 const InternalNode* nody = nullptr;
479 Idx i = 0;
480
481 // Check abscence of identical node
482 Link< NodeId >* currentElem = _functionGraph_->_var2NodeIdMap_[var]->list();
483 while (currentElem != nullptr) {
484 nody = _functionGraph_->_internalNodeMap_[currentElem->element()];
485
486 // Check on the other sons
487 i = 0;
488 while (i < var->domainSize() && sons[i] == nody->son(i))
489 ++i;
490 if (i == var->domainSize()) return currentElem->element();
491
492 currentElem = currentElem->nextLink();
493 }
494 return 0;
495 }

References _checkIsomorphism_(), _functionGraph_, gum::DiscreteVariable::domainSize(), gum::Link< T >::element(), gum::Link< T >::nextLink(), and gum::InternalNode::son().

Referenced by _checkIsomorphism_(), addInternalNode(), and nodeRedundancyCheck_().

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

◆ _isRedundant_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
bool gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::_isRedundant_ ( const DiscreteVariable * var,
NodeId * sons )
private

Checks if node has the same child for every variable value.

Warning
WON'T deallocate sons
Parameters
varThe node to check for.
sonsThe node sons.
Returns
Returns true if the node is redundant.

Definition at line 499 of file multiDimFunctionGraphManager_tpl.h.

501 {
502 for (Idx m = 1; m < var->domainSize(); m++)
503 if (sons[m] != sons[0]) return false;
504 return true;
505 }

References _isRedundant_(), and gum::DiscreteVariable::domainSize().

Referenced by _isRedundant_(), addInternalNode(), and nodeRedundancyCheck_().

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

◆ addInternalNode() [1/3]

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
NodeId gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode ( const DiscreteVariable * var)

Inserts a new non terminal node in graph.

NodeId of this node is generated automatically.

Parameters
varAssociated variable
Returns
The id of the added non terminal node.

Definition at line 95 of file multiDimFunctionGraphManager_tpl.h.

96 {
98 NodeId nid = _functionGraph_->_model_.addNode();
99 _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
100 _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
101
102 return nid;
103 }
InternalNode()
Default Constructor Creates an empty node with no variable attached.

References gum::InternalNode::InternalNode(), and _functionGraph_.

Referenced by gum::StatesCounter::_incState_(), gum::StatesChecker::_insertState_(), gum::AdaptiveRMaxPlaner::_visitLearner_(), addInternalNode(), gum::MultiDimFunctionGraphGenerator::generate(), and MultiDimFunctionGraph.

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

◆ addInternalNode() [2/3]

template<typename GUM_ELEMENT, template< typename > class TerminalNodePolicy>
virtual NodeId gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode ( const DiscreteVariable * var,
NodeId * sons )
pure virtual

Inserts a new non terminal node in graph.

NodeId of this node is generated automatically.

Parameters
varThe associated variable.
sonsA table of size var->domainSize() containing nodeid of sons nodes.
Returns
Returns the id of the added non terminal node.
Exceptions
OperationNotAllowedRaised if MultiDimFunctionGraph has no variable yet.

Implemented in gum::MultiDimFunctionGraphROManager< GUM_ELEMENT, TerminalNodePolicy >, and gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >.

References _adjacentSwap_(), _checkIsomorphism_(), _isRedundant_(), addInternalNode(), addInternalNode_(), addTerminalNode(), eraseNode(), migrateNode_(), minimizeSize(), moveTo(), nodeRedundancyCheck_(), and setSon().

Here is the call graph for this function:

◆ addInternalNode() [3/3]

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
NodeId gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode ( const DiscreteVariable * var,
NodeId nid )

Inserts a new non terminal node in graph.

NodeId of this node is generated automatically.

Parameters
varThe ssociated variable.
nidThe desired id for that node.
Returns
Returns the id of the added non terminal node.
Exceptions
OperationNotAllowedRaised if MultiDimFunctionGraph has no variable yet.

Definition at line 82 of file multiDimFunctionGraphManager_tpl.h.

84 {
86
87 _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
88
89 _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
90
91 return nid;
92 }

References gum::InternalNode::InternalNode(), and _functionGraph_.

Here is the call graph for this function:

◆ addInternalNode_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
NodeId gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode_ ( const DiscreteVariable * var,
NodeId * sons )
protected

Adds an internal node.

Parameters
varThe node to add.
sonsThe node sons.
Returns
Returns the added node id.

Definition at line 106 of file multiDimFunctionGraphManager_tpl.h.

108 {
110 NodeId nid = _functionGraph_->_model_.addNode();
111 _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
112 _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
113 for (Idx i = 0; i < newNodeStruct->nbSons(); i++)
114 if (!_functionGraph_->isTerminalNode(sons[i]))
115 _functionGraph_->_internalNodeMap_[sons[i]]->addParent(nid, i);
116
117 return nid;
118 }

References gum::InternalNode::InternalNode(), _functionGraph_, and gum::InternalNode::nbSons().

Referenced by addInternalNode(), gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode(), and nodeRedundancyCheck_().

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

◆ addTerminalNode()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
NodeId gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::addTerminalNode ( const GUM_ELEMENT & value)

Adds a value to the MultiDimFunctionGraph.

This will create a terminal node, which of id is returned. If a terminal node with such value already exists, its id will be return instead.

Parameters
valueThe value added by copy.
Returns
Returns he id of the terminal node hence created.

Definition at line 122 of file multiDimFunctionGraphManager_tpl.h.

123 {
124 if (_functionGraph_->existsTerminalNodeWithValue(value))
125 return _functionGraph_->terminalNodeId(value);
126
127 NodeId node = _functionGraph_->_model_.addNode();
129 return node;
130 }
NodeId addTerminalNode(const GUM_ELEMENT &value)
Adds a value to the MultiDimFunctionGraph.

References _functionGraph_.

Referenced by gum::StatesCounter::_incState_(), gum::AdaptiveRMaxPlaner::_visitLearner_(), addInternalNode(), gum::MultiDimFunctionGraphGenerator::generate(), gum::AdaptiveRMaxPlaner::initVFunction_(), gum::StatesChecker::reset(), and gum::StatesCounter::reset().

Here is the caller graph for this function:

◆ clean()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::clean ( )

Removes var without nodes in the diagram.

Definition at line 572 of file multiDimFunctionGraphManager_tpl.h.

572 {
575 varIter != oldSequence.end();
576 ++varIter)
577 if (!_functionGraph_->varNodeListe(*varIter)->list()) _functionGraph_->erase(**varIter);
578 }

References _functionGraph_, gum::SequenceImplementation< Key, Gen >::begin(), clean(), and gum::SequenceImplementation< Key, Gen >::end().

Referenced by gum::AdaptiveRMaxPlaner::_makeRMaxFunctionGraphs_(), clean(), gum::MultiDimFunctionGraphGenerator::generate(), and reduce().

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

◆ eraseNode()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::eraseNode ( NodeId id,
NodeId replacingId = 0,
bool updateParents = true )

Erases a node from the diagram.

Parameters
idThe id of the variable to erase.
replacingIdOffers the possibility to reroute any parent to the given node.
updateParentsIndicates if such remapping has to be done.
Exceptions
NotFoundRaised if node isn't in diagram.

Definition at line 134 of file multiDimFunctionGraphManager_tpl.h.

137 {
138 if (!_functionGraph_->_model_.exists(eraseId))
139 GUM_ERROR(NotFound, "Node : " << eraseId << " doesn't exists in the graph")
140
142 for (auto iterVar = _functionGraph_->variablesSequence().begin();
143 iterVar != _functionGraph_->variablesSequence().end();
144 ++iterVar) {
145 Link< NodeId >* nodeIter = _functionGraph_->_var2NodeIdMap_[*iterVar]->list();
146 while (nodeIter != nullptr) {
147 for (Idx modality = 0; modality < (*iterVar)->domainSize(); ++modality)
148 if (_functionGraph_->node(nodeIter->element())->son(modality) == eraseId)
149 setSon(nodeIter->element(), modality, replacingId);
150
151 nodeIter = nodeIter->nextLink();
152 }
153 }
154 _functionGraph_->eraseTerminalNode(eraseId);
155
156 } else {
157 InternalNode* eraseNode = _functionGraph_->_internalNodeMap_[eraseId];
158
159 if (updateParents) {
160 // setSon removes the current link from the parents of eraseNode
161 Link< Parent >* picle = eraseNode->parents();
162 while (picle != nullptr) {
163 const Parent parent = picle->element();
164 picle = picle->nextLink();
165 setSon(parent.parentId, parent.modality, replacingId);
166 }
167 }
168
169 // the sons of eraseNode must not consider it as a parent anymore
170 for (Idx i = 0; i < eraseNode->nbSons(); ++i)
171 if (_functionGraph_->isInternalNode(eraseNode->son(i)))
172 _functionGraph_->_internalNodeMap_[eraseNode->son(i)]->removeParent(eraseId, i);
173
174 _functionGraph_->_var2NodeIdMap_[eraseNode->nodeVar()]->searchAndRemoveLink(eraseId);
175
176 delete _functionGraph_->_internalNodeMap_[eraseId];
177 _functionGraph_->_internalNodeMap_.erase(eraseId);
178 }
179
180 _functionGraph_->_model_.eraseNode(eraseId);
181
182 if (_functionGraph_->_root_ == eraseId) _functionGraph_->_root_ = replacingId;
183 }
void eraseNode(NodeId id, NodeId replacingId=0, bool updateParents=true)
Erases a node from the diagram.
void setSon(const NodeId &node, const Idx &modality, const NodeId &sonNode)
Sets nodes son for given modality to designated son node.

References _functionGraph_.

Referenced by addInternalNode().

Here is the caller graph for this function:

◆ migrateNode_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::migrateNode_ ( const NodeId & x,
const NodeId & y )
protected

Remaps all arcs going to ou going from the first given node to the second node, then delete first node.

Parameters
xThe variable from which all arcs are removed.
yThe variable for which all of x arcs are added.

Definition at line 426 of file multiDimFunctionGraphManager_tpl.h.

428 {
429 InternalNode* org = _functionGraph_->_internalNodeMap_[origin];
430 // Upating parents after the change
431 // setSon removes the current link from the parents of org
432 Link< Parent >* picle = org->parents();
433 while (picle != nullptr) {
434 const Parent parent = picle->element();
435 picle = picle->nextLink();
436 setSon(parent.parentId, parent.modality, destination);
437 }
438
439 // Updating sons after the change
440 for (Idx i = 0; i < org->nbSons(); ++i)
441 if (_functionGraph_->_internalNodeMap_.exists(org->son(i)))
442 _functionGraph_->_internalNodeMap_[org->son(i)]->removeParent(origin, i);
443
444 delete org;
445 _functionGraph_->_internalNodeMap_.erase(origin);
447
448 if (_functionGraph_->root() == origin) this->setRootNode(destination);
449 }
void setRootNode(const NodeId &root)
Sets root node of decision diagram.

References _functionGraph_, gum::Link< T >::element(), migrateNode_(), gum::Parent::modality, gum::InternalNode::nbSons(), gum::Link< T >::nextLink(), gum::Parent::parentId, gum::InternalNode::parents(), setRootNode(), setSon(), and gum::InternalNode::son().

Referenced by addInternalNode(), migrateNode_(), and reduce_().

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

◆ minimizeSize()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::minimizeSize ( )

Performs a sifting in search of a(local) minimal size.

Definition at line 238 of file multiDimFunctionGraphManager_tpl.h.

238 {
239 // Ordering variables by number of nodes asssociated to them
243 = _functionGraph_->variablesSequence().beginSafe();
244 varIter != _functionGraph_->variablesSequence().endSafe();
245 ++varIter) {
246 const Link< NodeId >* curElem = _functionGraph_->_var2NodeIdMap_[*varIter]->list();
247 Idx nbElem = 0;
248 for (; curElem != nullptr; nbElem++, curElem = curElem->nextLink())
249 ;
250 varLvlSize.insert(*varIter, nbElem);
251 siftingSeq.insert(*varIter);
252 Idx pos = siftingSeq.pos(*varIter);
253 while (pos > 0 && varLvlSize[siftingSeq.atPos(pos - 1)] > nbElem) {
254 siftingSeq.swap(pos - 1, pos);
255 pos--;
256 }
257 }
258
259 // Sifting var par var
261 sifIter != siftingSeq.endSafe();
262 ++sifIter) {
263 // Initialization
264 Idx currentPos = _functionGraph_->variablesSequence().pos(*sifIter);
265 Idx bestSize = _functionGraph_->realSize();
267
268
269 // Sifting towards upper places
270 while (currentPos > 0) {
272 currentPos = _functionGraph_->variablesSequence().pos(*sifIter);
273 if (_functionGraph_->realSize() < bestSize) {
275 bestSize = _functionGraph_->realSize();
276 }
277 }
278
279 // Sifting towards lower places
282 currentPos = _functionGraph_->variablesSequence().pos(*sifIter);
283 if (_functionGraph_->realSize() < bestSize) {
285 bestSize = _functionGraph_->realSize();
286 }
287 }
288
290 }
291 }
void moveTo(const DiscreteVariable *x, Idx desiredPos)
Changes var position in variable sequence.

References MultiDimFunctionGraphManager(), and minimizeSize().

Referenced by addInternalNode(), and minimizeSize().

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

◆ moveTo()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::moveTo ( const DiscreteVariable * x,
Idx desiredPos )

Changes var position in variable sequence.

Parameters
xThe varaible to change.
desiredPosThe new posiition.

Definition at line 295 of file multiDimFunctionGraphManager_tpl.h.

297 {
298 // First we determine the position of both variable
299 // We also determine which one precede the other
300 if (_functionGraph_->variablesSequence().pos(movedVar) > desiredPos)
301 for (Idx currentPos = _functionGraph_->variablesSequence().pos(movedVar);
303 currentPos--) {
304 const DiscreteVariable* preVar = _functionGraph_->variablesSequence().atPos(currentPos - 1);
305 if (_functionGraph_->_var2NodeIdMap_[preVar]->list()
306 && _functionGraph_->_var2NodeIdMap_[movedVar]->list())
309 }
310 else
311 for (Idx currentPos = _functionGraph_->variablesSequence().pos(movedVar);
313 currentPos++) {
314 const DiscreteVariable* suiVar = _functionGraph_->variablesSequence().atPos(currentPos + 1);
315 if (_functionGraph_->_var2NodeIdMap_[suiVar]->list()
316 && _functionGraph_->_var2NodeIdMap_[movedVar]->list())
319 }
320 }
void _adjacentSwap_(const DiscreteVariable *x, const DiscreteVariable *y)
Swap two adjacent variable.

References moveTo().

Referenced by addInternalNode(), and moveTo().

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

◆ nodeRedundancyCheck_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
NodeId gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::nodeRedundancyCheck_ ( const DiscreteVariable * var,
NodeId * sonsMap )
protected

Check for redundancy.

Checks if a similar node does not already exists in the graph or if it has the same child for every variable value. If no node is a match, this node is added to the graph.

Warning
: will free by itself sonsMap if a match exists.
Parameters
varThe node to add in the graph.
sonsMapThe node sons.
Returns
Returns the nodes id in the graph.

Definition at line 454 of file multiDimFunctionGraphManager_tpl.h.

456 {
458
459 if (_isRedundant_(var, sonsIds)) {
460 SOA_DEALLOCATE(sonsIds, sizeof(NodeId) * var->domainSize());
461 } else {
463 if (newNode == 0) {
465 } else {
466 SOA_DEALLOCATE(sonsIds, sizeof(NodeId) * var->domainSize());
467 }
468 }
469
470 return newNode;
471 }
NodeId addInternalNode_(const DiscreteVariable *var, NodeId *sons)
Adds an internal node.

References _checkIsomorphism_(), _isRedundant_(), addInternalNode_(), gum::DiscreteVariable::domainSize(), nodeRedundancyCheck_(), and SOA_DEALLOCATE.

Referenced by addInternalNode(), gum::MultiDimFunctionGraphROManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode(), and nodeRedundancyCheck_().

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

◆ reduce()

template<typename GUM_ELEMENT, template< typename > class TerminalNodePolicy>
virtual void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::reduce ( )
pure virtual

Ensures that every isomorphic subgraphs are merged together.

Implemented in gum::MultiDimFunctionGraphROManager< GUM_ELEMENT, TerminalNodePolicy >, and gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >.

References clean(), and reduce_().

Referenced by gum::AdaptiveRMaxPlaner::_makeRMaxFunctionGraphs_(), and gum::MultiDimFunctionGraphGenerator::generate().

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

◆ reduce_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::reduce_ ( )
protected

Ensures that every isomorphic subgraphs are merged together.

Definition at line 509 of file multiDimFunctionGraphManager_tpl.h.

509 {
510 Link< NodeId >* currentNodeId = nullptr;
511 Link< NodeId >* nextNodeId = nullptr;
512 InternalNode* currentNode = nullptr;
513 bool theSame = true;
515
517 = _functionGraph_->variablesSequence().rbegin();
518 varIter != _functionGraph_->variablesSequence().rend();
519 --varIter) {
520 currentNodeId = _functionGraph_->_var2NodeIdMap_[*varIter]->list();
521
522 while (currentNodeId != nullptr) {
523 nextNodeId = currentNodeId->nextLink();
524 currentNode = _functionGraph_->_internalNodeMap_[currentNodeId->element()];
525
526 // First isomorphism to handle is the one where all node children are
527 // the same
528 theSame = true;
529 for (currentInd = 1; currentInd < (*varIter)->domainSize(); currentInd++) {
530 if (currentNode->son(currentInd) != currentNode->son(0)) {
531 theSame = false;
532 break;
533 }
534 }
535
536 if (theSame == true) {
537 migrateNode_(currentNodeId->element(), currentNode->son(0));
538 _functionGraph_->_var2NodeIdMap_[*varIter]->searchAndRemoveLink(currentNodeId->element());
540 continue;
541 }
542
543 // Second isomorphism to handle is the one where two nodes have same
544 // variable and same children
545 if (nextNodeId) {
547 InternalNode* anotherNode = nullptr;
548 Idx modality = 0;
549 while (anotherNodeId->nextLink() != nullptr) {
550 nextNodeId = anotherNodeId->nextLink();
551 anotherNode = _functionGraph_->_internalNodeMap_[anotherNodeId->element()];
552
553 // Check on the other sons
554 for (modality = 0; modality < (*varIter)->domainSize(); ++modality) {
555 if (anotherNode->son(modality) != currentNode->son(modality)) break;
556 if (modality == (*varIter)->domainSize() - 1) {
557 migrateNode_(anotherNodeId->element(), currentNodeId->element());
558 _functionGraph_->_var2NodeIdMap_[*varIter]->searchAndRemoveLink(
559 anotherNodeId->element());
560 }
561 }
562
564 }
565 }
566 currentNodeId = currentNodeId->nextLink();
567 }
568 }
569 }

References _functionGraph_, gum::Link< T >::element(), migrateNode_(), gum::Link< T >::nextLink(), reduce_(), and gum::InternalNode::son().

Referenced by reduce(), gum::MultiDimFunctionGraphROManager< GUM_ELEMENT, TerminalNodePolicy >::reduce(), and reduce_().

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

◆ setRootNode()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::setRootNode ( const NodeId & root)

Sets root node of decision diagram.

Parameters
rootThe node to set as root.

Definition at line 75 of file multiDimFunctionGraphManager_tpl.h.

76 {
77 _functionGraph_->_root_ = root;
78 }

References _functionGraph_.

Referenced by gum::StatesCounter::_incState_(), gum::StatesChecker::_insertState_(), gum::AdaptiveRMaxPlaner::_makeRMaxFunctionGraphs_(), gum::MultiDimFunctionGraphGenerator::generate(), gum::AdaptiveRMaxPlaner::initVFunction_(), migrateNode_(), MultiDimFunctionGraph, and gum::StatesCounter::reset().

Here is the caller graph for this function:

◆ setSon()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>
void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::setSon ( const NodeId & node,
const Idx & modality,
const NodeId & sonNode )

Sets nodes son for given modality to designated son node.

Parameters
nodeThe node to which a node is added.
modalityThe modality for which sonNode is added to node.
sonNodeThe node to add as a son to node.

Definition at line 187 of file multiDimFunctionGraphManager_tpl.h.

190 {
191 // Ensuring that both nodes exists in the graph
192 if (!_functionGraph_->_model_.exists(node))
193 GUM_ERROR(NotFound, "Node : " << node << " doesn't exists in the graph")
195 GUM_ERROR(NotFound, "Node : " << sonNode << " doesn't exists in the graph")
196
197 // Check if starting node is not terminal
199 GUM_ERROR(InvalidNode, "You cannot insert an arc from terminal node : " << node)
200
201 // Check if associated modality is lower than node bound variable domain
202 // size
206 "Modality " << modality << "is higher than domain size "
208 << "minus 1 of variable "
210
211 // Check if variable order is respected
219 << " is after variable "
221 << "in Function Graph order.")
222
226
227 // the old son is no longer a child of node for this modality
230
234 }

References _functionGraph_, GUM_ERROR, and setSon().

Referenced by gum::StatesCounter::_incState_(), gum::StatesChecker::_insertState_(), addInternalNode(), gum::MultiDimFunctionGraphGenerator::generate(), migrateNode_(), and setSon().

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

◆ MultiDimFunctionGraph

template<typename GUM_ELEMENT, template< typename > class TerminalNodePolicy>
MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy > * MultiDimFunctionGraph ( )
friend

This friend methods from is the only way to get an instance of a manager.

See class description for more info.

References MultiDimFunctionGraphManager(), addInternalNode(), and setRootNode().

Member Data Documentation

◆ _functionGraph_

template<typename GUM_ELEMENT, template< typename > class TerminalNodePolicy>
MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy >* gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::_functionGraph_
private

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