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

Computes the exact graph edit distance for general edit costs. More...

#include <anchor_aware_ged.hpp>

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

Private Member Functions
virtual void	ged_run_ (const GEDGraph &g, const GEDGraph &h, Result &result) final
	Runs the method with options specified by set_options(). More...
virtual void	ged_set_default_options_ () final
	Sets all options to default values. More...
virtual std::string	ged_valid_options_string_ () const final
	Returns string of all valid options. More...
virtual bool	ged_parse_option_ (const std::string &option, const std::string &arg) final
	Parses one option. More...
virtual void	ged_init_ () final
	Initializes the method. More...

Additional Inherited Members
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::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::AnchorAwareGED< UserNodeLabel, UserEdgeLabel >

Computes the exact graph edit distance for general edit costs.

Implements the following exact algorithm suggested and extends it to non-uniform edit costs:

• L. Chang, X. Feng, X. Lin, L. Qin, and W. Zhang: “Efficient graph edit distance computation and verification via anchor-aware lower bound estimation”, https://arxiv.org/abs/1709.06810

Supports the following options:

--<option> <arg>	modified parameter	default	more information
--threads <convertible to int greater 0>	number of threads	1	n.a.
--lsape-model ECBP|EBP|FLWC|FLCC|FBP|SFBP|FBP0	model for optimally solving LSAPE	ECBP	ged::LSAPESolver::Model
--time-limit <convertible to double>	time limit in seconds	0	if less or equal 0, no time limit is enforced
--search-method DFS|ASTAR	method for traversing the search tree	DFS	https://arxiv.org/abs/1709.06810 if DFS, the method computes an upper bound even if the time limit is reached
--lower-bound-method BRANCH|BRANCH_FAST	method for computing lower bound for incomplete node map	BRANCH_FAST	https://arxiv.org/abs/1709.06810
--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

Definition at line 50 of file anchor_aware_ged.hpp.

Member Function Documentation

ged_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::AnchorAwareGED< 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 anchor_aware_ged.ipp.

ged_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::AnchorAwareGED< 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 141 of file anchor_aware_ged.ipp.

ged_run_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::AnchorAwareGED< 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 63 of file anchor_aware_ged.ipp.

ged_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::AnchorAwareGED< 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 122 of file anchor_aware_ged.ipp.

ged_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::AnchorAwareGED< 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 134 of file anchor_aware_ged.ipp.

---

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

• src/methods/anchor_aware_ged.hpp
• src/methods/anchor_aware_ged.ipp