Scippy

SCIP

Solving Constraint Integer Programs

bidecomposition.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file bidecomposition.c
17  * @brief several decomposition methods for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements bi-connected components decomposition methods for several Steiner problems.
21  *
22  * A list of all interface methods can be found in bidecomposition.h.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 //#define SCIP_DEBUG
28 
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <assert.h>
33 #include "bidecomposition.h"
34 #include "stpvector.h"
35 #include "portab.h"
36 
37 /*
38  * Data structures
39  */
40 
42  int id; /**< node ID in the underlying graph */
43  int parent; /**< parent in the underlying graph */
44  int nextEdge; /**< next edge in the underlying graph */
45  int biconnStart; /**< start of current component in separate stack */
46  int lowpoint; /**< low-point of this node */
47  SCIP_Bool isArtPoint; /**< is articulation point? */
48 };
49 
50 
51 /*
52  * Local methods
53  */
54 
55 
56 /** sets root */
57 static inline
59  const GRAPH* g, /**< graph data structure */
60  CUTNODES* cutnodes /**< cut nodes */
61  )
62 {
63  if( !graph_pc_isPcMw(g) )
64  {
65  cutnodes->dfsroot = g->source;
66  }
67  else
68  {
69  int i;
70  const int nnodes = graph_get_nNodes(g);
71  const int pseudoroot = graph_pc_isRootedPcMw(g) ? -1 : g->source;
72 
73  assert(!g->extended);
74 
75  for( i = 0; i < nnodes; i++ )
76  {
77  if( Is_term(g->term[i]) && i != pseudoroot)
78  {
79  assert(!graph_pc_knotIsDummyTerm(g, i));
80  cutnodes->dfsroot = i;
81  break;
82  }
83  }
84 
85  assert(i < nnodes);
86  }
87 }
88 
89 
90 /** processes bi-connected component */
91 static
93  int root, /**< root of component */
94  int stack_start, /**< start of component in the stack */
95  CUTNODES* cutnodes /**< cut nodes */
96  )
97 {
98  const int ncomps = ++(cutnodes->biconn_ncomps);
99  int* biconn_nodesmark = cutnodes->biconn_nodesmark;
100  int* biconn_comproot = cutnodes->biconn_comproots;
101  STP_Vectype(int) biconn_stack = cutnodes->biconn_stack;
102 
103  assert(stack_start >= 0);
104  assert(StpVecGetSize(biconn_stack) > stack_start);
105  assert(ncomps > 0);
106  assert(biconn_comproot[ncomps] == -1);
107  assert(ncomps == 1 || biconn_comproot[ncomps - 1] != -1);
108 
109  biconn_comproot[ncomps] = root;
110 
111  for( int size = StpVecGetSize(biconn_stack); size != stack_start; size-- )
112  {
113  const int compnode = biconn_stack[size - 1];
114  SCIPdebugMessage("%d \n", compnode);
115 
116  assert(size >= 1);
117  assert(size == StpVecGetSize(biconn_stack));
118  assert(biconn_nodesmark[compnode] == 0);
119  assert(compnode != root);
120 
121  biconn_nodesmark[compnode] = ncomps;
122  StpVecPopBack(biconn_stack);
123  }
124 }
125 
126 
127 //#define USE_RECURSIVE_DFS
128 #ifdef USE_RECURSIVE_DFS
129 /** recursive DFS */
130 static
131 void cutNodesComputeRecursive(
132  const GRAPH* g, /**< graph data structure */
133  int node, /**< vertex */
134  int parent, /**< parent of node */
135  CUTNODES* cutnodes /**< cut nodes */
136  )
137 {
138 #ifdef CUTTREE_PRINT_STATISTICS
139  int* childcount_terms = cutnodes->childcount_terms;
140  int* childcount_nodes = cutnodes->childcount_nodes;
141 #endif
142 
143  int* const nodes_hittime = cutnodes->nodes_hittime;
144  const int myhittime = cutnodes->curr_hittime;
145  int mylowpoint = myhittime;
146  int nchildren = 0;
147  SCIP_Bool isCutNode = FALSE;
148  const SCIP_Bool nodeIsRoot = (parent == -1);
149 
150  nodes_hittime[node] = myhittime;
151  (cutnodes->curr_hittime)++;
152  StpVecPushBack(cutnodes->scip, cutnodes->biconn_stack, node);
153 
154  for( int e = g->outbeg[node]; e != EAT_LAST; e = g->oeat[e] )
155  {
156  const int head = g->head[e];
157  if( !g->mark[head] )
158  continue;
159 
160  /* not visited? */
161  if( nodes_hittime[head] < 0 )
162  {
163  const int stack_start = StpVecGetSize(cutnodes->biconn_stack);
164  assert(head != parent);
165 
166  cutNodesComputeRecursive(g, head, node, cutnodes);
167 
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);
171 #endif
172  if( nodeIsRoot )
173  {
174  nchildren++;
175 
176  if( nchildren > 1 )
177  {
178  SCIPdebugMessage("mark new bi-connected component from root \n");
179  cutNodesProcessComponent(node, stack_start, cutnodes);
180  }
181  }
182  else if( cutnodes->curr_lowpoint >= myhittime )
183  {
184  isCutNode = TRUE;
185 
186  SCIPdebugMessage("mark new bi-connected component from %d \n", node);
187  cutNodesProcessComponent(node, stack_start, cutnodes);
188  }
189 
190  if( mylowpoint > cutnodes->curr_lowpoint )
191  mylowpoint = cutnodes->curr_lowpoint;
192  }
193  else if( head != parent )
194  {
195  assert(nodes_hittime[head] >= 0);
196  if( mylowpoint > nodes_hittime[head] )
197  mylowpoint = nodes_hittime[head];
198  }
199  }
200 
201  if( nodeIsRoot && nchildren > 1 )
202  {
203  assert(!isCutNode);
204  isCutNode = TRUE;
205  SCIPdebugMessage("found parent cut node: %d \n", node);
206  }
207 
208  if( isCutNode )
209  {
210  StpVecPushBack(cutnodes->scip, cutnodes->artpoints, node);
211  }
212 
213  cutnodes->curr_lowpoint = mylowpoint;
214 }
215 #else
216 /** non-recursive DFS-based biconnected components helper */
217 static
219  const GRAPH* g, /**< graph data structure */
220  CUTNODES* cutnodes /**< cut nodes */
221  )
222 {
223  const int stack_top = cutnodes->stack_size - 1;
224  STACK_NODE* stack_top_data = &(cutnodes->stack_nodes[stack_top]);
225  const int node = stack_top_data->id;
226  int* const nodes_hittime = cutnodes->nodes_hittime;
227  int e;
228  SCIP_Bool childWasAdded = FALSE;
229  const SCIP_Bool isFirstNodeVisit = (stack_top_data->nextEdge == g->outbeg[node]);
230  SCIPdebugMessage("processing node %d, global hit-time=%d \n", node, cutnodes->curr_hittime);
231 
232  if( isFirstNodeVisit )
233  {
234  assert(StpVecGetSize(cutnodes->biconn_stack) < StpVecGetcapacity(cutnodes->biconn_stack));
235  assert(stack_top_data->lowpoint == -1);
236 
237  nodes_hittime[node] = (cutnodes->curr_hittime)++;
238  stack_top_data->lowpoint = nodes_hittime[node];
239  StpVecPushBack(cutnodes->scip, cutnodes->biconn_stack, node);
240  assert(!stack_top_data->isArtPoint);
241  }
242 
243  for( e = stack_top_data->nextEdge; e != EAT_LAST; e = g->oeat[e] )
244  {
245  const int head = g->head[e];
246  if( !g->mark[head] )
247  continue;
248 
249  /* not visited? */
250  if( nodes_hittime[head] < 0 )
251  {
252  assert(head != stack_top_data->parent);
253  assert(cutnodes->stack_size < g->knots);
254 
255  /* add child node to stack */
256  cutnodes->stack_nodes[cutnodes->stack_size++] =
257  (STACK_NODE) { .id = head, .parent = node, .nextEdge = g->outbeg[head],
258  .biconnStart = -1, .lowpoint = -1, .isArtPoint = FALSE };
259  childWasAdded = TRUE;
260  break;
261  }
262  else if( head != stack_top_data->parent )
263  {
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];
268  }
269  }
270  }
271  stack_top_data->nextEdge = (e != EAT_LAST) ? g->oeat[e] : EAT_LAST;
272 
273  /* are we finished with this node? */
274  if( !childWasAdded )
275  {
276  cutnodes->stack_size--;
277 
278  if( cutnodes->stack_size > 0 ) {
279  /* update hit-time of parent */
280  const int parent_pos = cutnodes->stack_size - 1;
281  if( cutnodes->stack_nodes[parent_pos].lowpoint > stack_top_data->lowpoint ) {
282  SCIPdebugMessage("update parent(%d) current lowpoint to %d \n", cutnodes->stack_nodes[parent_pos].id, stack_top_data->lowpoint);
283  cutnodes->stack_nodes[parent_pos].lowpoint = stack_top_data->lowpoint;
284  }
285  }
286  SCIPdebugMessage("finished node %d \n", node);
287  }
288 
289  if( !isFirstNodeVisit ) {
290  const SCIP_Bool nodeIsRoot = (node == cutnodes->dfsroot);
291  assert(nodeIsRoot == (stack_top_data->parent == -1));
292  SCIPdebugMessage("return to node %d, cutnodes->curr_lowpoint=%d \n", node, cutnodes->curr_lowpoint);
293 
294  if( nodeIsRoot )
295  {
296  assert(cutnodes->nrootcomps >= 0);
297  cutnodes->nrootcomps++;
298 
299  /* is root an articulation point? */
300  if( cutnodes->nrootcomps > 1 )
301  {
302  SCIPdebugMessage("mark new bi-connected component from root \n");
303  cutNodesProcessComponent(node, stack_top_data->biconnStart, cutnodes);
304 
305  /* have we detected for the first time that root is an articulation point? */
306  if( cutnodes->nrootcomps == 2 ) {
307  assert(!stack_top_data->isArtPoint);
308  stack_top_data->isArtPoint = TRUE;
309  }
310  }
311  }
312  else if( cutnodes->curr_lowpoint >= nodes_hittime[node] )
313  {
314  SCIPdebugMessage("mark new bi-connected component from %d \n", node);
315  cutNodesProcessComponent(node, stack_top_data->biconnStart, cutnodes);
316  stack_top_data->isArtPoint = TRUE;
317  }
318  }
319 
320  if( !childWasAdded && stack_top_data->isArtPoint ) {
321  StpVecPushBack(cutnodes->scip, cutnodes->artpoints, node);
322  }
323 
324  stack_top_data->biconnStart = StpVecGetSize(cutnodes->biconn_stack);
325  cutnodes->curr_lowpoint = stack_top_data->lowpoint;
326 }
327 
328 
329 /** non-recursive DFS */
330 static
332  const GRAPH* g, /**< graph data structure */
333  CUTNODES* cutnodes /**< cut nodes */
334  )
335 {
336  const int root = cutnodes->dfsroot;
337  assert(graph_knot_isInRange(g, root));
338  cutnodes->stack_nodes[0] = (STACK_NODE) { .id = root, .parent = -1, .nextEdge = g->outbeg[root], .biconnStart = -1, .lowpoint = -1, .isArtPoint = FALSE };
339  cutnodes->stack_size = 1;
340  SCIPdebugMessage("start bidecomposition check with node %d \n", root);
341 
342  while( cutnodes->stack_size > 0 )
343  {
344  cutNodesProcessNext(g, cutnodes);
345  }
346 }
347 #endif
348 
349 /** post-process */
350 static
352  const GRAPH* g, /**< graph data structure */
353  CUTNODES* cutnodes /**< cut nodes */
354  )
355 {
356  const int lastroot = cutnodes->artpoints[StpVecGetSize(cutnodes->artpoints) - 1];
357  assert(cutnodes->biconn_comproots[0] == -1);
358 
359  cutnodes->biconn_comproots[0] = lastroot;
360  cutnodes->biconn_ncomps++;
361 }
362 
363 #ifndef NDEBUG
364 /** builds CSR like arrays for biconnected components */
365 static
367  const CUTNODES* cutnodes, /**< cut nodes */
368  const GRAPH* g, /**< graph data structure */
369  const BIDECOMP* bidecomp /**< bi-decomposition structure */
370  )
371 {
372  const int* const nodes = bidecomp->nodes;
373  const int* const starts = bidecomp->starts;
374  const int* const biconn_nodesmark = cutnodes->biconn_nodesmark;
375  const int* const biconn_comproots = cutnodes->biconn_comproots;
376  const int ncomps = cutnodes->biconn_ncomps;
377 
378  for( int i = 0; i < ncomps; i++ )
379  {
380  const int comp_start = starts[i];
381  const int comp_end = starts[i + 1];
382  const int comp_root = biconn_comproots[i];
383 
384  assert(comp_start <= comp_end);
385 
386  SCIPdebugMessage("component %d is of size %d (root=%d); nodes: \n", i, comp_end - comp_start,
387  comp_root);
388 
389  for( int j = comp_start; j != comp_end; j++ )
390  {
391  const int comp_node = nodes[j];
392  assert(graph_knot_isInRange(g, comp_node));
393 
394 #ifdef SCIP_DEBUG
395  graph_knot_printInfo(g, comp_node);
396 #endif
397 
398  if( biconn_nodesmark[comp_node] != i )
399  {
400  int k = 0;
401  SCIP_Bool isCompRoot = FALSE;
402  for( k = 0; k < ncomps; k++ )
403  {
404  if( comp_node == biconn_comproots[k] )
405  {
406  isCompRoot = TRUE;
407  break;
408  }
409  }
410 
411  if( !isCompRoot )
412  {
413  printf("ERROR: no component root found \n");
414  return FALSE;
415  }
416  }
417  }
418  }
419 
420  return TRUE;
421 }
422 
423 #endif
424 
425 
426 /** builds CSR like arrays for biconnected components */
427 static
429  const CUTNODES* cutnodes, /**< cut nodes */
430  const GRAPH* g, /**< graph data structure */
431  BIDECOMP* bidecomp /**< bidecomposition data structure */
432  )
433 {
434  int* RESTRICT nodes = bidecomp->nodes;
435  int* RESTRICT starts = bidecomp->starts;
436  const int* const biconn_nodesmark = cutnodes->biconn_nodesmark;
437  const int* const biconn_comproots = cutnodes->biconn_comproots;
438  const int ncomps = cutnodes->biconn_ncomps;
439  const int nnodes = graph_get_nNodes(g);
440 
441  for( int i = 0; i <= ncomps; i++ )
442  starts[i] = 0;
443 
444  for( int i = 0; i < nnodes; i++ )
445  {
446  if( g->mark[i] && g->grad[i] > 0 )
447  {
448  const int compid = biconn_nodesmark[i];
449  assert(0 <= compid && compid < ncomps);
450 
451  starts[compid]++;
452  }
453  }
454 
455  /* we also need to count the component roots */
456  for( int i = 0; i < ncomps; i++ )
457  {
458  const int comproot = biconn_comproots[i];
459  if( biconn_nodesmark[comproot] != i && g->grad[comproot] > 0 )
460  starts[i]++;
461  }
462 
463  for( int i = 1; i <= ncomps; i++ )
464  starts[i] += starts[i - 1];
465 
466  assert(starts[ncomps] == starts[ncomps - 1]);
467 
468  /* now fill the values in */
469  for( int i = 0; i < nnodes; i++ )
470  {
471  if( g->mark[i] && g->grad[i] > 0 )
472  {
473  const int compid = biconn_nodesmark[i];
474  assert(0 <= compid && compid < ncomps);
475 
476  starts[compid]--;
477  nodes[starts[compid]] = i;
478 
479  assert(compid == 0 || starts[compid - 1] <= starts[compid]);
480  }
481  }
482 
483  for( int i = 0; i < ncomps; i++ )
484  {
485  const int comproot = biconn_comproots[i];
486  if( biconn_nodesmark[comproot] != i && g->grad[comproot] > 0 )
487  {
488  starts[i]--;
489  nodes[starts[i]] = comproot;
490  }
491  }
492 
493  assert(starts[0] == 0);
494  assert(starts[ncomps] <= nnodes + ncomps);
495 
496  assert(decomposeCsrIsValid(cutnodes, g, bidecomp));
497 }
498 
499 
500 /** gets first marked component */
501 static
503  SCIP* scip, /**< SCIP data structure */
504  const GRAPH* orggraph, /**< graph data structure */
505  int* subroot /**< the new root (out) */
506  )
507 {
508  const int* const gMark = orggraph->mark;
509  STP_Bool* nodes_isVisited;
510  STP_Vectype(int) stack = NULL;
511  const int nnodes = graph_get_nNodes(orggraph);
512  const int root = orggraph->source;
513  SCIP_Bool markedIsFound = FALSE;
514 
515  if( gMark[root] )
516  {
517  *subroot = root;
518  return SCIP_OKAY;
519  }
520 
521  SCIP_CALL( SCIPallocBufferArray(scip, &nodes_isVisited, nnodes) );
522 
523  for( int i = 0; i < nnodes; i++ )
524  nodes_isVisited[i] = FALSE;
525 
526  nodes_isVisited[root] = TRUE;
527  StpVecPushBack(scip, stack, root);
528 
529  /* DFS loop */
530  while( !StpVecIsEmpty(stack) && !markedIsFound )
531  {
532  const int node = stack[StpVecGetSize(stack) - 1];
533  assert(StpVecGetSize(stack) >= 1);
534  StpVecPopBack(stack);
535 
536  assert(graph_knot_isInRange(orggraph, node));
537 
538  for( int a = orggraph->outbeg[node]; a != EAT_LAST; a = orggraph->oeat[a] )
539  {
540  const int head = orggraph->head[a];
541 
542  if( !nodes_isVisited[head] )
543  {
544  if( gMark[head] )
545  {
546  assert(!markedIsFound);
547 
548  markedIsFound = TRUE;
549  *subroot = head;
550  break;
551  }
552  StpVecPushBack(scip, stack, head);
553  nodes_isVisited[head] = TRUE;
554  }
555  }
556  }
557 
558  assert(markedIsFound);
559 
560  StpVecFree(scip, stack);
561  SCIPfreeBufferArray(scip, &nodes_isVisited);
562 
563  return SCIP_OKAY;
564 }
565 
566 
567 /*
568  * Interface methods
569  */
570 
571 
572 /** initializes */
574  SCIP* scip, /**< SCIP data structure */
575  const GRAPH* g, /**< graph data structure */
576  CUTNODES** cutnodes /**< cut nodes */
577  )
578 {
579  CUTNODES* cn;
580  int* nodes_hittime;
581  int* biconn_nodesmark;
582  int* biconn_comproots;
583  const int nnodes = graph_get_nNodes(g);
584 
585  assert(scip);
586 
587  SCIP_CALL( SCIPallocMemory(scip, cutnodes) );
588  cn = *cutnodes;
589 
590 #ifdef CUTTREE_PRINT_STATISTICS
591  {
592  int* childcount_nodes;
593  int* childcount_terms;
594 
595  SCIP_CALL( SCIPallocMemoryArray(scip, &childcount_nodes, nnodes) );
596  SCIP_CALL( SCIPallocMemoryArray(scip, &childcount_terms, nnodes) );
597 
598  for( int k = 0; k < nnodes; k++ )
599  childcount_nodes[k] = 0;
600 
601  for( int k = 0; k < nnodes; k++ )
602  childcount_terms[k] = 0;
603 
604  cn->childcount_nodes = childcount_nodes;
605  cn->childcount_terms = childcount_terms;
606  }
607 #endif
608 
609  SCIP_CALL( SCIPallocMemoryArray(scip, &biconn_comproots, nnodes) );
610  SCIP_CALL( SCIPallocMemoryArray(scip, &biconn_nodesmark, nnodes) );
611  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes_hittime, nnodes) );
612  SCIP_CALL( SCIPallocMemoryArray(scip, &cn->stack_nodes, nnodes) );
613 
614  for( int k = 0; k < nnodes; k++ )
615  nodes_hittime[k] = -1;
616 
617 #ifndef NDEBUG
618  for( int k = 0; k < nnodes; k++ )
619  biconn_comproots[k] = -1;
620 #endif
621 
622  for( int k = 0; k < nnodes; k++ )
623  biconn_nodesmark[k] = 0;
624 
625  cn->scip = scip;
626  cn->artpoints = NULL;
627  cn->biconn_stack = NULL;
628  cn->biconn_comproots = biconn_comproots;
629  cn->biconn_nodesmark = biconn_nodesmark;
630  cn->nodes_hittime = nodes_hittime;
631  cn->stack_size = 0;
632  cn->biconn_ncomps = 0;
633  cn->dfsroot = -1;
634  cn->curr_lowpoint = -1;
635  cn->curr_hittime = -1;
636  cn->nrootcomps = -1;
637 
638  cutNodesSetDfsRoot(g, cn);
639 
640  StpVecReserve(scip, cn->biconn_stack, nnodes);
641 
642  return SCIP_OKAY;
643 }
644 
645 
646 /** exits */
648  SCIP* scip, /**< SCIP data structure */
649  CUTNODES** cutnodes /**< cut nodes */
650  )
651 {
652  CUTNODES* cn;
653 
654  assert(scip && cutnodes);
655  cn = *cutnodes;
656  assert(cn);
657 
658  StpVecFree(scip, cn->artpoints);
659  StpVecFree(scip, cn->biconn_stack);
660 
661  SCIPfreeMemoryArray(scip, &(cn->stack_nodes));
664  SCIPfreeMemoryArray(scip, &(cn->nodes_hittime));
665 
666 #ifdef CUTTREE_PRINT_STATISTICS
667  SCIPfreeMemoryArray(scip, &(cn->childcount_terms));
668  SCIPfreeMemoryArray(scip, &(cn->childcount_nodes));
669 #endif
670 
671  SCIPfreeMemory(scip, cutnodes);
672 }
673 
674 
675 /** computes cut-nodes and (implicitly) bi-connected components */
677  const GRAPH* g, /**< graph data structure */
678  CUTNODES* cutnodes /**< cut nodes */
679  )
680 {
681  assert(cutnodes);
682  assert(StpVecGetSize(cutnodes->biconn_stack) == 0);
683  assert(StpVecGetSize(cutnodes->artpoints) == 0);
684  assert(cutnodes->curr_lowpoint == -1);
685 
686  cutnodes->curr_hittime = 0;
687  cutnodes->nrootcomps = 0;
688  /* NOTE: we assume the graph to be connected, so we only do the DFS once */
689  /* todo make it non-recursive, otherwise it might crash for big graphs! */
690  SCIPdebugMessage("starting DFS from %d \n", cutnodes->dfsroot);
691 #ifdef USE_RECURSIVE_DFS
692  cutNodesComputeRecursive(g, cutnodes->dfsroot, -1, cutnodes);
693 #else
694  cutNodesCompute(g, cutnodes);
695 #endif
696 
697  SCIPdebugMessage("number of cut nodes: %d \n", StpVecGetSize(cutnodes->artpoints));
698  assert(cutnodes->biconn_ncomps >= StpVecGetSize(cutnodes->artpoints));
699 
700  if( cutnodes->biconn_ncomps > 0 )
701  {
702  assert(StpVecGetSize(cutnodes->artpoints) > 0);
703  cutNodesComputePostProcess(g, cutnodes);
704 
705  SCIPdebugMessage("%d bi-connected components found! \n", cutnodes->biconn_ncomps);
706  }
707 }
708 
709 /** initializes */
711  SCIP* scip, /**< SCIP data structure */
712  const CUTNODES* cutnodes, /**< cut nodes */
713  const GRAPH* g, /**< graph data structure */
714  BIDECOMP** bidecomposition /**< bidecomposition data structure */
715  )
716 {
717  BIDECOMP* bidecomp;
718  int* nodes;
719  int* starts;
720  const int nnodes = graph_get_nNodes(g);
721  const int ncomps = cutnodes->biconn_ncomps;
722 
723  assert(scip && cutnodes);
724  assert(ncomps >= 2);
725 
726  SCIP_CALL( SCIPallocMemory(scip, bidecomposition) );
727  bidecomp = *bidecomposition;
728 
729  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes, nnodes + ncomps) );
730  SCIP_CALL( SCIPallocMemoryArray(scip, &starts, ncomps + 1) );
731  bidecomp->subinout = NULL;
732  bidecomp->nodes = nodes;
733  bidecomp->starts = starts;
734  bidecomp->nbicomps = ncomps;
735 
736  decomposeBuildCsr(cutnodes, g, bidecomp);
737 
738  return SCIP_OKAY;
739 }
740 
741 
742 /** initializes */
744  SCIP* scip, /**< SCIP data structure */
745  const GRAPH* g, /**< graph data structure */
746  BIDECOMP* bidecomposition /**< bidecomposition data structure */
747  )
748 {
749  assert(scip && g && bidecomposition);
750  assert(!bidecomposition->subinout);
751 
752  SCIP_CALL( graph_subinoutInit(scip, g, &(bidecomposition->subinout)) );
753 
754  return SCIP_OKAY;
755 }
756 
757 
758 /** frees */
760  SCIP* scip, /**< SCIP data structure */
761  BIDECOMP** bidecomposition /**< bidecomposition data structure */
762  )
763 {
764  BIDECOMP* bidecomp;
765 
766  assert(scip && bidecomposition);
767 
768  bidecomp = *bidecomposition;
769  assert(bidecomp);
770 
771  if( bidecomp->subinout )
772  graph_subinoutFree(scip, &(bidecomp->subinout));
773 
774  SCIPfreeMemoryArray(scip, &(bidecomp->starts));
775  SCIPfreeMemoryArray(scip, &(bidecomp->nodes));
776 
777  SCIPfreeMemory(scip, bidecomposition);
778 }
779 
780 
781 /** marks subgraph of given component index */
783  const BIDECOMP* bidecomp, /**< all-components storage */
784  int compindex, /**< component index */
785  GRAPH* g /**< graph data structure */
786  )
787 {
788  int* const gMark = g->mark;
789  const SUBINOUT* const subinout = bidecomp->subinout;
790  const int* const contractionRecord = graph_subinoutGetContractionRecord(subinout);
791  const int* const compnodes = bidecomp->nodes;
792  const int compstart = bidecomp->starts[compindex];
793  const int compend = bidecomp->starts[compindex + 1];
794  const int nnodes = graph_get_nNodes(g);
795 
796  for( int i = 0; i < nnodes; i++ )
797  gMark[i] = FALSE;
798 
799  SCIPdebugMessage("marking subgraph: \n");
800 
801  for( int i = compstart; i != compend; i++ )
802  {
803  const int compnode = compnodes[i];
804  int realnode;
805 
806  assert(graph_knot_isInRange(g, compnode));
807 
808  if( contractionRecord[compnode] != -1 )
809  {
810  realnode = graph_knot_getContractionRecordAncestor(compnode, subinout);
811 
812  SCIPdebugMessage("(taking contracted node %d instead of %d:) \n", contractionRecord[compnode], compnode);
813  }
814  else
815  {
816  realnode = compnode;
817  }
818 #ifdef SCIP_DEBUG
819  graph_knot_printInfo(g, realnode);
820 #endif
821 
822  assert(graph_knot_isInRange(g, realnode));
823  gMark[realnode] = TRUE;
824  }
825 }
826 
827 
828 /** gets root of marked sub-component
829  * bidecomposition_markSub needs to be called before! */
831  SCIP* scip, /**< SCIP data structure */
832  const BIDECOMP* bidecomp, /**< all-components storage */
833  const GRAPH* orggraph, /**< graph data structure */
834  const GRAPH* subgraph, /**< graph data structure */
835  int* subroot /**< the new root (out) */
836  )
837 {
838  const int* nodemap_OrgToSub;
839 
840  assert(bidecomp && orggraph && subroot);
841  assert(bidecomp->subinout);
842 
843  *subroot = -1;
844 
845  SCIP_CALL( decomposeGetFirstMarked(scip, orggraph, subroot) );
846 
847  assert(graph_knot_isInRange(orggraph, *subroot));
848  assert(Is_term(orggraph->term[*subroot]));
849 
850  nodemap_OrgToSub = graph_subinoutGetOrgToSubNodeMap(bidecomp->subinout);
851  *subroot = nodemap_OrgToSub[*subroot];
852 
853  assert(graph_knot_isInRange(subgraph, *subroot));
854  assert(Is_term(subgraph->term[*subroot]));
855 
856  return SCIP_OKAY;
857 }
858 
859 
860 /** component consisting of at most one node? */
862  const BIDECOMP* bidecomp, /**< all-components storage */
863  int compindex /**< component index */
864  )
865 {
866  assert(bidecomp);
867  assert(0 <= compindex && compindex < bidecomp->nbicomps);
868 
869  {
870  const int compstart = bidecomp->starts[compindex];
871  const int compend = bidecomp->starts[compindex + 1];
872 
873  assert(compstart <= compend);
874 
875  if( compend - compstart <= 1 )
876  {
877  SCIPdebugMessage("component %d is of size %d, SKIP! \n", compindex, compend - compstart);
878  return TRUE;
879  }
880  }
881 
882  return FALSE;
883 }
884 
885 
886 /** checks whether bidecomposition check is possible */
888  const GRAPH* g /**< graph data structure */
889  )
890 {
891 #ifdef USE_RECURSIVE_DFS
892  int nnodes_real = 0;
893  const int nnodes = graph_get_nNodes(g);
894  const int* const isMarked = g->mark;
895 
896  assert(graph_isMarked(g));
897 
898  for( int i = 0; i < nnodes; i++ )
899  {
900  if( isMarked[i] )
901  nnodes_real++;
902  }
903 
904  return (nnodes_real < 75000);
905 #else
906  return TRUE;
907 #endif
908 }
909 
910 
911 /** returns nodes ratio of component and the remaining graph */
913  const BIDECOMP* bidecomp, /**< bidecomposition data structure */
914  int compindex /**< component index */
915  )
916 {
917  const int* const starts = bidecomp->starts;
918  SCIP_Real ratio;
919  const int ncomps = bidecomp->nbicomps;
920  const int nallnodes = starts[ncomps] - starts[0];
921  int compnnodes;
922 
923  assert(bidecomp);
924  assert(0 <= compindex && compindex < ncomps);
925  assert(nallnodes > 0);
926 
927  compnnodes = starts[compindex + 1] - starts[compindex];
928  ratio = (SCIP_Real) compnnodes / (SCIP_Real) nallnodes;
929 
930  SCIPdebugMessage("component nodes ratio: %f \n", ratio);
931  assert(GE(ratio, 0.0));
932 
933  return (ratio);
934 }
935 
936 
937 /** returns ratio of nodes of maximum component and the remaining graph */
939  const BIDECOMP* bidecomp /**< bidecomposition data structure */
940  )
941 {
942  const int* const starts = bidecomp->starts;
943  SCIP_Real maxratio;
944  const int ncomps = bidecomp->nbicomps;
945  const int ncompnodes = starts[ncomps] - starts[0];
946  int maxcompnnodes = 0;
947 
948  assert(bidecomp);
949  assert(0 < ncompnodes);
950 
951  SCIPdebugMessage("all component nodes=%d \n", ncompnodes);
952 
953  for( int i = 0; i < ncomps; i++ )
954  {
955  const int compnnodes = starts[i + 1] - starts[i];
956  if( maxcompnnodes < compnnodes )
957  maxcompnnodes = compnnodes;
958  }
959 
960  maxratio = (SCIP_Real) maxcompnnodes / (SCIP_Real) ncompnodes;
961 
962  SCIPdebugMessage("max. component number of nodes=%d \n", maxcompnnodes);
963  SCIPdebugMessage("maxratio=%f \n", maxratio);
964 
965  assert(GT(maxratio, 0.0));
966 
967  return (maxratio);
968 }
#define STP_Vectype(type)
Definition: stpvector.h:44
#define StpVecGetSize(vec)
Definition: stpvector.h:139
int graph_knot_getContractionRecordAncestor(int, const SUBINOUT *)
Definition: graph_sub.c:895
int *RESTRICT head
Definition: graphdefs.h:224
int * biconn_comproots
int source
Definition: graphdefs.h:195
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
SCIP_Bool bidecomposition_isPossible(const GRAPH *g)
#define Is_term(a)
Definition: graphdefs.h:102
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
static void cutNodesProcessNext(const GRAPH *g, CUTNODES *cutnodes)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
static void cutNodesComputePostProcess(const GRAPH *g, CUTNODES *cutnodes)
const int * graph_subinoutGetContractionRecord(const SUBINOUT *)
Definition: graph_sub.c:837
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
#define FALSE
Definition: def.h:87
void graph_subinoutFree(SCIP *, SUBINOUT **)
Definition: graph_sub.c:859
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void bidecomposition_free(SCIP *scip, BIDECOMP **bidecomposition)
#define StpVecPopBack(vec)
Definition: stpvector.h:182
#define EAT_LAST
Definition: graphdefs.h:58
#define StpVecReserve(scip, vec, _size_)
Definition: stpvector.h:186
#define SCIPdebugMessage
Definition: pub_message.h:87
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
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
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_Real bidecomposition_getCompNodeRatio(const BIDECOMP *bidecomp, int compindex)
int *RESTRICT oeat
Definition: graphdefs.h:231
int * nodes_hittime
#define GE(a, b)
Definition: portab.h:85
static void decomposeBuildCsr(const CUTNODES *cutnodes, const GRAPH *g, BIDECOMP *bidecomp)
int * biconn_nodesmark
SCIP_Bool extended
Definition: graphdefs.h:267
void bidecomposition_markSub(const BIDECOMP *bidecomp, int compindex, GRAPH *g)
#define StpVecGetcapacity(vec)
Definition: stpvector.h:129
void bidecomposition_cutnodesCompute(const GRAPH *g, CUTNODES *cutnodes)
STACK_NODE * stack_nodes
int *RESTRICT grad
Definition: graphdefs.h:201
static SCIP_Bool decomposeCsrIsValid(const CUTNODES *cutnodes, const GRAPH *g, const BIDECOMP *bidecomp)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real bidecomposition_getMaxcompNodeRatio(const BIDECOMP *bidecomp)
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
unsigned char STP_Bool
Definition: portab.h:34
SCIP_RETCODE bidecomposition_cutnodesInit(SCIP *scip, const GRAPH *g, CUTNODES **cutnodes)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE bidecomposition_initSubInOut(SCIP *scip, const GRAPH *g, BIDECOMP *bidecomposition)
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
static void cutNodesCompute(const GRAPH *g, CUTNODES *cutnodes)
const int * graph_subinoutGetOrgToSubNodeMap(const SUBINOUT *)
Definition: graph_sub.c:825
static void cutNodesProcessComponent(int root, int stack_start, CUTNODES *cutnodes)
int *RESTRICT term
Definition: graphdefs.h:196
void bidecomposition_cutnodesFree(SCIP *scip, CUTNODES **cutnodes)
#define StpVecIsEmpty(vec)
Definition: stpvector.h:148
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_RETCODE graph_subinoutInit(SCIP *, const GRAPH *, SUBINOUT **)
Definition: graph_sub.c:733
static SCIP_RETCODE decomposeGetFirstMarked(SCIP *scip, const GRAPH *orggraph, int *subroot)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIP_Real
Definition: def.h:177
#define StpVecFree(scip, vec)
Definition: stpvector.h:153
int *RESTRICT outbeg
Definition: graphdefs.h:204
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
#define nnodes
Definition: gastrans.c:65
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:167
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)