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

This is class is an implementation of a strict strategy for the GSpan algorithm. More...

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

+ Inheritance diagram for gum::prm::gspan::StrictSearch< GUM_SCALAR >:
+ Collaboration diagram for gum::prm::gspan::StrictSearch< GUM_SCALAR >:

Public Member Functions

Constructor and destructor.
 StrictSearch (Size freq=2)
 Default constructor. More...
 
 StrictSearch (const StrictSearch &from)
 Copy constructor. More...
 
virtual ~StrictSearch ()
 Destructor. More...
 
StrictSearchoperator= (const StrictSearch &from)
 Copy operator. More...
 
Search methods.
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)
 

Classes

struct  PData
 Private structure to represent data about a pattern. More...
 

Detailed Description

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

This is class is an implementation of a strict strategy for the GSpan algorithm.

This will force early cuts in the DFSTree and should help not spending much time searching for new patterns.

A new growth is accepted if it is at least better than its predecessor.

Definition at line 173 of file searchStrategy.h.

Constructor & Destructor Documentation

template<typename GUM_SCALAR >
INLINE gum::prm::gspan::StrictSearch< GUM_SCALAR >::StrictSearch ( Size  freq = 2)
explicit

Default constructor.

Definition at line 293 of file searchStrategy_tpl.h.

293  :
294  SearchStrategy< GUM_SCALAR >(), __freq(freq), __dot(".") {
295  GUM_CONSTRUCTOR(StrictSearch);
296  }
StrictSearch(Size freq=2)
Default constructor.
template<typename GUM_SCALAR >
INLINE gum::prm::gspan::StrictSearch< GUM_SCALAR >::StrictSearch ( const StrictSearch< GUM_SCALAR > &  from)

Copy constructor.

Definition at line 299 of file searchStrategy_tpl.h.

300  :
301  SearchStrategy< GUM_SCALAR >(from),
302  __freq(from.__freq) {
303  GUM_CONS_CPY(StrictSearch);
304  }
StrictSearch(Size freq=2)
Default constructor.
template<typename GUM_SCALAR >
INLINE gum::prm::gspan::StrictSearch< GUM_SCALAR >::~StrictSearch ( )
virtual

Destructor.

Definition at line 307 of file searchStrategy_tpl.h.

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

307  {
308  GUM_DESTRUCTOR(StrictSearch);
309  }
StrictSearch(Size freq=2)
Default constructor.

+ Here is the call graph for this function:

Member Function Documentation

template<typename GUM_SCALAR >
void gum::prm::gspan::StrictSearch< GUM_SCALAR >::__buildPatternGraph ( typename StrictSearch< GUM_SCALAR >::PData data,
Set< Potential< GUM_SCALAR > * > &  pool,
const Sequence< PRMInstance< GUM_SCALAR > * > &  match 
)
private

Definition at line 62 of file searchStrategy_tpl.h.

References gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNode(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::first(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::graph, gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::inners, gum::Set< Key, Alloc >::insert(), gum::BijectionImplementation< T1, T2, Alloc, Gen >::insert(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::mod, gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::node2attr, gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::outputs, and gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::vars.

Referenced by gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs().

65  {
66  for (const auto inst : match) {
67  for (const auto& elt : *inst) {
68  // Adding the node
69  NodeId id = data.graph.addNode();
70  data.node2attr.insert(id, __str(inst, elt.second));
71  data.mod.insert(id, elt.second->type()->domainSize());
72  data.vars.insert(id, &elt.second->type().variable());
73  pool.insert(
74  const_cast< Potential< GUM_SCALAR >* >(&(elt.second->cpf())));
75  }
76  }
77 
78  // Second we add edges and nodes to inners or outputs
79  for (const auto inst : match)
80  for (const auto& elt : *inst) {
81  NodeId node = data.node2attr.first(__str(inst, elt.second));
82  bool found =
83  false; // If this is set at true, then node is an outer node
84 
85  // Children existing in the instance type's DAG
86  for (const auto chld :
87  inst->type().containerDag().children(elt.second->id())) {
88  data.graph.addEdge(
89  node, data.node2attr.first(__str(inst, inst->get(chld))));
90  }
91 
92  // Parents existing in the instance type's DAG
93  for (const auto par :
94  inst->type().containerDag().parents(elt.second->id())) {
95  switch (inst->type().get(par).elt_type()) {
98  data.graph.addEdge(
99  node, data.node2attr.first(__str(inst, inst->get(par))));
100  break;
101  }
102 
104  for (const auto inst2 : inst->getInstances(par))
105  if (match.exists(inst2))
106  data.graph.addEdge(
107  node,
108  data.node2attr.first(
109  __str(inst2,
110  static_cast< const PRMSlotChain< GUM_SCALAR >& >(
111  inst->type().get(par)))));
112 
113  break;
114  }
115 
116  default: { /* Do nothing */
117  }
118  }
119  }
120 
121  // Referring PRMAttribute<GUM_SCALAR>
122  if (inst->hasRefAttr(elt.second->id())) {
123  const std::vector<
124  std::pair< PRMInstance< GUM_SCALAR >*, std::string > >& ref_attr =
125  inst->getRefAttr(elt.second->id());
126 
127  for (auto pair = ref_attr.begin(); pair != ref_attr.end(); ++pair) {
128  if (match.exists(pair->first)) {
129  NodeId id = pair->first->type().get(pair->second).id();
130 
131  for (const auto child :
132  pair->first->type().containerDag().children(id))
133  data.graph.addEdge(node,
134  data.node2attr.first(__str(
135  pair->first, pair->first->get(child))));
136  } else {
137  found = true;
138  }
139  }
140  }
141 
142  if (found)
143  data.outputs.insert(node);
144  else
145  data.inners.insert(node);
146  }
147  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
std::string __str(const PRMInstance< GUM_SCALAR > *i, const PRMAttribute< GUM_SCALAR > *a) const

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename GUM_SCALAR >
INLINE void gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs ( const Pattern p)
private

Definition at line 389 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__buildPatternGraph(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::__elimination_cost(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::__map, gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_computeCost(), and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_tree.

Referenced by gum::prm::gspan::StrictSearch< GUM_SCALAR >::__inner_cost(), and gum::prm::gspan::StrictSearch< GUM_SCALAR >::__outer_cost().

389  {
390  typename StrictSearch< GUM_SCALAR >::PData data;
391  Set< Potential< GUM_SCALAR >* > pool;
393  data, pool, *(this->_tree->data(*p).iso_map.begin().val()));
394  double inner = std::log(__elimination_cost(data, pool).first);
395  double outer = this->_computeCost(*p);
396  __map.insert(p, std::make_pair(inner, outer));
397  }
void __buildPatternGraph(typename StrictSearch< GUM_SCALAR >::PData &data, Set< Potential< GUM_SCALAR > * > &pool, const Sequence< PRMInstance< GUM_SCALAR > * > &match)
std::pair< Size, Size > __elimination_cost(typename StrictSearch< GUM_SCALAR >::PData &data, Set< Potential< GUM_SCALAR > * > &pool)
DFSTree< GUM_SCALAR > * _tree
HashTable< const Pattern *, std::pair< double, 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 >
std::pair< Size, Size > gum::prm::gspan::StrictSearch< GUM_SCALAR >::__elimination_cost ( typename StrictSearch< GUM_SCALAR >::PData data,
Set< Potential< GUM_SCALAR > * > &  pool 
)
private

Definition at line 150 of file searchStrategy_tpl.h.

References gum::MultiDimDecorator< GUM_SCALAR >::add(), gum::MultiDimDecorator< GUM_SCALAR >::domainSize(), gum::StaticTriangulation::eliminationOrder(), gum::MultiDimDecorator< GUM_SCALAR >::erase(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::graph, gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::inners, gum::Set< Key, Alloc >::insert(), gum::List< Val, Alloc >::insert(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::mod, gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::outputs, gum::Set< Key, Alloc >::size(), and gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::vars.

Referenced by gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs().

152  {
153  List< NodeSet > partial_order;
154 
155  if (data.inners.size()) partial_order.insert(data.inners);
156 
157  if (data.outputs.size()) partial_order.insert(data.outputs);
158 
159  PartialOrderedTriangulation t(&(data.graph), &(data.mod), &partial_order);
160  const std::vector< NodeId >& elim_order = t.eliminationOrder();
161  Size max(0), max_count(1);
162  Set< Potential< GUM_SCALAR >* > trash;
163  Potential< GUM_SCALAR >* pot = 0;
164 
165  for (size_t idx = 0; idx < data.inners.size(); ++idx) {
166  pot = new Potential< GUM_SCALAR >(new MultiDimSparse< GUM_SCALAR >(0));
167  pot->add(*(data.vars.second(elim_order[idx])));
168  trash.insert(pot);
169  Set< Potential< GUM_SCALAR >* > toRemove;
170 
171  for (const auto p : pool)
172  if (p->contains(*(data.vars.second(elim_order[idx])))) {
173  for (auto var = p->variablesSequence().begin();
174  var != p->variablesSequence().end();
175  ++var) {
176  try {
177  pot->add(**var);
178  } catch (DuplicateElement&) {}
179  }
180 
181  toRemove.insert(p);
182  }
183 
184  if (pot->domainSize() > max) {
185  max = pot->domainSize();
186  max_count = 1;
187  } else if (pot->domainSize() == max) {
188  ++max_count;
189  }
190 
191  for (const auto p : toRemove)
192  pool.erase(p);
193 
194  pot->erase(*(data.vars.second(elim_order[idx])));
195  }
196 
197  for (const auto pot : trash)
198  delete pot;
199 
200  return std::make_pair(max, max_count);
201  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename GUM_SCALAR >
INLINE double gum::prm::gspan::StrictSearch< GUM_SCALAR >::__inner_cost ( const Pattern p)
private

Definition at line 348 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs(), and gum::prm::gspan::StrictSearch< GUM_SCALAR >::__map.

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

348  {
349  try {
350  return __map[p].first;
351  } catch (NotFound&) {
352  __compute_costs(p);
353  return __map[p].first;
354  }
355  }
HashTable< const Pattern *, std::pair< double, double > > __map
void __compute_costs(const Pattern *p)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename GUM_SCALAR >
INLINE double gum::prm::gspan::StrictSearch< GUM_SCALAR >::__outer_cost ( const Pattern p)
private

Definition at line 358 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs(), and gum::prm::gspan::StrictSearch< GUM_SCALAR >::__map.

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

358  {
359  try {
360  return __map[p].second;
361  } catch (NotFound&) {
362  __compute_costs(p);
363  return __map[p].second;
364  }
365  }
HashTable< const Pattern *, std::pair< double, double > > __map
void __compute_costs(const Pattern *p)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename GUM_SCALAR >
INLINE std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::__str ( const PRMInstance< GUM_SCALAR > *  i,
const PRMAttribute< GUM_SCALAR > *  a 
) const
private

Definition at line 368 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__dot, gum::prm::PRMObject::name(), and gum::prm::PRMClassElement< GUM_SCALAR >::safeName().

370  {
371  return i->name() + __dot + a->safeName();
372  }

+ Here is the call graph for this function:

template<typename GUM_SCALAR >
INLINE std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::__str ( const PRMInstance< GUM_SCALAR > *  i,
const PRMAttribute< GUM_SCALAR > &  a 
) const
private

Definition at line 375 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__dot, gum::prm::PRMObject::name(), and gum::prm::PRMClassElement< GUM_SCALAR >::safeName().

377  {
378  return i->name() + __dot + a.safeName();
379  }

+ Here is the call graph for this function:

template<typename GUM_SCALAR >
INLINE std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::__str ( const PRMInstance< GUM_SCALAR > *  i,
const PRMSlotChain< GUM_SCALAR > &  a 
) const
private

Definition at line 382 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__dot, gum::prm::PRMSlotChain< GUM_SCALAR >::lastElt(), and gum::prm::PRMObject::name().

384  {
385  return i->name() + __dot + a.lastElt().safeName();
386  }

+ Here is the call graph for this function:

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::StrictSearch< 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 324 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__inner_cost(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::__outer_cost(), and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_tree.

327  {
328  return __inner_cost(child)
329  + this->_tree->frequency(*child) * __outer_cost(child)
330  < this->_tree->frequency(*child) * __outer_cost(parent);
331  }
double __outer_cost(const Pattern *p)
DFSTree< GUM_SCALAR > * _tree
double __inner_cost(const Pattern *p)

+ Here is the call graph for this function:

template<typename GUM_SCALAR >
INLINE bool gum::prm::gspan::StrictSearch< GUM_SCALAR >::accept_root ( const Pattern r)
virtual
template<typename GUM_SCALAR >
INLINE bool gum::prm::gspan::StrictSearch< GUM_SCALAR >::operator() ( LabelData i,
LabelData j 
)
virtual

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

Definition at line 341 of file searchStrategy_tpl.h.

References gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_tree, and gum::prm::gspan::LabelData::tree_width.

342  {
343  return i->tree_width * this->_tree->graph().size(i)
344  < j->tree_width * this->_tree->graph().size(j);
345  }
DFSTree< GUM_SCALAR > * _tree
template<typename GUM_SCALAR >
INLINE bool gum::prm::gspan::StrictSearch< GUM_SCALAR >::operator() ( gspan::Pattern i,
gspan::Pattern j 
)
virtual

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

Definition at line 334 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__inner_cost(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::__outer_cost(), and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_tree.

335  {
336  return __inner_cost(i) + this->_tree->frequency(*i) * __outer_cost(i)
337  < __inner_cost(j) + this->_tree->frequency(*j) * __outer_cost(j);
338  }
double __outer_cost(const Pattern *p)
DFSTree< GUM_SCALAR > * _tree
double __inner_cost(const Pattern *p)

+ Here is the call graph for this function:

template<typename GUM_SCALAR >
INLINE StrictSearch< GUM_SCALAR > & gum::prm::gspan::StrictSearch< GUM_SCALAR >::operator= ( const StrictSearch< GUM_SCALAR > &  from)

Copy operator.

Definition at line 313 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__freq.

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

313  {
314  __freq = from.__freq;
315  return *this;
316  }

+ 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>
std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::__dot
private
template<typename GUM_SCALAR>
Size gum::prm::gspan::StrictSearch< GUM_SCALAR >::__freq
private

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