General VF2-matching functionalities. More...

#include <VF2_MatchingHandler.hh>

Inheritance diagram for sgm::VF2_MatchingHandler:

Data Structures
class	LabelComparator

class	NodeData
	Data handler for node information used for node comparison. More...

class	VF2_match_handler
	Handles match reporting from VF2-engine. More...

Public Member Functions
	VF2_MatchingHandler ()

virtual	~VF2_MatchingHandler ()

Protected Types
typedef std::multiset< Label >	EdgeLabel

typedef std::vector< EdgeLabel * >	EdgeLabelVec
	Storage to enable fast memory clean up of EdgeLabels. More...

typedef int	Label

typedef std::vector< NodeData >	NodeDataVec
	Storage to enable fast memory clean up of NodeLabels. More...

typedef std::map< std::string, Label >	PatternMap

typedef std::vector< const Pattern_Interface * >	PatternVec
	container of patterns to match More...

typedef std::vector < Match_Reporter * >	ReporterVec
	container of match reporters to report matches to More...

enum	ResultMode { FIND_ONE, FIND_ALL }

Static Protected Member Functions
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)

Detailed Description

   The general interface necessary to enable the use of the VF2 library
   for graph and sub graph matching. It covers the needed data structures
   and routines.

Author: Martin Mann (c) 2011 - http://www.bioinf.uni-freiburg.de/~mmann/

Definition at line 41 of file VF2_MatchingHandler.hh.

Member Typedef Documentation

typedef std::multiset<Label> sgm::VF2_MatchingHandler::EdgeLabel

protected

collector for parallel edge handling, since VF2 does not support multiple edges between two nodes. Therefore, all labels of parallel edges are compiled into one edge.

Definition at line 133 of file VF2_MatchingHandler.hh.

typedef std::vector< EdgeLabel* > sgm::VF2_MatchingHandler::EdgeLabelVec

protected

Definition at line 136 of file VF2_MatchingHandler.hh.

typedef int sgm::VF2_MatchingHandler::Label

protected

Label class used in the internal VF-2 data structures that just indexes the known labels

Definition at line 52 of file VF2_MatchingHandler.hh.

typedef std::vector< NodeData > sgm::VF2_MatchingHandler::NodeDataVec

protected

Definition at line 128 of file VF2_MatchingHandler.hh.

typedef std::map< std::string, Label> sgm::VF2_MatchingHandler::PatternMap

protected

The data type that allows for the reuse of Label objects to be more memory efficient.

Definition at line 66 of file VF2_MatchingHandler.hh.

typedef std::vector< const Pattern_Interface* > sgm::VF2_MatchingHandler::PatternVec

protected

Definition at line 211 of file VF2_MatchingHandler.hh.

typedef std::vector< Match_Reporter* > sgm::VF2_MatchingHandler::ReporterVec

protected

Definition at line 213 of file VF2_MatchingHandler.hh.

Member Enumeration Documentation

enum sgm::VF2_MatchingHandler::ResultMode

protected

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.

Constructor & Destructor Documentation

sgm::VF2_MatchingHandler::VF2_MatchingHandler ( )

virtual sgm::VF2_MatchingHandler::~VF2_MatchingHandler ( )

virtual

Member Function Documentation

static bool sgm::VF2_MatchingHandler::areDegreeCompatible	(	const NodeDataVec &	patternNodes,
		const NodeDataVec &	targetNodes
	)

staticprotected

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 bool sgm::VF2_MatchingHandler::fillLoader	(	const Graph_Interface &	graph,
		vf2::ARGEdit &	loader,
		PatternMap &	patternLabel,
		NodeDataVec &	nodeData,
		EdgeLabelVec &	edgeLabels,
		bool	isPattern
	)

staticprotected

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

template<class VF2STATE , class NODECOMPARE , class EDGECOMPARE >

static size_t sgm::VF2_MatchingHandler::findMatches	(	const PatternVec &	pattern,
		const Graph_Interface &	target,
		ReporterVec &	output,
		const size_t	maxHits
	)

staticprotected

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

static bool sgm::VF2_MatchingHandler::isApplicable	(	const Pattern_Interface &	pattern,
		const Graph_Interface &	target,
		const Match &	match
	)

staticprotected

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:

src/sgm/VF2_MatchingHandler.hh

Data Structures

Public Member Functions

Protected Types

Static Protected Member Functions

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation