graph_pcbase.c
Go to the documentation of this file.
20 * This file contains several basic methods to process prize-collecting Steiner problem graphs and kinsmen
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44 /** remove non-leaf terminals by edge weight shifting (call before graph transformation was performed) */
86 assert(graph_edge_isBlocked(graph, e) == EQ(edgecosts[e], BLOCKED_MINOR) || EQ(edgecosts[e], BLOCKED));
234 /** contract an edge of rooted prize-collecting Steiner tree problem or maximum-weight connected subgraph problem
266 assert(!graph_pc_isMw(g)); // currently does not work due to offset issue in graph_pc_knotTofixedTerm!
284 /** contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem
355 /* NOTE: this case could happen, but not with current contraction calls; would need to keep edges for extension in this case */
618 /* for each terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
619 SCIP_CALL( graph_resize(scip, graph, (graph->ksize + graph->terms + 2), (graph->esize + graph->terms * 8) , -1) );
648 /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
670 /** shift costs of non-leaf terminals (call right after transformation to extended has been performed) */
689 assert(SCIPisEQ(scip, cost[e], cost[flipedge(e)]) || SCIPisGE(scip, cost[e], FARAWAY) || SCIPisGE(scip, cost[flipedge(e)], FARAWAY));
903 if( !isExtended && Is_term(g->term[i]) && graph_pc_realDegree(g, i, graph_pc_knotIsFixedTerm(g, i)) )
1382 /** check whether node is a terminal AND is not a leaf (or not contained) in at least one optimal tree */
1502 int* termmark /**< terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise) */
1584 // graph->prize[nonleafterm] = BLOCKED_MINOR; // todo quite hacky, because it destroys the invariant of non-leaf terms!
1681 if( orggraph->term2edge[orgtail] >= 0 && orggraph->term2edge[orghead] >= 0 && orggraph->term[orgtail] != orggraph->term[orghead] )
1769 /* todo somewhat hacky...but otherwise there is a problem if the graph vanished during presolving, because term2edge
1860 const SCIP_Bool edgeIsBlocked = EQ(graph->cost[e], BLOCKED_MINOR) || EQ(graph->cost[e], BLOCKED);
1895 const SCIP_Bool edgeIsBlocked = EQ(gCosts[edge_g], BLOCKED_MINOR) || EQ(gCosts[edge_g], BLOCKED);
2104 if( Is_term(graph->term[i]) && i != graph->source && SCIPisLT(scip, graph->prize[i], BLOCKED) )
2351 /** contract ancestors of an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem */
2377 SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->pcancestors[s]), graph_edge_getAncestors(g, ets), NULL));
2378 SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->pcancestors[t]), graph_edge_getAncestors(g, ets), NULL));
2384 /** contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem */
2437 /** contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem;
2438 * method decides whether to contract s into t or vice-versa. Offset is added to surviving node */
2494 return (type == STP_PCSPG || type == STP_RPCSPG || type == STP_MWCSP || type == STP_RMWCSP || type == STP_BRMWCSP);
2581 /** returns number of proper potential terminals (potential terminals excluding non-leaf terminals) */
2602 /** compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset, takes prizes into account! */
void graph_pc_shiftNonLeafCosts(SCIP *scip, GRAPH *g)
Definition: graph_pcbase.c:671
Definition: graphdefs.h:184
static void markNonLeafTerms_2trans(SCIP *scip, GRAPH *g)
Definition: graph_pcbase.c:46
Definition: struct_scip.h:59
SCIP_RETCODE graph_fixed_addEdge(SCIP *, int, GRAPH *)
Definition: graph_history.c:1760
SCIP_Real graph_pc_solGetObj(SCIP *scip, const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: graph_pcbase.c:2603
static void getBiasedMw(const GRAPH *graph, SCIP_Real *RESTRICT costbiased, SCIP_Real *RESTRICT prizebiased)
Definition: graph_pcbase.c:448
void graph_pc_enforceNonLeafTerm(SCIP *scip, GRAPH *graph, int nonleafterm)
Definition: graph_pcbase.c:1556
int graph_pc_getTwinTerm(const GRAPH *g, int vertex)
Definition: graph_pcbase.c:2653
void graph_pc_getBiased(const GRAPH *graph, SCIP_Real *RESTRICT costbiased, SCIP_Real *RESTRICT prizebiased)
Definition: graph_pcbase.c:2185
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *g, int node)
Definition: graph_pcbase.c:1344
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
includes methods for Steiner tree problem solutions
void graph_pc_knotToNonTermProperty(GRAPH *g, int node)
Definition: graph_pcbase.c:1044
static SCIP_RETCODE contractEdgeWithFixedEnd(SCIP *scip, GRAPH *g, int *solnode, int t, int s, int ets)
Definition: graph_pcbase.c:237
includes various files containing graph methods used for Steiner tree problems
SCIP_Bool graph_pc_knotIsPropPotTerm(const GRAPH *g, int node)
Definition: graph_pcbase.c:1288
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: graph_node.c:264
void graph_pc_getOrgCostsCsr(SCIP *scip, const GRAPH *g, CSR *csr)
Definition: graph_pcbase.c:1871
int graph_pc_nNonFixedTerms(const GRAPH *graph)
Definition: graph_pcbase.c:2549
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
static void mwKnotUpdateIncEdges(GRAPH *g, int node)
Definition: graph_pcbase.c:213
void graph_pc_termMarkProper(const GRAPH *g, int *termmark)
Definition: graph_pcbase.c:1500
SCIP_Bool graph_pc_term2edgeIsConsistent(SCIP *scip, const GRAPH *g)
Definition: graph_pcbase.c:874
SCIP_Bool graph_pc_isUnrootedPcMw(const GRAPH *g)
Definition: graph_pcbase.c:2669
SCIP_RETCODE graph_pc_contractEdge(SCIP *scip, GRAPH *g, int *solnode, int t, int s, int term4offset)
Definition: graph_pcbase.c:2385
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *scip, const GRAPH *graph)
Definition: graph_pcbase.c:2209
int graph_pc_getRoot2PtermEdge(const GRAPH *graph, int pseudoterm)
Definition: graph_pcbase.c:2499
SCIP_RETCODE graph_pc_contractNodeAncestors(SCIP *scip, GRAPH *g, int t, int s, int ets)
Definition: graph_pcbase.c:2352
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
void graph_pc_knotToFixedTerm(SCIP *scip, GRAPH *g, int node, SCIP_Real *offset)
Definition: graph_pcbase.c:1079
SCIP_Bool graph_pc_edgeIsExtended(const GRAPH *g, int edge)
Definition: graph_pcbase.c:1232
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
internal miscellaneous methods
Definition: type_set.h:43
Definition: type_retcode.h:33
SCIP_Bool graph_pc_knotHasMaxPrize(const GRAPH *g, int i)
Definition: graph_pcbase.c:1315
void graph_pc_enforcePseudoTerm(SCIP *scip, GRAPH *graph, int pterm)
Definition: graph_pcbase.c:1530
void graph_pc_termToNonTerm(SCIP *scip, GRAPH *g, int term)
Definition: graph_pcbase.c:1158
void graph_pc_getOrgCosts(SCIP *scip, const GRAPH *graph, SCIP_Real *edgecosts)
Definition: graph_pcbase.c:1829
void graph_pc_fixedTermToNonTerm(SCIP *scip, GRAPH *g, int term)
Definition: graph_pcbase.c:1189
int graph_pc_nProperPotentialTerms(const GRAPH *graph)
Definition: graph_pcbase.c:2582
void graph_pc_adaptSap(SCIP_Real bigM, GRAPH *graph, SCIP_Real *offset)
Definition: graph_pcbase.c:2156
SCIP_RETCODE graph_fixed_moveNodePc(SCIP *, int, GRAPH *)
Definition: graph_history.c:1798
SCIP_Bool graph_pc_costsEqualOrgCosts(SCIP *scip, const GRAPH *graph, const SCIP_Real *edgecosts)
Definition: graph_pcbase.c:1913
static SCIP_RETCODE contractEdgeNoFixedEnd(SCIP *scip, GRAPH *g, int *solnode, int t, int s, int ets, int term4offset)
Definition: graph_pcbase.c:287
void graph_pc_termToNonLeafTerm(SCIP *scip, GRAPH *g, int term, SCIP_Bool force)
Definition: graph_pcbase.c:1210
SCIP_RETCODE graph_pc_contractEdgeUnordered(SCIP *scip, GRAPH *g, int *solnode, int t, int s)
Definition: graph_pcbase.c:2439
void graph_pc_getReductionRatios(const GRAPH *graph, SCIP_Real *ratio_nodes, SCIP_Real *ratio_edges)
Definition: graph_pcbase.c:1751
Definition: graphdefs.h:138
int graph_pc_realDegree(const GRAPH *g, int i, SCIP_Bool fixedterm)
Definition: graph_pcbase.c:2112
static void getBiasedPc(const GRAPH *graph, SCIP_Real *RESTRICT costbiased, SCIP_Real *RESTRICT prizebiased)
Definition: graph_pcbase.c:371
Portable definitions.
static void setCostToOrgPcPreState(SCIP *scip, GRAPH *graph)
Definition: graph_pcbase.c:96
SCIP_Real graph_pc_getPosPrizeSum(SCIP *scip, const GRAPH *graph)
Definition: graph_pcbase.c:2091
SCIP_RETCODE graph_pc_initTerm2Edge(SCIP *scip, GRAPH *g, int size)
Definition: graph_pcbase.c:721
SCIP_Bool graph_pc_nonLeafTermIsEnforced(SCIP *scip, const GRAPH *graph, int nonleafterm)
Definition: graph_pcbase.c:1589
void graph_pc_knotToFixedTermProperty(GRAPH *g, int node)
Definition: graph_pcbase.c:1062
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *g, int node)
Definition: graph_pcbase.c:1257
void graph_pc_nonTermToFixedTerm(GRAPH *g, int node, SCIP_Real *offset)
Definition: graph_pcbase.c:1115
void graph_pc_enforceNode(SCIP *scip, GRAPH *graph, int term, SCIP_Real *offset)
Definition: graph_pcbase.c:1606
static void termDeleteExtension(SCIP *scip, GRAPH *g, int i, SCIP_Bool makeNonTerminal)
Definition: graph_pcbase.c:124
void graph_pc_knotChgPrize(GRAPH *g, SCIP_Real newprize, int node)
Definition: graph_pcbase.c:1399
void graph_pc_updateSubgraphEdge(const GRAPH *orggraph, const int *nodemapOrg2sub, int orgedge, GRAPH *subgraph)
Definition: graph_pcbase.c:1661
SCIP_RETCODE graph_pc_initSubgraph(SCIP *scip, GRAPH *subgraph)
Definition: graph_pcbase.c:763
SCIP_RETCODE graph_pc_initPrizes(SCIP *scip, GRAPH *g, int sizeprize)
Definition: graph_pcbase.c:741
void solstp_setVertexFromEdge(const GRAPH *g, const int *result, STP_Bool *solnode)
Definition: solstp.c:2078
void graph_pc_2transcheck(SCIP *scip, GRAPH *graph)
Definition: graph_pcbase.c:2076
int graph_pc_deleteTerm(SCIP *scip, GRAPH *g, int term, SCIP_Real *offset)
Definition: graph_pcbase.c:2235
SCIP_RETCODE graph_pc_finalizeSubgraph(SCIP *scip, GRAPH *subgraph)
Definition: graph_pcbase.c:795
void graph_pc_subtractPrize(SCIP *scip, GRAPH *g, SCIP_Real cost, int i)
Definition: graph_pcbase.c:2315
Definition: objbenders.h:33
SCIP_RETCODE graph_pc_presolInit(SCIP *scip, GRAPH *g)
Definition: graph_pcbase.c:815
SCIP_Bool graph_pc_transOrgAreConistent(SCIP *scip, const GRAPH *graph, SCIP_Bool verbose)
Definition: graph_pcbase.c:980
IDX * graph_edge_getAncestors(const GRAPH *, int)
Definition: graph_history.c:1202
SCIP_Bool graph_pc_evalTermIsNonLeaf(SCIP *scip, const GRAPH *g, int term)
Definition: graph_pcbase.c:1467
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *g, int term)
Definition: graph_pcbase.c:1431
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *g, int node)
Definition: graph_pcbase.c:1383