Concorde combs.h functions
CCcombs_greedy_cut
File:
COMBS/dngreedy.c
Header:
combs.h
Prototype:
int CCcombs_greedy_cut (CC_GCgraph *g, int *setsize, int *set,
int mark_fixed, int forced_moves, int bad_moves,
int fixed_moves, int *moves_done, double *cut_val)
Description:
RETURNS a set of nodes of having a small coboundary.
-g is the graph to grow in, including marks
-setsize is the size of the set (modified by greedy)
-set is the set of vertices (modified by greedy). This should
point to an array of size g->ncount (to handle any size set).
-mark_fixed, nodes with this mark are fixed (forbidden from
entering or leaving the set)
-forced_moves, make at least this many moves, even if they make
the cut worse. If a move is forced (ie, would not have happened
otherwise) then the result is fixed.
-bad_moves, make at least this many moves that make the cut worse.
The result of the bad move is fixed.
-fixed_moves, make at least this many moves, even if they make
the cut worse. Fix the result of each of these moves.
-moves_done, if non-NULL, should point to an int which will be
set to 1 if all of the forced moves, bad moves, and fixed moves
were made, and 0 if the cut ran out of available nodes before
making the required moves.
-cut_val is the set's cut value (set by greedy)
NOTES:
-assumes that status is 0 for every node in g, and restores
this condition on successful exit
-modifies the node fields qhandle, flow, setloc, setdeg, status
CCcombs_GC_build_graph
File:
COMBS/dngreedy.c
Header:
combs.h
Prototype:
int CCcombs_GC_build_graph (CC_GCgraph *G, int ncount, int ecount,
int *elist, double *x)
Description:
BUILDS the graph corresponding to the edge lists, using x for the
weights on the edges.
CCcombs_GC_init_graph
File:
COMBS/dngreedy.c
Header:
combs.h
Prototype:
void CCcombs_GC_init_graph (CC_GCgraph *G)
Description:
INITIALIZES the fields of the graph struct to NULL.
CCcombs_GC_free_graph
File:
COMBS/dngreedy.c
Header:
combs.h
Prototype:
void CCcombs_GC_free_graph (CC_GCgraph *G)
Description:
FREES the fields of the graph struct.
NOTES: differences from Denis Naddef's greedy grower:
1. Denis only adds nodes to the step. Greedy can delete nodes.
2. Denis selects any improving move. Greedy selects the most
improving move.
3. Denis has several methods of selecting a worsening move.
Greedy selects the least worsening move.
4. Denis continues until a cut < target is found, or until
badmoves worsening moves have been made. The best cut seen
during the process is returned. Greedy continues until
at least forced_moves moves have been made, and at least
bad_moves worsening moves have been made, and until there are
no more improving moves available. Greedy returns the final
cut.
5. Greedy supports fixed nodes.
CCcombs_find_blocks
File:
COMBS/block.c
Header:
combs.h
Prototype:
int CCcombs_find_blocks (int ncount, int ecount, int *elist,
double *x, int *nblocks, int **blockcnts, int ***blocks,
int *ncutnodes, int **cutnodes)
Description:
RETURNS the 2-connected components of the graph specified 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); if it is not
NULL, then the blocks components will be for the graph consisting
of the edges e with epsilon < x_e < 1 - epsilon
-nblocks will return the number of blocks (it can be NULL)
-blockcnts with return the size of the blocks (it can be NULL)
-blocks will return the members of the blocks (it can be NULL)
-ncutnodes with return the number of cutnodes (it can be NULL)
-cutnodes will return the cutnodes (it can be NULL)