Computes lower and upper bounds for general edit costs. More...

#include <bipartite.hpp>

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

Private Member Functions
virtual void	lsape_populate_instance_ (const GEDGraph &g, const GEDGraph &h, DMatrix &lsape_instance) final
	Populates the LSAPE instance. More...

Additional Inherited Members
Public Member Functions inherited from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >
virtual	~LSAPEBasedMethod ()=0
	Pure virtual destructor. More...

	LSAPEBasedMethod (const GEDData< UserNodeLabel, UserEdgeLabel > &ged_data)
	Constructor. More...

void	populate_instance_and_run_as_util (const GEDGraph &g, const GEDGraph &h, Result &result, DMatrix &lsape_instance)
	Runs the method with options specified by set_options() and provides access to constructed LSAPE instance. More...

void	populate_instance (const GEDGraph &g, const GEDGraph &h, DMatrix &lsape_instance)
	Populates the LSAPE instance. 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::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >
LSAPESolver::Model	lsape_model_
	Specifies model for optimal LSAPE solver.

LSAPESolver::GreedyMethod	greedy_method_
	Specifies method for greedy LSAPE solver.

bool	compute_lower_bound_
	Flag that should be set to `true` if and only if the method computes a lower bound.

bool	solve_optimally_
	Flag that equals `true` if an optimal LSAPE solver is used and `false` if a greedy method is employed.

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

Computes lower and upper bounds for general edit costs.

Implements the method Bipartite suggested in:

K. Riesen and H. Bunke: “Approximate graph edit distance computation by means of bipartite graph matching”, https://doi.org/10.1016/j.imavis.2008.04.004

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

Definition at line 42 of file bipartite.hpp.

Member Function Documentation

◆ lsape_populate_instance_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::Bipartite< UserNodeLabel, UserEdgeLabel >::lsape_populate_instance_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		DMatrix &	lsape_instance
	)

finalprivatevirtual

Populates the LSAPE instance.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[out]	lsape_instance	LSAPE instance of size (n + 1) x (m + 1), where n and m are the number of nodes in `g` and `h`. The last row and the last column represent insertion and deletion.

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

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 47 of file bipartite.ipp.

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

src/methods/bipartite.hpp
src/methods/bipartite.ipp

Private Member Functions

Additional Inherited Members

Detailed Description

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

Member Function Documentation

◆ lsape_populate_instance_()

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