aGrUM  0.13.2
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...
 
MatchedInstancesmatches (const gspan::Pattern &p)
 Returns a mapping between patterns and the sequence of instance in the interface graph matching them. More...
 
const MatchedInstancesmatches (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

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

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
prmThe PRM<GUM_SCALAR> used by this class.
sysThe PRMSystem<GUM_SCALAR> on which this class searches for patterns.
strategyThe search strategy used for pattern mining, the default strategy is gspan::FrequenceSearch.

Definition at line 352 of file gspan_tpl.h.

354  :
355  __graph(new gspan::InterfaceGraph< GUM_SCALAR >(sys)),
356  __tree(*__graph, strategy), __depth_stop(INT_MAX) {
357  GUM_CONSTRUCTOR(GSpan);
358  }
Size __depth_stop
The max depth allowed for the DSF tree.
Definition: gspan.h:219
gspan::DFSTree< GUM_SCALAR > __tree
The DFSTree used to discover new patters.
Definition: gspan.h:216
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
Definition: gspan.h:213
GSpan(const PRM< GUM_SCALAR > &prm, const PRMSystem< GUM_SCALAR > &sys, gspan::SearchStrategy< GUM_SCALAR > *strategy=0)
Default constructor.
Definition: gspan_tpl.h:352
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.

361  {
362  GUM_DESTRUCTOR(GSpan);
363 
364  for (const auto& elt : __matched_instances)
365  delete elt.second;
366 
367  delete __graph;
368  }
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
Definition: gspan.h:213
GSpan(const PRM< GUM_SCALAR > &prm, const PRMSystem< GUM_SCALAR > &sys, gspan::SearchStrategy< GUM_SCALAR > *strategy=0)
Default constructor.
Definition: gspan_tpl.h:352
HashTable< gspan::Pattern *, MatchedInstances * > __matched_instances
Mapping between a pattern and the multiset of instances matched to it.
Definition: gspan.h:235

Member Function Documentation

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_sizeThe size of all output nodes of a pattern.
frequencyThe 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.

392  {
393  return Idx(interface_size * frequency);
394  }
unsigned long Idx
Type for indexes.
Definition: types.h:43
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
eAn 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.

433  {
434  return (__graph->edges(e->l).size() >= 2)
435  && (__graph->nodes(e->l_u).size() >= 2)
436  && (__graph->nodes(e->l_v).size() >= 2);
437  }
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
Definition: gspan.h:213
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().

56  {
57  for (auto iter = __graph->labels().begin(); iter != __graph->labels().end();
58  ++iter) {
59  try {
60  if (__graph->nodes(iter.second()).size() >= 2) {
61  __cost.insert(iter.second(),
62  __cost_func(iter.second()->tree_width,
63  __graph->nodes(iter.second()).size()));
64  __nodes.push_back(const_cast< gspan::LabelData* >(iter.second()));
65  }
66  } catch (NotFound&) {
67  // It's a label over edges
68  if (__isEdgeEligible(*(__graph->edges(iter.second()).begin()))) {
69  __cost.insert(iter.second(),
70  __cost_func(iter.second()->tree_width,
71  __graph->edges(iter.second()).size()));
72  __edges.push_back(iter.second());
73  }
74  }
75  }
76 
77  Bijection< Idx, gspan::LabelData* >* new_labels =
78  new Bijection< Idx, gspan::LabelData* >();
79  GSpan< GUM_SCALAR >::LabelSort my_sort(this);
80  std::sort(__nodes.begin(), __nodes.end(), my_sort);
81  std::sort(__edges.begin(), __edges.end(), my_sort);
82  Size idx = 0;
83 
84  for (auto iter = __nodes.begin(); iter != __nodes.end(); ++iter) {
85  (*iter)->id = ++idx;
86  new_labels->insert(idx, *iter);
87  }
88 
89  for (auto iter = __edges.begin(); iter != __edges.end(); ++iter) {
90  (*iter)->id = ++idx;
91  new_labels->insert(idx, *iter);
92  __tree.addRoot(**iter);
93  }
94 
95  delete __graph->__labels;
96  __graph->__labels = new_labels;
97  }
bool __isEdgeEligible(typename gspan::EdgeData< GUM_SCALAR > *e)
Returns true if e is an eligible root edge.
Definition: gspan_tpl.h:433
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
std::vector< gspan::LabelData * > __nodes
The vector of nodes in __graph, in decreasing order of interest.
Definition: gspan.h:225
HashTable< gspan::LabelData *, Idx > __cost
Mapping between labels and their cost.
Definition: gspan.h:231
gspan::DFSTree< GUM_SCALAR > __tree
The DFSTree used to discover new patters.
Definition: gspan.h:216
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
Definition: gspan.h:213
std::vector< gspan::LabelData * > __edges
The vector of edges in __graph, in decreasing order of interest.
Definition: gspan.h:228
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
Size __cost_func(Size interface_size, Size frequency)
Returns the cost with respect to an interface size and its frequency. TODO replace this by a class to...
Definition: gspan_tpl.h:391

+ Here is the call graph for this function:

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

222  {
223  // First we put all the patterns in __patterns.
224  std::vector< NodeId > stack;
225 
226  for (std::list< NodeId >::reverse_iterator root = tree().roots().rbegin();
227  root != tree().roots().rend();
228  ++root)
229  stack.push_back(*root);
230 
231  NodeId id = 0;
232  std::list< NodeId >* children = nullptr;
233 
234  while (!stack.empty()) {
235  id = stack.back();
236  stack.pop_back();
237  __patterns.push_back(&(tree().pattern(id)));
238  children = &(tree().children(tree().pattern(id)));
239 
240  for (std::list< NodeId >::reverse_iterator child = children->rbegin();
241  child != children->rend();
242  ++child)
243  stack.push_back(*child);
244  }
245 
246  if (!__patterns.empty()) {
247  // We sort __patterns.
248  GSpan< GUM_SCALAR >::PatternSort my_sort(this);
249  std::sort(__patterns.begin(), __patterns.end(), my_sort);
250  // Now we need to find all the matches we can, using __patterns.
251  // We start by the best Pattern and add it's maximal independent set to
252  // __chosen
255  Sequence< PRMInstance< GUM_SCALAR >* >* match = nullptr;
256 
257  for (const auto node : tree().max_indep_set(*(__patterns.front()))) {
258  match = &(tree().iso_map(*(__patterns.front()), node));
259 
260  for (const auto i : *match)
261  __chosen.insert(i);
262 
263  matches->insert(match);
264  }
265 
266  __matched_instances.insert(__patterns.front(), matches);
267  // Now we see what kind of pattern we can still use
268  bool found;
269  UndiGraph* iso_graph = nullptr;
270 
271  for (auto patt = __patterns.begin() + 1; patt != __patterns.end();
272  ++patt) {
273  UndiGraph reduced_iso_graph;
274  std::vector< NodeId > degree_list;
275  iso_graph = &(tree().iso_graph(**patt));
276 
277  for (const auto node : iso_graph->nodes()) {
278  found = false;
279  match = &(tree().iso_map(**patt, node));
280 
281  for (const auto i : *match)
282  if (__chosen.exists(i)) {
283  found = true;
284  break;
285  }
286 
287  if (!found) {
288  // We add the pattern to the reduced isomorphism graph to compute
289  // the
290  // max independent set
291  // over the remaining matches
292  reduced_iso_graph.addNodeWithId(node);
293 
294  for (const auto iso : reduced_iso_graph.nodes())
295  if (iso_graph->existsEdge(node, iso))
296  reduced_iso_graph.addEdge(node, iso);
297 
298  degree_list.push_back(node);
299  }
300  }
301 
302  // We create a new set to hold all the chosen matches of patt
304  // We can compute the max independent set and the matches belonging to
305  // it
306  typename gspan::DFSTree< GUM_SCALAR >::NeighborDegreeSort my_sort(
307  reduced_iso_graph);
308  std::sort(degree_list.begin(), degree_list.end(), my_sort);
309  Set< NodeId > removed;
310 
311  for (const auto node : degree_list)
312  if (!removed.exists(node)) {
313  // First we update removed to follow the max independent set
314  // algorithm
315  removed.insert(node);
316 
317  for (const auto neighbor : reduced_iso_graph.neighbours(node))
318  removed.insert(neighbor);
319 
320  // Second we update match and matches to keep track of the current
321  // match
322  match = &(tree().iso_map(**patt, node));
323  matches->insert(match);
324 
325  for (const auto elt : *match)
326  __chosen.insert(elt);
327  }
328 
329  __matched_instances.insert(*patt, matches);
330  }
331 
332  // // We remove patterns with 0 matches
333  std::vector< size_t > trash;
334 
335  for (size_t idx = 0; idx < __patterns.size(); ++idx)
336  if (__matched_instances[__patterns[idx]]->size() < 2)
337  trash.push_back(idx);
338 
339  while (trash.size()) {
340  delete __matched_instances[__patterns[trash.back()]];
341  __matched_instances.erase(__patterns[trash.back()]);
342  // delete __patterns[trash.back()];
343  __patterns[trash.back()] = __patterns.back();
344  __patterns.pop_back();
345  trash.pop_back();
346  }
347  }
348  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
Set< Sequence< PRMInstance< GUM_SCALAR > * > * > MatchedInstances
Code alias.
Definition: gspan.h:167
Set< PRMInstance< GUM_SCALAR > * > __chosen
Contains all instance which belongs to a discovered and used pattern.
Definition: gspan.h:238
std::vector< gspan::Pattern * > __patterns
The vector of discovered patters, in decreasing order of interest.
Definition: gspan.h:222
gspan::DFSTree< GUM_SCALAR > & tree()
Returns the DFSTree used to discover new patters.
Definition: gspan_tpl.h:381
MatchedInstances & matches(const gspan::Pattern &p)
Returns a mapping between patterns and the sequence of instance in the interface graph matching them...
Definition: gspan_tpl.h:409
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
HashTable< gspan::Pattern *, MatchedInstances * > __matched_instances
Mapping between a pattern and the multiset of instances matched to it.
Definition: gspan.h:235

+ Here is the call graph for this function:

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
graphThe interface graph used in this discovery process.
pThe 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.

101  {
102  std::vector< gspan::Pattern* > stack;
103  stack.push_back(&pat);
104  // Pointers used in the following while
105  gspan::Pattern* p = nullptr;
106  HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >* edge_count =
107  nullptr;
108  gspan::EdgeGrowth< GUM_SCALAR >* edge_growth = nullptr;
109  Sequence< PRMInstance< GUM_SCALAR >* >* seq = nullptr;
110  PRMInstance< GUM_SCALAR >* current = nullptr;
111  PRMInstance< GUM_SCALAR >* neighbor = nullptr;
112 
113  // Neighbor_id is the neighbor's id in the interface graph and
114  // neighbor_node
115  // is its id in the rightmost path in the case of a backward edge growth
116  NodeId current_id = 0;
117  NodeId neighbor_node = 0;
118  gspan::LabelData* neighbor_label = 0;
119 
120  typename gspan::EdgeData< GUM_SCALAR >* edge_data = nullptr;
121 
122  size_t idx;
123  const std::list< NodeId >* children = 0;
124 
125  while (!stack.empty()) {
126  // Getting next pattern
127  p = stack.back();
128  stack.pop_back();
129 
130  if (p->code().codes.size() < __depth_stop) {
131  // We need the rightmost path of p
132  std::list< NodeId > r_path;
133  p->rightmostPath(r_path);
134  // Mapping used to count each possible child of p, the position in the
135  // vector
136  // matches the one in the rightmost path
137  std::vector<
138  HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >* >
139  count_vector;
140 
141  for (size_t i = 0; i < r_path.size(); ++i)
142  count_vector.push_back(
143  new HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >());
144 
145  // For each subgraph represented by p, we look for a valid edge growth
146  // for
147  // each instance match of p in its isomorphism graph.
148  for (const auto iso_node : __tree.iso_graph(*p).nodes()) {
149  seq = &(__tree.iso_map(*p, iso_node));
150  idx = 0;
151 
152  for (const auto node : r_path) {
153  edge_count = count_vector[idx];
154  // Retrieving the equivalent instance in the current match
155  current = seq->atPos((Idx)(node - 1));
156  current_id = ig.id(current);
157  // Checking for edges not in p
158 
159  for (const auto neighbor_id : ig.graph().neighbours(current_id)) {
160  neighbor = ig.node(neighbor_id).n;
161 
162  // We want a forward edge in any case or a backward edge if
163  // current
164  // is the rightmost vertex
165  if ((!seq->exists(neighbor)) || (node == r_path.back())) {
166  // Things we need to know: the LabelData data of the neighbour
167  // and,
168  // if it's a backward edge, its node id in the rightmost path
169  edge_data = &(ig.edge(current_id, neighbor_id));
170  neighbor_label =
171  (neighbor == edge_data->u) ? edge_data->l_u : edge_data->l_v;
172  neighbor_node =
173  (seq->exists(neighbor)) ? seq->pos(neighbor) + 1 : 0;
174  // Adding the edge growth to the edge_growth hashtable
175  gspan::EdgeGrowth< GUM_SCALAR > temp_growth(
176  node, edge_data->l, neighbor_label, neighbor_node);
177 
178  try {
179  edge_growth = (*edge_count)[temp_growth.toString()];
180  edge_growth->insert(current, neighbor);
181  } catch (NotFound&) {
182  edge_growth = new gspan::EdgeGrowth< GUM_SCALAR >(
183  node, edge_data->l, neighbor_label, neighbor_node);
184  edge_growth->insert(current, neighbor);
185  edge_count->insert(edge_growth->toString(), edge_growth);
186  }
187  }
188  }
189  }
190  }
191 
192  // Removing any infrequent child
193  for (size_t node = 0; node < count_vector.size(); ++node) {
194  edge_count = count_vector[node];
195 
196  for (const auto& elt : *edge_count) {
197  try {
198  __tree.growPattern(*p, *elt.second, 2);
199  } catch (OperationNotAllowed&) {
200  // The child was not minimal or was not worth considering
201  }
202 
203  delete elt.second;
204  }
205 
206  delete edge_count;
207  }
208 
209  // Calling __subgraph_mining over children of p
210  children = &(__tree.children(*p));
211 
212  for (std::list< NodeId >::const_reverse_iterator child =
213  children->rbegin();
214  child != children->rend();
215  ++child)
216  stack.push_back(&(__tree.pattern(*child)));
217  }
218  }
219  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
Size __depth_stop
The max depth allowed for the DSF tree.
Definition: gspan.h:219
gspan::DFSTree< GUM_SCALAR > __tree
The DFSTree used to discover new patters.
Definition: gspan.h:216
unsigned long Idx
Type for indexes.
Definition: types.h:43

+ Here is the call graph for this function:

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

33  {
34  Timer t;
36  gspan::InterfaceGraph< GUM_SCALAR > graph(*__graph);
37 
38  for (auto root = __tree.roots().begin(); root != __tree.roots().end();
39  ++root) {
40  if (__tree.strategy().accept_root(&(__tree.pattern(*root)))) {
41  gspan::Pattern& p = __tree.pattern(*root);
42  __subgraph_mining(graph, p);
43 
44  for (const auto node : __tree.iso_graph(p).nodes()) {
45  PRMInstance< GUM_SCALAR >* u = __tree.iso_map(p, node).atPos(0);
46  PRMInstance< GUM_SCALAR >* v = __tree.iso_map(p, node).atPos(1);
47  graph.graph().eraseEdge(Edge(graph.id(u), graph.id(v)));
48  }
49  }
50  }
51 
53  }
void __subgraph_mining(gspan::InterfaceGraph< GUM_SCALAR > &graph, gspan::Pattern &p)
Discovers new patterns by developing p.
Definition: gspan_tpl.h:100
void __sortPatterns()
Sort the patterns and compute their respective costs.
Definition: gspan_tpl.h:222
gspan::DFSTree< GUM_SCALAR > __tree
The DFSTree used to discover new patters.
Definition: gspan.h:216
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
Definition: gspan.h:213
void __sortNodesAndEdges()
Sort the nodes and edges of __graph.
Definition: gspan_tpl.h:56

+ Here is the call graph for this function:

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.

371  {
372  return __depth_stop;
373  }
Size __depth_stop
The max depth allowed for the DSF tree.
Definition: gspan.h:219
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.

421  {
422  return *__graph;
423  }
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
Definition: gspan.h:213
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.

427  {
428  return *__graph;
429  }
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
Definition: gspan.h:213
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.

409  {
410  return *(__matched_instances[const_cast< gspan::Pattern* >(&p)]);
411  }
HashTable< gspan::Pattern *, MatchedInstances * > __matched_instances
Mapping between a pattern and the multiset of instances matched to it.
Definition: gspan.h:235
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.

415  {
416  return *(__matched_instances[const_cast< gspan::Pattern* >(&p)]);
417  }
HashTable< gspan::Pattern *, MatchedInstances * > __matched_instances
Mapping between a pattern and the multiset of instances matched to it.
Definition: gspan.h:235
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.

397  {
398  return __patterns;
399  }
std::vector< gspan::Pattern * > __patterns
The vector of discovered patters, in decreasing order of interest.
Definition: gspan.h:222
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.

403  {
404  return __patterns;
405  }
std::vector< gspan::Pattern * > __patterns
The vector of discovered patters, in decreasing order of interest.
Definition: gspan.h:222
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
depthThe new maximal DFSTree depth.

Definition at line 376 of file gspan_tpl.h.

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

376  {
377  __depth_stop = depth;
378  }
Size __depth_stop
The max depth allowed for the DSF tree.
Definition: gspan.h:219
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()().

381  {
382  return __tree;
383  }
gspan::DFSTree< GUM_SCALAR > __tree
The DFSTree used to discover new patters.
Definition: gspan.h:216

+ Here is the caller graph for this function:

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.

386  {
387  return __tree;
388  }
gspan::DFSTree< GUM_SCALAR > __tree
The DFSTree used to discover new patters.
Definition: gspan.h:216

Member Data Documentation

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.

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.

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

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.

template<typename GUM_SCALAR>
gspan::InterfaceGraph< GUM_SCALAR >* gum::prm::GSpan< GUM_SCALAR >::__graph
private
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().

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.

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

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: