A growth is accepted if and only if the new growth has a tree width less large or equal than its father. More...

#include <agrum/PRM/gspan/DFSTree.h>

Inheritance diagram for gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >:

Collaboration diagram for gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >:

Public Member Functions
Constructor and destructor.
	TreeWidthSearch ()
	Default constructor. More...

	TreeWidthSearch (const TreeWidthSearch &from)
	Copy constructor. More...

virtual	~TreeWidthSearch ()
	Destructor. More...

TreeWidthSearch &	operator= (const TreeWidthSearch &from)
	Copy operator. More...

Search methods.
double	cost (const Pattern &p)

virtual bool	accept_root (const Pattern *r)

virtual bool	accept_growth (const Pattern parent, const Pattern child, const EdgeGrowth< GUM_SCALAR > &growth)

virtual bool	operator() (LabelData i, LabelData j)

virtual bool	operator() (Pattern i, Pattern j)

Search methods.
void	setTree (DFSTree< GUM_SCALAR > *tree)

Protected Attributes
DFSTree< GUM_SCALAR > *	_tree

Protected Member Functions
double	_computeCost (const Pattern &p)

Detailed Description

template<typename GUM_SCALAR>
class gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >

A growth is accepted if and only if the new growth has a tree width less large or equal than its father.

Definition at line 263 of file searchStrategy.h.

Constructor & Destructor Documentation

◆ TreeWidthSearch() [1/2]

template<typename GUM_SCALAR >

INLINE gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::TreeWidthSearch ( )

Default constructor.

Definition at line 406 of file searchStrategy_tpl.h.

                                                             :
           SearchStrategy< GUM_SCALAR >() {
         GUM_CONSTRUCTOR(TreeWidthSearch);
       }

◆ TreeWidthSearch() [2/2]

template<typename GUM_SCALAR >

INLINE gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::TreeWidthSearch ( const TreeWidthSearch< GUM_SCALAR > & from )

Copy constructor.

Definition at line 412 of file searchStrategy_tpl.h.

                                                     :
           SearchStrategy< GUM_SCALAR >(from) {
         GUM_CONS_CPY(TreeWidthSearch);
       }

◆ ~TreeWidthSearch()

template<typename GUM_SCALAR >

INLINE gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::~TreeWidthSearch ( )

virtual

Destructor.

Definition at line 419 of file searchStrategy_tpl.h.

                                                              {
         GUM_DESTRUCTOR(TreeWidthSearch);
       }

Member Function Documentation

◆ _computeCost()

template<typename GUM_SCALAR >

double gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_computeCost ( const Pattern & p )

protectedinherited

Definition at line 36 of file searchStrategy_tpl.h.

References gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::exists(), and gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::insert().

Referenced by gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs(), and gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::cost().

                                                                         {
         double                                        cost = 0;
         const Sequence< PRMInstance< GUM_SCALAR >* >& seq =
            *(this->_tree->data(p).iso_map.begin().val());
         Sequence< PRMClassElement< GUM_SCALAR >* > input_set;
 
         for (const auto inst: seq) {
           for (const auto input: inst->type().slotChains())
             for (const auto inst2: inst->getInstances(input->id()))
               if ((!seq.exists(inst2))
                   && (!input_set.exists(
                      &(inst2->get(input->lastElt().safeName()))))) {
                 cost += std::log(input->type().variable().domainSize());
                 input_set.insert(&(inst2->get(input->lastElt().safeName())));
               }
 
           for (auto vec = inst->beginInvRef(); vec != inst->endInvRef(); ++vec)
             for (const auto inverse: *vec.val())
               if (!seq.exists(inverse.first)) {
                 cost +=
                    std::log(inst->get(vec.key()).type().variable().domainSize());
                 break;
               }
         }
 
         return cost;
       }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ accept_growth()

template<typename GUM_SCALAR >

INLINE bool gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::accept_growth	(	const Pattern *	parent,
		const Pattern *	child,
		const EdgeGrowth< GUM_SCALAR > &	growth
	)

virtual

Implements gum::prm::gspan::SearchStrategy< GUM_SCALAR >.

Definition at line 451 of file searchStrategy_tpl.h.

References gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::cost().

                                                  {
         return cost(*parent) >= cost(*child);
       }

Here is the call graph for this function:

◆ accept_root()

template<typename GUM_SCALAR >

INLINE bool gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::accept_root ( const Pattern * r )

virtual

Implements gum::prm::gspan::SearchStrategy< GUM_SCALAR >.

Definition at line 441 of file searchStrategy_tpl.h.

References gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::cost(), gum::prm::gspan::Pattern::label(), gum::prm::gspan::Pattern::nodes(), and gum::prm::gspan::LabelData::tree_width.

                                                                              {
         Size tree_width = 0;
 
         for (const auto n: r->nodes())
           tree_width += r->label(n).tree_width;
 
         return tree_width >= cost(*r);
       }

Here is the call graph for this function:

◆ cost()

template<typename GUM_SCALAR >

INLINE double gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::cost ( const Pattern & p )

Definition at line 431 of file searchStrategy_tpl.h.

References gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::__map, and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_computeCost().

Referenced by gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::accept_growth(), gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::accept_root(), and gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::operator()().

                                                                         {
         try {
           return __map[&p];
         } catch (NotFound&) {
           __map.insert(&p, this->_computeCost(p));
           return __map[&p];
         }
       }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator()() [1/2]

template<typename GUM_SCALAR >

INLINE bool gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::operator()	(	LabelData *	i,
		LabelData *	j
	)

virtual

Implements gum::prm::gspan::SearchStrategy< GUM_SCALAR >.

Definition at line 465 of file searchStrategy_tpl.h.

References gum::prm::gspan::LabelData::tree_width.

                                                                           {
         return i->tree_width < j->tree_width;
       }

◆ operator()() [2/2]

template<typename GUM_SCALAR >

INLINE bool gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::operator()	(	gspan::Pattern *	i,
		gspan::Pattern *	j
	)

virtual

Implements gum::prm::gspan::SearchStrategy< GUM_SCALAR >.

Definition at line 459 of file searchStrategy_tpl.h.

References gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::cost().

                                                                              {
         return cost(*i) < cost(*j);
       }

Here is the call graph for this function:

◆ operator=()

template<typename GUM_SCALAR >

INLINE TreeWidthSearch< GUM_SCALAR > & gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::operator= ( const TreeWidthSearch< GUM_SCALAR > & from )

Copy operator.

Definition at line 425 of file searchStrategy_tpl.h.

                                                        {
         return *this;
       }

◆ setTree()

template<typename GUM_SCALAR >

INLINE void gum::prm::gspan::SearchStrategy< GUM_SCALAR >::setTree ( DFSTree< GUM_SCALAR > * tree )

inherited

Definition at line 233 of file searchStrategy_tpl.h.

References gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_tree.

                                                                           {
         this->_tree = tree;
       }

Member Data Documentation

◆ __map

template<typename GUM_SCALAR>

HashTable< const Pattern*, double > gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::__map

private

Definition at line 301 of file searchStrategy.h.

Referenced by gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::cost().

◆ _tree

template<typename GUM_SCALAR>

DFSTree< GUM_SCALAR >* gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_tree

protectedinherited

Definition at line 112 of file searchStrategy.h.

Referenced by gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs(), gum::prm::gspan::FrequenceSearch< GUM_SCALAR >::accept_growth(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::accept_growth(), gum::prm::gspan::FrequenceSearch< GUM_SCALAR >::accept_root(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::accept_root(), gum::prm::gspan::FrequenceSearch< GUM_SCALAR >::operator()(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::operator()(), gum::prm::gspan::SearchStrategy< GUM_SCALAR >::operator=(), and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::setTree().

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

agrum/PRM/gspan/searchStrategy.h
agrum/PRM/gspan/searchStrategy_tpl.h

Public Member Functions

Protected Attributes

Protected Member Functions

Detailed Description

template<typename GUM_SCALAR> class gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >

Constructor & Destructor Documentation

◆ TreeWidthSearch() [1/2]

◆ TreeWidthSearch() [2/2]

◆ ~TreeWidthSearch()

Member Function Documentation

◆ _computeCost()

◆ accept_growth()

◆ accept_root()

◆ cost()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator=()

◆ setTree()

Member Data Documentation

◆ __map

◆ _tree

template<typename GUM_SCALAR>
class gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >