This class discovers pattern in a PRM<GUM_SCALAR>'s PRMSystem<GUM_SCALAR> to speed up structured inference. More...

#include <agrum/PRM/gspan.h>

Collaboration diagram for gum::prm::GSpan< GUM_SCALAR >:

Classes
class	LabelSort
	Private class used to sort LabelData using STL sort algorithms. More...
class	PatternSort
	Private class used to sort Pattern using STL sort algorithms. More...

Public Member Functions
Constructors & destructor.
	GSpan (const PRM< GUM_SCALAR > &prm, const PRMSystem< GUM_SCALAR > &sys, gspan::SearchStrategy< GUM_SCALAR > *strategy=0)
	Default constructor.
	~GSpan ()
	Destructor.
Getters and setters.
Size	getMaxDFSDepth () const
	Returns the maximal depth of the DFSTree used to discover new patterns.
void	setMaxDFSDepth (Size depth)
	Defines the maximal depth of the DFSTree used by this class to discover new patterns.
gspan::DFSTree< GUM_SCALAR > &	tree ()
	Returns the DFSTree used to discover new patters.
const gspan::DFSTree< GUM_SCALAR > &	tree () const
	Returns the DFSTree used to discover new patters.
gspan::InterfaceGraph< GUM_SCALAR > &	interfaceGraph ()
	Returns the InterfaceGraph used by this.
const gspan::InterfaceGraph< GUM_SCALAR > &	interfaceGraph () const
	Returns the InterfaceGraph used by this.

Private Member Functions
Private Methods
void	_sortNodesAndEdges_ ()
	Sort the nodes and edges of graph.
void	_subgraph_mining_ (gspan::InterfaceGraph< GUM_SCALAR > &graph, gspan::Pattern &p)
	Discovers new patterns by developing p.
Size	_cost_func_ (Size interface_size, Size frequency)
	Returns the cost with respect to an interface size and its frequency.
void	_sortPatterns_ ()
	Sort the patterns and compute their respective costs.
bool	_isEdgeEligible_ (typename gspan::EdgeData< GUM_SCALAR > *e)
	Returns true if e is an eligible root edge.

Private Attributes
Private Members.
gspan::InterfaceGraph< GUM_SCALAR > *	_graph_
	The interface graph used by this class.
gspan::DFSTree< GUM_SCALAR >	_tree_
	The DFSTree used to discover new patters.
Size	_depth_stop_
	The max depth allowed for the DSF tree.
std::vector< gspan::Pattern * >	_patterns_
	The vector of discovered patters, in decreasing order of interest.
std::vector< gspan::LabelData * >	_nodes_
	The vector of nodes in graph, in decreasing order of interest.
std::vector< gspan::LabelData * >	_edges_
	The vector of edges in graph, in decreasing order of interest.
HashTable< gspan::LabelData *, Idx >	_cost_
	Mapping between labels and their cost.
HashTable< gspan::Pattern , MatchedInstances >	_matched_instances_
	Mapping between a pattern and the multiset of instances matched to it.
Set< PRMInstance< GUM_SCALAR > * >	_chosen_
	Contains all instance which belongs to a discovered and used pattern.

Pattern discovery methods.
using	MatchedInstances = Set< Sequence< PRMInstance< GUM_SCALAR >* >* >
	Code alias.
void	discoverPatterns ()
	This will methods will discover repeated patterns in the PRMSystem<GUM_SCALAR> assigned to this class.
std::vector< gspan::Pattern * > &	patterns ()
	Returns the Pattern mined by this class in a decreasing order of interest.
const std::vector< gspan::Pattern * > &	patterns () const
	Returns the Pattern mined by this class in a decreasing order of interest.
MatchedInstances &	matches (const gspan::Pattern &p)
	Returns a mapping between patterns and the sequence of instance in the interface graph matching them.
const MatchedInstances &	matches (const gspan::Pattern &p) const
	Returns a mapping between patterns and the sequence of instance in the interface graph matching them.

Detailed Description

template<GUM_Numeric GUM_SCALAR>
class gum::prm::GSpan< GUM_SCALAR >

This class discovers pattern in a PRM<GUM_SCALAR>'s PRMSystem<GUM_SCALAR> to speed up structured inference.

This class is not an inference algorithm for PRM<GUM_SCALAR>, however it can be used to speed up structured inference as it will discover repeated patterns including more than one PRMInstance<GUM_SCALAR>.

This algorithm proceeds in three main steps represented by the private methods GSpan:: sortNodesAndEdges(), GSpan:: subgraph_mining() and GSpan:: sortPatterns().

Definition at line 86 of file gspan.h.

Member Typedef Documentation

◆ MatchedInstances

template<GUM_Numeric GUM_SCALAR>

using gum::prm::GSpan< GUM_SCALAR >::MatchedInstances = Set< Sequence< PRMInstance< GUM_SCALAR >* >* >

Code alias.

Definition at line 185 of file gspan.h.

Constructor & Destructor Documentation

◆ GSpan()

template<GUM_Numeric GUM_SCALAR>

gum::prm::GSpan< GUM_SCALAR >::GSpan	(	const PRM< GUM_SCALAR > &	prm,
		const PRMSystem< GUM_SCALAR > &	sys,
		gspan::SearchStrategy< GUM_SCALAR > *	strategy = 0 )

Default constructor.

Parameters

prm	The PRM<GUM_SCALAR> used by this class.
sys	The PRMSystem<GUM_SCALAR> on which this class searches for patterns.
strategy	The search strategy used for pattern mining, the default strategy is gspan::FrequenceSearch.

Definition at line 366 of file gspan_tpl.h.

                                                                            :
        _graph_(new gspan::InterfaceGraph< GUM_SCALAR >(sys)), _tree_(*_graph_, strategy),
        _depth_stop_(INT_MAX) {
      GUM_CONSTRUCTOR(GSpan);
    }

References GSpan(), _depth_stop_, _graph_, and _tree_.

Referenced by GSpan(), gum::prm::GSpan< GUM_SCALAR >::LabelSort::LabelSort(), gum::prm::GSpan< GUM_SCALAR >::PatternSort::PatternSort(), and ~GSpan().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ~GSpan()

template<GUM_Numeric GUM_SCALAR>

gum::prm::GSpan< GUM_SCALAR >::~GSpan ( )

Destructor.

Definition at line 375 of file gspan_tpl.h.

                                {
      GUM_DESTRUCTOR(GSpan);
 
      for (const auto& elt: _matched_instances_)
        delete elt.second;
 
      delete _graph_;
    }

References GSpan(), _graph_, and _matched_instances_.

Here is the call graph for this function:

Member Function Documentation

◆ _cost_func_()

template<GUM_Numeric GUM_SCALAR>

Idx gum::prm::GSpan< GUM_SCALAR >::_cost_func_	(	Size	interface_size,
		Size	frequency )

private

Returns the cost with respect to an interface size and its frequency.

Parameters

interface_size	The size of all output nodes of a pattern.
frequency	The frequency of the pattern in the current interface graph.

Returns: the cost with respect to an interface size and its frequency.

Definition at line 405 of file gspan_tpl.h.

                                                                            {
      return Idx(interface_size * frequency);
    }

Referenced by _sortNodesAndEdges_().

Here is the caller graph for this function:

◆ _isEdgeEligible_()

template<GUM_Numeric GUM_SCALAR>

bool gum::prm::GSpan< GUM_SCALAR >::_isEdgeEligible_ ( typename gspan::EdgeData< GUM_SCALAR > * e )

private

Returns true if e is an eligible root edge.

Parameters

e	An EdgeData<GUM_SCALAR>.

Returns: true if e is an eligible root edge.

Definition at line 442 of file gspan_tpl.h.

                                                                             {
      return (_graph_->edges(e->l).size() >= 2) && (_graph_->nodes(e->l_u).size() >= 2)
          && (_graph_->nodes(e->l_v).size() >= 2);
    }

References _graph_, gum::prm::gspan::EdgeData< GUM_SCALAR >::l, gum::prm::gspan::EdgeData< GUM_SCALAR >::l_u, and gum::prm::gspan::EdgeData< GUM_SCALAR >::l_v.

Referenced by _sortNodesAndEdges_().

Here is the caller graph for this function:

◆ _sortNodesAndEdges_()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::GSpan< GUM_SCALAR >::_sortNodesAndEdges_ ( )

private

Sort the nodes and edges of graph.

Definition at line 79 of file gspan_tpl.h.

                                                  {
      for (auto iter = _graph_->labels().begin(); iter != _graph_->labels().end(); ++iter) {
        try {
          if (_graph_->nodes(iter.second()).size() >= 2) {
            _cost_.insert(
                iter.second(),
                _cost_func_(iter.second()->tree_width, _graph_->nodes(iter.second()).size()));
            _nodes_.push_back(const_cast< gspan::LabelData* >(iter.second()));
          }
        } catch (NotFound const&) {
          // It's a label over edges
          if (_isEdgeEligible_(*(_graph_->edges(iter.second()).begin()))) {
            _cost_.insert(
                iter.second(),
                _cost_func_(iter.second()->tree_width, _graph_->edges(iter.second()).size()));
            _edges_.push_back(iter.second());
          }
        }
      }
 
      Bijection< Idx, gspan::LabelData* >* new_labels = new Bijection< Idx, gspan::LabelData* >();
      GSpan< GUM_SCALAR >::LabelSort       my_sort(this);
      std::sort(_nodes_.begin(), _nodes_.end(), my_sort);
      std::sort(_edges_.begin(), _edges_.end(), my_sort);
      Size idx = 0;
 
      for (auto iter = _nodes_.begin(); iter != _nodes_.end(); ++iter) {
        (*iter)->id = ++idx;
        new_labels->insert(idx, *iter);
      }
 
      for (auto iter = _edges_.begin(); iter != _edges_.end(); ++iter) {
        (*iter)->id = ++idx;
        new_labels->insert(idx, *iter);
        _tree_.addRoot(**iter);
      }
 
      delete _graph_->_labels_;
      _graph_->_labels_ = new_labels;
    }

References _cost_, _cost_func_(), _edges_, _graph_, _isEdgeEligible_(), _nodes_, _tree_, and gum::BijectionImplementation< T1, T2, Gen >::insert().

Referenced by discoverPatterns().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _sortPatterns_()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::GSpan< GUM_SCALAR >::_sortPatterns_ ( )

private

Sort the patterns and compute their respective costs.

Definition at line 241 of file gspan_tpl.h.

                                             {
      // First we put all the patterns in  _patterns_.
      std::vector< NodeId > stack;
 
      for (std::list< NodeId >::reverse_iterator root = tree().roots().rbegin();
           root != tree().roots().rend();
           ++root)
        stack.push_back(*root);
 
      NodeId               id       = 0;
      std::list< NodeId >* children = nullptr;
 
      while (!stack.empty()) {
        id = stack.back();
        stack.pop_back();
        _patterns_.push_back(&(tree().pattern(id)));
        children = &(tree().children(tree().pattern(id)));
 
        for (std::list< NodeId >::reverse_iterator child = children->rbegin();
             child != children->rend();
             ++child)
          stack.push_back(*child);
      }
 
      if (!_patterns_.empty()) {
        // We sort  _patterns_.
        GSpan< GUM_SCALAR >::PatternSort my_sort(this);
        std::sort(_patterns_.begin(), _patterns_.end(), my_sort);
        // Now we need to find all the matches we can, using  _patterns_.
        // We start by the best Pattern and add it's maximal independent set to
        //  _chosen_
        GSpan< GUM_SCALAR >::MatchedInstances* matches
            = new GSpan< GUM_SCALAR >::MatchedInstances();
        Sequence< PRMInstance< GUM_SCALAR >* >* match = nullptr;
 
        for (const auto node: tree().max_indep_set(*(_patterns_.front()))) {
          match = &(tree().iso_map(*(_patterns_.front()), node));
 
          for (const auto i: *match)
            _chosen_.insert(i);
 
          matches->insert(match);
        }
 
        _matched_instances_.insert(_patterns_.front(), matches);
        // Now we see what kind of pattern we can still use
        bool       found;
        UndiGraph* iso_graph = nullptr;
 
        for (auto patt = _patterns_.begin() + 1; patt != _patterns_.end(); ++patt) {
          UndiGraph             reduced_iso_graph;
          std::vector< NodeId > degree_list;
          iso_graph = &(tree().iso_graph(**patt));
 
          for (const auto node: iso_graph->nodes()) {
            found = false;
            match = &(tree().iso_map(**patt, node));
 
            for (const auto i: *match)
              if (_chosen_.exists(i)) {
                found = true;
                break;
              }
 
            if (!found) {
              // We add the pattern to the reduced isomorphism graph to compute
              // the
              // max independent set
              // over the remaining matches
              reduced_iso_graph.addNodeWithId(node);
 
              for (const auto iso: reduced_iso_graph.nodes())
                if (iso_graph->existsEdge(node, iso)) reduced_iso_graph.addEdge(node, iso);
 
              degree_list.push_back(node);
            }
          }
 
          // We create a new set to hold all the chosen matches of patt
          matches = new GSpan< GUM_SCALAR >::MatchedInstances();
          // We can compute the max independent set and the matches belonging to
          // it
          typename gspan::DFSTree< GUM_SCALAR >::NeighborDegreeSort my_sort(reduced_iso_graph);
          std::sort(degree_list.begin(), degree_list.end(), my_sort);
          Set< NodeId > removed;
 
          for (const auto node: degree_list)
            if (!removed.exists(node)) {
              // First we update removed to follow the max independent set
              // algorithm
              removed.insert(node);
 
              for (const auto neighbor: reduced_iso_graph.neighbours(node))
                removed.insert(neighbor);
 
              // Second we update match and matches to keep track of the current
              // match
              match = &(tree().iso_map(**patt, node));
              matches->insert(match);
 
              for (const auto elt: *match)
                _chosen_.insert(elt);
            }
 
          _matched_instances_.insert(*patt, matches);
        }
 
        // // We remove patterns with 0 matches
        std::vector< size_t > trash;
 
        for (size_t idx = 0; idx < _patterns_.size(); ++idx)
          if (_matched_instances_[_patterns_[idx]]->size() < 2) trash.push_back(idx);
 
        while (trash.size()) {
          delete _matched_instances_[_patterns_[trash.back()]];
          _matched_instances_.erase(_patterns_[trash.back()]);
          // delete  _patterns_[trash.back()];
          _patterns_[trash.back()] = _patterns_.back();
          _patterns_.pop_back();
          trash.pop_back();
        }
      }
    }

References _chosen_, _matched_instances_, _patterns_, gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::Set< Key >::exists(), gum::EdgeGraphPart::existsEdge(), gum::SequenceImplementation< Key, Gen >::insert(), gum::Set< Key >::insert(), matches(), gum::EdgeGraphPart::neighbours(), gum::NodeGraphPart::nodes(), and tree().

Referenced by discoverPatterns().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _subgraph_mining_()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::GSpan< GUM_SCALAR >::_subgraph_mining_	(	gspan::InterfaceGraph< GUM_SCALAR > &	graph,
		gspan::Pattern &	p )

private

Discovers new patterns by developing p.

Parameters

graph	The interface graph used in this discovery process.
p	The pattern used as a base for discovery.

Definition at line 121 of file gspan_tpl.h.

                                                                                        {
      std::vector< gspan::Pattern* > stack;
      stack.push_back(&pat);
      // Pointers used in the following while
      gspan::Pattern*                                             p           = nullptr;
      HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >* edge_count  = nullptr;
      gspan::EdgeGrowth< GUM_SCALAR >*                            edge_growth = nullptr;
      Sequence< PRMInstance< GUM_SCALAR >* >*                     seq         = nullptr;
      PRMInstance< GUM_SCALAR >*                                  current     = nullptr;
      PRMInstance< GUM_SCALAR >*                                  neighbor    = nullptr;
 
      // Neighbor_id is the neighbor's id in the interface graph and
      // neighbor_node
      // is its id in the rightmost path in the case of a backward edge growth
      NodeId            current_id     = 0;
      NodeId            neighbor_node  = 0;
      gspan::LabelData* neighbor_label = 0;
 
      typename gspan::EdgeData< GUM_SCALAR >* edge_data = nullptr;
 
      size_t                     idx;
      const std::list< NodeId >* children = 0;
 
      while (!stack.empty()) {
        // Getting next pattern
        p = stack.back();
        stack.pop_back();
 
        if (p->code().codes.size() < _depth_stop_) {
          // We need the rightmost path of p
          std::list< NodeId > r_path;
          p->rightmostPath(r_path);
          // Mapping used to count each possible child of p, the position in the
          // vector
          // matches the one in the rightmost path
          std::vector< HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >* > count_vector;
 
          for (size_t i = 0; i < r_path.size(); ++i)
            count_vector.push_back(
                new HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >());
 
          // For each subgraph represented by p, we look for a valid edge growth
          // for
          // each instance match of p in its isomorphism graph.
          for (const auto iso_node: _tree_.iso_graph(*p).nodes()) {
            seq = &(_tree_.iso_map(*p, iso_node));
            idx = 0;
 
            for (const auto node: r_path) {
              edge_count = count_vector[idx];
              // Retrieving the equivalent instance in the current match
              current    = seq->atPos((Idx)(node - 1));
              current_id = ig.id(current);
              // Checking for edges not in p
 
              for (const auto neighbor_id: ig.internalGraph().neighbours(current_id)) {
                neighbor = ig.node(neighbor_id).n;
 
                // We want a forward edge in any case or a backward edge if
                // current
                // is the rightmost vertex
                if ((!seq->exists(neighbor)) || (node == r_path.back())) {
                  // Things we need to know: the LabelData data of the neighbour
                  // and,
                  // if it's a backward edge, its node id in the rightmost path
                  edge_data      = &(ig.edge(current_id, neighbor_id));
                  neighbor_label = (neighbor == edge_data->u) ? edge_data->l_u : edge_data->l_v;
                  neighbor_node  = (seq->exists(neighbor)) ? seq->pos(neighbor) + 1 : 0;
                  // Adding the edge growth to the edge_growth hashtable
                  gspan::EdgeGrowth< GUM_SCALAR > temp_growth(node,
                                                              edge_data->l,
                                                              neighbor_label,
                                                              neighbor_node);
 
                  if (edge_count->exists(temp_growth.toString())) {
                    edge_growth = (*edge_count)[temp_growth.toString()];
                    edge_growth->insert(current, neighbor);
                  } else {
                    edge_growth = new gspan::EdgeGrowth< GUM_SCALAR >(node,
                                                                      edge_data->l,
                                                                      neighbor_label,
                                                                      neighbor_node);
                    edge_growth->insert(current, neighbor);
                    edge_count->insert(edge_growth->toString(), edge_growth);
                  }
                }
              }
            }
          }
 
          // Removing any infrequent child
          for (size_t node = 0; node < count_vector.size(); ++node) {
            edge_count = count_vector[node];
 
            for (const auto& elt: *edge_count) {
              try {
                _tree_.growPattern(*p, *elt.second, 2);
              } catch (OperationNotAllowed const&) {
                // The child was not minimal or was not worth considering
              }
 
              delete elt.second;
            }
 
            delete edge_count;
          }
 
          // Calling  _subgraph_mining_ over children of p
          children = &(_tree_.children(*p));
 
          for (std::list< NodeId >::const_reverse_iterator child = children->rbegin();
               child != children->rend();
               ++child)
            stack.push_back(&(_tree_.pattern(*child)));
        }
      }
    }

Referenced by discoverPatterns().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ discoverPatterns()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::GSpan< GUM_SCALAR >::discoverPatterns ( )

This will methods will discover repeated patterns in the PRMSystem<GUM_SCALAR> assigned to this class.

The results are saved in a vector of Patterns which can be obtained by calling GSpan::patterns().

Definition at line 57 of file gspan_tpl.h.

                                               {
      Timer t;
      _sortNodesAndEdges_();
      gspan::InterfaceGraph< GUM_SCALAR > graph(*_graph_);
 
      for (auto root = _tree_.roots().begin(); root != _tree_.roots().end(); ++root) {
        if (_tree_.strategy().accept_root(&(_tree_.pattern(*root)))) {
          gspan::Pattern& p = _tree_.pattern(*root);
          _subgraph_mining_(graph, p);
 
          for (const auto node: _tree_.iso_graph(p).nodes()) {
            PRMInstance< GUM_SCALAR >* u = _tree_.iso_map(p, node).atPos(0);
            PRMInstance< GUM_SCALAR >* v = _tree_.iso_map(p, node).atPos(1);
            graph.internalGraph().eraseEdge(Edge(graph.id(u), graph.id(v)));
          }
        }
      }
 
      _sortPatterns_();
    }

References gum::Edge::Edge(), _graph_, _sortNodesAndEdges_(), _sortPatterns_(), _subgraph_mining_(), and _tree_.

Here is the call graph for this function:

◆ getMaxDFSDepth()

template<GUM_Numeric GUM_SCALAR>

Size gum::prm::GSpan< GUM_SCALAR >::getMaxDFSDepth ( ) const

Returns the maximal depth of the DFSTree used to discover new patterns.

Returns: the maximal depth of the DFSTree used to discover new patterns.

Definition at line 385 of file gspan_tpl.h.

                                                   {
      return _depth_stop_;
    }

References _depth_stop_.

◆ interfaceGraph() [1/2]

template<GUM_Numeric GUM_SCALAR>

gspan::InterfaceGraph< GUM_SCALAR > & gum::prm::GSpan< GUM_SCALAR >::interfaceGraph ( )

Returns the InterfaceGraph used by this.

Returns: the InterfaceGraph used by this.

Definition at line 432 of file gspan_tpl.h.

                                                                           {
      return *_graph_;
    }

References _graph_.

◆ interfaceGraph() [2/2]

template<GUM_Numeric GUM_SCALAR>

const gspan::InterfaceGraph< GUM_SCALAR > & gum::prm::GSpan< GUM_SCALAR >::interfaceGraph ( ) const

Returns the InterfaceGraph used by this.

Returns: the InterfaceGraph used by this.

Definition at line 437 of file gspan_tpl.h.

                                                                                       {
      return *_graph_;
    }

References _graph_.

◆ matches() [1/2]

template<GUM_Numeric GUM_SCALAR>

GSpan< GUM_SCALAR >::MatchedInstances & gum::prm::GSpan< GUM_SCALAR >::matches ( const gspan::Pattern & p )

Returns a mapping between patterns and the sequence of instance in the interface graph matching them.

Returns: a mapping between patterns and the sequence of instance in the interface graph matching them.

Definition at line 421 of file gspan_tpl.h.

                                                          {
      return *(_matched_instances_[const_cast< gspan::Pattern* >(&p)]);
    }

References _matched_instances_.

Referenced by _sortPatterns_().

Here is the caller graph for this function:

◆ matches() [2/2]

template<GUM_Numeric GUM_SCALAR>

const GSpan< GUM_SCALAR >::MatchedInstances & gum::prm::GSpan< GUM_SCALAR >::matches ( const gspan::Pattern & p ) const

Returns a mapping between patterns and the sequence of instance in the interface graph matching them.

Returns: a mapping between patterns and the sequence of instance in the interface graph matching them.

Definition at line 427 of file gspan_tpl.h.

                                                                {
      return *(_matched_instances_[const_cast< gspan::Pattern* >(&p)]);
    }

References _matched_instances_.

◆ patterns() [1/2]

template<GUM_Numeric GUM_SCALAR>

std::vector< gspan::Pattern * > & gum::prm::GSpan< GUM_SCALAR >::patterns ( )

Returns the Pattern mined by this class in a decreasing order of interest.

Returns: the Pattern mined by this class in a decreasing order of interest.

Definition at line 410 of file gspan_tpl.h.

                                                              {
      return _patterns_;
    }

References _patterns_.

◆ patterns() [2/2]

template<GUM_Numeric GUM_SCALAR>

const std::vector< gspan::Pattern * > & gum::prm::GSpan< GUM_SCALAR >::patterns ( ) const

Returns the Pattern mined by this class in a decreasing order of interest.

Returns: the Pattern mined by this class in a decreasing order of interest.

Definition at line 415 of file gspan_tpl.h.

                                                                          {
      return _patterns_;
    }

References _patterns_.

◆ setMaxDFSDepth()

template<GUM_Numeric GUM_SCALAR>

void gum::prm::GSpan< GUM_SCALAR >::setMaxDFSDepth ( Size depth )

Defines the maximal depth of the DFSTree used by this class to discover new patterns.

Parameters

depth The new maximal DFSTree depth.

Definition at line 390 of file gspan_tpl.h.

                                                       {
      _depth_stop_ = depth;
    }

References _depth_stop_.

◆ tree() [1/2]

template<GUM_Numeric GUM_SCALAR>

gspan::DFSTree< GUM_SCALAR > & gum::prm::GSpan< GUM_SCALAR >::tree ( )

Returns the DFSTree used to discover new patters.

Returns: the DFSTree used to discover new patters.

Definition at line 395 of file gspan_tpl.h.

                                                          {
      return _tree_;
    }

References _tree_.

Referenced by _sortPatterns_().

Here is the caller graph for this function:

◆ tree() [2/2]

template<GUM_Numeric GUM_SCALAR>

const gspan::DFSTree< GUM_SCALAR > & gum::prm::GSpan< GUM_SCALAR >::tree ( ) const

Returns the DFSTree used to discover new patters.

Returns: the DFSTree used to discover new patters.

Definition at line 400 of file gspan_tpl.h.

                                                                      {
      return _tree_;
    }

References _tree_.

Member Data Documentation

◆ _chosen_

template<GUM_Numeric GUM_SCALAR>

Set< PRMInstance< GUM_SCALAR >* > gum::prm::GSpan< GUM_SCALAR >::_chosen_

private

Contains all instance which belongs to a discovered and used pattern.

Definition at line 257 of file gspan.h.

Referenced by _sortPatterns_().

◆ _cost_

template<GUM_Numeric GUM_SCALAR>

HashTable< gspan::LabelData*, Idx > gum::prm::GSpan< GUM_SCALAR >::_cost_

private

Mapping between labels and their cost.

Definition at line 250 of file gspan.h.

Referenced by _sortNodesAndEdges_().

◆ _depth_stop_

template<GUM_Numeric GUM_SCALAR>

Size gum::prm::GSpan< GUM_SCALAR >::_depth_stop_

private

The max depth allowed for the DSF tree.

Definition at line 238 of file gspan.h.

Referenced by GSpan(), _subgraph_mining_(), getMaxDFSDepth(), and setMaxDFSDepth().

◆ _edges_

template<GUM_Numeric GUM_SCALAR>

std::vector< gspan::LabelData* > gum::prm::GSpan< GUM_SCALAR >::_edges_

private

The vector of edges in graph, in decreasing order of interest.

Definition at line 247 of file gspan.h.

Referenced by _sortNodesAndEdges_().

◆ _graph_

template<GUM_Numeric GUM_SCALAR>

gspan::InterfaceGraph< GUM_SCALAR >* gum::prm::GSpan< GUM_SCALAR >::_graph_

private

The interface graph used by this class.

Definition at line 232 of file gspan.h.

Referenced by GSpan(), ~GSpan(), _isEdgeEligible_(), _sortNodesAndEdges_(), discoverPatterns(), interfaceGraph(), and interfaceGraph().

◆ _matched_instances_

template<GUM_Numeric GUM_SCALAR>

HashTable< gspan::Pattern*, MatchedInstances* > gum::prm::GSpan< GUM_SCALAR >::_matched_instances_

private

Mapping between a pattern and the multiset of instances matched to it.

Definition at line 254 of file gspan.h.

Referenced by ~GSpan(), _sortPatterns_(), matches(), and matches().

◆ _nodes_

template<GUM_Numeric GUM_SCALAR>

std::vector< gspan::LabelData* > gum::prm::GSpan< GUM_SCALAR >::_nodes_

private

The vector of nodes in graph, in decreasing order of interest.

Definition at line 244 of file gspan.h.

Referenced by _sortNodesAndEdges_().

◆ _patterns_

template<GUM_Numeric GUM_SCALAR>

std::vector< gspan::Pattern* > gum::prm::GSpan< GUM_SCALAR >::_patterns_

private

The vector of discovered patters, in decreasing order of interest.

Definition at line 241 of file gspan.h.

Referenced by _sortPatterns_(), patterns(), and patterns().

◆ _tree_

template<GUM_Numeric GUM_SCALAR>

gspan::DFSTree< GUM_SCALAR > gum::prm::GSpan< GUM_SCALAR >::_tree_

private

The DFSTree used to discover new patters.

Definition at line 235 of file gspan.h.

Referenced by GSpan(), _sortNodesAndEdges_(), _subgraph_mining_(), discoverPatterns(), tree(), and tree().

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

agrum/PRM/gspan/DFSTree.h
agrum/PRM/inference/gspan.h
agrum/PRM/inference/gspan_tpl.h

Classes

Public Member Functions

Private Member Functions

Private Attributes

Pattern discovery methods.

Detailed Description

Member Typedef Documentation

◆ MatchedInstances

Constructor & Destructor Documentation

◆ GSpan()

◆ ~GSpan()

Member Function Documentation

◆ _cost_func_()

◆ _isEdgeEligible_()

◆ _sortNodesAndEdges_()

◆ _sortPatterns_()

◆ _subgraph_mining_()

◆ discoverPatterns()

◆ getMaxDFSDepth()

◆ interfaceGraph() [1/2]

◆ interfaceGraph() [2/2]

◆ matches() [1/2]

◆ matches() [2/2]

◆ patterns() [1/2]

◆ patterns() [2/2]

◆ setMaxDFSDepth()

◆ tree() [1/2]

◆ tree() [2/2]

Member Data Documentation

◆ _chosen_

◆ _cost_

◆ _depth_stop_

◆ _edges_

◆ _graph_

◆ _matched_instances_

◆ _nodes_

◆ _patterns_

◆ _tree_