main page
namespaces
classes
files
GGL home
Generated on Wed Apr 29 2015 11:51:40 for GGL-4.1.2 by
doxygen
1.8.3.1
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
src
sgm
GM_vf2.hh
Go to the documentation of this file.
1
#ifndef SGM_GM_VF2_H_
2
#define SGM_GM_VF2_H_
3
4
#include "
sgm/GraphMatching.hh
"
5
#include "
sgm/VF2_MatchingHandler.hh
"
6
7
8
namespace
sgm {
9
10
/*! @brief VF2 graph isomorphism
11
*
12
* An sgm::GraphMatching interface implementation that uses the
13
* implementation of the VF-2 algorithm for its computation.
14
*
15
* @author Martin Mann (c) 2008 http://www.bioinf.uni-freiburg.de/~mmann/
16
*/
17
class
GM_vf2
:
public
GraphMatching
,
public
VF2_MatchingHandler
{
18
19
protected
:
20
21
22
typedef
VF2_MatchingHandler::Label
Label
;
23
typedef
VF2_MatchingHandler::LabelComparator
LabelComparator
;
24
typedef
VF2_MatchingHandler::NodeData
NodeData
;
25
typedef
VF2_MatchingHandler::NodeDataVec
NodeDataVec
;
26
typedef
VF2_MatchingHandler::EdgeLabel
EdgeLabel
;
27
typedef
VF2_MatchingHandler::EdgeLabelVec
EdgeLabelVec
;
28
typedef
VF2_MatchingHandler::PatternMap
PatternMap
;
29
typedef
VF2_MatchingHandler::VF2_match_handler
VF2_match_handler
;
30
31
//! Comparator class for the node data used in the internal VF-2
32
//! data structures
33
class
NodeComparator
:
public
LabelComparator
{
34
public
:
35
//! the label defining the wildcard to use
36
using
LabelComparator::pWildcard
;
37
//! access to the pattern currently matched
38
const
sgm::Pattern_Interface
&
pattern
;
39
//! access to the target graph processed
40
const
sgm::Graph_Interface
&
target
;
41
//! construction
42
//! @param pWildcard access to the wildcard label
43
//! @param pattern the pattern currently matched
44
//! @param target the target graph currently processed
45
NodeComparator
(
const
Label
&
pWildcard
46
,
const
sgm::Pattern_Interface
&
pattern
47
,
const
sgm::Graph_Interface
&
target
);
48
//! comparison of the two pointers and objects.
49
//! @param pa first label pointer, assumed to be the pattern
50
//! @param pb second label pointer, assumed to be the target
51
//! @return true if the node data is compatible for matching
52
virtual
bool
compatible
(
void
*pa,
void
*pb);
53
};
54
55
//! Comparator class for the edge label used in the internal VF-2
56
//! data structures
57
class
EdgeLabelComparator
:
public
LabelComparator
{
58
public
:
59
//! the label defining the wildcard to use
60
using
LabelComparator::pWildcard
;
61
//! construction
62
//! @param pWildcard access to the wildcard label
63
EdgeLabelComparator
(
const
Label
&
pWildcard
);
64
//! comparison of the two pointers and objects.
65
//! @param pa first label pointer, assumed to be the pattern
66
//! @param pb second label pointer, assumed to be the target
67
//! @return true if pa and pb are Label pointers != NULL and pa
68
//! has a lexicographically smaller text
69
virtual
bool
compatible
(
void
*pa,
void
*pb);
70
};
71
72
73
74
75
public
:
76
77
//////////////////// GRAPH MATCHING INTERFACE //////////////////////////
78
79
//! Performs exact graph matching to find maxHits occurrences of the
80
//! pattern graph within the target graph. Each hit is reported to
81
//! the Match_Reporter object.
82
//! @param pattern the pattern graph to search for
83
//! @param target the graph to search the pattern within
84
//! @param reporter all hits are reported to that object
85
//! @param maxHits the maximal number of hits to find
86
//! @return the number of exact matches found
87
virtual
88
size_t
89
findMatches
(
const
Pattern_Interface
& pattern,
90
const
Graph_Interface
& target,
91
Match_Reporter
& reporter,
92
const
size_t
maxHits );
93
94
//! Performs exact graph matching to find maxHits occurrences of the
95
//! pattern graphs within the target graph. Each hit is reported to
96
//! the Match_Reporter object.
97
//! NOTE, the first maxHits matches of the pattern graphs according
98
//! to their order in the patterns container are reported, i.e. first
99
//! all occurrences of the first pattern are identified. If this does
100
//! not exceed the maxHits limit, the next pattern is matched and so
101
//! on until either no pattern is left or the maxHits limit is
102
//! exceeded.
103
//! @param patterns the container of the pattern graphs to search for
104
//! @param target the graph to search the pattern within
105
//! @param reporter all hits are reported to that object
106
//! @param maxHits the maximal number of hits to find
107
//! @return the number of exact matches found
108
virtual
109
size_t
110
findMatches
(
const
std::vector< const Pattern_Interface*> & patterns,
111
const
Graph_Interface
& target,
112
Match_Reporter
& reporter,
113
const
size_t
maxHits );
114
115
//! Performs exact graph matching to find maxHits occurrences of the
116
//! pattern graphs within the target graph. Each hit is reported to
117
//! the Match_Reporter object.
118
//! NOTE, the first maxHits matches of the pattern graphs according
119
//! to their order in the patterns container are reported, i.e. first
120
//! all occurrences of the first pattern are identified. If this does
121
//! not exceed the maxHits limit, the next pattern is matched and so
122
//! on until either no pattern is left or the maxHits limit is
123
//! exceeded.
124
//! @param patterns the container of the pattern graphs to search for
125
//! @param target the graph to search the pattern within
126
//! @param reporters each hit is reported to the corresponding object,
127
//! the container has to have the same length as patterns
128
//! @param maxHits the maximal number of hits to find
129
//! @return the number of exact matches found
130
virtual
131
size_t
132
findMatches
(
const
std::vector< const Pattern_Interface*> & patterns,
133
const
Graph_Interface
& target,
134
std::vector<Match_Reporter*> & reporters,
135
const
size_t
maxHits );
136
137
138
};
139
140
}
// namespace sgm
141
142
#endif
/*GM_VF2_H_*/