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 299 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 305 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 313 of file searchStrategy_tpl.h.

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

                                                       {
        GUM_DESTRUCTOR(StrictSearch);
      }

Here is the call graph for this function:

Member Function Documentation

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

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

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

Here is the call graph for this function:

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 64 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 395 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:

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:

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 155 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 354 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:

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

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

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

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

setTree()

template<typename GUM_SCALAR >

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

inherited

Definition at line 235 of file searchStrategy_tpl.h.

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

                                                                          {
        this->tree_ = tree;
      }

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 374 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 381 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 388 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:

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.

freq__

template<typename GUM_SCALAR >

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

private

Definition at line 212 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 216 of file searchStrategy.h.

tree_

template<typename GUM_SCALAR >

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

protectedinherited

Definition at line 112 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