# Solver-class: Spatial-KWD Solver In SpatialKWD: Spatial KWD for Large Spatial Maps

 Solver-class 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 `Xs, Yw, W1, W2, Ws`. `H1` First object of type `Histogram2D`. `H2` Second object of type `Histogram2D`. `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 `Xs` and `Ys`. Type: vector of doubles. `W2` Vector of weights of the bin at the positions specified by `Xs` and `Ys`. Type: vector of doubles. `Ws` Matrix of weights of the bin at the positions specified by `Xs` and `Ys`. Type: matrix of doubles. `name` Name of the parameter to set and/or get. Type: string. `value` Value to set the corresponding parameter specified by `name`. Type: double.

### 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 the `bipartite` 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 are `silent`, `info`, `debug`. The last is more verbose than the other two. The default value is set to `info`.

• `TimeLimit`: set the time limit for computing the distance between a pair of spatial maps. Min values: `INTMAX`. The default value is set to `INTMAX`.

• `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 to 10^{-6}.

### Methods

`compareExact(Xs, Ys, W1, W2)`:

compute the exact distance between the two vector of weights `W1` and `W2`, on the convex hull of the points defined by the two vectors `Xs` and `Ys`. The algorithm used by the solver is controlled by the parameter `ExactMethod` (see below). This method returns a single value (double), which is the KW-distance between `W1` and `W2`.

`compareExact(Xs, Ys, W1, Ws)`:

compute the exact distances between the vector of weights `W1` and each of the vector of weights in `Ws`, on the convex hull of the points defined by the two vectors `Xs` and `Ys`. The algorithm used by the solver is controlled by the parameter `ExactMethod` (see below). This method returns a vector of double of the same size of `Ws`, representing the distance of `W1` to every element of `Ws`.

`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 parameter `ExactMethod` (see below).

`compareApprox(Xs, Ys, W1, W2, L)`:

compute the approximate distance between the two vector of weights `W1` and `W2`, on the convex hull of the points defined by the two vectors `Xs` and `Ys`. The parameter `ApproxMethod` (see below) controls the algorithm used by the solver. This method returns a single value (double), which is the KW-distance between `W1` and `W2`.

`compareApprox(Xs, Ys, W1, Ws, L)`:

compute the approximate distances between the vector of weights `W1` and each of the vector of weights in `Ws`, on the convex hull of the points defined by the two vectors `Xs` and `Ys`. The parameter `ApproxMethod` (see below) controls the algorithm used by the solver. This method returns a vector of double of the same size of `Ws`, representing the distance of `W1` to every element of `Ws`.

`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 parameter `ApproxMethod` (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 new `value`. Every parameter has a default value. See below for the existing parameters.

`getParam(name)`:

return the current value of the parameter `name`.

See also `compareOneToOne`, `compareOneToMany`, `compareAll`, `focusArea`, and `Histogram2D`.