# SCIP

Solving Constraint Integer Programs

completegraph.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file completegraph.c
17  * @brief includes complete graph methods, in particular for MST calculation
18  * @author Daniel Rehfeldt
19  *
20  * Complete graph methods, in particular for MST calculation. Assumes a maximum size of the graph.
21  * Only sensible for small maximum sizes.
22  *
23  */
24
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26
27 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
28 /*lint -esym(766,string.h) */
29
30 //#define SCIP_DEBUG
31
32
33 #include "completegraph.h"
34 #include "portab.h"
35
36 #define NODE_ID_UNDEFINED -2
37
38
39 /** gets current number of nodes */
40 static inline
42  const CGRAPH* cgraph /**< the graph */
43 )
44 {
45  assert(cgraph);
46
47  return cgraph->nnodes_curr;
48 }
49
50
51 /** gets maximum number of nodes */
52 static inline
54  const CGRAPH* cgraph /**< the graph */
55 )
56 {
57  assert(cgraph);
58
59
60  return cgraph->nnodes_max;
61 }
62
63
64 /** gets start position in edge cost array */
65 static inline
67  int nodepos, /**< node position */
68  int nnodes_max /**< maximum number of nodes */
69 )
70 {
71  assert(nodepos >= 0);
72  assert(nodepos < nnodes_max);
73
74  return (nodepos * nnodes_max);
75 }
76
77
78 /** gets end position in edge cost array; NOT included! */
79 static inline
81  int nodepos, /**< node position */
82  int nnodes_curr, /**< current number of nodes */
83  int nnodes_max /**< maximum number of nodes */
84 )
85 {
86  assert(nodepos >= 0);
87  assert(nnodes_curr >= 0);
88  assert(nnodes_curr <= nnodes_max);
89  assert(nodepos < nnodes_curr);
90
91  return (nodepos * nnodes_max + nnodes_curr);
92 }
93
94
95 /** gets position of node with specified id */
96 static inline
98  const CGRAPH* cgraph, /**< new graph */
99  int nodeid /**< the node id */
100  )
101 {
102  int nodepos;
103  const int* const nodeids = cgraph->nodeids;
104
105  assert(cgraph_valid(cgraph));
106  assert(nodeid >= 0);
107
108  for( nodepos = cgraph->nnodes_curr - 1; nodepos >= 0; nodepos-- )
109  {
110  if( nodeids[nodepos] == nodeid )
111  break;
112  }
113
114  assert(nodepos >= 0);
115
116  return nodepos;
117 }
118
119
120 /** is the graph valid? */
122  const CGRAPH* cgraph /**< the graph */
123 )
124 {
125  const int nnodes_curr = getNnodesCurr(cgraph);
126  const int nnodes_max = getNnodesMax(cgraph);
127  const SCIP_Real* const edgecosts = cgraph->edgecosts;
128  const int* const nodeids = cgraph->nodeids;
129
130  assert(edgecosts && nodeids);
131  assert(nnodes_max > 1);
132  assert(nnodes_curr <= nnodes_max);
133  assert(nnodes_curr >= 0);
134  assert(cgraph->nnodes_active <= nnodes_curr);
135  assert(cgraph->nnodes_active >= 0);
136
137  for( int i = 0; i < nnodes_curr - 1; i++ )
138  {
139  if( getEdgeEnd(i, nnodes_curr, nnodes_max) > getEdgeStart(i + 1, nnodes_max) )
140  {
141  SCIPdebugMessage("positions are broken \n");
142  return FALSE;
143  }
144  }
145
146  for( int i = 0; i < nnodes_curr; i++ )
147  {
148  if( i != (nnodes_max - 1) && getEdgeStart(i, nnodes_max) > getEdgeStart(i + 1, nnodes_max) )
149  {
150  SCIPdebugMessage("positions are broken \n");
151  return FALSE;
152  }
153  }
154
155  for( int i = 0; i < nnodes_curr; i++ )
156  {
157  if( NODE_ID_UNDEFINED == nodeids[i] )
158  {
159  SCIPdebugMessage("node %d is wrongly set to NODE_ID_UNDEFINED \n", i);
160  return FALSE;
161  }
162  }
163
164
165  /* check if the edge costs are symmetric */
166  for( int i = 0; i < nnodes_curr; i++ )
167  {
168  const int start_i = getEdgeStart(i, nnodes_max);
169
170  for( int j = 0; j < nnodes_curr; j++ )
171  {
172  const int start_j = getEdgeStart(j, nnodes_max);
173  const SCIP_Real cost_ij = edgecosts[start_i + j];
174  const SCIP_Real cost_ji = edgecosts[start_j + i];
175
176  assert(i != j || EQ(cost_ij, FARAWAY));
177
178  if( !EQ(cost_ji, cost_ij) )
179  {
180  SCIPdebugMessage("wrong edge costs between %d and %d (%f != %f) \n", i, j, cost_ij, cost_ji);
181  return FALSE;
182  }
183  }
184  }
185
186 #ifndef NDEBUG
187  {
188  const int start = nnodes_curr > 0 ? getEdgeEnd(nnodes_curr - 1, nnodes_curr, nnodes_max) : 0;
189
190  for( int i = start; i < nnodes_max * nnodes_max; i++ )
191  {
192  if( !EQ(CGRAPH_EDGECOST_UNDEFINED_VALUE, edgecosts[i]) )
193  {
194  SCIPdebugMessage("unused edge value is wrong: %f \n", edgecosts[i]);
195  return FALSE;
196  }
197  }
198  for( int i = nnodes_curr; i < nnodes_max; i++ )
199  {
200  if( NODE_ID_UNDEFINED != nodeids[i] )
201  {
202  SCIPdebugMessage("node %d is not set to NODE_ID_UNDEFINED \n", i);
203  return FALSE;
204  }
205  }
206  }
207 #endif
208
209  return TRUE;
210 }
211
212
213 /** is the graph in sync with given node id list? */
215  const CGRAPH* cgraph, /**< the graph */
216  const int* ids, /**< node ids */
217  int nids /**< number of ids */
218 )
219 {
220  assert(cgraph && ids);
221  assert(cgraph->nodeids);
222
223  if( nids != cgraph->nnodes_curr )
224  {
225  SCIPdebugMessage("wrong number of ids (%d!=%d) \n", nids, cgraph->nnodes_curr);
226  return FALSE;
227  }
228
229  for( int i = 0; i < nids; i++ )
230  {
231  if( cgraph->nodeids[i] != ids[i] )
232  {
233  SCIPdebugMessage("wrong id for entry %d (%d!=%d) \n", i, cgraph->nodeids[i], ids[i]);
234  return FALSE;
235  }
236  }
237
238  return TRUE;
239 }
240
241
242 /** is node with given id in the graph?? */
244  const CGRAPH* cgraph, /**< the graph */
245  int id /**< the id */
246 )
247 {
248  const int nnodes = getNnodesCurr(cgraph);
249
250  assert(cgraph->nodeids);
251  assert(id >= 0);
252
253  for( int i = 0; i < nnodes; i++ )
254  {
255  if( cgraph->nodeids[i] == id )
256  {
257  return TRUE;
258  }
259  }
260
261  return FALSE;
262 }
263
264
265 /** initialize complete, undirected graph */
267  SCIP* scip, /**< SCIP data structure */
268  CGRAPH** cgraph, /**< new graph */
269  int maxnnodes /**< maximum number of nodes */
270  )
271 {
272  CGRAPH* g;
273
274  assert(scip && cgraph);
275  assert(maxnnodes > 1);
276
277  SCIP_CALL( SCIPallocMemory(scip, cgraph) );
278
279  g = *cgraph;
280
281  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->edgecosts), maxnnodes * maxnnodes) );
282  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->adjedgecosts), maxnnodes + 1) );
283  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->nodeids), maxnnodes) );
284  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->node_has_adjcosts), maxnnodes) );
285
286  g->nnodes_curr = 0;
287  g->nnodes_active = 0;
288  g->nnodes_max = maxnnodes;
289
290 #ifndef NDEBUG
291  for( int i = 0; i < maxnnodes * maxnnodes; i++ )
293
294  for( int i = 0; i < maxnnodes; i++ )
295  g->nodeids[i] = NODE_ID_UNDEFINED;
296
297  for( int i = 0; i < maxnnodes + 1; i++ )
299 #endif
300
301  assert(cgraph_valid(g));
302
303  SCIPdebugMessage("cgraph has been successfully built \n");
304
305  return SCIP_OKAY;
306 }
307
308
309 /** free complete graph */
311  SCIP* scip, /**< SCIP data structure */
312  CGRAPH** cgraph /**< new graph */
313  )
314 {
315  CGRAPH* g;
316
317  assert(scip && cgraph);
318
319  g = *cgraph;
320
322  SCIPfreeMemoryArray(scip, &(g->nodeids));
324  SCIPfreeMemoryArray(scip, &(g->edgecosts));
325
326  SCIPfreeMemory(scip, cgraph);
327 }
328
329
330 /** cleans, i.e. resets, graph */
332  CGRAPH* cgraph /**< new graph */
333  )
334 {
335  const int nnodes_curr = getNnodesCurr(cgraph);
336
337  assert(cgraph_valid(cgraph));
338
339  for( int i = 0; i < nnodes_curr; i++ )
340  cgraph_node_deleteTop(cgraph);
341
342  assert(cgraph_isEmpty(cgraph));
343 }
344
345
346 /** is the graph empty? */
348  const CGRAPH* cgraph /**< new graph */
349  )
350 {
351  assert(cgraph_valid(cgraph));
352
353  return (cgraph->nnodes_curr == 0);
354 }
355
356
357 /** has the given node adjacency costs? */
359  const CGRAPH* cgraph, /**< the complete graph */
360  int nodepos /**< the node position */
361  )
362 {
363  assert(cgraph_valid(cgraph));
364  assert(nodepos >= 0 && nodepos < getNnodesCurr(cgraph));
365
367 }
368
369
370 /** applies adjacency costs to node, but only use if smaller than existing ones. */
372  CGRAPH* cgraph, /**< the complete graph */
373  int nodepos, /**< the node position */
374  int nodeid /**< the node id (for debugging only) */
375  )
376 {
377  const int nnodes_curr = getNnodesCurr(cgraph);
378  const int nnodes_max = getNnodesMax(cgraph);
379  const int start = getEdgeStart(nodepos, nnodes_max);
380  SCIP_Real* const edgecosts = cgraph->edgecosts;
382
383  assert(nodepos >= 0 && nodepos < nnodes_curr);
384  assert(cgraph->nodeids[nodepos] == nodeid);
385
386  for( int i = start, j = 0; i != start + nnodes_curr; i++, j++ )
387  {
388  const SCIP_Real newcost = adjcosts[j];
389  assert(GE(newcost, 0.0));
390  assert(!EQ(edgecosts[i], CGRAPH_EDGECOST_UNDEFINED_VALUE));
391
392  if( newcost < edgecosts[i] )
393  edgecosts[i] = newcost;
394  }
395
396  for( int i = 0; i < nnodes_curr; i++ )
397  {
398  const SCIP_Real newcost = adjcosts[i];
399  const int pos = getEdgeStart(i, nnodes_max) + nodepos;
400
401  assert(!EQ(edgecosts[pos], CGRAPH_EDGECOST_UNDEFINED_VALUE));
402  assert(GE(newcost, 0.0));
403
404  if( newcost < edgecosts[pos] )
405  edgecosts[pos] = newcost;
406  }
407
409
411  assert(cgraph_valid(cgraph));
412 }
413
414
415 /** add node (at the end, so at position cgraph->nnodes_curr) */
417  CGRAPH* cgraph, /**< new graph */
418  int nodeid /**< the node id */
419  )
420 {
421  int lastedge;
422  SCIP_Real* const edgecosts = cgraph->edgecosts;
423  const int nodepos_new = cgraph->nnodes_curr;
424  const int nnodes_curr_new = nodepos_new + 1;
425  const int nnodes_max = cgraph->nnodes_max;
426  const int start_new = getEdgeStart(nodepos_new, nnodes_max);
427
428  assert(cgraph_valid(cgraph));
429  assert(edgecosts && cgraph->nodeids);
430  assert(nodeid >= 0);
431  assert(!cgraph_idIsContained(cgraph, nodeid));
432  assert(nodepos_new < nnodes_max);
433  assert(NODE_ID_UNDEFINED == cgraph->nodeids[nodepos_new]);
434
435  cgraph->nnodes_curr++;
436
437  for( int i = start_new; i < start_new + nodepos_new; i++ )
438  {
439  edgecosts[i] = FARAWAY;
440  }
441
442  for( int i = 0; i < nodepos_new; i++ )
443  {
444  const int end = getEdgeEnd(i, nodepos_new, nnodes_max);
445  assert(EQ(edgecosts[end], CGRAPH_EDGECOST_UNDEFINED_VALUE));
446
447  edgecosts[end] = FARAWAY;
448  }
449
450  lastedge = getEdgeEnd(nodepos_new, nnodes_curr_new, nnodes_max) - 1;
451  assert(lastedge >= 0 && lastedge == start_new + nodepos_new);
452  assert(EQ(CGRAPH_EDGECOST_UNDEFINED_VALUE, edgecosts[lastedge]));
453
454  edgecosts[lastedge] = FARAWAY;
455  cgraph->nodeids[nodepos_new] = nodeid;
457
458  assert(cgraph_valid(cgraph));
459 }
460
461
462 /** replaces node with id 'nodeid_new' by top node */
464  CGRAPH* cgraph, /**< new graph */
465  int nodeid_new /**< the new node id */
466  )
467 {
468  const int nnodes_curr = getNnodesCurr(cgraph);
469  const int nodepos_top = nnodes_curr - 1;
470  const int nodepos_new = getPositionFromId(cgraph, nodeid_new);
471
472  assert(cgraph_valid(cgraph));
473  assert(nodepos_new >= 0 && nodepos_new <= nodepos_top);
474
475  if( nodepos_new != nodepos_top )
476  {
477  const int nnodes_max = getNnodesMax(cgraph);
478  const int start_new = getEdgeStart(nodepos_new, nnodes_max);
479  const int start_top = getEdgeStart(nodepos_top, nnodes_max);
480  SCIP_Real* const edgecosts = cgraph->edgecosts;
481
482  for( int i = 0; i < nodepos_top; i++ )
483  {
484  if( i != nodepos_new )
485  {
486  const int edgepos = getEdgeStart(i, nnodes_max) + nodepos_new;
487
488  assert(EQ(edgecosts[edgepos], edgecosts[start_new + i]));
489
490  edgecosts[edgepos] = edgecosts[start_top + i];
491  }
492  }
493
494  assert(start_new + nodepos_top < start_top);
495
496  BMScopyMemoryArray(edgecosts + start_new, edgecosts + start_top, nodepos_top);
497
498  /* adapt diagonal entry */
499  edgecosts[start_new + nodepos_new] = FARAWAY;
500
501  cgraph->nodeids[nodepos_new] = cgraph->nodeids[nodepos_top];
502  }
503
504  cgraph_node_deleteTop(cgraph);
505
506  assert(cgraph_valid(cgraph));
507 }
508
509
510 /** deletes node at the top */
512  CGRAPH* cgraph /**< new graph */
513  )
514 {
515  assert(cgraph_valid(cgraph));
516  assert(cgraph->nnodes_curr <= cgraph->nnodes_max);
517  assert(cgraph->nnodes_curr > 0);
518
519  cgraph->nnodes_curr--;
520
521 #ifndef NDEBUG
522  {
523  int last_start;
524  int last_end;
525
526  assert(NODE_ID_UNDEFINED != cgraph->nodeids[cgraph->nnodes_curr]);
527
528  cgraph->nodeids[cgraph->nnodes_curr] = NODE_ID_UNDEFINED;
529
530  /* remove edge entries going to deleted vertex */
531  for( int i = 0; i < cgraph->nnodes_curr; i++ )
532  {
533  const int end = getEdgeEnd(i, cgraph->nnodes_curr, cgraph->nnodes_max);
534
535  assert(!EQ(cgraph->edgecosts[end], CGRAPH_EDGECOST_UNDEFINED_VALUE));
536
538  }
539
540  last_start = getEdgeStart(cgraph->nnodes_curr, cgraph->nnodes_max);
541  last_end = getEdgeEnd(cgraph->nnodes_curr, cgraph->nnodes_curr + 1, cgraph->nnodes_max);
542
543  /* remove entries of deleted vertex */
544  for( int i = last_start; i < last_end; i++ )
545  {
546  assert(!EQ(cgraph->edgecosts[i], CGRAPH_EDGECOST_UNDEFINED_VALUE));
548  }
549  }
550
551  assert(cgraph_valid(cgraph));
552
553 #endif
554 }
555
556
557 /** deletes node */
559  CGRAPH* cgraph, /**< new graph */
560  int nodeid /**< the node id */
561  )
562 {
563  int nodepos;
564  const int* const nodeids = cgraph->nodeids;
565
566  assert(cgraph_valid(cgraph));
567  assert(nodeid >= 0);
568
569  for( nodepos = cgraph->nnodes_curr - 1; nodepos >= 0; nodepos-- )
570  {
571  if( nodeids[nodepos] == nodeid )
572  break;
573  }
574
575  assert(nodepos >= 0);
576  assert(0 && "not fully implemented yet");
577 }
578
579
580 /** gets id of node at the top */
582  const CGRAPH* cgraph /**< new graph */
583  )
584 {
585  assert(cgraph_valid(cgraph));
586  assert(cgraph->nnodes_curr > 0);
587
588  return cgraph->nodeids[cgraph->nnodes_curr - 1];
589 }
590
591
592
593 /** Get edge cost.
594  * Note: quite slow, only use for debugging! */
596  const CGRAPH* cgraph, /**< new graph */
597  int nodeid_tail, /**< the node id */
598  int nodeid_head /**< the node id */
599  )
600 {
601  assert(cgraph);
602  assert(cgraph_valid(cgraph));
603  assert(0 && "not yet implemented");
604
605  return 0.0;
606 }
607
608
609 /** is the MST struct valid? */
611  const CGRAPH* cgraph, /**< new graph */
612  const CMST* cmst /**< the MST */
613 )
614 {
615  SCIP_Real obj;
616  const int nnodes = getNnodesCurr(cgraph);
617  const int nnodes_max = getNnodesMax(cgraph);
618  const SCIP_Real* const edgecosts = cgraph->edgecosts;
619  const int* const preds = cmst->predecessors;
620
621  assert(edgecosts && preds);
622
623  if( cmst->nnodes_max < nnodes )
624  {
625  SCIPdebugMessage("mst has not enough nodes \n");
626  return FALSE;
627  }
628
629  /* now check the objective */
630
631  obj = 0.0;
632
633  for( int i = 0; i < nnodes; i++ )
634  {
635  const int start = getEdgeStart(i, nnodes_max);
636  const int pred = preds[i];
637
638  if( pred == -1 )
639  continue;
640
641  assert(pred >= 0 && pred < nnodes);
642  assert(pred != i);
643
644  obj += edgecosts[start + pred];
645  }
646
647  if( !EQ(obj, cmst->mstobj) )
648  {
649  SCIPdebugMessage("wrong objective: %f != %f \n", obj, cmst->mstobj);
650  return FALSE;
651  }
652
653  SCIPdebugMessage("graph and mst are in sync! \n");
654
655  return TRUE;
656 }
657
658
659 /** initializes MST */
661  SCIP* scip, /**< SCIP data structure */
662  CMST** cmst, /**< the MST */
663  int maxnnodes /**< maximum number of nodes */
664  )
665 {
666  CMST* mst;
667
668  assert(scip && cmst);
669  assert(maxnnodes > 1);
670
671  SCIP_CALL( SCIPallocMemory(scip, cmst) );
672
673  mst = *cmst;
674
675  graph_heap_create(scip, maxnnodes, NULL, NULL, &(mst->heap));
676
677  SCIP_CALL( SCIPallocMemoryArray(scip, &(mst->dist), maxnnodes) );
678  SCIP_CALL( SCIPallocMemoryArray(scip, &(mst->predecessors), maxnnodes) );
679
680  mst->nnodes_max = maxnnodes;
681  mst->mstobj = 0.0;
682
683  SCIPdebugMessage("cmst has been successfully built \n");
684
685  return SCIP_OKAY;
686 }
687
688
689 /** frees MST */
691  SCIP* scip, /**< SCIP data structure */
692  CMST** cmst /**< MST */
693  )
694 {
695  CMST* mst;
696
697  assert(scip && cmst);
698
699  mst = *cmst;
700
701  SCIPfreeMemoryArray(scip, &(mst->predecessors));
702  SCIPfreeMemoryArray(scip, &(mst->dist));
703
704  graph_heap_free(scip, TRUE, TRUE, &(mst->heap));
705
706  SCIPfreeMemory(scip, cmst);
707 }
708
709
710 /** compute MST on given graph */
712  const CGRAPH* cgraph, /**< the graph to run on */
713  int mstroot, /**< root for the MST */
714  CMST* cmst /**< the MST */
715 )
716 {
717  const int nnodes_curr = getNnodesCurr(cgraph);
718  const int nnodes_max = getNnodesMax(cgraph);
719  SCIP_Real mstcost = 0.0;
720  const SCIP_Real* const edgecosts = cgraph->edgecosts;
721  int* const preds = cmst->predecessors;
722  SCIP_Real* const dist = cmst->dist;
723  DHEAP* const dheap = cmst->heap;
724  int* const state = dheap->position;
725
726 #ifndef NDEBUG
727  assert(edgecosts && preds && dist && dheap && state);
728  assert(cgraph_valid(cgraph));
729  assert(nnodes_curr <= cmst->nnodes_max);
730  assert(mstroot >= 0 && mstroot < nnodes_curr);
731
732  for( int i = 0; i < nnodes_curr; i++ )
734 #endif
735
736  for( int i = 0; i < nnodes_curr; i++ )
737  {
738  preds[i] = -1;
739  state[i] = UNKNOWN;
740  dist[i] = FARAWAY;
741  }
742
743  assert(graph_heap_isClean(dheap));
744
745  preds[mstroot] = -1;
746  dist[mstroot] = 0.0;
747  graph_heap_correct(mstroot, 0.0, dheap);
748
749  assert(dheap->size == 1);
750
751  /* build MST */
752  while( dheap->size > 0 )
753  {
754  const int k = graph_heap_deleteMinReturnNode(dheap);
755  const int start = getEdgeStart(k, nnodes_max);
756
757  mstcost += dist[k];
758
759  assert(k >= 0 && k < nnodes_curr);
760  assert(state[k] == CONNECT);
761
762  for( int m = 0; m < nnodes_curr; m++ )
763  {
764  if( state[m] != CONNECT )
765  {
766  const SCIP_Real ecost = edgecosts[start + m];
767
768  if( ecost < dist[m] )
769  {
770  assert(m != k);
771
772  dist[m] = ecost;
773  preds[m] = k;
774
775  graph_heap_correct(m, ecost, dheap);
776  }
777  }
778  }
779  }
780
781  cmst->mstobj = mstcost;
782
783 #ifndef NDEBUG
784  for( int i = 0; i < nnodes_curr; i++ )
785  {
786  assert(LT(dist[i], FARAWAY));
787  assert(preds[i] != -1 || i == mstroot);
788  }
789
790  assert(cmst_isSync(cgraph, cmst));
791 #endif
792 }
793
SCIP_RETCODE cmst_init(SCIP *scip, CMST **cmst, int maxnnodes)
static int getNnodesCurr(const CGRAPH *cgraph)
Definition: completegraph.c:41
SCIP_Bool cgraph_valid(const CGRAPH *cgraph)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
Definition: completegraph.h:48
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void cgraph_clean(CGRAPH *cgraph)
includes complete graph methods, in particular for MST calculation
void cgraph_node_append(CGRAPH *cgraph, int nodeid)
#define FALSE
Definition: def.h:87
SCIP_Real cgraph_edge_getCost(const CGRAPH *cgraph, int nodeid_tail, int nodeid_head)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void cgraph_node_deleteTop(CGRAPH *cgraph)
static int getPositionFromId(const CGRAPH *cgraph, int nodeid)
Definition: completegraph.c:97
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_Bool graph_heap_isClean(const DHEAP *)
Definition: graph_util.c:962
#define FARAWAY
Definition: graphdefs.h:89
DHEAP * heap
Definition: completegraph.h:71
static int getEdgeEnd(int nodepos, int nnodes_curr, int nnodes_max)
Definition: completegraph.c:80
int * position
Definition: graphdefs.h:305
SCIP_Bool cgraph_node_hasAdjCosts(const CGRAPH *cgraph, int nodepos)
#define GE(a, b)
Definition: portab.h:85
SCIP_Real * dist
Definition: completegraph.h:72
SCIP_Bool cmst_isSync(const CGRAPH *cgraph, const CMST *cmst)
#define CGRAPH_EDGECOST_UNDEFINED_VALUE
Definition: completegraph.h:39
SCIP_Bool cgraph_idsInSync(const CGRAPH *cgraph, const int *ids, int nids)
void cmst_free(SCIP *scip, CMST **cmst)
static int getNnodesMax(const CGRAPH *cgraph)
Definition: completegraph.c:53
#define NULL
Definition: lpi_spx1.cpp:155
#define EQ(a, b)
Definition: portab.h:79
#define SCIP_CALL(x)
Definition: def.h:384
#define LT(a, b)
Definition: portab.h:81
void cgraph_free(SCIP *scip, CGRAPH **cgraph)
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE cgraph_init(SCIP *scip, CGRAPH **cgraph, int maxnnodes)
static int getEdgeStart(int nodepos, int nnodes_max)
Definition: completegraph.c:66
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
Definition: completegraph.h:46
SCIP_Bool cgraph_isEmpty(const CGRAPH *cgraph)
void cgraph_node_repositionTop(CGRAPH *cgraph, int nodeid_new)
SCIP_Real mstobj
Definition: completegraph.h:74
void cgraph_node_delete(CGRAPH *cgraph, int nodeid)
SCIP_Bool cgraph_idIsContained(const CGRAPH *cgraph, int id)
int cgraph_node_getTopId(const CGRAPH *cgraph)
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
#define SCIP_Real
Definition: def.h:177
int graph_heap_deleteMinReturnNode(DHEAP *)
Definition: graph_util.c:1076
SCIP_Real * edgecosts
Definition: completegraph.h:45
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
void cgraph_node_applyMinAdjCosts(CGRAPH *cgraph, int nodepos, int nodeid)
void graph_heap_correct(int, SCIP_Real, DHEAP *)
Definition: graph_util.c:1166
int * predecessors
Definition: completegraph.h:73
#define NODE_ID_UNDEFINED
Definition: completegraph.c:36
void cmst_computeMst(const CGRAPH *cgraph, int mstroot, CMST *cmst)