Concorde cut.h functions
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.)