Abstract class for methods that use lossy transformations to LSAPE for approximating the graph edit distance. More...

#include <lsape_based_method.hpp>

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

[legend]

Public Member Functions
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
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.

Private Member Functions
virtual void	ged_init_ () final
	Initializes the method. More...

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

virtual bool	ged_parse_option_ (const std::string &option, const std::string &arg) final
	Parses one option. More...

virtual std::string	ged_valid_options_string_ () const final
	Returns string of all valid options. More...

virtual void	ged_set_default_options_ () final
	Sets all options to default values. More...

virtual void	lsape_init_ ()
	Initializes the method after initializing the global variables for the graphs. More...

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

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

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

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

virtual void	lsape_init_graph_ (const GEDGraph &graph)
	Initializes global variables for one graph. More...

virtual void	lsape_pre_graph_init_ (bool called_at_runtime)
	Initializes the method at runtime or during initialization before initializing the global variables for the graphs. More...

virtual void	lsape_default_post_graph_init_ ()
	Default initializes the method at runtime after initializing the global variables for the graphs. More...

virtual double	lsape_lower_bound_scaling_factor_ (const GEDGraph &g, const GEDGraph &h)
	Returns scaling factor for lower bound. More...

Detailed Description

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

Abstract class for methods that use lossy transformations to LSAPE for approximating the graph edit distance.

Implements the paradigm LSAPE-GED described in:

D. B. Blumenthal, S. Bougleux, J. Gamper, and L. Brun: “Ring based approximation of graph edit distance”, S+SSPR 2018,

and the extension of LSAPE-GED which uses node centrality measures:

K. Riesen, H. Bunke, and A. Fischer: “Improving graph edit distance approximation by centrality measures”, https:://doi.org/10.1016/j.patcog.2014.11.002

All derived classes support the following options:

`--<option> <arg>`	modified parameter	default	more information
`--threads <convertible to int greater 0>`	number of threads	1	can be used by derived classes
`--lsape-model ECBP\|EBP\|FLWC\|FLCC\|FBP\|SFBP\|FBP0`	model for optimally solving LSAPE	`ECBP`	ged::LSAPESolver::Model
`--greedy-method BASIC\|REFINED\|LOSS\|BASIC_SORT\|INT_BASIC_SORT`	method for greedily solving LSAPE	`BASIC`	ged::LSAPESolver::GreedyMethod
`--optimal TRUE\|FALSE`	solve optimally or greedily	`TRUE`	if `TRUE`, the option `--greedy-method` has no effect if `FALSE`, the option `--lsape-method` has no effect
`--centrality-method NONE\|DEGREE\|EIGENVECTOR\|PAGERANK`	node centrality method	`NONE`	https:://doi.org/10.1016/j.patcog.2014.11.002 if `NONE`, the option `--centrality-weight` has no effect
`--centrality-weight <convertible to double between 0 and 1>`	weight of node centralities	0.7	https:://doi.org/10.1016/j.patcog.2014.11.002
`--max-num-solutions ALL\|<convertible to int greater 0>`	maximal number of solutions	1	the actual number of computed solutions might be smaller than the specified value

Definition at line 56 of file lsape_based_method.hpp.

Constructor & Destructor Documentation

◆ ~LSAPEBasedMethod()

template<class UserNodeLabel , class UserEdgeLabel >

ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::~LSAPEBasedMethod ( )

pure virtual

Pure virtual destructor.

Note: Must be implemented by derived classes.

Definition at line 35 of file lsape_based_method.ipp.

◆ LSAPEBasedMethod()

template<class UserNodeLabel , class UserEdgeLabel >

ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::LSAPEBasedMethod ( const GEDData< UserNodeLabel, UserEdgeLabel > & ged_data )

Constructor.

Parameters

[in] ged_data The instance on which the method should be run.

Definition at line 39 of file lsape_based_method.ipp.

Member Function Documentation

◆ ged_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::ged_init_ ( )

finalprivatevirtual

Initializes the method.

Note: Must be overridden by derived classes that require initialization.

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

Definition at line 116 of file lsape_based_method.ipp.

◆ ged_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

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

finalprivatevirtual

Parses one option.

Parameters

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

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

Note: Must be overridden by derived classes that have options.

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

Definition at line 135 of file lsape_based_method.ipp.

◆ ged_run_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::ged_run_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		Result &	result
	)

finalprivatevirtual

Runs the method with options specified by set_options().

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[out]	result	Result variable.

Note: Must be overridden by derived classes.

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

Definition at line 127 of file lsape_based_method.ipp.

◆ ged_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::ged_set_default_options_ ( )

finalprivatevirtual

Sets all options to default values.

Note: Must be overridden by derived classes that have options.

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

Definition at line 273 of file lsape_based_method.ipp.

◆ ged_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::ged_valid_options_string_ ( ) const

finalprivatevirtual

Returns string of all valid options.

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

Note: Must be overridden by derived classes that have options.

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

Definition at line 263 of file lsape_based_method.ipp.

◆ lsape_default_post_graph_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_default_post_graph_init_ ( )

privatevirtual

Default initializes the method at runtime after initializing the global variables for the graphs.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that require default initialization at runtime after initializing the global variables for the graphs.

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, and ged::Ring< UserNodeLabel, UserEdgeLabel >.

Definition at line 415 of file lsape_based_method.ipp.

◆ lsape_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_init_ ( )

privatevirtual

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

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

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, ged::Walks< UserNodeLabel, UserEdgeLabel >, ged::Ring< UserNodeLabel, UserEdgeLabel >, and ged::Subgraph< UserNodeLabel, UserEdgeLabel >.

Definition at line 376 of file lsape_based_method.ipp.

◆ lsape_init_graph_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_init_graph_ ( const GEDGraph & graph )

privatevirtual

Initializes global variables for one graph.

Parameters

[in] graph Graph for which the global variables have to be initialized.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that require to initialize custom global variables.

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, ged::Walks< UserNodeLabel, UserEdgeLabel >, ged::Ring< UserNodeLabel, UserEdgeLabel >, ged::BranchUniform< UserNodeLabel, UserEdgeLabel >, ged::Star< UserNodeLabel, UserEdgeLabel >, ged::BranchFast< UserNodeLabel, UserEdgeLabel >, and ged::Subgraph< UserNodeLabel, UserEdgeLabel >.

Definition at line 405 of file lsape_based_method.ipp.

◆ lsape_lower_bound_scaling_factor_()

template<class UserNodeLabel , class UserEdgeLabel >

double ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_lower_bound_scaling_factor_	(	const GEDGraph &	g,
		const GEDGraph &	h
	)

privatevirtual

Returns scaling factor for lower bound.

Parameters

[in]	g	g Input graph.
[in]	h	h Input graph.

Returns: The factor by which the optimal LSAPE solution has to be scaled in order to arrive at a valid lower bound.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that require scaling of the optimal LSAPE solution for computing their lower bounds.

Reimplemented in ged::Star< UserNodeLabel, UserEdgeLabel >.

Definition at line 420 of file lsape_based_method.ipp.

◆ lsape_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

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

privatevirtual

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

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 of ged::LSAPEBasedMethod that have options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod.

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, ged::Walks< UserNodeLabel, UserEdgeLabel >, ged::Ring< UserNodeLabel, UserEdgeLabel >, ged::Subgraph< UserNodeLabel, UserEdgeLabel >, ged::BranchUniform< UserNodeLabel, UserEdgeLabel >, ged::Star< UserNodeLabel, UserEdgeLabel >, and ged::BranchFast< UserNodeLabel, UserEdgeLabel >.

Definition at line 381 of file lsape_based_method.ipp.

◆ lsape_populate_instance_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_populate_instance_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		DMatrix &	lsape_instance
	)

privatevirtual

Populates the LSAPE instance.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[out]	lsape_instance	LSAPE instance of size (n + 1) x (m + 1), where n and m are the number of nodes in `g` and `h`. The last row and the last column represent insertion and deletion.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod.

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, ged::Walks< UserNodeLabel, UserEdgeLabel >, ged::Ring< UserNodeLabel, UserEdgeLabel >, ged::Subgraph< UserNodeLabel, UserEdgeLabel >, ged::BranchUniform< UserNodeLabel, UserEdgeLabel >, ged::BranchFast< UserNodeLabel, UserEdgeLabel >, ged::Star< UserNodeLabel, UserEdgeLabel >, ged::Bipartite< UserNodeLabel, UserEdgeLabel >, ged::Branch< UserNodeLabel, UserEdgeLabel >, and ged::Node< UserNodeLabel, UserEdgeLabel >.

Definition at line 400 of file lsape_based_method.ipp.

◆ lsape_pre_graph_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_pre_graph_init_ ( bool called_at_runtime )

privatevirtual

Initializes the method at runtime or during initialization before initializing the global variables for the graphs.

Parameters

[in] called_at_runtime Equals true if called at runtime and false if called during initialization. Must be overridden by derived classes of ged::LSAPEBasedMethod that require default initialization at runtime before initializing the global variables for the graphs.

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, ged::Walks< UserNodeLabel, UserEdgeLabel >, ged::Ring< UserNodeLabel, UserEdgeLabel >, and ged::Subgraph< UserNodeLabel, UserEdgeLabel >.

Definition at line 410 of file lsape_based_method.ipp.

◆ lsape_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_set_default_options_ ( )

privatevirtual

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

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

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, ged::Walks< UserNodeLabel, UserEdgeLabel >, ged::Ring< UserNodeLabel, UserEdgeLabel >, ged::BranchUniform< UserNodeLabel, UserEdgeLabel >, ged::Star< UserNodeLabel, UserEdgeLabel >, ged::BranchFast< UserNodeLabel, UserEdgeLabel >, and ged::Subgraph< UserNodeLabel, UserEdgeLabel >.

Definition at line 395 of file lsape_based_method.ipp.

◆ lsape_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_valid_options_string_ ( ) const

privatevirtual

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

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

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

Reimplemented in ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >, ged::Walks< UserNodeLabel, UserEdgeLabel >, ged::Ring< UserNodeLabel, UserEdgeLabel >, ged::BranchUniform< UserNodeLabel, UserEdgeLabel >, ged::Star< UserNodeLabel, UserEdgeLabel >, ged::Subgraph< UserNodeLabel, UserEdgeLabel >, and ged::BranchFast< UserNodeLabel, UserEdgeLabel >.

Definition at line 388 of file lsape_based_method.ipp.

◆ populate_instance()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::populate_instance	(	const GEDGraph &	g,
		const GEDGraph &	h,
		DMatrix &	lsape_instance
	)

Populates the LSAPE instance.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[out]	lsape_instance	LSAPE instance.

Definition at line 56 of file lsape_based_method.ipp.

◆ populate_instance_and_run_as_util()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >::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.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[out]	result	Result variable.
[out]	lsape_instance	LSAPE instance.

Definition at line 71 of file lsape_based_method.ipp.

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

src/methods/lsape_based_method.hpp
src/methods/lsape_based_method.ipp

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ ~LSAPEBasedMethod()

◆ LSAPEBasedMethod()

Member Function Documentation

◆ ged_init_()

◆ ged_parse_option_()

◆ ged_run_()

◆ ged_set_default_options_()

◆ ged_valid_options_string_()

◆ lsape_default_post_graph_init_()

◆ lsape_init_()

◆ lsape_init_graph_()

◆ lsape_lower_bound_scaling_factor_()

◆ lsape_parse_option_()

◆ lsape_populate_instance_()

◆ lsape_pre_graph_init_()

◆ lsape_set_default_options_()

◆ lsape_valid_options_string_()

◆ populate_instance()

◆ populate_instance_and_run_as_util()

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