Concorde edgegen.h functions
CCedgegen_x_k_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_x_k_nearest (int ncount, int k, CCdatagroup *dat,
double *wcoord, int wantlist, int *ecount, int **elist,
int silent)
Description:
RETURNS the k_nearest neighbor graph (for X-Norms)
-ncount is the number of nodes
-k is the number of nearest neighbors wanted
-dat contains the info to generate edge lengths
-wcoord are nodeweights for Held-Karp style edge lengths, using
len[i,j] + wcoord[i] + wcoord[j] (wcoord can be NULL)
-wantlist should be set to 0 if you don't want the edges
-ecount returns the number of edges if wantlist is 1
-elist returns the edges in end1 end2 format if wantlist is 1
CCedgegen_x_quadrant_k_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_x_quadrant_k_nearest (int ncount, int k,
CCdatagroup *dat, double *wcoord, int wantlist, int *ecount,
int **elist, int silent)
Description:
RETURNS the quadrant k_nearest_graph (for X-Norms)
CCedgegen_x_node_k_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_x_node_k_nearest (CCxnear *xn, int n, int k,
int ncount, int *list)
Description:
RETURNS the k nearest neighbors from node n (for X-Norms
-xn is a structure built by a call to CCedgegen_xnear_build ()
-list returns the neighbors of n. The calling routine should
be sure that list points to an array of length at least num.
CCedgegen_x_node_quadrant_k_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_x_node_quadrant_k_nearest (CCxnear *xn, int n, int k,
int ncount, int *list)
Description:
RETURNS the quadrant k nearest to node n (for X-Norms)
-xn is a structure built by a call to CCedgegen_xnear_build ()
-list returns the neighbors of n. The calling routine should
be sure that list points to a sufficiently large array (4*num
for D2_SIZE norms and 8*num for D3_SIZE norms)
CCedgegen_x_node_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_x_node_nearest (CCxnear *xn, int ncount, int ni,
char *marks)
Description:
RETURNS the nearest unmarked node to node n (as the return value)
-marks is an array. The entries that are nonzero correspond to
nodes that will not be looked at in the search.
CCedgegen_x_nearest_neighbor_tour
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_x_nearest_neighbor_tour (int ncount, int start,
CCdatagroup *dat, int *outcycle, double *val)
Description:
RETURNS a nearest neighbor tour, starting at node start.
-outcycle will contain the tour if it is not NULL (the calling
routine should be sure it points to an array of length at
least ncount if it is not set to NULL)
-val will return the length of the tour.
CCedgegen_junk_k_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_junk_k_nearest (int ncount, int k, CCdatagroup *dat,
double *wcoord, int wantlist, int *ecount, int **elist,
int silent)
Description:
RETURNS the k-nearest graph (for JUNK-Norms)
-see CCedgegen_x_k_nearest (above) for the variables
CCedgegen_junk_node_k_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_junk_node_k_nearest (CCdatagroup *dat, double *wcoord,
int n, int k, int ncount, int *list)
Description:
RETURNS the k nearest neighbors to node n (for JUNK-Norms)
-list returns the neighbors of n. The calling routine should
be sure that list points to an array of length at least num.
CCedgegen_junk_node_nearest
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_junk_node_nearest (CCdatagroup *dat, double *wcoord,
int ncount, int n, char *marks)
Description:
RETURNS the nearest unmarked node to node n (as the return value)
-marks is an array, the nodes with marks[i] nonzero are ignored.
CCedgegen_junk_nearest_neighbor_tour
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_junk_nearest_neighbor_tour (int ncount, int start,
CCdatagroup *dat, int *outcycle, double *val, int silent)
Description:
RETURNS a nearest neighbor tour starting at node start. Note that
this will be slow for large problems (it is a quadratic routine)
-see the describtion of CCedgegen_x_nearest_neighbor_tour above
CCedgegen_xnear_build
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
int CCedgegen_xnear_build (int ncount, CCdatagroup *dat,
double *wcoord, CCxnear *xn)
Description:
RETURNS the structure needed for calls to
CCedgegen_x_node_k_nearest and
CCedgegen_x_node_quadrant_k_nearest (the calling routine should
be sure that xn points to such a structure). All this routine
does is permute the data so that the x coordinates are in
nonincreasing order.
CCedgegen_xnear_free
File:
EDGEGEN/xnear.c
Header:
edgegen.h
Prototype:
void CCedgegen_xnear_free (CCxnear *xn)
Description:
FREES the CCxnear structure pointed to by xn
NOTES:
All routines other than CCedgegen_xnear_free and
CCedgegen_x_node_nearest return 0 on success and 1 on failure
(normally due to running out of memory).
The X-Norm functions will also work for KD-Norms, but they are
much slower than the KD-Norm functions.
CCedgegen_read
File:
EDGEGEN/edgegen.c
Header:
edgegen.h
Prototype:
int CCedgegen_read (char *egname, CCedgegengroup *plan)
Description:
READS an edgegen description from file egname.
-egname the name of a file
-plan returns the description of the mix of edges (can be used
in a call to CCedgegen_edges () to obtain the edgeset).
CCedgegen_edges
File:
EDGEGEN/edgegen.c
Header:
edgegen.h
Prototype:
int CCedgegen_edges (CCedgegengroup *plan, int ncount,
CCdatagroup *dat, double *wcoord, int *ecount, int **elist,
int silent, CCrandstate *rstate)
Description:
RETURNS the set of edges described in plan.
-plan describes the mix of edges
-ncount is the number of nodes
-dat contains the info to generate edge lengths
-wcoord are nodeweights for Held-Karp style edge lengths, using
len[i,j] + wcoord[i] + wcoord[j] (wcoord can be NULL)
-ecount returns the number of edges
-elist returns the edges in end1 end2 format
-silent will suppress print messages if set to a nonzero value.
CCedgegen_init_edgegengroup
File:
EDGEGEN/edgegen.c
Header:
edgegen.h
Prototype:
void CCedgegen_init_edgegengroup (CCedgegengroup *plan)
Description:
SETS the fields in plan to 0 (since there are so many fields to
to deal with)
NOTES:
To use CCedgegen_edges, look at the defintion of CCedgegengroup
in edgegen.h - you should be able to guess what the parmeters mean.
Note that wcoord is only used by a limited number of the generating
routines, for example nearest, but not linkern.
The functions CCedgegen_edges and CCedgegen_read will return
nonzero values if they fail (for example, if they run out of memory.
The description file passed to CCedgegen_read should contain a
list of some of the following commands:
EDGEGEN RANDOM #
-find # random edges
EDGEGEN NEAREST #
-find the nearest # edges
EDGEGEN QUADNEAREST #
-find the quadrant-nearest # edges
EDGEGEN FRAC_TWOMATCH_NEAREST # [PRICED] [BASIC]
-find the nearest # using the reduced costs of a
fractional 2-matching as the edgelengths. If either
of the optional arguments PRICED or BASIC is
specified then the 2-matching used will be either
priced against the complete edgeset or converted to
a basic optimal solution (or both).
EDGEGEN GREEDY_TOUR
-find a greedy tour
EDGEGEN BORUVKA_TOUR
-find a Boruvka tour
EDGEGEN QBORUVKA_TOUR
-find a quick Boruvka tour
EDGEGEN NN_TOUR #
-find # nearest-neighbor tours
EDGEGEN RANDOM_TOUR #
-find # random tours
EDGEGEN TWOOPT_TOUR #
-find # 2-opt tours
EDGEGEN TWOPT5_TOUR #
-find # 2.5-opt tours
EDGEGEN THREEOPT_TOUR #
-find # 3-opt tours
EDGEGEN LINKERN #1 #2 [QUADNEAREST #3] [NEAREST #4]
[GREEDY_START | NN_START | RANDOM_START
| BORUVKA_START | QBORUVKA_START]
-find #1 Iterated Lin-Kernighan tours using #2
kicks.
The good edgeset can be specified by the optional
arguments QUADNEAREST and NEAREST (the two can be
used together). The initial tours can be specfied
by using one of GREEDY_START, NN_START,
BORUVKA_START, QBORUVKA_START, or RANDOM_START.
EDGEGEN NN_TWOMATCH #
-find # nearest-neighbor 2-matchings
EDGEGEN TREE
-find a minimum weight spanning tree.
EDGEGEN FRAC_TWOMATCH [PRICED] [BASIC]
-find a minmum weight 2-matching (priced against the
complete edgeset) (that is a basic optimal
solution)
EDGEGEN DELAUNAY
-find the edges in the (Euclidean-norm) Delaunay
triangulation (using Steve Fortune's sweep2 code).
M_LINKERN
-find # lin ker matchings