Computes an upper bound for general edit costs. More...

#include <ipfp.hpp>

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

Private Member Functions
void	ls_run_from_initial_solution_ (const GEDGraph &g, const GEDGraph &h, double lower_bound, const NodeMap &initial_node_map, NodeMap &output_node_map) final
	Runs the local search from an initial node map. More...

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

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

virtual bool	ls_parse_option_ (const std::string &options, const std::string &arg) final
	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 final
	Returns string of all valid options that are not among the ones shared by all derived classes of ged::LSBasedMethod. More...

Additional Inherited Members
Public Member Functions inherited from ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >
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 inherited from ged::LSBasedMethod< UserNodeLabel, UserEdgeLabel >
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::IPFP< UserNodeLabel, UserEdgeLabel >

Computes an upper bound for general edit costs.

Implements the method IPFP (Frank-Wolfe for QAP and GED) suggested in:

S. Bougleux, L. Brun, V. Carletti, P. Foggia, B. Gaüzère, and M. Vento: “Graph edit distance as a quadratic assignment problem” https://doi.org/10.1016/j.patrec.2016.10.001,

the reduction QAPE suggested in:

S. Bougleux, B. Gaüzère, and L. Brun: “Graph edit distance as a quadratic program” https://doi.org/10.1109/ICPR.2016.7899881,

the extension m-IPFP suggested in:

É. Daller, S. Bougleux, B. Gaüzère, and L. Brun: “Approximate graph edit distance by several local searches in parallel”, https://doi.org/10.5220/0006599901490158,

and the extension C-QAP suggested in:

D. B. Blumenthal, É. Daller, S. Bougleux, and L. Brun: “Quasimetric graph edit distance as a compact quadratic assignment problem”, accepted for publication at ICPR 2018

Supports the following options:

`--<option> <arg>`	modified parameter	default	more information
`--iterations <convertible to int greater equal 0>`	maximal number of iterations	`100`	if `0`, no iteration based termination criterion is used
`--time-limit <convertible to double>`	time limit in seconds	`0`	if less or equal `0`, no time limit is enforced
`--epsilon <convertible to double>`	convergence threshold	`0.001`	if less or equal `0`, no convergence based termination criterion is used
`--lsape-model ECBP\|EBP\|FLWC\|FLCC\|FBP\|SFBP\|FBP0`	model for optimally solving LSAPE	`ECBP`	ged::LSAPESolver::Model
`--quadratic-model QAPE\|B-QAP\|C-QAP`	quadratic assignment model	`QAPE`	ICPR paper

Definition at line 64 of file ipfp.hpp.

Member Function Documentation

◆ ls_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

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

Definition at line 196 of file ipfp.ipp.

◆ ls_run_from_initial_solution_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::IPFP< 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
	)

finalprivatevirtual

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

Definition at line 53 of file ipfp.ipp.

◆ ls_runtime_init_()

template<class UserNodeLabel , class UserEdgeLabel >

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

finalprivatevirtual

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

Definition at line 170 of file ipfp.ipp.

◆ ls_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

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

finalprivatevirtual

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

Definition at line 178 of file ipfp.ipp.

◆ ls_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

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

finalprivatevirtual

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

Definition at line 189 of file ipfp.ipp.

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

src/methods/ipfp.hpp
src/methods/ipfp.ipp

Private Member Functions

Additional Inherited Members

Detailed Description

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

Member Function Documentation

◆ 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::IPFP< UserNodeLabel, UserEdgeLabel >