Abstract class for methods that use variants of local search for upper bounding the graph edit distance. More...

#include <ls_based_method.hpp>

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

[legend]

Public Member Functions
virtual	~LSBasedMethod ()=0
	Pure virtual destructor. More...

	LSBasedMethod (const GEDData< UserNodeLabel, UserEdgeLabel > &ged_data)
	Constructor. 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
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	ls_run_from_initial_solution_ (const GEDGraph &g, const GEDGraph &h, double lower_bound, const NodeMap &initial_node_map, NodeMap &output_node_map)
	Runs the local search from an initial node map. More...

virtual void	ls_init_ ()
	Initializes the method. More...

virtual void	ls_runtime_init_ (const GEDGraph &g, const GEDGraph &h)
	Initializes the method for a run between two graphs. More...

virtual bool	ls_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::LSBasedMethod. More...

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

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

Detailed Description

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

Abstract class for methods that use variants of local search for upper bounding the graph edit distance.

All derived methods support the following options:

`--<option> <arg>`	modified parameter	default	more information
`--initialization-method BIPARTITE_ML\|BIPARTITE\|BRANCH_FAST\|BRANCH_UNIFORM\|BRANCH\|NODE\|RING_ML\|RING\|SUBGRAPH\|WALKS\|RANDOM`	method for computing the initial solution	`RANDOM`	if `RANDOM`, the option `--initialization-options` has no effect
`--initialization-options '[–<option> <arg>] [...]'`	options string passed to the initialization method	`''`	ged::BipartiteML, ged::Bipartite, ged::BranchFast, ged::BranchUniform, ged::Branch, ged::Node ged::RingML, ged::Ring, ged::Subgraph, ged::Walks
`--lower-bound-method BRANCH\|BRANCH_FAST\|BRANCH_TIGHT\|NONE`	method for computing lower bound used as a termination criterion	`NONE`	if `NONE`, the lower bound computed by the initialization method is used
`--random-substitution-ratio <convertible to double between 0 and 1>`	ratio of node substitutions in randomly constructed initial solutions	`1`	n.a
`--initial-solutions <convertible to int greater 0>`	number of initial solutions	`1`	if greater `1` and if a non-random initialization method is chosen, those initial solution that cannot be computed non-randomly because the initialization method does not yield enough solutions are computed randomly
`--ratio-runs-from-initial-solutions <convertible to double greater 0 and smaller equal 1>`	determines number of runs from initial solutions	`1`	if set to `r` and `--initial-solutions` is set to `k`, all remaining initial solutions are discarded as soon as `r` * `k` runs have been completed
`--threads <convertible to int greater 0>`	number of threads	`1`	used for initializing the initialization method and for parallelly running local searches from several initial solutions
`--num-randpost-loops <convertible to int greater equal 0>`	number of loops of RANDPOST algorithm	`0`	https://doi.org/10.1007/978-3-319-97785-0_44
`--max-randpost-retrials <convertible to int greater equal 0>`	number of times the RANDPOST algorithm flattens the probability distribution if it encounters already converged solutions	`10`	https://doi.org/10.1007/978-3-319-97785-0_44
`--randpost-penalty <convertible to double between 0 and 1>`	if set value close to `1`, expensive solutions count less for constructing the counts matrix	`0`	n.a.
`--randpost-decay <convertible to double between 0 and 1>`	if set value close to `0`, previous iterations contribute less when constructing the counts matrix	`1`	n.a.
`--log <file name>`	name of log-file for RANDPOST	`""`	if not empty, a log-file for RANDPOST is created
`--randomness REAL\|PSEUDO`	use real randomness or pseudo randomness	`REAL`	n.a.

Definition at line 52 of file ls_based_method.hpp.

Constructor & Destructor Documentation

◆ ~LSBasedMethod()

template<class UserNodeLabel , class UserEdgeLabel >

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

pure virtual

Pure virtual destructor.

Note: Must be implemented by derived classes.

Definition at line 35 of file ls_based_method.ipp.

◆ LSBasedMethod()

template<class UserNodeLabel , class UserEdgeLabel >

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

Constructor.

Parameters

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

Definition at line 42 of file ls_based_method.ipp.

Member Function Documentation

◆ ged_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSBasedMethod< 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 63 of file ls_based_method.ipp.

◆ ged_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::LSBasedMethod< 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 157 of file ls_based_method.ipp.

◆ ged_run_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSBasedMethod< 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 76 of file ls_based_method.ipp.

◆ ged_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSBasedMethod< 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 382 of file ls_based_method.ipp.

◆ ged_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::LSBasedMethod< 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 372 of file ls_based_method.ipp.

◆ ls_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >::ls_init_ ( )

privatevirtual

Initializes the method.

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

Definition at line 619 of file ls_based_method.ipp.

◆ ls_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >::ls_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::LSBasedMethod.

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

Reimplemented in ged::IPFP< UserNodeLabel, UserEdgeLabel >, ged::BPBeam< UserNodeLabel, UserEdgeLabel >, and ged::Refine< UserNodeLabel, UserEdgeLabel >.

Definition at line 629 of file ls_based_method.ipp.

◆ ls_run_from_initial_solution_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >::ls_run_from_initial_solution_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		double	lower_bound,
		const NodeMap &	initial_node_map,
		NodeMap &	output_node_map
	)

privatevirtual

Runs the local search from an initial node map.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	lower_bound	A lower bound for GED which can be used as a termination criterion.
[in]	initial_node_map	Initial node map.
[out]	output_node_map	Node map constructed by local search.

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

Reimplemented in ged::IPFP< UserNodeLabel, UserEdgeLabel >, ged::BPBeam< UserNodeLabel, UserEdgeLabel >, and ged::Refine< UserNodeLabel, UserEdgeLabel >.

Definition at line 614 of file ls_based_method.ipp.

◆ ls_runtime_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >::ls_runtime_init_	(	const GEDGraph &	g,
		const GEDGraph &	h
	)

privatevirtual

Initializes the method for a run between two graphs.

Parameters

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

Note: Must be overridden by derived classes of ged::LSBasedMethod that require initialization at runtime.

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

Definition at line 624 of file ls_based_method.ipp.

◆ ls_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >::ls_set_default_options_ ( )

privatevirtual

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

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

Reimplemented in ged::IPFP< UserNodeLabel, UserEdgeLabel >, ged::BPBeam< UserNodeLabel, UserEdgeLabel >, and ged::Refine< UserNodeLabel, UserEdgeLabel >.

Definition at line 643 of file ls_based_method.ipp.

◆ ls_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >::ls_valid_options_string_ ( ) const

privatevirtual

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

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

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

Reimplemented in ged::IPFP< UserNodeLabel, UserEdgeLabel >, ged::BPBeam< UserNodeLabel, UserEdgeLabel >, and ged::Refine< UserNodeLabel, UserEdgeLabel >.

Definition at line 636 of file ls_based_method.ipp.

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

src/methods/ls_based_method.hpp
src/methods/ls_based_method.ipp

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ ~LSBasedMethod()

◆ LSBasedMethod()

Member Function Documentation

◆ ged_init_()

◆ ged_parse_option_()

◆ ged_run_()

◆ ged_set_default_options_()

◆ ged_valid_options_string_()

◆ ls_init_()

◆ ls_parse_option_()

◆ ls_run_from_initial_solution_()

◆ ls_runtime_init_()

◆ ls_set_default_options_()

◆ ls_valid_options_string_()

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