Uses LSAPE instances to approximate GED via simulated annealing. More...

#include <simulated_annealing.hpp>

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

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...

Additional Inherited Members
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::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::SimulatedAnnealing< UserNodeLabel, UserEdgeLabel >

Uses LSAPE instances to approximate GED via simulated annealing.

Implements the simulated annealing method suggested in:

K. Riesen, A. Fischer, H. Bunke: “Improved graph edit distance approximation with simulated annealing”, https:://doi.org/10.1007/978-3-319-58961-9_20,

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

D. B. Blumenthal, S. Bougleux, J. Gamper, L. Brun: “Designing heuristics for graph edit distance.”, To be submitted to PR.

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

`--<option> <arg>`	modified parameter	default	more information
`--threads <convertible to int greater 0>`	number of threads	1	used for populating the LSAPE instance and computing the lower bound
`--iterations <convertible to int greater 0>`	number of iterations	1000	https:://doi.org/10.1007/978-3-319-58961-9_20
`--start-probability <convertible to double between 0 and 1>`	probability of accepting deterioration at start of simulated annealing	0.8	https:://doi.org/10.1007/978-3-319-58961-9_20
`--end-probability <convertible to double between 0 and 1>`	probability of accepting deterioration at end of simulated annealing	0.01	https:://doi.org/10.1007/978-3-319-58961-9_20
`--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 method for populating the LSAPE instance is used
`--lsape-method BIPARTITE\|BRANCH_FAST\|BRANCH_UNIFORM\|BRANCH\|NODE\|RING\|SUBGRAPH\|WALKS\|BIPARTITE_ML\|RING_ML`	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 56 of file simulated_annealing.hpp.

Member Function Documentation

◆ ged_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::SimulatedAnnealing< 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 132 of file simulated_annealing.ipp.

◆ ged_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::SimulatedAnnealing< 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 167 of file simulated_annealing.ipp.

◆ ged_run_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::SimulatedAnnealing< 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 59 of file simulated_annealing.ipp.

◆ ged_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::SimulatedAnnealing< 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 142 of file simulated_annealing.ipp.

◆ ged_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::SimulatedAnnealing< 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 160 of file simulated_annealing.ipp.

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

src/methods/simulated_annealing.hpp
src/methods/simulated_annealing.ipp

Private Member Functions

Additional Inherited Members

Detailed Description

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

Member Function Documentation

◆ ged_init_()

◆ ged_parse_option_()

◆ ged_run_()

◆ ged_set_default_options_()

◆ ged_valid_options_string_()

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