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...
StrictSearch &	operator= (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 175 of file searchStrategy.h.

Constructor & Destructor Documentation

StrictSearch() [1/2]

template<typename GUM_SCALAR >

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

explicit

Default constructor.

Definition at line 280 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                               :
          SearchStrategy< GUM_SCALAR >(), _freq_(freq), _dot_(".") {
        GUM_CONSTRUCTOR(StrictSearch);
      }

Here is the call graph for this function:

StrictSearch() [2/2]

template<typename GUM_SCALAR >

INLINE gum::prm::gspan::StrictSearch< GUM_SCALAR >::StrictSearch

(

const StrictSearch< GUM_SCALAR > &

from

)

Copy constructor.

Definition at line 286 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                                                            :
          SearchStrategy< GUM_SCALAR >(from), _freq_(from._freq_) {
        GUM_CONS_CPY(StrictSearch);
      }

Here is the call graph for this function:

~StrictSearch()

template<typename GUM_SCALAR >

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

virtual

Destructor.

Definition at line 292 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                       {
        GUM_DESTRUCTOR(StrictSearch);
      }

Here is the call graph for this function:

Member Function Documentation

_buildPatternGraph_()

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::prm::gspan::operator<<().

                                                              {
        for (const auto inst: match) {
          for (const auto& elt: *inst) {
            // Adding the node
            NodeId id = data.graph.addNode();
            data.node2attr.insert(id, _str_(inst, elt.second));
            data.mod.insert(id, elt.second->type()->domainSize());
            data.vars.insert(id, &elt.second->type().variable());
            pool.insert(const_cast< Potential< GUM_SCALAR >* >(&(elt.second->cpf())));
          }
        }

        // Second we add edges and nodes to inners or outputs
        for (const auto inst: match)
          for (const auto& elt: *inst) {
            NodeId node  = data.node2attr.first(_str_(inst, elt.second));
            bool   found = false;   // If this is set at true, then node is an outer node

            // Children existing in the instance type's DAG
            for (const auto chld: inst->type().containerDag().children(elt.second->id())) {
              data.graph.addEdge(node, data.node2attr.first(_str_(inst, inst->get(chld))));
            }

            // Parents existing in the instance type's DAG
            for (const auto par: inst->type().containerDag().parents(elt.second->id())) {
              switch (inst->type().get(par).elt_type()) {
                case PRMClassElement< GUM_SCALAR >::prm_attribute:
                case PRMClassElement< GUM_SCALAR >::prm_aggregate: {
                  data.graph.addEdge(node, data.node2attr.first(_str_(inst, inst->get(par))));
                  break;
                }

                case PRMClassElement< GUM_SCALAR >::prm_slotchain: {
                  for (const auto inst2: inst->getInstances(par))
                    if (match.exists(inst2))
                      data.graph.addEdge(node,
                                         data.node2attr.first(
                                            _str_(inst2,
                                                  static_cast< const PRMSlotChain< GUM_SCALAR >& >(
                                                     inst->type().get(par)))));

                  break;
                }

                default: { /* Do nothing */
                }
              }
            }

            // Referring PRMAttribute<GUM_SCALAR>
            if (inst->hasRefAttr(elt.second->id())) {
              const std::vector< std::pair< PRMInstance< GUM_SCALAR >*, std::string > >& ref_attr
                 = inst->getRefAttr(elt.second->id());

              for (auto pair = ref_attr.begin(); pair != ref_attr.end(); ++pair) {
                if (match.exists(pair->first)) {
                  NodeId id = pair->first->type().get(pair->second).id();

                  for (const auto child: pair->first->type().containerDag().children(id))
                    data.graph.addEdge(
                       node,
                       data.node2attr.first(_str_(pair->first, pair->first->get(child))));
                } else {
                  found = true;
                }
              }
            }

            if (found)
              data.outputs.insert(node);
            else
              data.inners.insert(node);
          }
      }

Here is the call graph for this function:

_compute_costs_()

template<typename GUM_SCALAR >

INLINE void gum::prm::gspan::StrictSearch< GUM_SCALAR >::_compute_costs_ ( const Pattern *  p )

private

Definition at line 371 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                                              {
        typename StrictSearch< GUM_SCALAR >::PData data;
        Set< Potential< GUM_SCALAR >* >            pool;
        _buildPatternGraph_(data, pool, *(this->tree_->data(*p).iso_map.begin().val()));
        double inner = std::log(_elimination_cost_(data, pool).first);
        double outer = this->computeCost_(*p);
        _map_.insert(p, std::make_pair(inner, outer));
      }

Here is the call graph for this function:

_elimination_cost_()

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

References gum::prm::gspan::operator<<().

                                                           {
        List< NodeSet > partial_order;

        if (data.inners.size()) partial_order.insert(data.inners);

        if (data.outputs.size()) partial_order.insert(data.outputs);

        PartialOrderedTriangulation     t(&(data.graph), &(data.mod), &partial_order);
        const std::vector< NodeId >&    elim_order = t.eliminationOrder();
        Size                            max(0), max_count(1);
        Set< Potential< GUM_SCALAR >* > trash;
        Potential< GUM_SCALAR >*        pot = 0;

        for (size_t idx = 0; idx < data.inners.size(); ++idx) {
          pot = new Potential< GUM_SCALAR >(new MultiDimSparse< GUM_SCALAR >(0));
          pot->add(*(data.vars.second(elim_order[idx])));
          trash.insert(pot);
          Set< Potential< GUM_SCALAR >* > toRemove;

          for (const auto p: pool)
            if (p->contains(*(data.vars.second(elim_order[idx])))) {
              for (auto var = p->variablesSequence().begin(); var != p->variablesSequence().end();
                   ++var) {
                try {
                  pot->add(**var);
                } catch (DuplicateElement&) {}
              }

              toRemove.insert(p);
            }

          if (pot->domainSize() > max) {
            max       = pot->domainSize();
            max_count = 1;
          } else if (pot->domainSize() == max) {
            ++max_count;
          }

          for (const auto p: toRemove)
            pool.erase(p);

          pot->erase(*(data.vars.second(elim_order[idx])));
        }

        for (const auto pot: trash)
          delete pot;

        return std::make_pair(max, max_count);
      }

Here is the call graph for this function:

_inner_cost_()

template<typename GUM_SCALAR >

INLINE double gum::prm::gspan::StrictSearch< GUM_SCALAR >::_inner_cost_ ( const Pattern *  p )

private

Definition at line 330 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                                             {
        try {
          return _map_[p].first;
        } catch (NotFound&) {
          _compute_costs_(p);
          return _map_[p].first;
        }
      }

Here is the call graph for this function:

_outer_cost_()

template<typename GUM_SCALAR >

INLINE double gum::prm::gspan::StrictSearch< GUM_SCALAR >::_outer_cost_ ( const Pattern *  p )

private

Definition at line 340 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                                             {
        try {
          return _map_[p].second;
        } catch (NotFound&) {
          _compute_costs_(p);
          return _map_[p].second;
        }
      }

Here is the call graph for this function:

_str_() [1/3]

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

References gum::prm::gspan::operator<<().

                                                                                      {
        return i->name() + _dot_ + a->safeName();
      }

Here is the call graph for this function:

_str_() [2/3]

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

References gum::prm::gspan::operator<<().

                                                                                      {
        return i->name() + _dot_ + a.safeName();
      }

Here is the call graph for this function:

_str_() [3/3]

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

References gum::prm::gspan::operator<<().

                                                                                      {
        return i->name() + _dot_ + a.lastElt().safeName();
      }

Here is the call graph for this function:

accept_growth()

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

References gum::prm::gspan::operator<<().

                                                                                           {
        return _inner_cost_(child) + this->tree_->frequency(*child) * _outer_cost_(child)
             < this->tree_->frequency(*child) * _outer_cost_(parent);
      }

Here is the call graph for this function:

accept_root()

template<typename GUM_SCALAR >

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

virtual

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

Definition at line 304 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                                          {
        return (this->tree_->frequency(*r) >= _freq_);
      }

Here is the call graph for this function:

computeCost_()

template<typename GUM_SCALAR >

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

protectedinherited

Definition at line 35 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

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

operator()() [1/2]

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

References gum::prm::gspan::operator<<().

                                                                                   {
        return i->tree_width * this->tree_->graph().size(i)
             < j->tree_width * this->tree_->graph().size(j);
      }

Here is the call graph for this function:

operator()() [2/2]

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

References gum::prm::gspan::operator<<().

                                                                                         {
        return _inner_cost_(i) + this->tree_->frequency(*i) * _outer_cost_(i)
             < _inner_cost_(j) + this->tree_->frequency(*j) * _outer_cost_(j);
      }

Here is the call graph for this function:

operator=()

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

References gum::prm::gspan::operator<<().

                                                                                     {
        _freq_ = from._freq_;
        return *this;
      }

Here is the call graph for this function:

setTree()

template<typename GUM_SCALAR >

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

inherited

Definition at line 219 of file searchStrategy_tpl.h.

References gum::prm::gspan::operator<<().

                                                                                   {
        this->tree_ = tree;
      }

Here is the call graph for this function:

Member Data Documentation

_dot_

template<typename GUM_SCALAR >

std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::_dot_

private

Definition at line 236 of file searchStrategy.h.

_freq_

template<typename GUM_SCALAR >

Size gum::prm::gspan::StrictSearch< GUM_SCALAR >::_freq_

private

Definition at line 211 of file searchStrategy.h.

_map_

template<typename GUM_SCALAR >

HashTable< const Pattern*, std::pair< double, double > > gum::prm::gspan::StrictSearch< GUM_SCALAR >::_map_

private

Definition at line 215 of file searchStrategy.h.

tree_

template<typename GUM_SCALAR >

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

protectedinherited

Definition at line 111 of file searchStrategy.h.

---

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

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