35 template <
typename GUM_SCALAR >
38 __sortNodesAndEdges();
41 for (
auto root = __tree.roots().begin(); root != __tree.roots().end();
43 if (__tree.strategy().accept_root(&(__tree.pattern(*root)))) {
45 __subgraph_mining(graph, p);
47 for (
const auto node : __tree.iso_graph(p).nodes()) {
58 template <
typename GUM_SCALAR >
60 for (
auto iter = __graph->labels().begin(); iter != __graph->labels().end();
63 if (__graph->nodes(iter.second()).size() >= 2) {
64 __cost.insert(iter.second(),
65 __cost_func(iter.second()->tree_width,
66 __graph->nodes(iter.second()).size()));
67 __nodes.push_back(const_cast< gspan::LabelData* >(iter.second()));
71 if (__isEdgeEligible(*(__graph->edges(iter.second()).begin()))) {
72 __cost.insert(iter.second(),
73 __cost_func(iter.second()->tree_width,
74 __graph->edges(iter.second()).size()));
75 __edges.push_back(iter.second());
83 std::sort(__nodes.begin(), __nodes.end(), my_sort);
84 std::sort(__edges.begin(), __edges.end(), my_sort);
87 for (
auto iter = __nodes.begin(); iter != __nodes.end(); ++iter) {
89 new_labels->
insert(idx, *iter);
92 for (
auto iter = __edges.begin(); iter != __edges.end(); ++iter) {
94 new_labels->
insert(idx, *iter);
95 __tree.addRoot(**iter);
98 delete __graph->__labels;
99 __graph->__labels = new_labels;
102 template <
typename GUM_SCALAR >
105 std::vector< gspan::Pattern* > stack;
106 stack.push_back(&pat);
126 const std::list< NodeId >* children = 0;
128 while (!stack.empty()) {
133 if (p->
code().
codes.size() < __depth_stop) {
135 std::list< NodeId > r_path;
144 for (
size_t i = 0; i < r_path.size(); ++i)
145 count_vector.push_back(
151 for (
const auto iso_node : __tree.iso_graph(*p).nodes()) {
152 seq = &(__tree.iso_map(*p, iso_node));
155 for (
const auto node : r_path) {
156 edge_count = count_vector[idx];
158 current = seq->
atPos((
Idx)(node - 1));
159 current_id = ig.
id(current);
162 for (
const auto neighbor_id : ig.
graph().neighbours(current_id)) {
163 neighbor = ig.
node(neighbor_id).n;
168 if ((!seq->
exists(neighbor)) || (node == r_path.back())) {
172 edge_data = &(ig.
edge(current_id, neighbor_id));
174 (neighbor == edge_data->
u) ? edge_data->
l_u : edge_data->
l_v;
176 (seq->
exists(neighbor)) ? seq->
pos(neighbor) + 1 : 0;
179 node, edge_data->
l, neighbor_label, neighbor_node);
182 edge_growth = (*edge_count)[temp_growth.
toString()];
183 edge_growth->
insert(current, neighbor);
186 node, edge_data->
l, neighbor_label, neighbor_node);
187 edge_growth->
insert(current, neighbor);
196 for (
size_t node = 0; node < count_vector.size(); ++node) {
197 edge_count = count_vector[node];
199 for (
const auto& elt : *edge_count) {
201 __tree.growPattern(*p, *elt.second, 2);
213 children = &(__tree.children(*p));
215 for (std::list< NodeId >::const_reverse_iterator child =
217 child != children->rend();
219 stack.push_back(&(__tree.pattern(*child)));
224 template <
typename GUM_SCALAR >
227 std::vector< NodeId > stack;
229 for (std::list< NodeId >::reverse_iterator root = tree().roots().rbegin();
230 root != tree().roots().rend();
232 stack.push_back(*root);
235 std::list< NodeId >* children =
nullptr;
237 while (!stack.empty()) {
240 __patterns.push_back(&(tree().pattern(
id)));
241 children = &(tree().children(tree().pattern(
id)));
243 for (std::list< NodeId >::reverse_iterator child = children->rbegin();
244 child != children->rend();
246 stack.push_back(*child);
249 if (!__patterns.empty()) {
252 std::sort(__patterns.begin(), __patterns.end(), my_sort);
260 for (
const auto node : tree().max_indep_set(*(__patterns.front()))) {
261 match = &(tree().iso_map(*(__patterns.front()), node));
263 for (
const auto i : *match)
266 matches->insert(match);
269 __matched_instances.insert(__patterns.front(), matches);
274 for (
auto patt = __patterns.begin() + 1; patt != __patterns.end();
277 std::vector< NodeId > degree_list;
278 iso_graph = &(tree().iso_graph(**patt));
280 for (
const auto node : iso_graph->
nodes()) {
282 match = &(tree().iso_map(**patt, node));
284 for (
const auto i : *match)
285 if (__chosen.exists(i)) {
297 for (
const auto iso : reduced_iso_graph.
nodes())
299 reduced_iso_graph.
addEdge(node, iso);
301 degree_list.push_back(node);
311 std::sort(degree_list.begin(), degree_list.end(), my_sort);
314 for (
const auto node : degree_list)
315 if (!removed.exists(node)) {
320 for (
const auto neighbor : reduced_iso_graph.
neighbours(node))
321 removed.insert(neighbor);
325 match = &(tree().iso_map(**patt, node));
328 for (
const auto elt : *match)
329 __chosen.insert(elt);
332 __matched_instances.insert(*patt, matches);
336 std::vector< size_t > trash;
338 for (
size_t idx = 0; idx < __patterns.size(); ++idx)
339 if (__matched_instances[__patterns[idx]]->size() < 2)
340 trash.push_back(idx);
342 while (trash.size()) {
343 delete __matched_instances[__patterns[trash.back()]];
344 __matched_instances.erase(__patterns[trash.back()]);
346 __patterns[trash.back()] = __patterns.back();
347 __patterns.pop_back();
353 template <
typename GUM_SCALAR >
358 __graph(new gspan::InterfaceGraph< GUM_SCALAR >(sys)),
359 __tree(*__graph, strategy), __depth_stop(INT_MAX) {
360 GUM_CONSTRUCTOR(
GSpan);
363 template <
typename GUM_SCALAR >
365 GUM_DESTRUCTOR(
GSpan);
373 template <
typename GUM_SCALAR >
378 template <
typename GUM_SCALAR >
383 template <
typename GUM_SCALAR >
388 template <
typename GUM_SCALAR >
393 template <
typename GUM_SCALAR >
396 return Idx(interface_size * frequency);
399 template <
typename GUM_SCALAR >
404 template <
typename GUM_SCALAR >
405 INLINE
const std::vector< gspan::Pattern* >&
410 template <
typename GUM_SCALAR >
416 template <
typename GUM_SCALAR >
422 template <
typename GUM_SCALAR >
428 template <
typename GUM_SCALAR >
434 template <
typename GUM_SCALAR >
437 return (
__graph->edges(e->
l).size() >= 2)
444 template <
typename GUM_SCALAR >
450 template <
typename GUM_SCALAR >
456 template <
typename GUM_SCALAR >
461 template <
typename GUM_SCALAR >
471 template <
typename GUM_SCALAR >
477 template <
typename GUM_SCALAR >
484 template <
typename GUM_SCALAR >
489 template <
typename GUM_SCALAR >
493 return gspan->
tree().strategy().operator()(i, j);
void insert(const T1 &first, const T2 &second)
Inserts a new association in the gum::Bijection.
GSpan * gspan
A pointer over an instance of the GSpan class using this class.
bool __isEdgeEligible(typename gspan::EdgeData< GUM_SCALAR > *e)
Returns true if e is an eligible root edge.
This class is used to define an edge growth of a pattern in this DFSTree.
virtual void addNodeWithId(const NodeId id)
try to insert a node with the given id
Idx pos(const Key &key) const
Returns the position of the object passed in argument (if it exists).
PatternSort(GSpan *my_gspan)
Default constructor.
Set< Sequence< PRMInstance< GUM_SCALAR > *> *> MatchedInstances
Code alias.
Inner class to handle data about labels in this interface graph.
PRMInstance< GUM_SCALAR > * u
One of the two instance represented by this edge.
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
An PRMInstance is a Bayesian Network fragment defined by a Class and used in a PRMSystem.
DFSCode & code()
Returns the DFSCode of this Pattern.
The generic class for storing (ordered) sequences of objects.
virtual void addEdge(const NodeId first, const NodeId second)
insert a new edge into the undirected graph
LabelSort(GSpan *my_gspan)
Default constructor.
Size __depth_stop
The max depth allowed for the DSF tree.
LabelData * l_u
The label data of u.
NodeData< GUM_SCALAR > & node(const PRMInstance< GUM_SCALAR > *i)
Returns data about a node.
Inner class to handle data about edges in __graph.
void __subgraph_mining(gspan::InterfaceGraph< GUM_SCALAR > &graph, gspan::Pattern &p)
Discovers new patterns by developing p.
This is used to generate the max_indep_set of a Pattern.
This class represent the interface graph of a given gum::prm::PRMSystem<GUM_SCALAR>.
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
std::vector< EdgeCode *> codes
The vector containing the EdgeCode composing this DFSCode.
void __sortPatterns()
Sort the patterns and compute their respective costs.
The class for generic Hash Tables.
bool operator()(gspan::Pattern *i, gspan::Pattern *j)
Returns true if i's cost is lesser than j's.
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
LabelData * l
The labal data of this edge.
Representation of a setA Set is a structure that contains arbitrary elements.
gspan::DFSTree< GUM_SCALAR > __tree
The DFSTree used to discover new patters.
A DFSTree is used by gspan to sort lexicographically patterns discovered in an interface graph...
~PatternSort()
Destructor.
UndiGraph & graph()
Returns the graph of this interface graph.
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
std::vector< gspan::Pattern *> __patterns
The vector of discovered patters, in decreasing order of interest.
gspan::InterfaceGraph< GUM_SCALAR > * __graph
The interface graph used by this class.
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
A PRMSystem is a container of PRMInstance and describe a relational skeleton.
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
bool exists(const Key &k) const
Check the existence of k in the sequence.
Private class used to sort LabelData using STL sort algorithms.
Set of pairs of elements with fast search for both elements.
GSpan * gspan
A pointer over an instance of the GSpan class using this class.
gspan::DFSTree< GUM_SCALAR > & tree()
Returns the DFSTree used to discover new patters.
void rightmostPath(std::list< NodeId > &r_path) const
Fill r_path with the rightmost path of this Pattern. The list is supposed empty.
gspan::InterfaceGraph< GUM_SCALAR > & interfaceGraph()
Returns the InterfaceGraph used by this.
LabelData * l_v
The label data of v.
NodeId id(const PRMInstance< GUM_SCALAR > &i) const
Returns the id of i in this interface graph.
void discoverPatterns()
This will methods will discover repeated patterns in the PRMSystem<GUM_SCALAR> assigned to this class...
This class represents a Probabilistic Relational PRMSystem<GUM_SCALAR>.
The base class for all undirected edges.
This class discovers pattern in a PRM<GUM_SCALAR>'s PRMSystem<GUM_SCALAR> to speed up structured infe...
std::vector< gspan::Pattern *> & patterns()
Returns the Pattern mined by this class in a decreasing order of interest.
std::string toString()
Return a string representation of this.
void setMaxDFSDepth(Size depth)
Defines the maximal depth of the DFSTree used by this class to discover new patterns.
Base class for undirected graphs.
Class used to compute response times for benchmark purposesThis class represents a classic timer...
Size Idx
Type for indexes.
void __sortNodesAndEdges()
Sort the nodes and edges of __graph.
GSpan(const PRM< GUM_SCALAR > &prm, const PRMSystem< GUM_SCALAR > &sys, gspan::SearchStrategy< GUM_SCALAR > *strategy=0)
Default constructor.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Private class used to sort Pattern using STL sort algorithms.
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
EdgeData< GUM_SCALAR > & edge(NodeId u, NodeId v)
Returns data about an edge.
Size getMaxDFSDepth() const
Returns the maximal depth of the DFSTree used to discover new patterns.
MatchedInstances & matches(const gspan::Pattern &p)
Returns a mapping between patterns and the sequence of instance in the interface graph matching them...
This contains all the information we want for a node in a DFSTree.
This is an abstract class used to tune search strategies in the gspan algorithm.
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...
Size NodeId
Type for node ids.
void insert(const Key &k)
Inserts a new element into the set.
bool operator()(gspan::LabelData *i, gspan::LabelData *j)
Returns true if i's cost is lesser than j's.
HashTable< gspan::Pattern *, MatchedInstances *> __matched_instances
Mapping between a pattern and the multiset of instances matched to it.
const Key & atPos(Idx i) const
Returns the object at the pos i.
void insert(PRMInstance< GUM_SCALAR > *u, PRMInstance< GUM_SCALAR > *v)
Add the pair (u,v) as a match for the current growth.
void insert(const Key &k)
Insert an element at the end of the sequence.