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

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

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

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

~StrictSearch()

template<typename GUM_SCALAR >

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

virtual

Destructor.

Definition at line 310 of file searchStrategy_tpl.h.

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::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 65 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().

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

Here is the caller 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 392 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().

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

Here is the caller 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 153 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().

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

Here is the caller 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 351 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()().

                                                                             {
        try {
          return __map[p].first;
        } catch (NotFound&) {
          __compute_costs(p);
          return __map[p].first;
        }
      }

Here is the call graph for this function:

Here is the caller 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 361 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()().

                                                                             {
        try {
          return __map[p].second;
        } catch (NotFound&) {
          __compute_costs(p);
          return __map[p].second;
        }
      }

Here is the call graph for this function:

Here is the caller 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 371 of file searchStrategy_tpl.h.

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

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

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

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

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

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

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 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::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 327 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.

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

References gum::prm::gspan::StrictSearch< GUM_SCALAR >::__freq, and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::_tree.

                                                                          {
        return (this->_tree->frequency(*r) >= __freq);
      }

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

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

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

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

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

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

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

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

Here is the caller 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 233 of file searchStrategy_tpl.h.

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

                                                                          {
        this->_tree = tree;
      }

Member Data Documentation

__dot

template<typename GUM_SCALAR>

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

private

Definition at line 237 of file searchStrategy.h.

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

__freq

template<typename GUM_SCALAR>

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

private

Definition at line 212 of file searchStrategy.h.

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

__map

template<typename GUM_SCALAR>

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

private

Definition at line 216 of file searchStrategy.h.

Referenced by gum::prm::gspan::StrictSearch< GUM_SCALAR >::__compute_costs(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::__inner_cost(), and gum::prm::gspan::StrictSearch< GUM_SCALAR >::__outer_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