Concorde edgegen.h functions

Organizational index     Function index     Program index     Macro index     Data Types index    

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