Concorde cut.h functions

Organizational index     Function index     Program index     Macro index     Data Types index    

CCcut_SRK_init_graph

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_init_graph (CC_SRKgraph *G)
Description:
INITIALIZES the fields of the CC_SRKgraph.

CCcut_SRK_buildgraph

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_buildgraph (CC_SRKgraph *G, int ncount, int ecount,
    int *elist, double *dlen)
Description:
MISSING

CCcut_SRK_free_graph

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_free_graph (CC_SRKgraph *G)
Description:
FREES the CC_SRKgraph.

CCcut_SRK_init_expinfo

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_init_expinfo (CC_SRKexpinfo *expand)
Description:
MISSING

CCcut_SRK_free_expinfo

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_free_expinfo (CC_SRKexpinfo *expand)
Description:
MISSING

CCcut_SRK_init_callback

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_init_callback (CC_SRKcallback *cb)
Description:
MISSING

CCcut_SRK_grab_edges

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_grab_edges (CC_SRKgraph *G, int *oncount, int *oecount,
    int **olist, double **olen, CC_SRKexpinfo *expand)
Description:
      int **omembers)
RETURNS the edges and member lists for the shrunk graph.
 -G is a pointer to a shrunk graph
 -oncount returns the number of nodes in the shrunk graph
 -oecount returns the number of edges in the shrunk graph
 -olist returns the edges in node node format
 -olen returns the edge lengths
 -expand will be filled in with a memindex and members array;
  memindex returns pointers into the members array, the
  members of node i will be stored in from memindex[i] to
  memindex[i+1] - 1, so memindex is ncount + 1 long; members
  returns the nodes lists corresponding to each node in the
  shrunk graph. (expand can be NULL)

CCcut_SRK_grab_nodes

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_grab_nodes (CC_SRKgraph *G, CC_SRKexpinfo *expand)
Description:
RETURNS the member lists for the shrunk graph (see above)

CCcut_SRK_trivial

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_trivial (int ncount, CC_SRKexpinfo *expand)
Description:
MISSING

CCcut_SRK_expand

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_expand (CC_SRKexpinfo *expand, int *arr, int size,
    int *pnewarr, int *pnewsize)
Description:
MISSING

CCcut_SRK_identify_paths

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_paths (CC_SRKgraph *G, int *newcount,
    int onecnt_okay)
Description:
MISSING

CCcut_SRK_identify_paths_to_edges

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_paths_to_edges (CC_SRKgraph *G, int *newcount,
    int onecnt_okay)
Description:
MISSING

CCcut_SRK_identify_ones

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_ones (CC_SRKgraph *G, int *count,
    double epsilon)
Description:
MISSING

CCcut_SRK_identify_one_triangles

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_one_triangles (CC_SRKgraph *G, int *count,
    CC_SRKnode *qstart, double epsilon, double cutoff, int unmarked)
Description:
SHRINKS any one edge that sits in a tight triangle.
 -G is the current shrunk graph
 -count returns the number of shrunk triangles (can be NULL)
 -qstart can point to the start of a queue (linked by qnext)
 -epsilon is used to determine one edges (at least 1.0 - epsilon)
 -cutoff is used to determine tight triangles (weight cutoff)
 -unmarked should be nonzero if only unmarked nodes (determined
  by G->marker) should be involved in shrinks

CCcut_SRK_identify_tight_triangles

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_tight_triangles (CC_SRKgraph *G, int *count,
    double cutoff, int unmarked)
Description:
SHRINKS any tight triangle into a single node.
 -G is the current shrunk graph
 -count returns the number of shrunk triangles (can be NULL)
 -cutoff is used to decide if a triangle is tight (shrunk any T
  with x(T) >= cutoff)
 -unmarked should be nonzero if only unmarked nodes (determined
  by G->marker) should be involved in shrinks
NOTES: All new shrunk nodes will be marked.

CCcut_SRK_identify_tight_squares

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_tight_squares (CC_SRKgraph *G, int *count,
    double cutoff, int unmarked)
Description:
SHRINKS tight squares into a single nodes.
  -see above.

CCcut_SRK_identify_triangle_square

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_triangle_square (CC_SRKgraph *G, int *count,
    double epsilon, int unmarked)
Description:
SHRINKS tight triangles within tight squares.
  -epsilon is used to determine the tight triangle and square.

CCcut_SRK_identify_one_square

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_one_square (CC_SRKgraph *G, int *count,
    double epsilon, double cutoff, int unmarked)
Description:
SHRINKS two opposite 1-edge in a tight 4-square

CCcut_SRK_identify_nodes

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_identify_nodes (CC_SRKgraph *G, CC_SRKnode *n,
    CC_SRKnode *m)
Description:
MISSING

CCcut_SRK_increment_marker

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_increment_marker (CC_SRKgraph *G)
Description:
INCREASES the field used to mark nodes by 1.

CCcut_SRK_subtour_shrink

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_subtour_shrink (CC_SRKgraph *G, double *minval,
    double epsilon, CC_SRKcallback *cb, int **cut, int *cutcount)
Description:
MISSING

CCcut_SRK_identify_pr_edges

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_identify_pr_edges (CC_SRKgraph *G, double *minval,
    int *count, CC_SRKnode *qstart, double epsilon,
    CC_SRKcallback *cb, int **cut, int *cutcount)
Description:
MISSING

CCcut_SRK_defluff

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_defluff (CC_SRKGRAPH *G)
Description:
MISSING

CCcut_SRK_set_mark

File:
CUT/shrink.c
Header:
cut.h
Prototype:
void CCcut_SRK_set_mark (CC_SRKgraph *G, int marker)
Description:
SETS the mark field of all active nodes to marker.

CCcut_SRK_original_ncount

File:
CUT/shrink.c
Header:
cut.h
Prototype:
int CCcut_SRK_original_ncount (CC_SRKexpinfo *expand)
Description:
  RETURNS the number of nodes in the original (unshrunk) graph.
NOTES: Cyles of 1's will be shrunk into single nodes.

CCcut_linsub

File:
CUT/segments.c
Header:
cut.h
Prototype:
int CCcut_linsub (int ncount, int ecount, int *endmark, int *elist,
    double *x, double maxval, void *u_data,
    int (*cut_callback) (double cut_val, int cut_start, int cut_end,
    void *u_data))
Description:
-ncount is the number of nodes
-ecount is the number of edges
-endmark indicates which segments are of interest, by indicating
 whether a node can be a right or left end of a segment
-elist contains the LP edges in node node format
-x is an LP solution
-maxval is the maximum cut value desired
-u_data is user data to be passed to cut_callback
-cut_callback is a function to be called for segments which
 define a cut of value < cutlim.  The cut is cut_start,
 cut_start+1, ..., cut_end, and has value cut_val.  cut_callback
 will be called for the minimum segment cut starting at each
 endpoint marked as a right end, provided that cut has value <
 cutlim.

CCcut_linsub_allcuts

File:
CUT/segments.c
Header:
cut.h
Prototype:
int CCcut_linsub_allcuts (int ncount, int ecount, int *perm,
    int *endmark, int *elist, double *x, double maxval,
    void *u_data, int (*cut_callback) (double cut_val,
    int cut_start, int cut_end, void *u_data))
Description:
    -ncount is the number of nodes
    -ecount is the number of edges
    -perm is a permutation of the nodes (if perm == (int *) NULL,
     the identity permutation will be used)
    -elist contains the LP edges in node node format
    -endmark indicates which segments are of interest, by indicating
     whether a node can be a right or left end of a segment
    -x is an LP solution
    -maxval is the maximum cut value desired
    -u_data is data to be passed to the callback
    -cut_callback is a function to be called for every segment which
     defines a cut of value <= cutlim.  The cut is perm[cut_start],
     perm[cut_start+1], ..., perm[cut_end], and has value cut_val.
     if cut_callback returns a nonzero value, CCcut_linsub_allcuts
     will terminate.
NOTES:
    CCcut_linsub runs in time O(m log n).
    CCcut_linsub_allcuts runs in time O(m log n + |C| log n) where
    |C| is the number of cuts found.

CCcut_mincut

File:
CUT/mincut.c
Header:
cut.h
Prototype:
int CCcut_mincut (int ncount, int ecount, int *elist, double *dlen,
    double *cutval, int **cut, int *cutcount)
Description:
 COMPUTES the global minimum cut in an undirected graph.
  -ncount is the number of nodes in the graph.
  -ecount is the number of edges in the graph.
  -elist is the list of edges in end0 end1 format
  -dlen is a list of the edge capacities
  -cutval returns the capacity of the mincut (it can be NULL).
  -cut will return the indices of the nodes in the minimum cut;
   this variable can be passed in as NULL, otherwise it will be
   an allocated to an array of the appropriate length.
  -cutcount will return the number of nodes in the minimum cut if
   cut is not NULL (if cut is NULL, then cutcount can be NULL).
NOTES: This function assumes graph is connected. Paths of 1's are
 are shrunk - this is valid for the tsp, but not in general.

CCcut_violated_cuts

File:
CUT/mincut.c
Header:
cut.h
Prototype:
int CCcut_violated_cuts (int ncount, int ecount, int *elist,
    double *dlen, double cutoff, int (*doit_fn) (double, int,
    int *, void *), void *pass_param)
Description:
COMPUTES the global minimum cut, but calls the doit_fn function
for any cut the algorithm encounters that has capacity at most
cutoff. 
 -doit_fn (if not NULL) will be called for each cut having capacity
   less than or equal to the cutoff value; the arguments will be the
   value of the cut, the number of nodes in the cut, the array of
   the members of the cut, and pass_param.
 -pass_param will be passed to doit_fn; it can be NULL or it can be
   used to pass information to the doit_fn function.
NOTES: This function assumes graph is connected.
NOTES:
This code works with undirected graphs. The shrinking routines
assume that we are working with the TSP and not interested in cuts
of weight 2.0 or more.

CCcut_gomory_hu

File:
CUT/gomoryhu.c
Header:
cut.h
Prototype:
int CCcut_gomory_hu (CC_GHtree *T, int ncount, int ecount,
    int *elist, double *ecap, int markcount, int *marks,
    CCrandstate *rstate)
Description:
COMPUTES the Gomory-Hu tree of the marked nodes in G.
 -T returns the tree (a description is given in the code below)
 -ncount, ecount, elist specify the input graph
 -ecap lists the capacities of the edges
 -markcount is the length of the array marks (if markcount is 0,
  then every node is a terminal)
 -marks lists the special nodes (the terminals)

CCcut_GHtreefree

File:
CUT/gomoryhu.c
Header:
cut.h
Prototype:
void CCcut_GHtreefree (CC_GHtree *T)
Description:
FREES the tree pointed by T.

CCcut_GHtreeinit

File:
CUT/gomoryhu.c
Header:
cut.h
Prototype:
void CCcut_GHtreeinit (CC_GHtree *T)
Description:
INITIALIZES the fields of T to NULL.

CCcut_GHtreeprint

File:
CUT/gomoryhu.c
Header:
cut.h
Prototype:
void CCcut_GHtreeprint (CC_GHtree *T)
Description:
   PRINTS the Gomory-Hu tree to stdout.
NOTES:
  This code has only been tested on the instances that arise in
  exact blossom seperation.

CCcut_mincut_st

File:
CUT/cut_st.c
Header:
cut.h
Prototype:
int CCcut_mincut_st (int ncount, int ecount, int *elist, double *ecap,
    int s, int t, double *value, int **cut, int *cutcount)
Description:
COMPUTES the min st-cut in a directed or undirected graph.
  -ncount is the number of nodes in the graph.
  -ecount is the number of directed (undirected) edges.
  -elist gives the edges in node node format (interpreted as
       tail head when compiled for directed graphs).
  -ecap gives the capacities of the edges.
  -s is the name of the source node.
  -t is the name of the sink node.
  -value returns the capacity of the minimum cut.
  -cut (if not NULL) returns a list of nodes in a a minimum cut (it
   returns the side that contains t); it will be allocated to an
   array of the appropriate size.
  -cutcount returns the number of nodes in the listed cut, if cut
   is not NULL (if cut is NULL, then cutcount can be NULL).
NOTES:
  Returns 0 if it worked and 1 otherwise (for example, when one
  of the mallocs failed). The nodes in the graph should be named
  0 through #nodes - 1.
  Define UNDIRECTED_GRAPH to compile the code for undirected
  graphs. (This appears to be the way to go for tsp instances.)
  Two node selection rules are implemented: queue and highest
  label. One of QUEUE_PRF and HIGHEST_LABEL_PRF must be defined
  (but not both).
  The code can carry out global relabelings via a backwards
  breadth-first-search from the sink. The frequency of the
  relabelings is controlled by the defined constant
  GLOBAL_RELABEL_FREQUENCY. A relabling will occur after each
  #nodes * GLOBAL_RELABEL_FREQUENCY nodes have been processed.
  A resonable choice for the constant is 1.
  Defining USE_GAP turns on the gap heuristic of Derigs and
  Meyer for determing nodes that can be labeled to ncount.
  This can be used with either the queue or highest label
  variants.
  To use this code for maxflows, allow nodes with labels up to
  2*ncount to become active, or implement an algorithm to
  decompose the preflow to create a flow.

CCcut_connect_components

File:
CUT/connect.c
Header:
cut.h
Prototype:
int CCcut_connect_components (int ncount, int ecount, int *elist,
    double *x, int *ncomp, int **compscount, int **comps)
Description:
RETURNS the connected components of the graph given by the edgeset
 -ncount is the number of nodes
 -ecount is the number of edges
 -elist is the edge list in node node format
 -x is an vector of length ecount (it can be NULL); is it is not
  NULL, then the connected components will be for the graph
  consisting of the positive edges
 -ncomp will return the number of connected components
 -compscount will return the number of nodes in each of the
  components (it will be an ncomp long array)
 -comps will return the nodes in the components (it will be an
  ncount array, with the first compscount[0] elements making up
  the first component, etc.)