ged::CompactMIP< UserNodeLabel, UserEdgeLabel > Class Template Reference

Mixed integer linear programming formulation of the graph edit distance. More...

#include <compact_mip.hpp>

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

Private Member Functions
virtual void	mip_populate_model_ (const GEDGraph &g, const GEDGraph &h, GRBModel &model) final
	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) final
	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) final
	Given a, possibly sub-optimally, solved model, this method constructs an LSAPE instance for projecting a continuous solution to a node map. More...

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

Detailed Description

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

Mixed integer linear programming formulation of the graph edit distance.

Implements the compact MIP formulation suggested in:

• D. B. Blumenthal and J. Gamper: “On the exact computation of the graph edit distance”, https://doi.org/10.1016/j.patrec.2018.05.002

Does not support any options except for the ones supported by ged::MIPBasedMethod.

Definition at line 43 of file compact_mip.hpp.

Member Function Documentation

mip_model_to_lsape_projection_problem_()

template<class UserNodeLabel , class UserEdgeLabel >

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

finalprivatevirtual

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

Definition at line 230 of file compact_mip.ipp.

mip_model_to_node_map_()

template<class UserNodeLabel , class UserEdgeLabel >

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

finalprivatevirtual

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

Definition at line 211 of file compact_mip.ipp.

mip_populate_model_()

template<class UserNodeLabel , class UserEdgeLabel >

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

finalprivatevirtual

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

Definition at line 47 of file compact_mip.ipp.

---

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

• src/methods/compact_mip.hpp
• src/methods/compact_mip.ipp