GEDLIB  1.0
Private Member Functions | List of all members
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 >:
Inheritance graph
[legend]

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 NodeMapget_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:

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]gInput graph.
[in]hInput graph.
[in]modelPossibly sub-optimally solved model.
[in,out]lsape_instanceThe 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]gInput graph.
[in]hInput graph.
[in]modelPossibly sub-optimally solved unrelaxed model.
[out]node_mapNode 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]gInput graph.
[in]hInput graph.
[out]modelThe 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: