This class solves LSAPE instances by calling the library lsape available at https://bougleux.users.greyc.fr/lsape/. More...

#include <lsape_solver.hpp>

Public Types
enum	Model { ECBP =0, FLWC =1, EBP =2, FLCC =3, FBP =4, FBP0 =5, SFBP =6 }
	Selects a model for solving LSAPE with the Hungarian algorithm. More...

enum	GreedyMethod { BASIC =0, REFINED =1, LOSS =2, BASIC_SORT =3, INT_BASIC_SORT =4 }
	Selects a greedy method. More...

Public Member Functions
	LSAPESolver (const DMatrix *cost_matrix)
	Constructs solver for LSAPE problem instance. More...

	LSAPESolver ()
	Constructs empty solver.

void	set_problem (const DMatrix *cost_matrix)
	Sets the LSAPE problem instance. More...

void	clear_solution ()
	Clears a previously computed solution.

void	set_model (const Model &model)
	Makes the solver use a specific model for optimal solving. More...

void	set_greedy_method (const GreedyMethod &greedy_method)
	Makes the solver use a greedy method. More...

void	solve (int num_solutions=1)
	Solves the LSAPE problem instance. More...

double	minimal_cost () const
	Returns the cost of the computed solutions. More...

std::size_t	get_assigned_col (std::size_t row, std::size_t solution_id=0) const
	Returns the assigned column. More...

std::size_t	get_assigned_row (std::size_t col, std::size_t solution_id=0) const
	Returns the assigned row. More...

double	get_slack (std::size_t row, std::size_t col) const
	Returns the slack of a cell. More...

double	get_dual_var_row (std::size_t row) const
	Returns the dual variable of a row. More...

double	get_dual_var_col (std::size_t col) const
	Returns the dual variable of a column. More...

const DMatrix *	cost_matrix () const
	Returns the LSAPE problem instance. More...

const std::vector< std::size_t > &	row_to_col_assignment (std::size_t solution_id=0) const
	Returns the assignment from rows to columns. More...

const std::vector< std::size_t > &	col_to_row_assignment (std::size_t solution_id=0) const
	Returns the assignment from columns to rows. More...

std::size_t	num_rows () const
	Returns the number of real rows of the LSAPE problem instance, i.e, the number of rows of the internal cost matrix minus 1. More...

std::size_t	num_cols () const
	Returns the number of real columns of the LSAPE problem instance, i.e, the number of columns of the internal cost matrix minus 1. More...

std::size_t	total_num_rows () const
	Returns the total number of rows of the LSAPE problem instance. More...

std::size_t	total_num_cols () const
	Returns the total number of columns of the LSAPE problem instance. More...

std::size_t	num_solutions () const
	Returns the number of solutions. More...

Detailed Description

This class solves LSAPE instances by calling the library lsape available at https://bougleux.users.greyc.fr/lsape/.

Definition at line 38 of file lsape_solver.hpp.

Member Enumeration Documentation

◆ GreedyMethod

enum ged::LSAPESolver::GreedyMethod

Selects a greedy method.

The different greedy methods are described in:

K. Riesen, M. Ferrer, A. Fischer, and H. Bunke: “Approximation of graph edit distance in quadratic time”, https://doi.org/10.1007/978-3-319-18224-7_1

Enumerator
BASIC	See https://doi.org/10.1007/978-3-319-18224-7_1.
REFINED	See https://doi.org/10.1007/978-3-319-18224-7_1.
LOSS	See https://doi.org/10.1007/978-3-319-18224-7_1.
BASIC_SORT	See https://doi.org/10.1007/978-3-319-18224-7_1.
INT_BASIC_SORT	See https://doi.org/10.1007/978-3-319-18224-7_1.

Definition at line 66 of file lsape_solver.hpp.

◆ Model

enum ged::LSAPESolver::Model

Selects a model for solving LSAPE with the Hungarian algorithm.

The different models are described in:

S. Bougleux, B. Gaüzère, D. B. Blumenthal, and L. Brun: “Fast linear sum assignment with error-correction and no cost constraints”, https://doi.org/10.1016/j.patrec.2018.03.032

Enumerator
ECBP	Adaption of Hungarian Algorithm to LSAPE.
FLWC	Reduction to compact LSAP instance without cost constraints.
EBP	Reduction to extended LSAP instance without cost constraints.
FLCC	Reduction to compact LSAP instance for quasimetric costs.
FBP	Reduction to compact LSAP instance for quasimetric costs.
FBP0	Reduction to compact LSAP instance for quasimetric costs.
SFBP	Reduction to compact LSAP instance for quasimetric costs.

Definition at line 49 of file lsape_solver.hpp.

Constructor & Destructor Documentation

◆ LSAPESolver()

ged::LSAPESolver::LSAPESolver ( const DMatrix * cost_matrix )

Constructs solver for LSAPE problem instance.

Parameters

[in] cost_matrix Pointer to the LSAPE problem instance that should be solved.

Definition at line 33 of file lsape_solver.ipp.

Member Function Documentation

◆ col_to_row_assignment()

const std::vector< std::size_t > & ged::LSAPESolver::col_to_row_assignment ( std::size_t solution_id = 0 ) const

Returns the assignment from columns to rows.

Parameters

[in] solution_id The ID of the solutions whose assignment should be returned.

Returns: Constant reference of assignment of columns to rows in the solution with ID solution_id.

Definition at line 141 of file lsape_solver.ipp.

◆ cost_matrix()

const DMatrix * ged::LSAPESolver::cost_matrix ( ) const

Returns the LSAPE problem instance.

Returns: Constant pointer to the LSAPE problem instance.

Definition at line 165 of file lsape_solver.ipp.

◆ get_assigned_col()

std::size_t ged::LSAPESolver::get_assigned_col	(	std::size_t	row,
		std::size_t	solution_id = `0`
	)		const

Returns the assigned column.

Parameters

[in]	row	Row whose assigned column should be returned.
[in]	solution_id	ID of the solution where the assignment should be looked up.

Returns: Column to which row is assigned to in solution with ID solution_id or ged::undefined() if row is not assigned to any column.

Definition at line 123 of file lsape_solver.ipp.

◆ get_assigned_row()

std::size_t ged::LSAPESolver::get_assigned_row	(	std::size_t	col,
		std::size_t	solution_id = `0`
	)		const

Returns the assigned row.

Parameters

[in]	col	Column whose assigned row should be returned.
[in]	solution_id	ID of the solution where the assignment should be looked up.

Returns: Row to which col is assigned to in solution with ID solution_id or ged::undefined() if col is not assigned to any row.

Definition at line 129 of file lsape_solver.ipp.

◆ get_dual_var_col()

double ged::LSAPESolver::get_dual_var_col ( std::size_t col ) const

Returns the dual variable of a column.

Parameters

[in] col The column.

Returns: Dual variable of the column col.

Definition at line 159 of file lsape_solver.ipp.

◆ get_dual_var_row()

double ged::LSAPESolver::get_dual_var_row ( std::size_t row ) const

Returns the dual variable of a row.

Parameters

[in] row The row.

Returns: Dual variable of the row row.

Definition at line 153 of file lsape_solver.ipp.

◆ get_slack()

double ged::LSAPESolver::get_slack	(	std::size_t	row,
		std::size_t	col
	)		const

Returns the slack of a cell.

Parameters

[in]	row	Row of the cell.
[in]	col	Column of the cell.

Returns: Slack of the cell (row, col).

Definition at line 147 of file lsape_solver.ipp.

◆ minimal_cost()

double ged::LSAPESolver::minimal_cost ( ) const

Returns the cost of the computed solutions.

Returns: Cost of computed solutions.

Definition at line 117 of file lsape_solver.ipp.

◆ num_cols()

std::size_t ged::LSAPESolver::num_cols ( ) const

Returns the number of real columns of the LSAPE problem instance, i.e, the number of columns of the internal cost matrix minus 1.

Returns: Number of real columns of the LSAPE problem instance.

Definition at line 177 of file lsape_solver.ipp.

◆ num_rows()

std::size_t ged::LSAPESolver::num_rows ( ) const

Returns the number of real rows of the LSAPE problem instance, i.e, the number of rows of the internal cost matrix minus 1.

Returns: Number of real rows of the LSAPE problem instance.

Definition at line 171 of file lsape_solver.ipp.

◆ num_solutions()

std::size_t ged::LSAPESolver::num_solutions ( ) const

Returns the number of solutions.

Returns: Actual number of solutions computed by solve(). Might be smaller than num_solutions.

Definition at line 195 of file lsape_solver.ipp.

◆ row_to_col_assignment()

const std::vector< std::size_t > & ged::LSAPESolver::row_to_col_assignment ( std::size_t solution_id = 0 ) const

Returns the assignment from rows to columns.

Parameters

[in] solution_id The ID of the solutions whose assignment should be returned.

Returns: Constant reference of assignment of rows to columns in the solution with ID solution_id.

Definition at line 135 of file lsape_solver.ipp.

◆ set_greedy_method()

void ged::LSAPESolver::set_greedy_method ( const GreedyMethod & greedy_method )

Makes the solver use a greedy method.

Parameters

[in] greedy_method The greedy method that should be used.

Definition at line 81 of file lsape_solver.ipp.

◆ set_model()

void ged::LSAPESolver::set_model ( const Model & model )

Makes the solver use a specific model for optimal solving.

Parameters

[in] model The model that should be used.

Definition at line 74 of file lsape_solver.ipp.

◆ set_problem()

void ged::LSAPESolver::set_problem ( const DMatrix * cost_matrix )

Sets the LSAPE problem instance.

Parameters

[in] cost_matrix Pointer to the LSAPE problem instance that should be solved.

Definition at line 56 of file lsape_solver.ipp.

◆ solve()

void ged::LSAPESolver::solve ( int num_solutions = 1 )

Solves the LSAPE problem instance.

Parameters

[in] num_solutions The maximal number of solutions that should be computed.

Definition at line 88 of file lsape_solver.ipp.

◆ total_num_cols()

std::size_t ged::LSAPESolver::total_num_cols ( ) const

Returns the total number of columns of the LSAPE problem instance.

Returns: Total number of columns of the LSAPE problem instance.

Definition at line 189 of file lsape_solver.ipp.

◆ total_num_rows()

std::size_t ged::LSAPESolver::total_num_rows ( ) const

Returns the total number of rows of the LSAPE problem instance.

Returns: Total number of rows of the LSAPE problem instance.

Definition at line 183 of file lsape_solver.ipp.

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

src/util/lsape_solver.hpp
src/util/lsape_solver.ipp

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ GreedyMethod

◆ Model

Constructor & Destructor Documentation

◆ LSAPESolver()

Member Function Documentation

◆ col_to_row_assignment()

◆ cost_matrix()

◆ get_assigned_col()

◆ get_assigned_row()

◆ get_dual_var_col()

◆ get_dual_var_row()

◆ get_slack()

◆ minimal_cost()

◆ num_cols()

◆ num_rows()

◆ num_solutions()

◆ row_to_col_assignment()

◆ set_greedy_method()

◆ set_model()

◆ set_problem()

◆ solve()

◆ total_num_cols()

◆ total_num_rows()