75 for( i = 0; i <
nnodes; i++ )
101 STP_Vectype(
int) biconn_stack = cutnodes->biconn_stack;
103 assert(stack_start >= 0);
106 assert(biconn_comproot[ncomps] == -1);
107 assert(ncomps == 1 || biconn_comproot[ncomps - 1] != -1);
109 biconn_comproot[ncomps] = root;
111 for(
int size =
StpVecGetSize(biconn_stack); size != stack_start; size-- )
113 const int compnode = biconn_stack[size - 1];
118 assert(biconn_nodesmark[compnode] == 0);
119 assert(compnode != root);
121 biconn_nodesmark[compnode] = ncomps;
128 #ifdef USE_RECURSIVE_DFS 131 void cutNodesComputeRecursive(
138 #ifdef CUTTREE_PRINT_STATISTICS 139 int* childcount_terms = cutnodes->childcount_terms;
140 int* childcount_nodes = cutnodes->childcount_nodes;
145 int mylowpoint = myhittime;
150 nodes_hittime[node] = myhittime;
156 const int head = g->
head[e];
161 if( nodes_hittime[head] < 0 )
163 const int stack_start =
StpVecGetSize(cutnodes->biconn_stack);
166 cutNodesComputeRecursive(g, head, node, cutnodes);
168 #ifdef CUTTREE_PRINT_STATISTICS 169 childcount_nodes[node] += childcount_nodes[head] + 1;
170 childcount_terms[node] += childcount_terms[head] + (
Is_term(g->
term[head]) ? 1 : 0);
195 assert(nodes_hittime[head] >= 0);
196 if( mylowpoint > nodes_hittime[head] )
197 mylowpoint = nodes_hittime[head];
201 if( nodeIsRoot && nchildren > 1 )
223 const int stack_top = cutnodes->
stack_size - 1;
225 const int node = stack_top_data->
id;
232 if( isFirstNodeVisit )
235 assert(stack_top_data->
lowpoint == -1);
238 stack_top_data->
lowpoint = nodes_hittime[node];
245 const int head = g->
head[e];
250 if( nodes_hittime[head] < 0 )
252 assert(head != stack_top_data->
parent);
258 .biconnStart = -1, .lowpoint = -1, .isArtPoint =
FALSE };
259 childWasAdded =
TRUE;
262 else if( head != stack_top_data->
parent )
264 assert(nodes_hittime[head] >= 0);
265 if( stack_top_data->
lowpoint > nodes_hittime[head] ) {
266 SCIPdebugMessage(
"update my lowpoint to %d (from %d) \n", nodes_hittime[head], head);
267 stack_top_data->
lowpoint = nodes_hittime[head];
280 const int parent_pos = cutnodes->
stack_size - 1;
289 if( !isFirstNodeVisit ) {
291 assert(nodeIsRoot == (stack_top_data->
parent == -1));
320 if( !childWasAdded && stack_top_data->
isArtPoint ) {
336 const int root = cutnodes->
dfsroot;
356 const int lastroot = cutnodes->artpoints[
StpVecGetSize(cutnodes->artpoints) - 1];
372 const int*
const nodes = bidecomp->
nodes;
373 const int*
const starts = bidecomp->
starts;
378 for(
int i = 0; i < ncomps; i++ )
380 const int comp_start = starts[i];
381 const int comp_end = starts[i + 1];
382 const int comp_root = biconn_comproots[i];
384 assert(comp_start <= comp_end);
386 SCIPdebugMessage(
"component %d is of size %d (root=%d); nodes: \n", i, comp_end - comp_start,
389 for(
int j = comp_start; j != comp_end; j++ )
391 const int comp_node = nodes[j];
398 if( biconn_nodesmark[comp_node] != i )
402 for( k = 0; k < ncomps; k++ )
404 if( comp_node == biconn_comproots[k] )
413 printf(
"ERROR: no component root found \n");
434 int* RESTRICT nodes = bidecomp->
nodes;
435 int* RESTRICT starts = bidecomp->
starts;
441 for(
int i = 0; i <= ncomps; i++ )
444 for(
int i = 0; i <
nnodes; i++ )
448 const int compid = biconn_nodesmark[i];
449 assert(0 <= compid && compid < ncomps);
456 for(
int i = 0; i < ncomps; i++ )
458 const int comproot = biconn_comproots[i];
459 if( biconn_nodesmark[comproot] != i && g->
grad[comproot] > 0 )
463 for(
int i = 1; i <= ncomps; i++ )
464 starts[i] += starts[i - 1];
466 assert(starts[ncomps] == starts[ncomps - 1]);
469 for(
int i = 0; i <
nnodes; i++ )
473 const int compid = biconn_nodesmark[i];
474 assert(0 <= compid && compid < ncomps);
477 nodes[starts[compid]] = i;
479 assert(compid == 0 || starts[compid - 1] <= starts[compid]);
483 for(
int i = 0; i < ncomps; i++ )
485 const int comproot = biconn_comproots[i];
486 if( biconn_nodesmark[comproot] != i && g->
grad[comproot] > 0 )
489 nodes[starts[i]] = comproot;
493 assert(starts[0] == 0);
494 assert(starts[ncomps] <= nnodes + ncomps);
504 const GRAPH* orggraph,
508 const int*
const gMark = orggraph->
mark;
512 const int root = orggraph->
source;
523 for(
int i = 0; i <
nnodes; i++ )
524 nodes_isVisited[i] =
FALSE;
526 nodes_isVisited[root] =
TRUE;
540 const int head = orggraph->
head[
a];
542 if( !nodes_isVisited[head] )
546 assert(!markedIsFound);
548 markedIsFound =
TRUE;
553 nodes_isVisited[head] =
TRUE;
558 assert(markedIsFound);
581 int* biconn_nodesmark;
582 int* biconn_comproots;
590 #ifdef CUTTREE_PRINT_STATISTICS 592 int* childcount_nodes;
593 int* childcount_terms;
598 for(
int k = 0; k <
nnodes; k++ )
599 childcount_nodes[k] = 0;
601 for(
int k = 0; k <
nnodes; k++ )
602 childcount_terms[k] = 0;
604 cn->childcount_nodes = childcount_nodes;
605 cn->childcount_terms = childcount_terms;
614 for(
int k = 0; k <
nnodes; k++ )
615 nodes_hittime[k] = -1;
618 for(
int k = 0; k <
nnodes; k++ )
619 biconn_comproots[k] = -1;
622 for(
int k = 0; k <
nnodes; k++ )
623 biconn_nodesmark[k] = 0;
626 cn->artpoints =
NULL;
627 cn->biconn_stack =
NULL;
654 assert(scip && cutnodes);
666 #ifdef CUTTREE_PRINT_STATISTICS 691 #ifdef USE_RECURSIVE_DFS 692 cutNodesComputeRecursive(g, cutnodes->
dfsroot, -1, cutnodes);
723 assert(scip && cutnodes);
727 bidecomp = *bidecomposition;
732 bidecomp->
nodes = nodes;
733 bidecomp->
starts = starts;
749 assert(scip && g && bidecomposition);
766 assert(scip && bidecomposition);
768 bidecomp = *bidecomposition;
788 int*
const gMark = g->
mark;
791 const int*
const compnodes = bidecomp->
nodes;
792 const int compstart = bidecomp->
starts[compindex];
793 const int compend = bidecomp->
starts[compindex + 1];
796 for(
int i = 0; i <
nnodes; i++ )
801 for(
int i = compstart; i != compend; i++ )
803 const int compnode = compnodes[i];
808 if( contractionRecord[compnode] != -1 )
812 SCIPdebugMessage(
"(taking contracted node %d instead of %d:) \n", contractionRecord[compnode], compnode);
823 gMark[realnode] =
TRUE;
833 const GRAPH* orggraph,
834 const GRAPH* subgraph,
838 const int* nodemap_OrgToSub;
840 assert(bidecomp && orggraph && subroot);
851 *subroot = nodemap_OrgToSub[*subroot];
867 assert(0 <= compindex && compindex < bidecomp->nbicomps);
870 const int compstart = bidecomp->
starts[compindex];
871 const int compend = bidecomp->
starts[compindex + 1];
873 assert(compstart <= compend);
875 if( compend - compstart <= 1 )
877 SCIPdebugMessage(
"component %d is of size %d, SKIP! \n", compindex, compend - compstart);
891 #ifdef USE_RECURSIVE_DFS 894 const int*
const isMarked = g->
mark;
898 for(
int i = 0; i <
nnodes; i++ )
904 return (nnodes_real < 75000);
917 const int*
const starts = bidecomp->
starts;
919 const int ncomps = bidecomp->
nbicomps;
920 const int nallnodes = starts[ncomps] - starts[0];
924 assert(0 <= compindex && compindex < ncomps);
925 assert(nallnodes > 0);
927 compnnodes = starts[compindex + 1] - starts[compindex];
931 assert(
GE(ratio, 0.0));
942 const int*
const starts = bidecomp->
starts;
944 const int ncomps = bidecomp->
nbicomps;
945 const int ncompnodes = starts[ncomps] - starts[0];
946 int maxcompnnodes = 0;
949 assert(0 < ncompnodes);
953 for(
int i = 0; i < ncomps; i++ )
955 const int compnnodes = starts[i + 1] - starts[i];
956 if( maxcompnnodes < compnnodes )
957 maxcompnnodes = compnnodes;
965 assert(
GT(maxratio, 0.0));
#define STP_Vectype(type)
#define StpVecGetSize(vec)
int graph_knot_getContractionRecordAncestor(int, const SUBINOUT *)
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
SCIP_Bool bidecomposition_isPossible(const GRAPH *g)
#define SCIPfreeMemoryArray(scip, ptr)
static void cutNodesProcessNext(const GRAPH *g, CUTNODES *cutnodes)
#define SCIPallocMemoryArray(scip, ptr, num)
static void cutNodesComputePostProcess(const GRAPH *g, CUTNODES *cutnodes)
const int * graph_subinoutGetContractionRecord(const SUBINOUT *)
void graph_knot_printInfo(const GRAPH *, int)
void graph_subinoutFree(SCIP *, SUBINOUT **)
enum SCIP_Retcode SCIP_RETCODE
void bidecomposition_free(SCIP *scip, BIDECOMP **bidecomposition)
#define StpVecPopBack(vec)
#define StpVecReserve(scip, vec, _size_)
#define SCIPfreeBufferArray(scip, ptr)
struct biconnected_stack_node STACK_NODE
static void cutNodesSetDfsRoot(const GRAPH *g, CUTNODES *cutnodes)
header only, simple implementation of an STL like vector
several decomposition methods for Steiner tree problems
SCIP_Real bidecomposition_getCompNodeRatio(const BIDECOMP *bidecomp, int compindex)
static void decomposeBuildCsr(const CUTNODES *cutnodes, const GRAPH *g, BIDECOMP *bidecomp)
void bidecomposition_markSub(const BIDECOMP *bidecomp, int compindex, GRAPH *g)
#define StpVecGetcapacity(vec)
void bidecomposition_cutnodesCompute(const GRAPH *g, CUTNODES *cutnodes)
static SCIP_Bool decomposeCsrIsValid(const CUTNODES *cutnodes, const GRAPH *g, const BIDECOMP *bidecomp)
SCIP_Real bidecomposition_getMaxcompNodeRatio(const BIDECOMP *bidecomp)
SCIP_RETCODE bidecomposition_cutnodesInit(SCIP *scip, const GRAPH *g, CUTNODES **cutnodes)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE bidecomposition_initSubInOut(SCIP *scip, const GRAPH *g, BIDECOMP *bidecomposition)
SCIP_Bool graph_isMarked(const GRAPH *)
static void cutNodesCompute(const GRAPH *g, CUTNODES *cutnodes)
const int * graph_subinoutGetOrgToSubNodeMap(const SUBINOUT *)
static void cutNodesProcessComponent(int root, int stack_start, CUTNODES *cutnodes)
void bidecomposition_cutnodesFree(SCIP *scip, CUTNODES **cutnodes)
#define StpVecIsEmpty(vec)
#define SCIPfreeMemory(scip, ptr)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_RETCODE graph_subinoutInit(SCIP *, const GRAPH *, SUBINOUT **)
static SCIP_RETCODE decomposeGetFirstMarked(SCIP *scip, const GRAPH *orggraph, int *subroot)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define StpVecFree(scip, vec)
int graph_get_nNodes(const GRAPH *)
#define SCIPallocMemory(scip, ptr)
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
#define StpVecPushBack(scip, vec, value)
SCIP_Bool bidecomposition_componentIsTrivial(const BIDECOMP *bidecomp, int compindex)
SCIP_RETCODE bidecomposition_getMarkedSubRoot(SCIP *scip, const BIDECOMP *bidecomp, const GRAPH *orggraph, const GRAPH *subgraph, int *subroot)
SCIP_RETCODE bidecomposition_init(SCIP *scip, const CUTNODES *cutnodes, const GRAPH *g, BIDECOMP **bidecomposition)