reduce_simple.c
Go to the documentation of this file.
21 * Mosts tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
191 int* edgestate /**< array to store status of (directed) edge (for propagation, can otherwise be set to NULL) */
502 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[Edge_anti(e2)], NULL) );
503 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(e1)]), g->ancestors[e2], NULL) );
565 /* delete all nodes that cannot reach a terminal other than the root by forward arcs (not using the root) */
753 if( g->oeat[e] != EAT_FREE && SCIPisZero(scip, g->cost[e]) && SCIPisZero(scip, g->cost[flipedge(e)]) )
1074 if( Is_term(g->term[k]) && !graph_pc_knotIsFixedTerm(g, k) && !graph_pc_termIsNonLeafTerm(g, k) )
1189 printf("terminal node %d (original index %d) lies in separate connected component \n", k, k + 1);
Definition: misc_stp.h:88
int graph_edge_nPseudoAncestors(const GRAPH *, int)
Definition: graph_history.c:1159
SCIP_RETCODE reduce_simple(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *solnode, int *nelims, int *edgestate)
Definition: reduce_simple.c:184
SCIP_RETCODE reduce_fixedConflicts(SCIP *scip, const int *edgestate, GRAPH *g, int *countnew)
Definition: reduce_simple.c:832
SCIP_RETCODE graph_knot_contractFixed(SCIP *, GRAPH *, int *, int, int, int)
Definition: graph_node.c:521
Definition: graphdefs.h:184
Definition: struct_scip.h:59
SCIP_RETCODE graph_fixed_addEdge(SCIP *, int, GRAPH *)
Definition: graph_history.c:1760
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
int graph_pseudoAncestorsGetHashArraySize(const PSEUDOANS *)
Definition: graph_history.c:1321
SCIP_Bool graph_pc_term2edgeIsConsistent(SCIP *, const GRAPH *)
Definition: graph_pcbase.c:874
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE graph_knot_replaceDeg2(SCIP *, int, SCIP_Real, int, GRAPH *, SCIP_Bool *)
Definition: graph_node.c:158
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: graph_node.c:264
SCIP_RETCODE reduce_unconnectedInfeas(SCIP *scip, SCIP_Bool beVerbose, GRAPH *g, SCIP_Bool *infeas)
Definition: reduce_simple.c:1164
void graph_pc_termToNonLeafTerm(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_pcbase.c:1210
static SCIP_RETCODE cutEdgePrune(SCIP *scip, int start, int end, int cutedge, GRAPH *g)
Definition: reduce_simple.c:61
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1431
void reduce_identifyNonLeafTerms(SCIP *scip, GRAPH *g)
Definition: reduce_simple.c:1052
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
SCIP_RETCODE reduce_rpt(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:916
SCIP_RETCODE reduce_unconnected(SCIP *scip, GRAPH *g)
Definition: reduce_simple.c:1097
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
Definition: struct_misc.h:51
SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP *, GRAPH *, int *, int, int)
Definition: graph_node.c:539
Definition: type_retcode.h:33
Definition: type_retcode.h:34
SCIP_RETCODE reduce_cutEdgeTryPrune(SCIP *scip, int cutedge, GRAPH *g, SCIP_Bool *success)
Definition: reduce_simple.c:1001
SCIP_RETCODE reduce_contract0Edges(SCIP *scip, GRAPH *g, int *solnode, SCIP_Bool savehistory)
Definition: reduce_simple.c:733
const int * graph_edge_getPseudoAncestors(const GRAPH *, int)
Definition: graph_history.c:1187
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1383
SCIP_RETCODE graph_trail_costAware(SCIP *, const GRAPH *, int, SCIP_Bool *)
Definition: graph_util.c:353
Portable definitions.
SCIP_RETCODE graph_trail_arr(SCIP *, const GRAPH *, int, SCIP_Bool *)
Definition: graph_util.c:336
SCIP_RETCODE reduce_deleteMultiedges(SCIP *scip, GRAPH *g)
Definition: reduce_simple.c:782
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:934
SCIP_RETCODE reduce_simple_sap(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:397
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1257
static SCIP_RETCODE cutEdgeProbe(SCIP *scip, const GRAPH *g, int start, int end, SCIP_Bool *RESTRICT nodes_visited, SCIP_Bool *terminalFound)
Definition: reduce_simple.c:99
SCIP_RETCODE reduce_simple_hc(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:655
const int * graph_getFixpseudonodes(SCIP *, const GRAPH *)
Definition: graph_history.c:1957
SCIP_RETCODE reduce_unconnectedForDirected(SCIP *scip, GRAPH *g)
Definition: reduce_simple.c:1134
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_Bool graph_pc_evalTermIsNonLeaf(SCIP *, const GRAPH *, int)
Definition: graph_pcbase.c:1467
Definition: objbenders.h:33
includes various reduction methods for Steiner tree problems
SCIP callable library.
IDX * graph_edge_getAncestors(const GRAPH *, int)
Definition: graph_history.c:1202