gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy > Class Template Reference

#include <multiDimFunctionGraphManager.h>

Inheritance diagram for gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >:

Collaboration diagram for gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >:

Public Member Functions
void	clean ()
	Removes var without nodes in the diagram.
Inherited methods
NodeId	addInternalNode (const DiscreteVariable *var, NodeId *sons) override
	Inserts a new non terminal node in graph.
void	reduce () override
	Ensures that every isomorphic subgraphs are merged together.

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

Friends
MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy > *	MultiDimFunctionGraph ()
	This friend methods from is the only way to get an instance of a manager.

Constructor and destructor
	MultiDimFunctionGraphTreeManager (MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > *master)
	Class constructor.
	~MultiDimFunctionGraphTreeManager () override
	Class destructor.

Manipulation methods.
void	_adjacentSwap_ (const DiscreteVariable *x, const DiscreteVariable *y)
	Swap two adjacent variable.
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	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.

Redundancy methods.
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.
NodeId	nodeRedundancyCheck_ (const DiscreteVariable *var, NodeId *sonsMap)
	Check for redundancy.
void	reduce_ ()
	Ensures that every isomorphic subgraphs are merged together.

Nodes manipulation methods.
void	setRootNode (const NodeId &root)
	Sets root node of decision diagram.
NodeId	addInternalNode (const DiscreteVariable *var)
	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.
NodeId	addInternalNode_ (const DiscreteVariable *var, NodeId *sons)
	Adds an internal node.

Detailed Description

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

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.

#include <agrum/base/multidim/implementations/multiDimFunctionGraphManager.h>

Template Parameters

GUM_ELEMENT	The type of scalars stored in the multidimensional table.
TerminalNodePolicy	The terminal node policy to use.

Definition at line 357 of file multiDimFunctionGraphManager.h.

Constructor & Destructor Documentation

MultiDimFunctionGraphTreeManager()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>

gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >::MultiDimFunctionGraphTreeManager ( MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy > * master )

private

Class constructor.

Definition at line 569 of file multiDimFunctionGraphManager_tpl.h.

                                                                            :
      MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >(master) {
    GUM_CONSTRUCTOR(MultiDimFunctionGraphTreeManager);
  }

References gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::MultiDimFunctionGraphManager(), and MultiDimFunctionGraphTreeManager().

Referenced by MultiDimFunctionGraphTreeManager(), and ~MultiDimFunctionGraphTreeManager().

Here is the call graph for this function:

Here is the caller graph for this function:

~MultiDimFunctionGraphTreeManager()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>

gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >::~MultiDimFunctionGraphTreeManager ( )

override

Class destructor.

Definition at line 578 of file multiDimFunctionGraphManager_tpl.h.

                                                                                            {
    GUM_DESTRUCTOR(MultiDimFunctionGraphTreeManager);
  }

References MultiDimFunctionGraphTreeManager(), and ~MultiDimFunctionGraphTreeManager().

Referenced by ~MultiDimFunctionGraphTreeManager().

Here is the call graph for this function:

Here is the caller 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 )

privateinherited

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

x	The first variable to swap.
y	The second variable to swap.

Definition at line 310 of file multiDimFunctionGraphManager_tpl.h.

                                 {
    LinkedList< NodeId >* oldxNodes     = _functionGraph_->_var2NodeIdMap_[x];
    _functionGraph_->_var2NodeIdMap_[x] = new LinkedList< NodeId >();
    LinkedList< NodeId >* oldyNodes     = _functionGraph_->_var2NodeIdMap_[y];
    _functionGraph_->_var2NodeIdMap_[y] = new LinkedList< NodeId >();
 
 
    InternalNode* currentOldXNode     = nullptr;
    NodeId*       currentNewXNodeSons = nullptr;
    Idx           indx                = 0;
 
    NodeId* currentNewYNodeSons = nullptr;
    NodeId  currentNewYNodeId   = 0;
    Idx     indy                = 0;
 
    while (oldxNodes->list()) {
      // Recuperating a node associated to variables x
      currentOldXNode = _functionGraph_->_internalNodeMap_[oldxNodes->list()->element()];
 
      // Creating a new node associated to variable y
      currentNewYNodeSons = InternalNode::allocateNodeSons(y);
 
      // Now the graph needs to be remap by inserting nodes bound to x
      // for each values assumed by y
      for (indy = 0; indy < y->domainSize(); ++indy) {
        // Creating a new node bound to x that will be the son of the node
        // tied to y for the current value assumed by y
        currentNewXNodeSons = InternalNode::allocateNodeSons(x);
 
        // Iterating on the different values taht x can assumed to do the remap
        for (indx = 0; indx < x->domainSize(); ++indx) {
          currentNewXNodeSons[indx] = currentOldXNode->son(indx);
          if (!_functionGraph_->isTerminalNode(currentOldXNode->son(indx))
              && _functionGraph_->node(currentOldXNode->son(indx))->nodeVar() == y)
            currentNewXNodeSons[indx]
                = _functionGraph_->node(currentOldXNode->son(indx))->son(indy);
        }
 
        // Inserting the new node bound to x
        currentNewYNodeSons[indy] = nodeRedundancyCheck_(x, currentNewXNodeSons);
      }
 
      // Replacing old node x by new node y
      currentNewYNodeId = currentNewYNodeSons[0];
      if (_isRedundant_(y, currentNewYNodeSons)) {
        migrateNode_(oldxNodes->list()->element(), currentNewYNodeId);
        SOA_DEALLOCATE(currentNewYNodeSons, y->domainSize() * sizeof(NodeId));
      } else {
        currentNewYNodeId = _checkIsomorphism_(y, currentNewYNodeSons);
        if (currentNewYNodeId != 0) {
          migrateNode_(oldxNodes->list()->element(), currentNewYNodeId);
          SOA_DEALLOCATE(currentNewYNodeSons, y->domainSize() * sizeof(NodeId));
        } else {
          // Updating the sons (they must not consider old x as their parent)
          for (Idx i = 0; i < currentOldXNode->nodeVar()->domainSize(); ++i) {
            if (_functionGraph_->_internalNodeMap_.exists(currentOldXNode->son(i))) {
              _functionGraph_->_internalNodeMap_[currentOldXNode->son(i)]->removeParent(
                  oldxNodes->list()->element(),
                  i);
            }
          }
          // Reaffecting old node x internal attributes to correct new one
          currentOldXNode->setNode(y, currentNewYNodeSons);
          // Updating new sons (they must consider the node as a parent)
          for (Idx i = 0; i < currentOldXNode->nodeVar()->domainSize(); ++i) {
            if (_functionGraph_->_internalNodeMap_.exists(currentNewYNodeSons[i])) {
              _functionGraph_->_internalNodeMap_[currentNewYNodeSons[i]]->addParent(
                  oldxNodes->list()->element(),
                  i);
            }
          }
 
          _functionGraph_->_var2NodeIdMap_[y]->addLink(oldxNodes->list()->element());
        }
      }
 
      oldxNodes->searchAndRemoveLink(oldxNodes->list()->element());
    }
    delete oldxNodes;
 
    while (oldyNodes->list()) {
      NodeId curId = oldyNodes->list()->element();
      if (_functionGraph_->_internalNodeMap_[curId]->parents() == nullptr) {
        for (Idx i = 0; i < _functionGraph_->_internalNodeMap_[curId]->nodeVar()->domainSize(); ++i)
          if (_functionGraph_->_internalNodeMap_.exists(
                  _functionGraph_->_internalNodeMap_[curId]->son(i)))
            _functionGraph_->_internalNodeMap_[_functionGraph_->_internalNodeMap_[curId]->son(i)]
                ->removeParent(curId, i);
        delete _functionGraph_->_internalNodeMap_[curId];
        _functionGraph_->_internalNodeMap_.erase(curId);
        _functionGraph_->_model_.eraseNode(curId);
      } else {
        _functionGraph_->_var2NodeIdMap_[y]->addLink(curId);
      }
      oldyNodes->searchAndRemoveLink(curId);
    }
    delete oldyNodes;
  }

References _adjacentSwap_(), and _functionGraph_.

Referenced by _adjacentSwap_().

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 )

privateinherited

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

var	The node to check for.
sons	The node sons.

Returns

Returns the node id if found, 0 otherwhise.

Definition at line 459 of file multiDimFunctionGraphManager_tpl.h.

                                    {
    const InternalNode* nody = nullptr;
    Idx                 i    = 0;
 
    // Check abscence of identical node
    Link< NodeId >* currentElem = _functionGraph_->_var2NodeIdMap_[var]->list();
    while (currentElem != nullptr) {
      nody = _functionGraph_->_internalNodeMap_[currentElem->element()];
 
      // Check on the other sons
      i = 0;
      while (i < var->domainSize() && sons[i] == nody->son(i))
        ++i;
      if (i == var->domainSize()) return currentElem->element();
 
      currentElem = currentElem->nextLink();
    }
    return 0;
  }

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

Referenced by _checkIsomorphism_(), 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 )

privateinherited

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

Warning

WON'T deallocate sons

Parameters

var	The node to check for.
sons	The node sons.

Returns

Returns true if the node is redundant.

Definition at line 483 of file multiDimFunctionGraphManager_tpl.h.

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

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

Referenced by _isRedundant_(), 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 )

inherited

Inserts a new non terminal node in graph.

NodeId of this node is generated automatically.

Parameters

var	Associated variable

Returns

The id of the added non terminal node.

Definition at line 95 of file multiDimFunctionGraphManager_tpl.h.

                                   {
    InternalNode* newNodeStruct = new InternalNode(var);
    NodeId        nid           = _functionGraph_->_model_.addNode();
    _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
    _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
 
    return nid;
  }

References _functionGraph_.

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

Here is the caller graph for this function:

addInternalNode() [2/3]

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>

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

inherited

Inserts a new non terminal node in graph.

NodeId of this node is generated automatically.

Parameters

var	The ssociated variable.
nid	The desired id for that node.

Returns

Returns the id of the added non terminal node.

Exceptions

OperationNotAllowed

Raised if MultiDimFunctionGraph has no variable yet.

Definition at line 82 of file multiDimFunctionGraphManager_tpl.h.

                                   {
    InternalNode* newNodeStruct = new InternalNode(var);
 
    _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
 
    _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
 
    return nid;
  }

References _functionGraph_.

addInternalNode() [3/3]

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>

NodeId gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode ( const DiscreteVariable * var, NodeId * sons )

overridevirtual

Inserts a new non terminal node in graph.

NodeId of this node is generated automatically.

Parameters

var	The associated variable.
sons	A table of size var->domainSize() containing nodeid of sons nodes.

Returns

Returns the id of the added non terminal node.

Exceptions

OperationNotAllowed

Raised if MultiDimFunctionGraph has no variable yet.

Implements gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >.

Definition at line 583 of file multiDimFunctionGraphManager_tpl.h.

                                    {
    return this->addInternalNode_(var, sons);
  }

References gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::addInternalNode_().

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 )

protectedinherited

Adds an internal node.

Parameters

var	The node to add.
sons	The node sons.

Returns

Returns the added node id.

Definition at line 106 of file multiDimFunctionGraphManager_tpl.h.

                                    {
    InternalNode* newNodeStruct = new InternalNode(var, sons);
    NodeId        nid           = _functionGraph_->_model_.addNode();
    _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
    _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
    for (Idx i = 0; i < newNodeStruct->nbSons(); i++)
      if (!_functionGraph_->isTerminalNode(sons[i]))
        _functionGraph_->_internalNodeMap_[sons[i]]->addParent(nid, i);
 
    return nid;
  }

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

Referenced by 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 )

inherited

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

value

The value added by copy.

Returns

Returns he id of the terminal node hence created.

Definition at line 122 of file multiDimFunctionGraphManager_tpl.h.

                                {
    if (_functionGraph_->existsTerminalNodeWithValue(value))
      return _functionGraph_->terminalNodeId(value);
 
    NodeId node = _functionGraph_->_model_.addNode();
    _functionGraph_->addTerminalNode(node, value);
    return node;
  }

References _functionGraph_.

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

Here is the caller graph for this function:

clean()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>

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

inherited

Removes var without nodes in the diagram.

Definition at line 556 of file multiDimFunctionGraphManager_tpl.h.

                                                                              {
    Sequence< const DiscreteVariable* > oldSequence(_functionGraph_->variablesSequence());
    for (SequenceIterator< const DiscreteVariable* > varIter = oldSequence.begin();
         varIter != oldSequence.end();
         ++varIter)
      if (!_functionGraph_->varNodeListe(*varIter)->list()) _functionGraph_->erase(**varIter);
  }

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

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

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 )

inherited

Erases a node from the diagram.

Parameters

id	The id of the variable to erase.
replacingId	Offers the possibility to reroute any parent to the given node.
updateParents	Indicates if such remapping has to be done.

Exceptions

NotFound

Raised if node isn't in diagram.

Definition at line 134 of file multiDimFunctionGraphManager_tpl.h.

                            {
    if (!_functionGraph_->_model_.exists(eraseId))
      GUM_ERROR(NotFound, "Node : " << eraseId << " doesn't exists in the graph")
 
    if (_functionGraph_->isTerminalNode(eraseId)) {
      for (auto iterVar = _functionGraph_->variablesSequence().begin();
           iterVar != _functionGraph_->variablesSequence().end();
           ++iterVar) {
        Link< NodeId >* nodeIter = _functionGraph_->_var2NodeIdMap_[*iterVar]->list();
        while (nodeIter != nullptr) {
          for (Idx modality = 0; modality < (*iterVar)->domainSize(); ++modality)
            if (_functionGraph_->node(nodeIter->element())->son(modality) == eraseId)
              setSon(nodeIter->element(), modality, replacingId);
 
          nodeIter = nodeIter->nextLink();
        }
      }
      _functionGraph_->eraseTerminalNode(eraseId);
 
    } else {
      InternalNode* eraseNode = _functionGraph_->_internalNodeMap_[eraseId];
 
      if (updateParents) {
        Link< Parent >* picle = eraseNode->parents();
        while (picle != nullptr) {
          setSon(picle->element().parentId, picle->element().modality, replacingId);
          picle = picle->nextLink();
        }
      }
 
      _functionGraph_->_var2NodeIdMap_[_functionGraph_->_internalNodeMap_[eraseId]->nodeVar()]
          ->searchAndRemoveLink(eraseId);
 
      delete _functionGraph_->_internalNodeMap_[eraseId];
      _functionGraph_->_internalNodeMap_.erase(eraseId);
    }
 
    _functionGraph_->_model_.eraseNode(eraseId);
 
    if (_functionGraph_->_root_ == eraseId) _functionGraph_->_root_ = replacingId;
  }

References _functionGraph_.

migrateNode_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>

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

protectedinherited

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

Parameters

x	The variable from which all arcs are removed.
y	The variable for which all of x arcs are added.

Definition at line 412 of file multiDimFunctionGraphManager_tpl.h.

                                 {
    InternalNode* org = _functionGraph_->_internalNodeMap_[origin];
    // Upating parents after the change
    Link< Parent >* picle = org->parents();
    while (picle != nullptr) {
      setSon(picle->element().parentId, picle->element().modality, destination);
      picle = picle->nextLink();
    }
 
    // Updating sons after the change
    for (Idx i = 0; i < org->nbSons(); ++i)
      if (_functionGraph_->_internalNodeMap_.exists(org->son(i)))
        _functionGraph_->_internalNodeMap_[org->son(i)]->removeParent(origin, i);
 
    delete org;
    _functionGraph_->_internalNodeMap_.erase(origin);
    _functionGraph_->_model_.eraseNode(origin);
 
    if (_functionGraph_->root() == origin) this->setRootNode(destination);
  }

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

Referenced by 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 ( )

inherited

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

Definition at line 224 of file multiDimFunctionGraphManager_tpl.h.

                                                                                     {
    // Ordering variables by number of nodes asssociated to them
    Sequence< const DiscreteVariable* >       siftingSeq;
    HashTable< const DiscreteVariable*, Idx > varLvlSize;
    for (SequenceIteratorSafe< const DiscreteVariable* > varIter
         = _functionGraph_->variablesSequence().beginSafe();
         varIter != _functionGraph_->variablesSequence().endSafe();
         ++varIter) {
      const Link< NodeId >* curElem = _functionGraph_->_var2NodeIdMap_[*varIter]->list();
      Idx                   nbElem  = 0;
      for (; curElem != nullptr; nbElem++, curElem = curElem->nextLink())
        ;
      varLvlSize.insert(*varIter, nbElem);
      siftingSeq.insert(*varIter);
      Idx pos = siftingSeq.pos(*varIter);
      while (pos > 0 && varLvlSize[siftingSeq.atPos(pos - 1)] > nbElem) {
        siftingSeq.swap(pos - 1, pos);
        pos--;
      }
    }
 
    // Sifting var par var
    for (SequenceIteratorSafe< const DiscreteVariable* > sifIter = siftingSeq.beginSafe();
         sifIter != siftingSeq.endSafe();
         ++sifIter) {
      // Initialization
      Idx currentPos = _functionGraph_->variablesSequence().pos(*sifIter);
      Idx bestSize   = _functionGraph_->realSize();
      Idx bestPos    = currentPos;
 
 
      // Sifting towards upper places
      while (currentPos > 0) {
        moveTo(*sifIter, currentPos - 1);
        currentPos = _functionGraph_->variablesSequence().pos(*sifIter);
        if (_functionGraph_->realSize() < bestSize) {
          bestPos  = currentPos;
          bestSize = _functionGraph_->realSize();
        }
      }
 
      // Sifting towards lower places
      while (currentPos < _functionGraph_->variablesSequence().size() - 1) {
        moveTo(*sifIter, currentPos + 1);
        currentPos = _functionGraph_->variablesSequence().pos(*sifIter);
        if (_functionGraph_->realSize() < bestSize) {
          bestPos  = currentPos;
          bestSize = _functionGraph_->realSize();
        }
      }
 
      moveTo(*sifIter, bestPos);
    }
  }

References MultiDimFunctionGraphManager(), and minimizeSize().

Referenced by 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 )

inherited

Changes var position in variable sequence.

Parameters

x	The varaible to change.
desiredPos	The new posiition.

Definition at line 281 of file multiDimFunctionGraphManager_tpl.h.

                                          {
    // First we determine the position of both variable
    // We also determine which one precede the other
    if (_functionGraph_->variablesSequence().pos(movedVar) > desiredPos)
      for (Idx currentPos = _functionGraph_->variablesSequence().pos(movedVar);
           currentPos != desiredPos;
           currentPos--) {
        const DiscreteVariable* preVar = _functionGraph_->variablesSequence().atPos(currentPos - 1);
        if (_functionGraph_->_var2NodeIdMap_[preVar]->list()
            && _functionGraph_->_var2NodeIdMap_[movedVar]->list())
          _adjacentSwap_(preVar, movedVar);
        _functionGraph_->invert_(currentPos - 1, currentPos);
      }
    else
      for (Idx currentPos = _functionGraph_->variablesSequence().pos(movedVar);
           currentPos != desiredPos;
           currentPos++) {
        const DiscreteVariable* suiVar = _functionGraph_->variablesSequence().atPos(currentPos + 1);
        if (_functionGraph_->_var2NodeIdMap_[suiVar]->list()
            && _functionGraph_->_var2NodeIdMap_[movedVar]->list())
          _adjacentSwap_(movedVar, suiVar);
        _functionGraph_->invert_(currentPos, currentPos + 1);
      }
  }

References moveTo().

Referenced by 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 )

protectedinherited

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

var	The node to add in the graph.
sonsMap	The node sons.

Returns

Returns the nodes id in the graph.

Definition at line 438 of file multiDimFunctionGraphManager_tpl.h.

                                       {
    NodeId newNode = sonsIds[0];
 
    if (_isRedundant_(var, sonsIds)) {
      SOA_DEALLOCATE(sonsIds, sizeof(NodeId) * var->domainSize());
    } else {
      newNode = _checkIsomorphism_(var, sonsIds);
      if (newNode == 0) {
        newNode = addInternalNode_(var, sonsIds);
      } else {
        SOA_DEALLOCATE(sonsIds, sizeof(NodeId) * var->domainSize());
      }
    }
 
    return newNode;
  }

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

Referenced by 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< class > class TerminalNodePolicy>

void gum::MultiDimFunctionGraphTreeManager< GUM_ELEMENT, TerminalNodePolicy >::reduce ( )

overridevirtual

Ensures that every isomorphic subgraphs are merged together.

Implements gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >.

Definition at line 590 of file multiDimFunctionGraphManager_tpl.h.

{}

reduce_()

template<typename GUM_ELEMENT, template< class > class TerminalNodePolicy>

void gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::reduce_ ( )

protectedinherited

Ensures that every isomorphic subgraphs are merged together.

Definition at line 493 of file multiDimFunctionGraphManager_tpl.h.

                                                                                {
    Link< NodeId >* currentNodeId = nullptr;
    Link< NodeId >* nextNodeId    = nullptr;
    InternalNode*   currentNode   = nullptr;
    bool            theSame       = true;
    Idx             currentInd;
 
    for (SequenceIterator< const DiscreteVariable* > varIter
         = _functionGraph_->variablesSequence().rbegin();
         varIter != _functionGraph_->variablesSequence().rend();
         --varIter) {
      currentNodeId = _functionGraph_->_var2NodeIdMap_[*varIter]->list();
 
      while (currentNodeId != nullptr) {
        nextNodeId  = currentNodeId->nextLink();
        currentNode = _functionGraph_->_internalNodeMap_[currentNodeId->element()];
 
        // First isomorphism to handle is the one where all node children are
        // the same
        theSame = true;
        for (currentInd = 1; currentInd < (*varIter)->domainSize(); currentInd++) {
          if (currentNode->son(currentInd) != currentNode->son(0)) {
            theSame = false;
            break;
          }
        }
 
        if (theSame == true) {
          migrateNode_(currentNodeId->element(), currentNode->son(0));
          _functionGraph_->_var2NodeIdMap_[*varIter]->searchAndRemoveLink(currentNodeId->element());
          currentNodeId = nextNodeId;
          continue;
        }
 
        // Second isomorphism to handle is the one where two nodes have same
        // variable and same children
        if (nextNodeId) {
          Link< NodeId >* anotherNodeId = currentNodeId->nextLink();
          InternalNode*   anotherNode   = nullptr;
          Idx             modality      = 0;
          while (anotherNodeId->nextLink() != nullptr) {
            nextNodeId  = anotherNodeId->nextLink();
            anotherNode = _functionGraph_->_internalNodeMap_[anotherNodeId->element()];
 
            // Check on the other sons
            for (modality = 0; modality < (*varIter)->domainSize(); ++modality) {
              if (anotherNode->son(modality) != currentNode->son(modality)) break;
              if (modality == (*varIter)->domainSize() - 1) {
                migrateNode_(anotherNodeId->element(), currentNodeId->element());
                _functionGraph_->_var2NodeIdMap_[*varIter]->searchAndRemoveLink(
                    anotherNodeId->element());
              }
            }
 
            anotherNodeId = nextNodeId;
          }
        }
        currentNodeId = currentNodeId->nextLink();
      }
    }
  }

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

Referenced by 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 )

inherited

Sets root node of decision diagram.

Parameters

root	The node to set as root.

Definition at line 75 of file multiDimFunctionGraphManager_tpl.h.

                          {
    _functionGraph_->_root_ = root;
  }

References _functionGraph_.

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

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 )

inherited

Sets nodes son for given modality to designated son node.

Parameters

node	The node to which a node is added.
modality	The modality for which sonNode is added to node.
sonNode	The node to add as a son to node.

Definition at line 181 of file multiDimFunctionGraphManager_tpl.h.

                             {
    // Ensuring that both nodes exists in the graph
    if (!_functionGraph_->_model_.exists(node))
      GUM_ERROR(NotFound, "Node : " << node << " doesn't exists in the graph")
    if (!_functionGraph_->_model_.exists(sonNode))
      GUM_ERROR(NotFound, "Node : " << sonNode << " doesn't exists in the graph")
 
    // Check if starting node is not terminal
    if (_functionGraph_->isTerminalNode(node))
      GUM_ERROR(InvalidNode, "You cannot insert an arc from terminal node : " << node)
 
    // Check if associated modality is lower than node bound variable domain
    // size
    if (_functionGraph_->isInternalNode(node)
        && modality > _functionGraph_->_internalNodeMap_[node]->nodeVar()->domainSize() - 1)
      GUM_ERROR(InvalidArgument,
                "Modality " << modality << "is higher than domain size "
                            << _functionGraph_->_internalNodeMap_[node]->nodeVar()->domainSize()
                            << "minus 1 of variable "
                            << _functionGraph_->_internalNodeMap_[node]->nodeVar()->name())
 
    // Check if variable order is respected
    if (_functionGraph_->isInternalNode(sonNode)
        && _functionGraph_->variablesSequence().pos(
               _functionGraph_->_internalNodeMap_[node]->nodeVar())
               >= _functionGraph_->variablesSequence().pos(
                   _functionGraph_->_internalNodeMap_[sonNode]->nodeVar()))
      GUM_ERROR(OperationNotAllowed,
                "Variable " << _functionGraph_->_internalNodeMap_[node]->nodeVar()
                            << " is after variable "
                            << _functionGraph_->_internalNodeMap_[sonNode]->nodeVar()
                            << "in Function Graph order.")
 
    _functionGraph_->_internalNodeMap_[node]->setSon(modality, sonNode);
    if (sonNode && !_functionGraph_->isTerminalNode(sonNode))
      _functionGraph_->_internalNodeMap_[sonNode]->addParent(node, modality);
  }

References _functionGraph_, GUM_ERROR, and setSon().

Referenced by gum::MultiDimFunctionGraphGenerator::generate(), migrateNode_(), and setSon().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Symbol Documentation

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.

Member Data Documentation

_functionGraph_

template<typename GUM_ELEMENT, template< typename > class TerminalNodePolicy>

MultiDimFunctionGraph< GUM_ELEMENT, TerminalNodePolicy >* gum::MultiDimFunctionGraphManager< GUM_ELEMENT, TerminalNodePolicy >::_functionGraph_

privateinherited

The multidimdecisiongraph supposed to be edited.

Definition at line 334 of file multiDimFunctionGraphManager.h.

Referenced by MultiDimFunctionGraphManager(), _adjacentSwap_(), _checkIsomorphism_(), addInternalNode(), addInternalNode(), addInternalNode_(), addTerminalNode(), clean(), eraseNode(), migrateNode_(), reduce_(), setRootNode(), and setSon().

---

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

• agrum/base/multidim/implementations/multiDimFunctionGraph.h
• agrum/base/multidim/implementations/multiDimFunctionGraphManager.h
• agrum/base/multidim/implementations/multiDimFunctionGraphManager_tpl.h