gum::prm::GSpan< GUM_SCALAR > Class Template Reference

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

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

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

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

Detailed Description

template<typename 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 54 of file DFSTree.h.

Member Typedef Documentation

MatchedInstances

template<typename GUM_SCALAR>

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

Code alias.

Definition at line 167 of file gspan.h.

Constructor & Destructor Documentation

GSpan()

template<typename GUM_SCALAR >

INLINE 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 352 of file gspan_tpl.h.

                                                                               :
        __graph(new gspan::InterfaceGraph< GUM_SCALAR >(sys)),
        __tree(*__graph, strategy), __depth_stop(INT_MAX) {
      GUM_CONSTRUCTOR(GSpan);
    }

~GSpan()

template<typename GUM_SCALAR >

INLINE gum::prm::GSpan< GUM_SCALAR >::~GSpan

(

)

Destructor.

Definition at line 361 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__graph, and gum::prm::GSpan< GUM_SCALAR >::__matched_instances.

                                       {
      GUM_DESTRUCTOR(GSpan);

      for (const auto& elt : __matched_instances)
        delete elt.second;

      delete __graph;
    }

Member Function Documentation

__cost_func()

template<typename GUM_SCALAR >

INLINE 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. TODO replace this by a class to enable different cost policies.

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 391 of file gspan_tpl.h.

                                                                {
      return Idx(interface_size * frequency);
    }

__isEdgeEligible()

template<typename GUM_SCALAR >

INLINE 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 433 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__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.

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

__sortNodesAndEdges()

template<typename GUM_SCALAR >

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

private

Sort the nodes and edges of __graph.

Definition at line 56 of file gspan_tpl.h.

References gum::BijectionImplementation< T1, T2, Alloc, std::is_scalar< T1 >::value &&std::is_scalar< T2 >::value >::insert().

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

Here is the call graph for this function:

__sortPatterns()

template<typename GUM_SCALAR >

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

private

Sort the patterns and compute their respective costs.

Definition at line 222 of file gspan_tpl.h.

References gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::EdgeGraphPart::existsEdge(), gum::Set< Key, Alloc >::insert(), gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::insert(), gum::EdgeGraphPart::neighbours(), and gum::NodeGraphPart::nodes().

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

Here is the call graph for this function:

__subgraph_mining()

template<typename 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 100 of file gspan_tpl.h.

References gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::atPos(), gum::prm::gspan::Pattern::code(), gum::prm::gspan::DFSCode::codes, gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::edge(), gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::exists(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::graph(), gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::id(), gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::insert(), gum::HashTable< Key, Val, Alloc >::insert(), gum::prm::gspan::EdgeData< GUM_SCALAR >::l, gum::prm::gspan::EdgeData< GUM_SCALAR >::l_u, gum::prm::gspan::EdgeData< GUM_SCALAR >::l_v, gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::node(), gum::SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >::pos(), gum::prm::gspan::Pattern::rightmostPath(), gum::prm::gspan::EdgeGrowth< GUM_SCALAR >::toString(), and gum::prm::gspan::EdgeData< GUM_SCALAR >::u.

                                                                 {
      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.graph().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);

                  try {
                    edge_growth = (*edge_count)[temp_growth.toString()];
                    edge_growth->insert(current, neighbor);
                  } catch (NotFound&) {
                    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&) {
                // 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)));
        }
      }
    }

Here is the call graph for this function:

discoverPatterns()

template<typename 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 33 of file gspan_tpl.h.

References gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::graph(), and gum::prm::gspan::InterfaceGraph< GUM_SCALAR >::id().

                                               {
      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.graph().eraseEdge(Edge(graph.id(u), graph.id(v)));
          }
        }
      }

      __sortPatterns();
    }

Here is the call graph for this function:

getMaxDFSDepth()

template<typename GUM_SCALAR >

INLINE 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 371 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__depth_stop.

                                                          {
      return __depth_stop;
    }

interfaceGraph() [1/2]

template<typename GUM_SCALAR >

INLINE 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 421 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__graph.

                                               {
      return *__graph;
    }

interfaceGraph() [2/2]

template<typename GUM_SCALAR >

INLINE 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 427 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__graph.

                                                           {
      return *__graph;
    }

matches() [1/2]

template<typename GUM_SCALAR >

INLINE 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 409 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__matched_instances.

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

matches() [2/2]

template<typename GUM_SCALAR >

INLINE 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 415 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__matched_instances.

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

patterns() [1/2]

template<typename GUM_SCALAR >

INLINE 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 397 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__patterns.

                                                                     {
      return __patterns;
    }

patterns() [2/2]

template<typename GUM_SCALAR >

INLINE 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 403 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__patterns.

                                                     {
      return __patterns;
    }

setMaxDFSDepth()

template<typename GUM_SCALAR >

INLINE 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 376 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__depth_stop.

                                                              {
      __depth_stop = depth;
    }

tree() [1/2]

template<typename GUM_SCALAR >

INLINE 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 381 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__tree.

Referenced by gum::prm::GSpan< GUM_SCALAR >::PatternSort::operator()().

                                                                 {
      return __tree;
    }

Here is the caller graph for this function:

tree() [2/2]

template<typename GUM_SCALAR >

INLINE 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 386 of file gspan_tpl.h.

References gum::prm::GSpan< GUM_SCALAR >::__tree.

                                                                             {
      return __tree;
    }

Member Data Documentation

__chosen

template<typename 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 238 of file gspan.h.

__cost

template<typename GUM_SCALAR>

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

private

Mapping between labels and their cost.

Definition at line 231 of file gspan.h.

__depth_stop

template<typename GUM_SCALAR>

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

private

The max depth allowed for the DSF tree.

Definition at line 219 of file gspan.h.

Referenced by gum::prm::GSpan< GUM_SCALAR >::getMaxDFSDepth(), and gum::prm::GSpan< GUM_SCALAR >::setMaxDFSDepth().

__edges

template<typename 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 228 of file gspan.h.

__graph

template<typename GUM_SCALAR>

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

private

The interface graph used by this class.

Definition at line 213 of file gspan.h.

Referenced by gum::prm::GSpan< GUM_SCALAR >::__isEdgeEligible(), gum::prm::GSpan< GUM_SCALAR >::interfaceGraph(), and gum::prm::GSpan< GUM_SCALAR >::~GSpan().

__matched_instances

template<typename 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 235 of file gspan.h.

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

__nodes

template<typename 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 225 of file gspan.h.

__patterns

template<typename 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 222 of file gspan.h.

Referenced by gum::prm::GSpan< GUM_SCALAR >::patterns().

__tree

template<typename GUM_SCALAR>

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

private

The DFSTree used to discover new patters.

Definition at line 216 of file gspan.h.

Referenced by gum::prm::GSpan< GUM_SCALAR >::LabelSort::operator()(), and gum::prm::GSpan< GUM_SCALAR >::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