Class implementingting a function graph manager. More...

#include <multiDimFunctionGraphManager.h>

Inheritance diagram for gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >:

Collaboration diagram for gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >:

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

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

Constructors / Destructors
MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy > *	MultiDimFunctionGraph ()
	This friend methods from is the only way to get an instance of a manager.
	MultiDimFunctionGraphManager (MultiDimFunctionGraph< GUM_SCALAR, 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_SCALAR &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_SCALAR, template< typename > class TerminalNodePolicy>
class gum::MultiDimFunctionGraphManager< GUM_SCALAR, 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.
#include <agrum/base/multidim/implementations/multiDimFunctionGraphManager.h>

multiDimFunctionGraphManager.h
Headers of MultiDimFunctionGraphManager.

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 =
   MultiDimFunctionGraph<double>::getReducedAndOrderedInstance();
auto manager = dg->manager();

Template Parameters

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

Definition at line 97 of file multiDimFunctionGraphManager.h.

Constructor & Destructor Documentation

◆ MultiDimFunctionGraphManager()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

INLINE gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::MultiDimFunctionGraphManager ( MultiDimFunctionGraph< GUM_SCALAR, 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.

                                                                         {
    GUM_CONSTRUCTOR(MultiDimFunctionGraphManager);
    _functionGraph_ = mddg;
  }

References MultiDimFunctionGraphManager(), and _functionGraph_.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ~MultiDimFunctionGraphManager()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

INLINE gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::~MultiDimFunctionGraphManager ( )

virtual

Class destructor.

Definition at line 70 of file multiDimFunctionGraphManager_tpl.h.

                                                                                           {
    GUM_DESTRUCTOR(MultiDimFunctionGraphManager);
  }

References MultiDimFunctionGraphManager(), and ~MultiDimFunctionGraphManager().

Referenced by ~MultiDimFunctionGraphManager().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

◆ _adjacentSwap_()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

void gum::MultiDimFunctionGraphManager< GUM_SCALAR, 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

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

Definition at line 311 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_SCALAR, template< class > class TerminalNodePolicy>

INLINE NodeId gum::MultiDimFunctionGraphManager< GUM_SCALAR, 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

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

Returns: Returns the node id if found, 0 otherwhise.

Definition at line 461 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_SCALAR, template< class > class TerminalNodePolicy>

INLINE bool gum::MultiDimFunctionGraphManager< GUM_SCALAR, 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

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

Returns: Returns true if the node is redundant.

Definition at line 485 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_SCALAR, template< class > class TerminalNodePolicy>

INLINE NodeId gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::addInternalNode ( const DiscreteVariable * var )

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 96 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_SCALAR, template< typename > class TerminalNodePolicy>

virtual NodeId gum::MultiDimFunctionGraphManager< GUM_SCALAR, 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

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.

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

◆ addInternalNode() [3/3]

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

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

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 83 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_()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

INLINE NodeId gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::addInternalNode_	(	const DiscreteVariable *	var,
		NodeId *	sons )

protected

Adds an internal node.

Parameters

var	The node to add.
sons	The node sons.

Returns: Returns the added node id.

Definition at line 107 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_SCALAR, TerminalNodePolicy >::addInternalNode(), and nodeRedundancyCheck_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addTerminalNode()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

INLINE NodeId gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::addTerminalNode ( const GUM_SCALAR & 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

value The value added by copy.

Returns: Returns he id of the terminal node hence created.

Definition at line 123 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_SCALAR, template< class > class TerminalNodePolicy>

INLINE void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::clean ( )

Removes var without nodes in the diagram.

Definition at line 558 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_SCALAR, template< class > class TerminalNodePolicy>

void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::eraseNode	(	NodeId	id,
		NodeId	replacingId = 0,
		bool	updateParents = true )

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 135 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;
  }

◆ migrateNode_()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

INLINE void gum::MultiDimFunctionGraphManager< GUM_SCALAR, 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

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

Definition at line 413 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_SCALAR, template< class > class TerminalNodePolicy>

void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::minimizeSize ( )

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

Definition at line 225 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_SCALAR, template< class > class TerminalNodePolicy>

void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::moveTo	(	const DiscreteVariable *	x,
		Idx	desiredPos )

Changes var position in variable sequence.

Parameters

x	The varaible to change.
desiredPos	The new posiition.

Definition at line 282 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_SCALAR, template< class > class TerminalNodePolicy>

INLINE NodeId gum::MultiDimFunctionGraphManager< GUM_SCALAR, 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 itslef 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 440 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_SCALAR, TerminalNodePolicy >::addInternalNode(), and nodeRedundancyCheck_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reduce()

template<typename GUM_SCALAR, template< typename > class TerminalNodePolicy>

virtual void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::reduce ( )

pure virtual

Ensures that every isomorphic subgraphs are merged together.

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

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

Here is the caller graph for this function:

◆ reduce_()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

INLINE void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::reduce_ ( )

protected

Ensures that every isomorphic subgraphs are merged together.

Definition at line 495 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_SCALAR, TerminalNodePolicy >::reduce(), and reduce_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setRootNode()

template<typename GUM_SCALAR, template< class > class TerminalNodePolicy>

INLINE void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::setRootNode ( const NodeId & root )

Sets root node of decision diagram.

Parameters

root	The node to set as root.

Definition at line 76 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_SCALAR, template< class > class TerminalNodePolicy>

INLINE void gum::MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy >::setSon	(	const NodeId &	node,
		const Idx &	modality,
		const NodeId &	sonNode )

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 182 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:

◆ MultiDimFunctionGraph

template<typename GUM_SCALAR, template< typename > class TerminalNodePolicy>

MultiDimFunctionGraphManager< GUM_SCALAR, TerminalNodePolicy > * MultiDimFunctionGraph ( )

friend

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

See class description for more info.

Member Data Documentation

◆ _functionGraph_

template<typename GUM_SCALAR, template< typename > class TerminalNodePolicy>

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

private

The multidimdecisiongraph supposed to be edited.

Definition at line 334 of file multiDimFunctionGraphManager.h.

Referenced by MultiDimFunctionGraphManager(), _adjacentSwap_(), _checkIsomorphism_(), addInternalNode(), addInternalNode(), addInternalNode_(), addTerminalNode(), clean(), 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

Public Member Functions

Private Attributes

Constructors / Destructors

Nodes manipulation methods.

Manipulation methods.

Redundancy methods.

Detailed Description

Constructor & Destructor Documentation

◆ MultiDimFunctionGraphManager()

◆ ~MultiDimFunctionGraphManager()

Member Function Documentation

◆ _adjacentSwap_()

◆ _checkIsomorphism_()

◆ _isRedundant_()

◆ addInternalNode() [1/3]

◆ addInternalNode() [2/3]

◆ addInternalNode() [3/3]

◆ addInternalNode_()

◆ addTerminalNode()

◆ clean()

◆ eraseNode()

◆ migrateNode_()

◆ minimizeSize()

◆ moveTo()

◆ nodeRedundancyCheck_()

◆ reduce()

◆ reduce_()

◆ setRootNode()

◆ setSon()

Friends And Related Symbol Documentation

◆ MultiDimFunctionGraph

Member Data Documentation

◆ _functionGraph_