Concorde kdtree.h functions
CCkdtree_twoopt_tour
File:
KDTREE/kdtwoopt.c
Header:
kdtree.h
Prototype:
int CCkdtree_twoopt_tour (CCkdtree *kt, int ncount, CCdatagroup *dat,
int *incycle, int *outcycle, double *val,
int run_two_and_a_half_opt, int silent, CCrandstate *rstate)
Description:
RETURNS a 2-opted cycle (well, approximately 2-opted)
-kt can be NULL.
-Does not use node weights.
-incycle is the starting cycle.
-If outcycle is not NULL, then it should point to an array of
length at least ncount (allocated by the calling routine). The
final tour will be placed in this array.
-The length of the tour is returned in val.
-If in_run_two_and_a_half_opt is nonzero, then some limited
3-swapping is performded.
-silent (if nonzero then very little info will be printed)
CCkdtree_3opt_tour
File:
KDTREE/kdtwoopt.c
Header:
kdtree.h
Prototype:
int CCkdtree_3opt_tour (CCkdtree *kt, int ncount, CCdatagroup *dat,
int *incycle, int *outcycle, double *val, silent,
CCrandstate *rstate)
Description:
RETURNS an approximately 3-opted tour.
-kt can be NULL.
CCkdtree_prim_spanningtree
File:
KDTREE/kdspan.c
Header:
kdtree.h
Prototype:
int CCkdtree_prim_spanningtree (CCkdtree *kt, int ncount,
CCdatagroup *dat, double *wcoord, int *outtree, double *val,
CCrandstate *rstate)
Description:
RETURNS a min weight spanning tree.
-kt is a pointer to a CCkdtree built by a call to CCkdtree_build.
If kt is NULL, then CCkdtree_build will be called.
-If wcoord is not NULL, then the array should have nonnegative
values. The code will use Held-Karp style distances.
-If outtree is non NULL, it should point to an array of length
at least 2*ncount - 2. The edges in the min spanning tree will
be returned in the array in end end format.
-The length of the min tree is returned in val.
CCkdtree_greedy_tour
File:
KDTREE/kdspan.c
Header:
kdtree.h
Prototype:
int CCkdtree_greedy_tour (CCkdtree *kt, int ncount, CCdatagroup *dat,
int *outcycle, double *val, int silent, CCrandstate *rstate)
Description:
RETURNS a greedy tour. (No randomization (expect in building the
CCkdtree) so there is no point in calling this more than once)
-kt can be NULL.
-Does not use node weights.
-If outcycle is non NUL, it should point to an array of length
at least ncount. The cycle will be returned in node node node
format.
CCkdtree_far_add_tour
File:
KDTREE/kdspan.c
Header:
kdtree.h
Prototype:
int CCkdtree_far_add_tour (CCkdtree *kt, int ncount, int start,
CCdatagroup *dat, int *outcycle, double *val, CCrandstate *rstate)
Description:
RETURNS a farthest addition tour, beginning with node start.
-like CCkdtree_greedy_tour.
CCkdtree_qboruvka_tour
File:
KDTREE/kdspan.c
Header:
kdtree.h
Prototype:
int CCkdtree_qboruvka_tour (CCkdtree *kt, int ncount,
CCdatagroup *dat, int *outcycle, double *val, CCrandstate *rstate)
Description:
MISSING
CCkdtree_boruvka_tour
File:
KDTREE/kdspan.c
Header:
kdtree.h
Prototype:
int CCkdtree_boruvka_tour (CCkdtree *kt, int ncount,
CCdatagroup *dat, int *outcycle, double *val, CCrandstate *rstate)
Description:
MISSING
CCkdtree_k_nearest
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_k_nearest (CCkdtree *kt, int ncount, int k,
CCdatagroup *dat, double *wcoord, int wantlist, int *ocount,
int **olist, int silent, CCrandstate *rstate)
Description:
RETURNS the k-nearest neighbor graph.
-kt can be NULL, otherwise it should point to a CCkdtree built
by a call to kdbuild ()
-ncount is the number of points.
-k is the number of nearest neighbors wanted.
-wcoord is an array of node weights (like Held-Karp), it can
be NULL. The weights should be nonnegative.
-wantlist is 1 if you want the function to return the edges.
-ocount returns the number of edges (if wantlist is 1) and
olist returns the edgelist is end1 end2 format.
-silent will turn off print messages if set to nonzero value.
CCkdtree_quadrant_k_nearest
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_quadrant_k_nearest (CCkdtree *kt, int ncount, int k,
CCdatagroup *dat, double *wcoord,
int wantlist, int *ocount, int **olist, int silent,
CCrandstate *rstate)
Description:
RETURNS the quadrant k-nearest neighbor graph.
-see CCkdtree_k_nearest.
CCkdtree_node_k_nearest
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_node_k_nearest (CCkdtree *kt, int ncount, int n, int k,
CCdatagroup *dat, double *wcoord, int *list, CCrandstate *rstate)
Description:
RETURNS the k nearest points to point n.
-The k points are return in list (and list must be allocated by
calling routine.
-kt is a pointer to a CCkdtree previously built by
CCkdtree_build.
CCkdtree_node_quadrant_k_nearest
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_node_quadrant_k_nearest (CCkdtree *kt, int ncount,
int n, int k, CCdatagroup *dat, double *wcoord, int *list,
CCrandstate *rstate)
Description:
RETURNS the quadrant k nearest point to point n.
-see CCkdtree_node_k_nearest.
CCkdtree_node_nearest
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_node_nearest (ktree *kt, int n, CCdatagroup *dat,
double *wcoord)
Description:
RETURNS the nearest point to point n.
-kt CANNOT be NULL.
-The point is returned as the function value. kt is a pointer
to a CCkdtree (previously buildt by a call to CCkdtree_build)
CCkdtree_fixed_radius_nearest
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_fixed_radius_nearest (CCkdtree *kt, CCdatagroup *dat,
double *wcoord, int n, double rad,
int (*doit_fn) (int, int, void *), void *pass_param)
Description:
ACTION: Calls the function doit_fn (n, a, void *), where a ranges
over all points within distance rad of the point n. The
void * field can be used to bundle a group of parmeters
into pass_param that will be passed to doit_fn.
-kt CANNOT be NULL.
-doit_fn can also call CCkdtree_fixed_radius_nearest (no globals
are set by the function calls)
-pass_param can be NULL or used to point to a structure with
with parameters for doit_fn.
CCkdtree_nearest_neighbor_tour
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_nearest_neighbor_tour (CCkdtree *kt, int ncount,
int start, CCdatagroup *dat, int *outcycle, double *val,
CCrandstate *rstate)
Description:
-kt can be NULL.
-Node weights are not used.
-start is the starting node for the tour.
-if outcycle is not NULL, then it should point to a array of
length at least ncount (allocated by the calling routine). The
cycle will be returned in the array in node node node format.
-the length of the tour is return in val.
CCkdtree_nearest_neighbor_2match
File:
KDTREE/kdnear.c
Header:
kdtree.h
Prototype:
int CCkdtree_nearest_neighbor_2match (CCkdtree *kt, int ncount,
int start, CCdatagroup *dat, int *outmatch, double *val,
CCrandstate *rstate)
Description:
-Like CCkdtree_nearest_neighbor_tour. If outmatch is not NULL
then it should point to an array of length at least 2*ncount.
NOTES:
If memory is tight, use CCkdtree_node_k_nearest to get the
edges one node at a time. (CCkdtree_k_nearest () builds a hash
table to avoid duplicate edges, and it will use 8 * nedges
bytes.)
CCkdtree_node_nearest returns the nearest point as the
function value; CCkdtree_fixed_radius_nearest returns 1 if
doit_fn returns a nonzero value, otherwise it returns 0; all
other routines return 0 if successful and 1 otherwise.
CCkdtree_build
File:
KDTREE/kdbuild.c
Header:
kdtree.h
Prototype:
int CCkdtree_build (CCkdtree *kt, int ncount, CCdatagroup *dat,
double *wcoord, CCrandstate *rstate)
Description:
-When called, intree should point to a CCkdtree struct that the
funtion will load with the tree it builds. The wcoord array
is used for node weights (like in Held-Karp), it can be NULL.
The node weights must be nonegative (for cutoffs).
CCkdtree_free
File:
KDTREE/kdbuild.c
Header:
kdtree.h
Prototype:
void CCkdtree_free (CCkdtree *kt)
Description:
-Frees the space (including the ptrs) used by kt.
CCkdtree_delete
File:
KDTREE/kdbuild.c
Header:
kdtree.h
Prototype:
void CCkdtree_delete (CCkdtree *kt, int k)
Description:
-Deletes the point k from the CCkdtree kt.
CCkdtree_undelete
File:
KDTREE/kdbuild.c
Header:
kdtree.h
Prototype:
void CCkdtree_undelete (CCkdtree *kt, int k)
Description:
-Puts the previously deleted point k back into kt.
CCkdtree_delete_all
File:
KDTREE/kdbuild.c
Header:
kdtree.h
Prototype:
void CCkdtree_delete_all (CCkdtree *kt, int ncount)
Description:
-Deletes all points in kt.
CCkdtree_undelete_all
File:
KDTREE/kdbuild.c
Header:
kdtree.h
Prototype:
void CCkdtree_undelete_all (CCkdtree *kt, int ncount)
Description:
-Puts all deleted points back in kt. Used to cleanup trees.
NOTES:
On a 32 bit machine, a CCkdtree on n nodes needs about 52n
bytes of memory. CCkdtree_build will return 1 if an error
occurs (most likely running out of memory).
CCutil_sprand () should be called before calling
CCkdtree_build ().