Camargue
|
Class for computing and storing Karp partitions. More...
#include <karp.hpp>
Public Member Functions | |
KarpPartition ()=default | |
Default construct an empty partition. | |
KarpPartition (const Data::Instance &inst, bool make_dummy, bool save_part) | |
Construct a KarpPartition, with the option to force a dummy partition and/or write the partition to file. More... | |
KarpPartition (const Data::Instance &inst) | |
Construct a partition from an Instance inst . | |
int | num_parts () const |
The number of sub-regions into which the data has been partitioned. | |
const std::vector< int > & | operator[] (int i) const |
The nodes of the i th partition. | |
Static Public Member Functions | |
static int | bucket_size (const int ncount) |
Maximum partition size as function of number of nodes ncount . | |
Private Attributes | |
std::vector< std::vector< int > > | part_list |
A ragged matrix storing the partitions. | |
Class for computing and storing Karp partitions.
Computes a geometric partition of a TSP instance, a la Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in The Plane (Karp, 1977). Given geometric TSP data, it partitions the set of nodes into rectangles containing at most some fixed number of nodes.
CMR::Data::KarpPartition::KarpPartition | ( | const Data::Instance & | inst, |
bool | make_dummy, | ||
bool | save_part | ||
) |
Construct a KarpPartition, with the option to force a dummy partition and/or write the partition to file.
A dummy partition consists of the whole vertex set. Dummy partitions are used by default if inst
has under 300 nodes, or if its norm is incompatible with the Concorde KD tree code.
inst | the Instance to generate the partition from. |
make_dummy | if true, force a dummy partition to be used. |
save_part | if true, save the partition to a file called inst.problem_name().kpart . |