graph_history.c
Go to the documentation of this file.
20 * Graph ancestor methods for Steiner problems. Usually used to reconstruct a graph after reductions
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
427 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(blockedans->blocks[block_id]), capacity_old, capacity_new) );
556 SCIP_CALL( blockedAncestors_appendArray(scip, block_target, ancestors_source, size_source, breakOnConflict, hasharr_size, blockedans_target, conflict) );
704 SCIP_CALL( SCIPallocMemoryArray(scip, &(singletonans->pseudoancestors), singletonans->npseudoancestors) );
705 BMScopyMemoryArray(singletonans->pseudoancestors, pseudoancestors, singletonans->npseudoancestors);
716 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(singletonans->ancestors), graph_edge_getAncestors(g, edge), &conflict) );
722 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(singletonans->ancestors), g->ancestors[edge], &conflict) );
725 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(singletonans->revancestors), g->ancestors[flipedge(edge)], &conflict) );
897 blockedAncestors_hashDirty(pseudoancestors->ans_halfedges, halfedge, revertIfConflict, conflict, hasharr);
913 blockedAncestors_hashDirty(pseudoancestors->ans_nodes, node, revertIfConflict, conflict, hasharr);
1024 SCIP_CALL_ABORT( SCIPallocCleanBufferArray(scip, &hasharr, graph_pseudoAncestorsGetHashArraySize(g->pseudoancestors)) );
1085 SCIP_CALL( blockedAncestors_init(pseudoancestors->halfnedges, &(pseudoancestors->ans_halfedges)) );
1327 assert(getNextPow2(pseudoancestors->nAllPseudoancestors + 1) > pseudoancestors->nAllPseudoancestors);
1350 SCIP_CALL( blockedAncestors_appendCopy(scip, target, pseudoancestors->ans_halfedges, source, revertIfConflict,
1372 SCIP_CALL( blockedAncestors_appendCopy(scip, node_target, pseudoancestors->ans_nodes, node_source, revertIfConflict,
1395 SCIP_CALL( blockedAncestors_appendCopy(scip, target, pseudoancestors->ans_nodes, node_source, revertIfConflict,
1418 SCIP_CALL( blockedAncestors_appendCopy(scip, node_target, pseudoancestors->ans_halfedges, source, revertIfConflict,
1449 SCIP_CALL( blockedAncestors_appendArray(scip, target, ancestors, nancestors, revertIfConflict, hasharr_size, pseudoancestors->ans_halfedges, conflict) );
1482 SCIP_CALL( blockedAncestors_appendArray(scip, target, ancestors, nancestors, revertIfConflict, hasharr_size, pseudoancestors->ans_halfedges, conflict) );
1488 /** appends pseudo ancestors of edge_source to edge_target, ancestors for edge_source are deleted */
1498 SCIP_CALL( graph_pseudoAncestors_appendCopyEdge(scip, edge_target, edge_source, revertIfConflict, g, conflict) );
1505 /** appends pseudo ancestors of node source to node target, ancestors for source are deleted */
1515 SCIP_CALL( graph_pseudoAncestors_appendCopyNode(scip, node_target, node_source, revertIfConflict, g, conflict) );
1538 SCIP_CALL( blockedAncestors_addAncestor(scip, target, ancestor, hasharr_size, pseudoancestors->ans_halfedges) );
1562 SCIP_CALL( blockedAncestors_addAncestor(scip, node_target, ancestor, hasharr_size, pseudoancestors->ans_nodes) );
1655 SCIPfreeBlockMemoryArray(scip, &(fixedcomponents->fixpseudonodes), fixedcomponents->nfixnodes);
1737 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(fixedcomponents->fixpseudonodes), nfixnnodes_new) );
1743 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(fixedcomponents->fixpseudonodes), nfixnnodes, nfixnnodes_new) );
1770 SCIP_CALL( graph_fixed_add(scip, graph_edge_getAncestors(g, edge), graph_edge_getPseudoAncestors(g, edge),
1931 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(fixed_copy->fixpseudonodes), fixed_copy->nfixnodes) );
1932 BMScopyMemoryArray(fixed_copy->fixpseudonodes, fixed_org->fixpseudonodes, fixed_copy->nfixnodes);
static SCIP_RETCODE blockedAncestors_appendCopy(SCIP *scip, int block_target, const BLOCKANS *blockedans_source, int block_source, SCIP_Bool breakOnConflict, int hasharr_size, BLOCKANS *blockedans_target, SCIP_Bool *conflict)
Definition: graph_history.c:531
Definition: misc_stp.h:88
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
SCIP_RETCODE graph_fixed_moveNodePc(SCIP *scip, int node, GRAPH *g)
Definition: graph_history.c:1798
static SCIP_RETCODE blockedAncestors_realloc(SCIP *scip, int block_id, int capacity_new, BLOCKANS *blockedans)
Definition: graph_history.c:401
SCIP_Bool graph_valid_pseudoAncestors(SCIP *scip, const GRAPH *g)
Definition: graph_history.c:1569
SCIP_RETCODE graph_pseudoAncestors_appendCopyEdgeToNode(SCIP *scip, int node_target, int edge_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1403
void graph_freePseudoAncestors(SCIP *scip, GRAPH *g)
Definition: graph_history.c:1101
Definition: graphdefs.h:184
int graph_pseudoAncestorsGetHashArraySize(const PSEUDOANS *pseudoancestors)
Definition: graph_history.c:1321
Definition: struct_scip.h:59
const int * graph_edge_getPseudoAncestors(const GRAPH *g, int edge)
Definition: graph_history.c:1187
static void blockedAncestors_unhashDirty(const BLOCKANS *blockedans, int block_id, int *hasharr)
Definition: graph_history.c:331
void graph_singletonAncestors_freeMembers(SCIP *scip, SINGLETONANS *singletonans)
Definition: graph_history.c:734
SCIP_RETCODE graph_pseudoAncestors_addToNode(SCIP *scip, int node_target, int ancestor, GRAPH *g)
Definition: graph_history.c:1545
SCIP_Bool graph_pseudoAncestors_edgeIsHashed(const PSEUDOANS *pseudoancestors, int edge, const int *hasharr)
Definition: graph_history.c:948
static void blockedAncestors_hash(const BLOCKANS *blockedans, int block_id, int *hasharr)
Definition: graph_history.c:225
void graph_pseudoAncestors_unhashNode(const PSEUDOANS *pseudoancestors, int node, int *hasharr)
Definition: graph_history.c:870
includes various files containing graph methods used for Steiner tree problems
void graph_edge_printPseudoAncestors(const GRAPH *g, int edge)
Definition: graph_history.c:1248
SCIP_RETCODE graph_singletonAncestors_init(SCIP *scip, const GRAPH *g, int edge, SINGLETONANS *singletonans)
Definition: graph_history.c:684
void graph_pseudoAncestors_hashNodeDirty(const PSEUDOANS *pseudoancestors, int node, SCIP_Bool revertIfConflict, SCIP_Bool *conflict, int *hasharr)
Definition: graph_history.c:902
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_RETCODE graph_pseudoAncestors_appendMoveEdge(SCIP *scip, int edge_target, int edge_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1489
static void blockedAncestors_free(SCIP *scip, BLOCKANS **blockedans)
Definition: graph_history.c:197
void graph_knot_printPseudoAncestors(const GRAPH *g, int node)
Definition: graph_history.c:1226
static void blockedAncestors_freeBlock(SCIP *scip, int block_id, BLOCKANS *blockedans)
Definition: graph_history.c:168
static SCIP_Bool fixedPseudoAncestorsAreValid(SCIP *scip, const GRAPH *g)
Definition: graph_history.c:649
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
static SCIP_Bool blockedAncestors_hashIsHitBlock(const BLOCKANS *blockedans, int block_id, const int *hasharr)
Definition: graph_history.c:372
const int * graph_knot_getPseudoAncestors(const GRAPH *g, int node)
Definition: graph_history.c:1269
int graph_knot_nPseudoAncestors(const GRAPH *g, int node)
Definition: graph_history.c:1174
static SCIP_Bool ancestorsMarkConflict(const GRAPH *graph, int edge, int *ancestormark)
Definition: graph_history.c:88
SCIP_RETCODE graph_initContractTracing(SCIP *scip, GRAPH *graph)
Definition: graph_history.c:1836
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
SCIP_RETCODE graph_pseudoAncestors_appendCopyArrayToEdge(SCIP *scip, int edge_target, const int *ancestors, int nancestors, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1458
const int * graph_getFixpseudonodes(SCIP *scip, const GRAPH *g)
Definition: graph_history.c:1957
SCIP_RETCODE graph_copyFixed(SCIP *scip, GRAPH *g, SCIP_Bool moveFixedEdges, GRAPH *g_copy)
Definition: graph_history.c:1895
Definition: type_retcode.h:33
struct blocked_pseudo_ancestor BLOCKANS
static SCIP_RETCODE blockedAncestors_init(int nblocks, BLOCKANS **blockedans)
Definition: graph_history.c:132
SCIP_Bool graph_pseudoAncestors_nodeIsHashed(const PSEUDOANS *pseudoancestors, int node, const int *hasharr)
Definition: graph_history.c:962
SCIP_RETCODE graph_initAncestors(SCIP *scip, GRAPH *g)
Definition: graph_history.c:975
static SCIP_Bool blockedAncestors_blockIsValid(int block_id, const BLOCKANS *blockedans, int *hasharr)
Definition: graph_history.c:438
void graph_free_fixedEdgesOnly(SCIP *scip, GRAPH *g)
Definition: graph_history.c:1671
void graph_pseudoAncestors_unhashEdge(const PSEUDOANS *pseudoancestors, int edge, int *hasharr)
Definition: graph_history.c:854
void graph_pseudoAncestors_hashNode(const PSEUDOANS *pseudoancestors, int node, int *hasharr)
Definition: graph_history.c:840
static SCIP_RETCODE blockedAncestors_appendArray(SCIP *scip, int block_target, const int *ancestors_source, int size_source, SCIP_Bool breakOnConflict, int hasharr_size, BLOCKANS *blockedans_target, SCIP_Bool *conflict)
Definition: graph_history.c:458
static SCIP_Bool blockedAncestors_isValid(SCIP *scip, int hasharr_size, const BLOCKANS *blockedans)
Definition: graph_history.c:607
void graph_addPseudoAncestor(GRAPH *g, int *pseudoancestor)
Definition: graph_history.c:1293
static SCIP_Bool blockedAncestors_hashIsHit(const BLOCKANS *blockedans, int ancestor, const int *hasharr)
Definition: graph_history.c:357
void graph_knot_delPseudoAncestors(SCIP *scip, int node_free, GRAPH *g)
Definition: graph_history.c:1144
SCIP_RETCODE graph_initPseudoAncestors(SCIP *scip, GRAPH *g)
Definition: graph_history.c:1049
SCIP_RETCODE graph_fixed_add(SCIP *scip, IDX *edges, const int *pseudonodes, int npseudonodes, GRAPH *g)
Definition: graph_history.c:1698
SCIP_RETCODE graph_pseudoAncestors_appendCopyEdge(SCIP *scip, int edge_target, int edge_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1334
Definition: graphdefs.h:173
SCIP_RETCODE graph_pseudoAncestors_appendCopyNode(SCIP *scip, int node_target, int node_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1358
SCIP_Bool graph_valid_ancestors(SCIP *scip, const GRAPH *g)
Definition: graph_history.c:753
Definition: graph_history.c:34
Portable definitions.
static void blockedAncestors_hashDirty(const BLOCKANS *blockedans, int block_id, SCIP_Bool revertIfConflict, SCIP_Bool *conflict, int *hasharr)
Definition: graph_history.c:277
SCIP_RETCODE graph_fixed_addEdge(SCIP *scip, int edge, GRAPH *g)
Definition: graph_history.c:1760
static void blockedAncestors_unhashPartial(const BLOCKANS *blockedans, int block_id, int nAncestorsToClean, int *hasharr)
Definition: graph_history.c:250
static SCIP_RETCODE blockedAncestors_addAncestor(SCIP *scip, int block_target, int ancestor, int hasharr_size, BLOCKANS *blockedans)
Definition: graph_history.c:565
SCIP_RETCODE graph_pseudoAncestors_appendCopyNodeToEdge(SCIP *scip, int edge_target, int node_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1380
SCIP_RETCODE graph_pseudoAncestors_appendCopySingToEdge(SCIP *scip, int edge_target, const SINGLETONANS *source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1426
static void ancestorsUnmarkConflict(const GRAPH *graph, int edge, int *ancestormark)
Definition: graph_history.c:114
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1344
IDX * graph_edge_getAncestors(const GRAPH *g, int edge)
Definition: graph_history.c:1202
void graph_pseudoAncestors_unhashEdgeDirty(const PSEUDOANS *pseudoancestors, int edge, int *hasharr)
Definition: graph_history.c:918
int graph_getNfixpseudonodes(const GRAPH *g)
Definition: graph_history.c:1971
SCIP_RETCODE graph_fixed_addNodePc(SCIP *scip, int node, GRAPH *g)
Definition: graph_history.c:1778
Definition: graph_history.c:52
void graph_addPseudoAncestors(int nadd, GRAPH *g)
Definition: graph_history.c:1307
SCIP_Bool graph_pseudoAncestors_edgesInConflict(SCIP *scip, const GRAPH *g, const int *edges, int nedges)
Definition: graph_history.c:1010
void graph_pseudoAncestors_hashEdgeDirty(const PSEUDOANS *pseudoancestors, int edge, SCIP_Bool revertIfConflict, SCIP_Bool *conflict, int *hasharr)
Definition: graph_history.c:884
void graph_pseudoAncestors_hashEdge(const PSEUDOANS *pseudoancestors, int edge, int *hasharr)
Definition: graph_history.c:824
int graph_edge_nPseudoAncestors(const GRAPH *g, int edge)
Definition: graph_history.c:1159
int graph_getNpseudoAncestors(const GRAPH *g)
Definition: graph_history.c:1282
SCIP_RETCODE graph_initPseudoAncestorsSized(SCIP *scip, int nedges, GRAPH *g)
Definition: graph_history.c:1064
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
SCIP_RETCODE graph_pseudoAncestors_appendMoveNode(SCIP *scip, int node_target, int node_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
Definition: graph_history.c:1506
SCIP_RETCODE graph_pseudoAncestors_addToEdge(SCIP *scip, int edge_target, int ancestor, GRAPH *g)
Definition: graph_history.c:1523
int graph_contractTrace(int node, const GRAPH *graph)
Definition: graph_history.c:1872
void graph_pseudoAncestors_unhashNodeDirty(const PSEUDOANS *pseudoancestors, int node, int *hasharr)
Definition: graph_history.c:934
Definition: graph_history.c:43
SCIP_Bool graph_knot_hasContractTrace(int node, const GRAPH *graph)
Definition: graph_history.c:1859
void graph_edge_delPseudoAncestors(SCIP *scip, int edge_free, GRAPH *g)
Definition: graph_history.c:1128