Solver-class {SpatialKWD} | R Documentation |
Spatial-KWD Solver
Description
The Solver
class is the main wrapper to the core algorithms implemented in the Spatial KWD package.
It has several methods that permit to compare two, or more, objects of type Histogram2D
.
If you use the helper functions described at the begging of this document, you can avoid using this class directly
Arguments
n |
Number of bins in the histograms |
H1 |
First object of type |
H2 |
Second object of type |
L |
Approximation parameter. Higher values of L give a more accurate solution, but they require a longer running time. Table X gives the guarantee approximation bound as a function of L. Type: positive integer. |
Xs |
Vector of horizontal coordinates the bins. Type: vector of integers. |
Ys |
Vector of vertical coordinates the bins. Type: vector of integers. |
W1 |
Vector of weights of the bin at the positions specified by |
W2 |
Vector of weights of the bin at the positions specified by |
Ws |
Matrix of weights of the bin at the positions specified by |
name |
Name of the parameter to set and/or get. Type: string. |
value |
Value to set the corresponding parameter specified by |
Details
The public methods of this class are:
The Solver
class can be controlled by the list of parameters given in the following table, which can be set with the setParam(name, value)
method. A detailed description of each parameter is given below.
Parameter Name | Possible Values | Default Value |
Method | exact, approx | approx |
Model | bipartite, mincostflow | mincostflow |
Algorithm | fullmodel, colgen | colgen |
Verbosity | silent, info, debug | info |
TimeLimit | Any positive integer smaller than INTMAX | INTMAX |
OptTolerance | Any value in [10^{-9}, 10^{-1}] | 10^{-6}
|
-
Method
: set which method to use for computing the exact distance between a pair of histograms. The options for this parameter are:-
exact
: Compute the exact KW distance. This method is only helpful for small and sparse spatial maps. -
approx
: Compute an approximation KW distance which depends on the parameter L. This is the default value.
-
-
Model
: set which network model to use for computing the exact distance between a pair of histograms. The options for this parameter are:-
bipartite
: Build a complete bipartite graph. This method is only helpful for small and sparse spatial maps. -
mincostflow
: Build an uncapacitated network flow. This is, in general, smaller than thebipartite
model, except for very sparse histograms.
-
-
Algorithm
: set which algorithm to use to compute an approximate distance between a pair of histograms, which depends on the parameter L. The options for this parameter are:-
fullmodel
: Build a complete network model and solve the corresponding problem. -
colgen
: Build the network model incrementally while computing the KW distance. It is the recommended method for very large dense spatial maps. On medium and small spatial maps, the fullmodel could be faster.
The default value is set to
colgen
. -
-
Verbosity
: set the level of verbosity of the logs. Possible values aresilent
,info
,debug
. The last is more verbose than the other two. The default value is set toinfo
. -
TimeLimit
: set the time limit for computing the distance between a pair of spatial maps. Min values:INTMAX
. The default value is set toINTMAX
. -
OptTolerance
: Optimality tolerance on negative reduced cost variables to enter the basis. Min value:10^{-9}
, max value:10^{-1}
. The default value is set to10^{-6}
.
Methods
compareExact(Xs, Ys, W1, W2)
:compute the exact distance between the two vector of weights
W1
andW2
, on the convex hull of the points defined by the two vectorsXs
andYs
. The algorithm used by the solver is controlled by the parameterExactMethod
(see below). This method returns a single value (double), which is the KW-distance betweenW1
andW2
.compareExact(Xs, Ys, W1, Ws)
:compute the exact distances between the vector of weights
W1
and each of the vector of weights inWs
, on the convex hull of the points defined by the two vectorsXs
andYs
. The algorithm used by the solver is controlled by the parameterExactMethod
(see below). This method returns a vector of double of the same size ofWs
, representing the distance ofW1
to every element ofWs
.compareExact(Xs, Ys, Ws)
:compute a symmetric matrix of pairwise exact distances between all the possible pairs of the vector listed in
Ws
. The algorithm used by the solver is controlled by the parameterExactMethod
(see below).compareApprox(Xs, Ys, W1, W2, L)
:compute the approximate distance between the two vector of weights
W1
andW2
, on the convex hull of the points defined by the two vectorsXs
andYs
. The parameterApproxMethod
(see below) controls the algorithm used by the solver. This method returns a single value (double), which is the KW-distance betweenW1
andW2
.compareApprox(Xs, Ys, W1, Ws, L)
:compute the approximate distances between the vector of weights
W1
and each of the vector of weights inWs
, on the convex hull of the points defined by the two vectorsXs
andYs
. The parameterApproxMethod
(see below) controls the algorithm used by the solver. This method returns a vector of double of the same size ofWs
, representing the distance ofW1
to every element ofWs
.compareApprox(Xs, Ys, Ws, L)
:compute a symmetric matrix of pairwise approximate distances (which depends on the value of L) between all the possible pairs of the vector listed in
Ws
. The parameterApproxMethod
(see below) controls the algorithm used by the solver.runtime()
:return the runtime in seconds to the last call to one of the compare methods. It reports the runtime of the execution of the Network Simplex algorithm.
preprocesstime()
:return the preprocessing time in seconds to the last call to one of the compare methods. It reports the execution time to set up the main data structures and to compute the convex hull of all the input histograms.
setParam(name, value)
:set the parameter
name
to the newvalue
. Every parameter has a default value. See below for the existing parameters.getParam(name)
:return the current value of the parameter
name
.
See Also
See also compareOneToOne
, compareOneToMany
, compareAll
, focusArea
, and Histogram2D
.