Abstract class for methods that use mixed integer linear programming for exactly or approximatively computing the graph edit distance. More...

#include <mip_based_method.hpp>

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

[legend]

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

	MIPBasedMethod (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
bool	relax_
	If `true`, the model populated by mip_populate_model_() must be continuous.

bool	map_root_to_root_
	If `true`, the model populated by mip_populate_model_() must enforce that the nodes with ID 0 are mapped to each other.

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	mip_populate_model_ (const GEDGraph &g, const GEDGraph &h, GRBModel &model)
	Runs the local search from an initial node map. More...

virtual void	mip_model_to_node_map_ (const GEDGraph &g, const GEDGraph &h, GRBModel &model, NodeMap &node_map)
	Given a, possibly sub-optimally, solved unrelaxed model, this method constructs a node map and sets its induced cost. More...

virtual bool	mip_model_to_lsape_projection_problem_ (const GEDGraph &g, const GEDGraph &h, GRBModel &model, DMatrix &lsape_instance)
	Given a, possibly sub-optimally, solved model, this method constructs an LSAPE instance for projecting a continuous solution to a node map. More...

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

virtual bool	mip_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::MIPBasedMethod. More...

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

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

Detailed Description

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

Abstract class for methods that use mixed integer linear programming for exactly or approximatively computing the graph edit distance.

All derived methods support the following options:

`--<option> <arg>`	modified parameter	default	more information
`--threads <convertible to int greater 0>`	number of threads	`1`	number of threads to be used by MIP/LP solver
`--time-limit <convertible to double>`	time limit in seconds	`0`	if less or equal `0`, no time limit is enforced
`--relax TRUE\|FALSE`	if `TRUE`, all integrality constraints are relaxed	`FALSE`	if `TRUE`, the model populated by mip_populate_model_() must be continuous
`--project-to-node-map TRUE\|FALSE`	if `TRUE`, continuous solutions of relaxed models are projected to node maps	`TRUE`	mip_model_to_lsape_projection_problem_()
`--tune TRUE\|FALSE`	if `TRUE`, the parameters of the model are tuned before optimization	`FALSE`	Gurobi Manual
`--tune-time-limit <convertible to double>`	time limit for parameter tuning in seconds	`0`	if less or equal `0`, the time limit is set automatically
`--map-root-to-root TRUE\|FALSE`	decide if the roots of the input graphs are mapped to each other	`FALSE`	if `TRUE`, the nodes with ID 0 of the input graphs are mapped to each other
`--lsape-model ECBP\|EBP\|FLWC\|FLCC\|FBP\|SFBP\|FBP0`	model for optimally solving LSAPE	`ECBP`	ged::LSAPESolver::Model

Definition at line 48 of file mip_based_method.hpp.

Constructor & Destructor Documentation

◆ ~MIPBasedMethod()

template<class UserNodeLabel , class UserEdgeLabel >

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

pure virtual

Pure virtual destructor.

Note: Must be implemented by derived classes.

Definition at line 35 of file mip_based_method.ipp.

◆ MIPBasedMethod()

template<class UserNodeLabel , class UserEdgeLabel >

ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::MIPBasedMethod ( 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 mip_based_method.ipp.

Member Function Documentation

◆ ged_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MIPBasedMethod< 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 54 of file mip_based_method.ipp.

◆ ged_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::MIPBasedMethod< 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 136 of file mip_based_method.ipp.

◆ ged_run_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MIPBasedMethod< 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 61 of file mip_based_method.ipp.

◆ ged_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MIPBasedMethod< 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 245 of file mip_based_method.ipp.

◆ ged_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::MIPBasedMethod< 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 235 of file mip_based_method.ipp.

◆ mip_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::mip_init_ ( )

privatevirtual

Initializes the method.

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

Definition at line 279 of file mip_based_method.ipp.

◆ mip_model_to_lsape_projection_problem_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::mip_model_to_lsape_projection_problem_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		GRBModel &	model,
		DMatrix &	lsape_instance
	)

privatevirtual

Given a, possibly sub-optimally, solved model, this method constructs an LSAPE instance for projecting a continuous solution to a node map.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	model	Possibly sub-optimally solved model.
[in,out]	lsape_instance	The LSAPE instance to be constructed. Initialized as matrix of ones.

Returns: Boolean false by default. Derived classes that override this method must return true.

Note: Must be overridden by derived classes of ged::MIPBasedMethod that want to provide upper bounds when called with the option –relax TRUE. The LSAPE instance lsape_instance should be constructed such that, when constructed for an unrelaxed model, the unique optimal solution for lsape_instance corresponds to the node map constructed by mip_model_to_node_map_().

Reimplemented in ged::F1< UserNodeLabel, UserEdgeLabel >, ged::BLPNoEdgeLabels< UserNodeLabel, UserEdgeLabel >, ged::CompactMIP< UserNodeLabel, UserEdgeLabel >, and ged::F2< UserNodeLabel, UserEdgeLabel >.

Definition at line 272 of file mip_based_method.ipp.

◆ mip_model_to_node_map_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::mip_model_to_node_map_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		GRBModel &	model,
		NodeMap &	node_map
	)

privatevirtual

Given a, possibly sub-optimally, solved unrelaxed model, this method constructs a node map and sets its induced cost.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	model	Possibly sub-optimally solved unrelaxed model.
[out]	node_map	Node map which has to be constructed and whose induced cost has to be set.

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

Reimplemented in ged::F1< UserNodeLabel, UserEdgeLabel >, ged::BLPNoEdgeLabels< UserNodeLabel, UserEdgeLabel >, ged::CompactMIP< UserNodeLabel, UserEdgeLabel >, and ged::F2< UserNodeLabel, UserEdgeLabel >.

Definition at line 267 of file mip_based_method.ipp.

◆ mip_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::mip_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::MIPBasedMethod.

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

Definition at line 284 of file mip_based_method.ipp.

◆ mip_populate_model_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::mip_populate_model_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		GRBModel &	model
	)

privatevirtual

Runs the local search from an initial node map.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[out]	model	The mixed integer linear programming model. Must be continuous if `relax_` equals `true`.

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

Reimplemented in ged::F1< UserNodeLabel, UserEdgeLabel >, ged::BLPNoEdgeLabels< UserNodeLabel, UserEdgeLabel >, ged::CompactMIP< UserNodeLabel, UserEdgeLabel >, and ged::F2< UserNodeLabel, UserEdgeLabel >.

Definition at line 262 of file mip_based_method.ipp.

◆ mip_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::mip_set_default_options_ ( )

privatevirtual

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

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

Definition at line 298 of file mip_based_method.ipp.

◆ mip_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::MIPBasedMethod< UserNodeLabel, UserEdgeLabel >::mip_valid_options_string_ ( ) const

privatevirtual

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

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

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

Definition at line 291 of file mip_based_method.ipp.

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

src/methods/mip_based_method.hpp
src/methods/mip_based_method.ipp

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ ~MIPBasedMethod()

◆ MIPBasedMethod()

Member Function Documentation

◆ ged_init_()

◆ ged_parse_option_()

◆ ged_run_()

◆ ged_set_default_options_()

◆ ged_valid_options_string_()

◆ mip_init_()

◆ mip_model_to_lsape_projection_problem_()

◆ mip_model_to_node_map_()

◆ mip_parse_option_()

◆ mip_populate_model_()

◆ mip_set_default_options_()

◆ mip_valid_options_string_()

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