ged::LSAPSolver Class Reference

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

#include <lsap_solver.hpp>

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

Public Member Functions
	LSAPSolver (const DMatrix *cost_matrix)
	Constructs solver for LSAP problem instance. More...
	LSAPSolver ()
	Constructs empty solver.
void	solve (int num_solutions=1)
	Solves the LSAP problem instance. More...
void	set_problem (const DMatrix *cost_matrix)
	Sets the LSAP problem instance. More...
void	set_greedy_method (const GreedyMethod &greedy_method)
	Makes the solver use a greedy method. More...
void	set_hungarian_algorithm ()
	Makes the solver use the Hungarian algorithm for optimal solving.
void	clear_solution ()
	Clears a previously computed solution.
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 LSAP problem instance. More...
std::size_t	num_rows () const
	Returns the number of rows of the LSAP problem instance. More...
std::size_t	num_cols () const
	Returns the number of columns of the LSAP 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_solutions () const
	Returns the number of solutions. More...

Detailed Description

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

Definition at line 39 of file lsap_solver.hpp.

Member Enumeration Documentation

GreedyMethod

enum ged::LSAPSolver::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 50 of file lsap_solver.hpp.

Constructor & Destructor Documentation

LSAPSolver()

ged::LSAPSolver::LSAPSolver

(

const DMatrix *

cost_matrix

)

Constructs solver for LSAP problem instance.

Parameters

[in]

cost_matrix

Pointer to the LSAP problem instance that should be solved.

Definition at line 33 of file lsap_solver.ipp.

Member Function Documentation

col_to_row_assignment()

const std::vector< std::size_t > & ged::LSAPSolver::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 155 of file lsap_solver.ipp.

cost_matrix()

const DMatrix * ged::LSAPSolver::cost_matrix

(

)

const

Returns the LSAP problem instance.

Returns

Constant pointer to the LSAP problem instance.

Definition at line 161 of file lsap_solver.ipp.

get_assigned_col()

std::size_t ged::LSAPSolver::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 119 of file lsap_solver.ipp.

get_assigned_row()

std::size_t ged::LSAPSolver::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 125 of file lsap_solver.ipp.

get_dual_var_col()

double ged::LSAPSolver::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 143 of file lsap_solver.ipp.

get_dual_var_row()

double ged::LSAPSolver::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 137 of file lsap_solver.ipp.

get_slack()

double ged::LSAPSolver::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 131 of file lsap_solver.ipp.

minimal_cost()

double ged::LSAPSolver::minimal_cost

(

)

const

Returns the cost of the computed solutions.

Returns

Cost of computed solutions.

Definition at line 113 of file lsap_solver.ipp.

num_cols()

std::size_t ged::LSAPSolver::num_cols

(

)

const

Returns the number of columns of the LSAP problem instance.

Returns

Number of columns of the LSAP problem instance.

Definition at line 173 of file lsap_solver.ipp.

num_rows()

std::size_t ged::LSAPSolver::num_rows

(

)

const

Returns the number of rows of the LSAP problem instance.

Returns

Number of rows of the LSAP problem instance.

Definition at line 167 of file lsap_solver.ipp.

num_solutions()

std::size_t ged::LSAPSolver::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 179 of file lsap_solver.ipp.

row_to_col_assignment()

const std::vector< std::size_t > & ged::LSAPSolver::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 149 of file lsap_solver.ipp.

set_greedy_method()

void ged::LSAPSolver::set_greedy_method

(

const GreedyMethod &

greedy_method

)

Makes the solver use a greedy method.

Parameters

[in]

greedy_method

The greedy method that should be sued.

Definition at line 63 of file lsap_solver.ipp.

set_problem()

void ged::LSAPSolver::set_problem

(

const DMatrix *

cost_matrix

)

Sets the LSAP problem instance.

Parameters

[in]

cost_matrix

Pointer to the LSAP problem instance that should be solved.

Definition at line 56 of file lsap_solver.ipp.

solve()

void ged::LSAPSolver::solve

(

int

num_solutions = 1

)

Solves the LSAP problem instance.

Parameters

[in]

num_solutions

The maximal number of solutions that should be computed.

Definition at line 88 of file lsap_solver.ipp.

---

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

• src/util/lsap_solver.hpp
• src/util/lsap_solver.ipp