multiDimFunctionGraphManager_tpl.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2025 by                                             *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *                                                                          *
 *   The aGrUM/pyAgrum library is free software; you can redistribute it    *
 *   and/or modify it under the terms of either :                           *
 *                                                                          *
 *    - the GNU Lesser General Public License as published by               *
 *      the Free Software Foundation, either version 3 of the License,      *
 *      or (at your option) any later version,                              *
 *    - the MIT license (MIT),                                              *
 *    - or both in dual license, as here.                                   *
 *                                                                          *
 *   (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html)    *
 *                                                                          *
 *   This aGrUM/pyAgrum library is distributed in the hope that it will be  *
 *   useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,          *
 *   INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
 *   FOR A PARTICULAR PURPOSE  AND NONINFRINGEMENT. IN NO EVENT SHALL THE   *
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,        *
 *   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR  *
 *   OTHER DEALINGS IN THE SOFTWARE.                                        *
 *                                                                          *
 *   See LICENCES for more details.                                         *
 *                                                                          *
 *   SPDX-FileCopyrightText: Copyright 2005-2025                            *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *   SPDX-License-Identifier: LGPL-3.0-or-later OR MIT                      *
 *                                                                          *
 *   Contact  : info_at_agrum_dot_org                                       *
 *   homepage : http://agrum.gitlab.io                                      *
 *   gitlab   : https://gitlab.com/agrumery/agrum                           *
 *                                                                          *
 ****************************************************************************/
#pragma once
 

#include <agrum/base/core/sequence.h>
#include <agrum/base/multidim/implementations/multiDimFunctionGraphManager.h>
#include <agrum/base/multidim/utils/FunctionGraphUtilities/link.h>
 
namespace gum {
 
  // Default constructor
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE
      MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::MultiDimFunctionGraphManager(
          MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >* mddg) {
    GUM_CONSTRUCTOR(MultiDimFunctionGraphManager);
    _functionGraph_ = mddg;
  }
 
  // Destructor
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE MultiDimFunctionGraphManager< GUM_SCALAR,
                                       TerminalNodePolicy >::~MultiDimFunctionGraphManager() {
    GUM_DESTRUCTOR(MultiDimFunctionGraphManager);
  }

  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::setRootNode(
      const NodeId& root) {
    _functionGraph_->_root_ = root;
  }
 
  // Inserts a new non terminal node in graph.
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE NodeId MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::addInternalNode(
      const DiscreteVariable* var,
      NodeId                  nid) {
    InternalNode* newNodeStruct = new InternalNode(var);
 
    _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
 
    _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
 
    return nid;
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE NodeId MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::addInternalNode(
      const DiscreteVariable* var) {
    InternalNode* newNodeStruct = new InternalNode(var);
    NodeId        nid           = _functionGraph_->_model_.addNode();
    _functionGraph_->_internalNodeMap_.insert(nid, newNodeStruct);
    _functionGraph_->_var2NodeIdMap_[var]->addLink(nid);
 
    return nid;
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE NodeId MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::addInternalNode_(
      const DiscreteVariable* var,
      NodeId*                 sons) {
    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;
  }
 
  // Adds a value to the MultiDimFunctionGraph.
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE NodeId MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::addTerminalNode(
      const GUM_SCALAR& value) {
    if (_functionGraph_->existsTerminalNodeWithValue(value))
      return _functionGraph_->terminalNodeId(value);
 
    NodeId node = _functionGraph_->_model_.addNode();
    _functionGraph_->addTerminalNode(node, value);
    return node;
  }
 
  // Erases a node from the diagram.
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::eraseNode(
      NodeId eraseId,
      NodeId replacingId,
      bool   updateParents) {
    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;
  }

  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::setSon(
      const NodeId& node,
      const Idx&    modality,
      const NodeId& sonNode) {
    // 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);
  }
 
  // Changes var position in variable sequence
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::minimizeSize() {
    // 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);
    }
  }
 
  // Changes var position in variable sequence
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::moveTo(
      const DiscreteVariable* movedVar,
      Idx                     desiredPos) {
    // 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);
      }
  }
 
  // Swap two adjacent variable.
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::_adjacentSwap_(
      const DiscreteVariable* x,
      const DiscreteVariable* y) {
    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;
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::migrateNode_(
      const NodeId& origin,
      const NodeId& destination) {
    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);
  }
 
  // Checks if a similar node does not already exists in the graph or
  // if it has the same child for every variable value.
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE NodeId
      MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::nodeRedundancyCheck_(
          const DiscreteVariable* var,
          NodeId*                 sonsIds) {
    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;
  }
 
  // Checks if a similar node does not already exists in the graph.
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE NodeId MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::_checkIsomorphism_(
      const DiscreteVariable* var,
      NodeId*                 sons) {
    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;
  }
 
  // Checks if node has the same child for every variable value
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE bool MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::_isRedundant_(
      const DiscreteVariable* var,
      NodeId*                 sons) {
    for (Idx m = 1; m < var->domainSize(); m++)
      if (sons[m] != sons[0]) return false;
    return true;
  }
 
  // Ensures that every isomorphic subgraphs are merged together.
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::reduce_() {
    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();
      }
    }
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  INLINE void MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::clean() {
    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);
  }
 
  // ==========================================================================
  // MultiDimFunctionGraphTreeManager
  // ==========================================================================
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  MultiDimFunctionGraphTreeManager< GUM_SCALAR, TerminalNodePolicy >::
      MultiDimFunctionGraphTreeManager(
          MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >* master) :
      MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >(master) {
    GUM_CONSTRUCTOR(MultiDimFunctionGraphTreeManager);
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  MultiDimFunctionGraphTreeManager< GUM_SCALAR,
                                    TerminalNodePolicy >::~MultiDimFunctionGraphTreeManager() {
    GUM_DESTRUCTOR(MultiDimFunctionGraphTreeManager);
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  NodeId MultiDimFunctionGraphTreeManager< GUM_SCALAR, TerminalNodePolicy >::addInternalNode(
      const DiscreteVariable* var,
      NodeId*                 sons) {
    return this->addInternalNode_(var, sons);
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  void MultiDimFunctionGraphTreeManager< GUM_SCALAR, TerminalNodePolicy >::reduce() {}
 
  // ===========================================================================
  // MultiDimFunctionGraphROManager
  // ===========================================================================
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  MultiDimFunctionGraphROManager< GUM_SCALAR, TerminalNodePolicy >::MultiDimFunctionGraphROManager(
      MultiDimFunctionGraph< GUM_SCALAR, TerminalNodePolicy >* master) :
      MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >(master) {
    GUM_CONSTRUCTOR(MultiDimFunctionGraphROManager);
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  MultiDimFunctionGraphROManager< GUM_SCALAR,
                                  TerminalNodePolicy >::~MultiDimFunctionGraphROManager() {
    GUM_DESTRUCTOR(MultiDimFunctionGraphROManager);
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  NodeId MultiDimFunctionGraphROManager< GUM_SCALAR, TerminalNodePolicy >::addInternalNode(
      const DiscreteVariable* var,
      NodeId*                 sons) {
    return this->nodeRedundancyCheck_(var, sons);
  }
 
  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
  void MultiDimFunctionGraphROManager< GUM_SCALAR, TerminalNodePolicy >::reduce() {
    this->reduce_();
  }
 
}   // namespace gum