Uses characteristics of an LSAPE instance for defining feature vectors for node edit operations. More...

#include <bipartite_ml.hpp>

Inheritance diagram for ged::BipartiteML< UserNodeLabel, UserEdgeLabel >:

Private Member Functions
virtual void	ml_init_ () final
	Initializes the method after initializing the global variables for the graphs. More...

virtual void	ml_set_default_options_ () final
	Sets all options that are not among the ones shared by all derived classes of ged::MLBasedMethod to default values. More...

virtual bool	ml_parse_option_ (const std::string &option, const std::string &arg) final
	Parses one option that is not among the ones shared by all derived classes of ged::MLBasedMethod. More...

virtual std::string	ml_valid_options_string_ () const final
	Returns string of all valid options that are not among the ones shared by all derived classes of ged::MLBasedMethod. More...

virtual void	ml_init_feature_variables_ (const GEDGraph &g, const GEDGraph &h, std::size_t num_threads) final
	Initializes variables that are used for populating the feature vectors of assignments between two input graphs. More...

virtual void	ml_populate_substitution_feature_vector_ (const GEDGraph &g, const GEDGraph &h, GEDGraph::NodeID i, GEDGraph::NodeID k, std::vector< double > &feature_vector) final
	Computes substitution feature vector. More...

virtual void	ml_populate_deletion_feature_vector_ (const GEDGraph &g, GEDGraph::NodeID i, std::vector< double > &feature_vector) final
	Computes deletion feature vector. More...

virtual void	ml_populate_insertion_feature_vector_ (const GEDGraph &h, GEDGraph::NodeID k, std::vector< double > &feature_vector) final
	Computes insertion feature vector. More...

virtual std::size_t	ml_get_num_features_ () final
	Returns the number of features. More...

Additional Inherited Members
Public Member Functions inherited from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >
double	predict (const GEDGraph &g, const GEDGraph &h, const NodeMap::Assignment &assignment)
	Predicts the type of a node assignment. More...

Public Member Functions inherited from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >
virtual	~LSAPEBasedMethod ()=0
	Pure virtual destructor. More...

	LSAPEBasedMethod (const GEDData< UserNodeLabel, UserEdgeLabel > &ged_data)
	Constructor. More...

void	populate_instance_and_run_as_util (const GEDGraph &g, const GEDGraph &h, Result &result, DMatrix &lsape_instance)
	Runs the method with options specified by set_options() and provides access to constructed LSAPE instance. More...

void	populate_instance (const GEDGraph &g, const GEDGraph &h, DMatrix &lsape_instance)
	Populates the LSAPE instance. More...

Public Member Functions inherited from ged::GEDMethod< UserNodeLabel, UserEdgeLabel >
virtual	~GEDMethod ()=0
	Pure virtual destructor. More...

	GEDMethod (const GEDData< UserNodeLabel, UserEdgeLabel > &ged_data)
	Constructor. More...

void	set_options (const std::string &options)
	Sets the options of the method. More...

void	run (GEDGraph::GraphID g_id, GEDGraph::GraphID h_id)
	Runs the method with options specified by set_options(). More...

void	run_as_util (const GEDGraph &g, const GEDGraph &h, Result &result)
	Runs the method with options specified by set_options(). More...

void	init ()
	Initializes the method with options specified by set_options().

double	get_upper_bound () const
	Returns an upper bound. More...

double	get_lower_bound () const
	Returns a lower bound. More...

Seconds	get_runtime () const
	Returns the runtime. More...

Seconds	get_init_time () const
	Returns the initialization time. More...

const NodeMap &	get_node_map () const
	Returns a graph matching. More...

Protected Attributes inherited from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >
std::size_t	num_features_
	The size of the feature vectors.

Protected Attributes inherited from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >
LSAPESolver::Model	lsape_model_
	Specifies model for optimal LSAPE solver.

LSAPESolver::GreedyMethod	greedy_method_
	Specifies method for greedy LSAPE solver.

bool	compute_lower_bound_
	Flag that should be set to `true` if and only if the method computes a lower bound.

bool	solve_optimally_
	Flag that equals `true` if an optimal LSAPE solver is used and `false` if a greedy method is employed.

std::size_t	num_threads_
	The number of threads to be used.

Protected Attributes inherited from ged::GEDMethod< UserNodeLabel, UserEdgeLabel >
bool	initialized_
	A flag that equals true if init() has been called and false otherwise.

const GEDData< UserNodeLabel, UserEdgeLabel > &	ged_data_
	The data on which the method is run.

Detailed Description

template<class UserNodeLabel, class UserEdgeLabel>
class ged::BipartiteML< UserNodeLabel, UserEdgeLabel >

Uses characteristics of an LSAPE instance for defining feature vectors for node edit operations.

Implements the feature vectors suggested in:

K. Riesen and M. Ferrer: “Predicting the correctness of node assignments in bipartite graph matching”, https://doi.org/10.1016/j.patrec.2015.10.007,

and their extension to general instantiations of LSAPE-GED suggested in:

D. B. Blumenthal, S. Bougleux, J. Gamper, L. Brun: “Upper bounding GED via transformations to LSAPE based on rings and machine learning.”, To be submitted to TKDE.

Supports the following options in addition to the ones supported by ged::MLBasedMethod.

`--<option> <arg>`	modified parameter	default	more information
`--lsape-method BIPARTITE\|BRANCH_FAST\|BRANCH_UNIFORM\|BRANCH\|NODE\|RING\|SUBGRAPH\|WALKS`	method for populating the LSAPE instance	`BIPARTITE`	if `BIPARTITE`, the feature vectors are identical to the ones suggested in https://doi.org/10.1016/j.patrec.2015.10.007
`--lsape-options '[–<option> <arg>] [...]'`	options string passed to the method used for populating the LSAPE instance	`''`	ged::Bipartite, ged::BranchFast, ged::BranchUniform, ged::Branch, ged::Node, ged::Ring, ged::Subgraph, ged::Walks

Definition at line 51 of file bipartite_ml.hpp.

Member Function Documentation

◆ ml_get_num_features_()

template<class UserNodeLabel , class UserEdgeLabel >

std::size_t ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_get_num_features_ ( )

finalprivatevirtual

Returns the number of features.

Returns: Size of the feature vectors employed by the derived class.

Note: Must be overridden by derived classes.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 182 of file bipartite_ml.ipp.

◆ ml_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_init_ ( )

finalprivatevirtual

Initializes the method after initializing the global variables for the graphs.

Note: Must be overridden by derived classes of ged::MLBasedMethod that require custom initialization.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 53 of file bipartite_ml.ipp.

◆ ml_init_feature_variables_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_init_feature_variables_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		std::size_t	num_threads
	)

finalprivatevirtual

Initializes variables that are used for populating the feature vectors of assignments between two input graphs.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	num_threads	The number of available threads.

Note: Must be overridden by derived classes that require initialization of variables used for populating the feature vectors of assignments between two input graphs.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 132 of file bipartite_ml.ipp.

◆ ml_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_parse_option_	(	const std::string &	option,
		const std::string &	arg
	)

finalprivatevirtual

Parses one option that is not among the ones shared by all derived classes of ged::MLBasedMethod.

Parameters

[in]	option	The name of the option.
[in]	arg	The argument of the option.

Returns: Returns true if option is a valid option name for the method and false otherwise.

Note: Must be overridden by derived classes that have options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 76 of file bipartite_ml.ipp.

◆ ml_populate_deletion_feature_vector_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_populate_deletion_feature_vector_	(	const GEDGraph &	g,
		GEDGraph::NodeID	i,
		std::vector< double > &	feature_vector
	)

finalprivatevirtual

Computes deletion feature vector.

Parameters

[in]	g	Input graph.
[in]	i	ID of node in `g` that has to be deleted.
[out]	feature_vector	Return variable. Empty when called. Must be of size ged::MLBasedMethod::num_features_ when exiting.

Note: Must be overridden by derived classes.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 156 of file bipartite_ml.ipp.

◆ ml_populate_insertion_feature_vector_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_populate_insertion_feature_vector_	(	const GEDGraph &	h,
		GEDGraph::NodeID	k,
		std::vector< double > &	feature_vector
	)

finalprivatevirtual

Computes insertion feature vector.

Parameters

[in]	h	Input graph.
[in]	k	ID of node in `h` that has to be inserted.
[out]	feature_vector	Return variable. Empty when called. Must be of size ged::MLBasedMethod::num_features_ when exiting.

Note: Must be overridden by derived classes.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 169 of file bipartite_ml.ipp.

◆ ml_populate_substitution_feature_vector_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_populate_substitution_feature_vector_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		GEDGraph::NodeID	i,
		GEDGraph::NodeID	k,
		std::vector< double > &	feature_vector
	)

finalprivatevirtual

Computes substitution feature vector.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	i	ID of node in `g` that has to be substituted.
[in]	k	ID of node in `h` that has to be substituted.
[out]	feature_vector	Return variable. Empty when called. Must be of size ged::MLBasedMethod::num_features_ when exiting.

Note: Must be overridden by derived classes.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 143 of file bipartite_ml.ipp.

◆ ml_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_set_default_options_ ( )

finalprivatevirtual

Sets all options that are not among the ones shared by all derived classes of ged::MLBasedMethod to default values.

Note: Must be overridden by derived classes that have options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 60 of file bipartite_ml.ipp.

◆ ml_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::BipartiteML< UserNodeLabel, UserEdgeLabel >::ml_valid_options_string_ ( ) const

finalprivatevirtual

Returns string of all valid options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Returns: String of the form "[--<option> <arg>] [...]".

Note: Must be overridden by derived classes that have options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Reimplemented from ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 69 of file bipartite_ml.ipp.

The documentation for this class was generated from the following files:

src/methods/bipartite_ml.hpp
src/methods/bipartite_ml.ipp

Private Member Functions

Additional Inherited Members

Detailed Description

template<class UserNodeLabel, class UserEdgeLabel> class ged::BipartiteML< UserNodeLabel, UserEdgeLabel >

Member Function Documentation

◆ ml_get_num_features_()

◆ ml_init_()

◆ ml_init_feature_variables_()

◆ ml_parse_option_()

◆ ml_populate_deletion_feature_vector_()

◆ ml_populate_insertion_feature_vector_()

◆ ml_populate_substitution_feature_vector_()

◆ ml_set_default_options_()

◆ ml_valid_options_string_()

template<class UserNodeLabel, class UserEdgeLabel>
class ged::BipartiteML< UserNodeLabel, UserEdgeLabel >