VF2 graph isomorphism.
More...
#include <GM_vf2.hh>
|
| static bool | areDegreeCompatible (const NodeDataVec &patternNodes, const NodeDataVec &targetNodes) |
| |
| static bool | fillLoader (const Graph_Interface &graph, vf2::ARGEdit &loader, PatternMap &patternLabel, NodeDataVec &nodeData, EdgeLabelVec &edgeLabels, bool isPattern) |
| |
| template<class VF2STATE , class NODECOMPARE , class EDGECOMPARE > |
| static size_t | findMatches (const PatternVec &pattern, const Graph_Interface &target, ReporterVec &output, const size_t maxHits) |
| |
| static bool | isApplicable (const Pattern_Interface &pattern, const Graph_Interface &target, const Match &match) |
| |
An sgm::GraphMatching interface implementation that uses the
implementation of the VF-2 algorithm for its computation.
- Author
- Martin Mann (c) 2008 http://www.bioinf.uni-freiburg.de/~mmann/
Definition at line 17 of file GM_vf2.hh.
Data type that defines the the search mode of findMatches(..) function
| Enumerator |
|---|
| FIND_ONE |
|
| FIND_ALL |
|
Definition at line 47 of file VF2_MatchingHandler.hh.
| static bool sgm::VF2_MatchingHandler::areDegreeCompatible |
( |
const NodeDataVec & |
patternNodes, |
|
|
const NodeDataVec & |
targetNodes |
|
) |
| |
|
staticprotectedinherited |
checks whether or not the pattern is compatible with the target based on the out degree information of the nodes.
- Parameters
-
| patternNodes | the node data of the pattern |
| targetNodes | the node data of the target |
- Returns
- true, if the pattern node degree distribution is compatible with the distribution of the target; false otherwise
Static function that is used by findMatches to fill the internally used ARGEdit objects.
- Parameters
-
| graph | the graph to be 'filled' into the loader |
| loader | the loader to fill |
| patternLabel | the already known labels from the graph |
| nodeData | the container that will hold the node data. |
| edgeLabels | the container that will hold all edge labels. |
| isPattern | If true, than graph will be used to fill patternLabel and all nodes and edges in the loader will get a label. If false, only known label from the pattern graph are set in the loader, all other are set to NULL. |
- Returns
- false if isPattern == false and at least one label in the graph is not present in patternLabel, true otherwise
Performs exact graph matching to find maxHits occurrences of the pattern graph within the target graph. Each hit is reported to the Match_Reporter object.
- Parameters
-
| pattern | the pattern graph to search for |
| target | the graph to search the pattern within |
| reporter | all hits are reported to that object |
| maxHits | the maximal number of hits to find |
- Returns
- the number of exact matches found
Implements sgm::GraphMatching.
Performs exact graph matching to find maxHits occurrences of the pattern graphs within the target graph. Each hit is reported to the Match_Reporter object. NOTE, the first maxHits matches of the pattern graphs according to their order in the patterns container are reported, i.e. first all occurrences of the first pattern are identified. If this does not exceed the maxHits limit, the next pattern is matched and so on until either no pattern is left or the maxHits limit is exceeded.
- Parameters
-
| patterns | the container of the pattern graphs to search for |
| target | the graph to search the pattern within |
| reporter | all hits are reported to that object |
| maxHits | the maximal number of hits to find |
- Returns
- the number of exact matches found
Implements sgm::GraphMatching.
Performs exact graph matching to find maxHits occurrences of the pattern graphs within the target graph. Each hit is reported to the Match_Reporter object. NOTE, the first maxHits matches of the pattern graphs according to their order in the patterns container are reported, i.e. first all occurrences of the first pattern are identified. If this does not exceed the maxHits limit, the next pattern is matched and so on until either no pattern is left or the maxHits limit is exceeded.
- Parameters
-
| patterns | the container of the pattern graphs to search for |
| target | the graph to search the pattern within |
| reporters | each hit is reported to the corresponding object, the container has to have the same length as patterns |
| maxHits | the maximal number of hits to find |
- Returns
- the number of exact matches found
Implements sgm::GraphMatching.
template<class VF2STATE , class NODECOMPARE , class EDGECOMPARE >
Performs exact sub-graph matching to find all occurences of the pattern graph within the target graph. Each hit is reported to the Match_Reporter object.
- Parameters
-
| pattern | the container of pattern graphs to search for |
| target | the graph to search the pattern within |
| output | container of match reporters, one for each pattern to match, all hits of each pattern are reported to the according output object |
| maxHits | the maximal number of matches to find |
- Returns
- the number of exact matches found
Checks whether or not a given pattern match fulfills the additional matching constraints requested by the pattern.
- Parameters
-
| pattern | the pattern to be found |
| target | the graph the left side was found within, i.e. in that the rule should be applied |
| match | contains the indices of the matched left side nodes in the target graph. match[i] corresponds to the mapping of the i-th vertex in the leftSide graph. |
The documentation for this class was generated from the following file:
