aGrUM  0.13.2
gum::prm::gspan::TreeWidthSearch< GUM_SCALAR > Class Template Reference

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...
 
TreeWidthSearchoperator= (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 260 of file searchStrategy.h.

Constructor & Destructor Documentation

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

Default constructor.

Definition at line 402 of file searchStrategy_tpl.h.

402  :
403  SearchStrategy< GUM_SCALAR >() {
404  GUM_CONSTRUCTOR(TreeWidthSearch);
405  }
TreeWidthSearch()
Default constructor.
template<typename GUM_SCALAR >
INLINE gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::TreeWidthSearch ( const TreeWidthSearch< GUM_SCALAR > &  from)

Copy constructor.

Definition at line 408 of file searchStrategy_tpl.h.

409  :
410  SearchStrategy< GUM_SCALAR >(from) {
411  GUM_CONS_CPY(TreeWidthSearch);
412  }
TreeWidthSearch()
Default constructor.
template<typename GUM_SCALAR >
INLINE gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::~TreeWidthSearch ( )
virtual

Destructor.

Definition at line 415 of file searchStrategy_tpl.h.

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

415  {
416  GUM_DESTRUCTOR(TreeWidthSearch);
417  }
TreeWidthSearch()
Default constructor.

+ Here is the call graph for this function:

Member Function Documentation

template<typename GUM_SCALAR >
double gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_computeCost ( const Pattern p)
protectedinherited

Definition at line 33 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().

33  {
34  double cost = 0;
35  const Sequence< PRMInstance< GUM_SCALAR >* >& seq =
36  *(this->_tree->data(p).iso_map.begin().val());
37  Sequence< PRMClassElement< GUM_SCALAR >* > input_set;
38 
39  for (const auto inst : seq) {
40  for (const auto input : inst->type().slotChains())
41  for (const auto inst2 : inst->getInstances(input->id()))
42  if ((!seq.exists(inst2))
43  && (!input_set.exists(
44  &(inst2->get(input->lastElt().safeName()))))) {
45  cost += std::log(input->type().variable().domainSize());
46  input_set.insert(&(inst2->get(input->lastElt().safeName())));
47  }
48 
49  for (auto vec = inst->beginInvRef(); vec != inst->endInvRef(); ++vec)
50  for (const auto inverse : *vec.val())
51  if (!seq.exists(inverse.first)) {
52  cost +=
53  std::log(inst->get(vec.key()).type().variable().domainSize());
54  break;
55  }
56  }
57 
58  return cost;
59  }
DFSTree< GUM_SCALAR > * _tree

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 446 of file searchStrategy_tpl.h.

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

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

+ Here is the call graph for this function:

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 436 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.

436  {
437  Size tree_width = 0;
438 
439  for (const auto n : r->nodes())
440  tree_width += r->label(n).tree_width;
441 
442  return tree_width >= cost(*r);
443  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50

+ Here is the call graph for this function:

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

Definition at line 426 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()().

426  {
427  try {
428  return __map[&p];
429  } catch (NotFound&) {
430  __map.insert(&p, this->_computeCost(p));
431  return __map[&p];
432  }
433  }
HashTable< const Pattern *, double > __map
double _computeCost(const Pattern &p)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 460 of file searchStrategy_tpl.h.

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

461  {
462  return i->tree_width < j->tree_width;
463  }
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 454 of file searchStrategy_tpl.h.

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

455  {
456  return cost(*i) < cost(*j);
457  }

+ Here is the call graph for this function:

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 421 of file searchStrategy_tpl.h.

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

421  {
422  return *this;
423  }

+ Here is the caller graph for this function:

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

Definition at line 230 of file searchStrategy_tpl.h.

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

230  {
231  this->_tree = tree;
232  }
DFSTree< GUM_SCALAR > * _tree

Member Data Documentation

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

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