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

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

Public Member Functions
Constructor and destructor.
	StrictSearch (Size freq=2)
	Default constructor.
	StrictSearch (const StrictSearch &from)
	Copy constructor.
	~StrictSearch () override
	Destructor.
StrictSearch &	operator= (const StrictSearch &from)
	Copy operator.
Search methods.
bool	accept_root (const Pattern *r) override
bool	accept_growth (const Pattern parent, const Pattern child, const EdgeGrowth< GUM_SCALAR > &growth) override
bool	operator() (LabelData i, LabelData j) override
bool	operator() (Pattern i, Pattern j) override
Search methods.
void	setTree (DFSTree< GUM_SCALAR > *tree)

Protected Member Functions
double	computeCost_ (const Pattern &p)

Protected Attributes
DFSTree< GUM_SCALAR > *	tree_

Private Member Functions
double	_inner_cost_ (const Pattern *p)
double	_outer_cost_ (const Pattern *p)
void	_compute_costs_ (const Pattern *p)
std::string	_str_ (const PRMInstance< GUM_SCALAR > i, const PRMAttribute< GUM_SCALAR > a) const
std::string	_str_ (const PRMInstance< GUM_SCALAR > *i, const PRMAttribute< GUM_SCALAR > &a) const
std::string	_str_ (const PRMInstance< GUM_SCALAR > *i, const PRMSlotChain< GUM_SCALAR > &a) const
void	_buildPatternGraph_ (typename StrictSearch< GUM_SCALAR >::PData &data, Set< Tensor< GUM_SCALAR > * > &pool, const Sequence< PRMInstance< GUM_SCALAR > * > &match)
std::pair< Size, Size >	_elimination_cost_ (typename StrictSearch< GUM_SCALAR >::PData &data, Set< Tensor< GUM_SCALAR > * > &pool)

Private Attributes
Size	_freq_
HashTable< const Pattern *, std::pair< double, double > >	_map_
std::string	_dot_

Detailed Description

template<GUM_Numeric 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 183 of file searchStrategy.h.

Constructor & Destructor Documentation

◆ StrictSearch() [1/2]

template<GUM_Numeric GUM_SCALAR>

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

explicit

Default constructor.

Definition at line 294 of file searchStrategy_tpl.h.

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

References gum::prm::gspan::SearchStrategy< GUM_SCALAR >::SearchStrategy(), StrictSearch(), _dot_, and _freq_.

Referenced by StrictSearch(), StrictSearch(), ~StrictSearch(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ StrictSearch() [2/2]

template<GUM_Numeric GUM_SCALAR>

gum::prm::gspan::StrictSearch< GUM_SCALAR >::StrictSearch ( const StrictSearch< GUM_SCALAR > & from )

Copy constructor.

Definition at line 300 of file searchStrategy_tpl.h.

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

References gum::prm::gspan::SearchStrategy< GUM_SCALAR >::SearchStrategy(), StrictSearch(), and _freq_.

Here is the call graph for this function:

◆ ~StrictSearch()

template<GUM_Numeric GUM_SCALAR>

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

override

Destructor.

Definition at line 306 of file searchStrategy_tpl.h.

                                                {
        GUM_DESTRUCTOR(StrictSearch);
      }

References StrictSearch().

Here is the call graph for this function:

Member Function Documentation

◆ _buildPatternGraph_()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::gspan::StrictSearch< GUM_SCALAR >::_buildPatternGraph_	(	typename StrictSearch< GUM_SCALAR >::PData &	data,
		Set< Tensor< GUM_SCALAR > * > &	pool,
		const Sequence< PRMInstance< GUM_SCALAR > * > &	match )

private

Definition at line 84 of file searchStrategy_tpl.h.

                                                               {
        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< Tensor< 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);
          }
      }

References _str_(), gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNode(), gum::BijectionImplementation< T1, T2, std::is_scalar< T1 >::value &&std::is_scalar< T2 >::value >::first(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::graph, gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::inners, gum::BijectionImplementation< T1, T2, std::is_scalar< T1 >::value &&std::is_scalar< T2 >::value >::insert(), gum::Set< Key >::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, gum::prm::PRMClassElement< GUM_SCALAR >::prm_aggregate, gum::prm::PRMClassElement< GUM_SCALAR >::prm_attribute, gum::prm::PRMClassElement< GUM_SCALAR >::prm_slotchain, and gum::prm::gspan::StrictSearch< GUM_SCALAR >::PData::vars.

Referenced by _compute_costs_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _compute_costs_()

template<GUM_Numeric GUM_SCALAR>

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

private

Definition at line 381 of file searchStrategy_tpl.h.

                                                                       {
        typename StrictSearch< GUM_SCALAR >::PData data;
        Set< Tensor< 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));
      }

References _buildPatternGraph_(), _elimination_cost_(), _map_, gum::prm::gspan::SearchStrategy< GUM_SCALAR >::computeCost_(), and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::tree_.

Referenced by _inner_cost_(), and _outer_cost_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _elimination_cost_()

template<GUM_Numeric GUM_SCALAR>

std::pair< Size, Size > gum::prm::gspan::StrictSearch< GUM_SCALAR >::_elimination_cost_	(	typename StrictSearch< GUM_SCALAR >::PData &	data,
		Set< Tensor< GUM_SCALAR > * > &	pool )

private

Definition at line 161 of file searchStrategy_tpl.h.

                                                            {
        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< Tensor< GUM_SCALAR >* > trash;
        Tensor< GUM_SCALAR >*        pot = 0;
 
        for (size_t idx = 0; idx < data.inners.size(); ++idx) {
          pot = new Tensor< GUM_SCALAR >(new MultiDimSparse< GUM_SCALAR >(0));
          pot->add(*(data.vars.second(elim_order[idx])));
          trash.insert(pot);
          Set< Tensor< 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 const&) {}
              }
 
              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);
      }

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

Referenced by _compute_costs_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _inner_cost_()

template<GUM_Numeric GUM_SCALAR>

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

private

Definition at line 343 of file searchStrategy_tpl.h.

                                                                      {
        auto pm = _map_.tryGet(p);
        if (!pm) {
          _compute_costs_(p);
          pm = _map_.tryGet(p);
        }
        return pm->first;
      }

References _compute_costs_(), and _map_.

Referenced by accept_growth(), and operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _outer_cost_()

template<GUM_Numeric GUM_SCALAR>

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

private

Definition at line 353 of file searchStrategy_tpl.h.

                                                                      {
        auto pm = _map_.tryGet(p);
        if (!pm) {
          _compute_costs_(p);
          pm = _map_.tryGet(p);
        }
        return pm->second;
      }

References _compute_costs_(), and _map_.

Referenced by accept_growth(), and operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _str_() [1/3]

template<GUM_Numeric GUM_SCALAR>

std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::_str_	(	const PRMInstance< GUM_SCALAR > *	i,
		const PRMAttribute< GUM_SCALAR > &	a ) const

private

Definition at line 369 of file searchStrategy_tpl.h.

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

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

Here is the call graph for this function:

◆ _str_() [2/3]

template<GUM_Numeric GUM_SCALAR>

std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::_str_	(	const PRMInstance< GUM_SCALAR > *	i,
		const PRMAttribute< GUM_SCALAR > *	a ) const

private

Definition at line 363 of file searchStrategy_tpl.h.

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

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

Referenced by _buildPatternGraph_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _str_() [3/3]

template<GUM_Numeric GUM_SCALAR>

std::string gum::prm::gspan::StrictSearch< GUM_SCALAR >::_str_	(	const PRMInstance< GUM_SCALAR > *	i,
		const PRMSlotChain< GUM_SCALAR > &	a ) const

private

Definition at line 375 of file searchStrategy_tpl.h.

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

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

Here is the call graph for this function:

◆ accept_growth()

template<GUM_Numeric GUM_SCALAR>

bool gum::prm::gspan::StrictSearch< GUM_SCALAR >::accept_growth	(	const Pattern *	parent,
		const Pattern *	child,
		const EdgeGrowth< GUM_SCALAR > &	growth )

overridevirtual

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

Definition at line 323 of file searchStrategy_tpl.h.

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

References _inner_cost_(), _outer_cost_(), and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::tree_.

Here is the call graph for this function:

◆ accept_root()

template<GUM_Numeric GUM_SCALAR>

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

overridevirtual

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

Definition at line 318 of file searchStrategy_tpl.h.

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

References _freq_, and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::tree_.

◆ computeCost_()

template<GUM_Numeric GUM_SCALAR>

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

protectedinherited

Definition at line 57 of file searchStrategy_tpl.h.

                                                                        {
        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;
      }

References gum::SequenceImplementation< Key, Gen >::exists(), gum::SequenceImplementation< Key, Gen >::insert(), and tree_.

Referenced by gum::prm::gspan::StrictSearch< GUM_SCALAR >::_compute_costs_(), and gum::prm::gspan::TreeWidthSearch< GUM_SCALAR >::cost().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator()() [1/2]

template<GUM_Numeric GUM_SCALAR>

bool gum::prm::gspan::StrictSearch< GUM_SCALAR >::operator()	(	LabelData *	i,
		LabelData *	j )

overridevirtual

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

Definition at line 337 of file searchStrategy_tpl.h.

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

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

◆ operator()() [2/2]

template<GUM_Numeric GUM_SCALAR>

bool gum::prm::gspan::StrictSearch< GUM_SCALAR >::operator()	(	gspan::Pattern *	i,
		gspan::Pattern *	j )

overridevirtual

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

Definition at line 331 of file searchStrategy_tpl.h.

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

References _inner_cost_(), _outer_cost_(), and gum::prm::gspan::SearchStrategy< GUM_SCALAR >::tree_.

Here is the call graph for this function:

◆ operator=()

template<GUM_Numeric GUM_SCALAR>

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

Copy operator.

Definition at line 312 of file searchStrategy_tpl.h.

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

References StrictSearch(), and _freq_.

Here is the call graph for this function:

◆ setTree()

template<GUM_Numeric GUM_SCALAR>

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

inherited

Definition at line 236 of file searchStrategy_tpl.h.

                                                                            {
        this->tree_ = tree;
      }

References tree_.

Referenced by operator=().

Here is the caller graph for this function:

Member Data Documentation

◆ _dot_

template<GUM_Numeric GUM_SCALAR>

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

private

Definition at line 246 of file searchStrategy.h.

Referenced by StrictSearch(), _str_(), _str_(), and _str_().

◆ _freq_

template<GUM_Numeric GUM_SCALAR>

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

private

Definition at line 219 of file searchStrategy.h.

Referenced by StrictSearch(), StrictSearch(), accept_root(), and operator=().

◆ _map_

template<GUM_Numeric GUM_SCALAR>

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

private

Definition at line 223 of file searchStrategy.h.

Referenced by _compute_costs_(), _inner_cost_(), and _outer_cost_().

◆ tree_

template<GUM_Numeric GUM_SCALAR>

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

protectedinherited

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

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ StrictSearch() [1/2]

◆ StrictSearch() [2/2]

◆ ~StrictSearch()

Member Function Documentation

◆ _buildPatternGraph_()

◆ _compute_costs_()

◆ _elimination_cost_()

◆ _inner_cost_()

◆ _outer_cost_()

◆ _str_() [1/3]

◆ _str_() [2/3]

◆ _str_() [3/3]

◆ accept_growth()

◆ accept_root()

◆ computeCost_()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator=()

◆ setTree()

Member Data Documentation

◆ _dot_

◆ _freq_

◆ _map_

◆ tree_