# SCIP

Solving Constraint Integer Programs

graph_stats.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 graph_stats.c
17  * @brief includes several graph statistic methods for Steiner problem graphs
18  * @author Daniel Rehfeldt
19  *
20  * This file contains methods to obtain statistics on the given Steiner problem instance.
21  */
22
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24
25 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
26 /*lint -esym(766,string.h) */
27 //#define SCIP_DEBUG
28
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <assert.h>
33 #include "portab.h"
34 #include "graph.h"
35
36
37 #define STP_UNIFORM_MINRATIO 0.9
38 #define STP_UNIFORM_RANGEMIN 0.9
39 #define STP_UNIFORM_RANGEMAX 1.1
40
41
42 /**@name Local methods
43  *
44  * @{
45  */
46
47
48 /**@} */
49
50 /**@name Interface methods
51  *
52  * @{
53  */
54
55
56 /** is the given graph a variant that is effectively an STP?? */
58  const GRAPH* g /**< the graph */
59  )
60 {
61  const int type = g->stp_type;
62  assert(g);
63
64  return (type == STP_SPG || type == STP_RSMT || type == STP_GSTP || type == STP_OARSMT);
65 }
66
67
68 /** is the given graph (originally) undirected? */
70  const GRAPH* g /**< the graph */
71  )
72 {
73  assert(g);
74
75  if( g->stp_type == STP_SAP || g->stp_type == STP_DHCSTP || g->stp_type == STP_NWPTSPG )
76  return FALSE;
77
78  return TRUE;
79 }
80
81
82 /** is the given graph (originally) directed? */
84  const GRAPH* g /**< the graph */
85  )
86 {
87  assert(g);
88
89  return !(graph_typeIsUndirected(g));
90 }
91
92
93 /** is the edge blocked? */
95  const GRAPH* g, /**< the graph */
96  int e /**< the edge */
97  )
98 {
99  assert(g);
100  assert(e >= 0 && e < g->edges);
101
102  if( EQ(g->cost[e], BLOCKED_MINOR) || EQ(g->cost[e], BLOCKED) )
103  return TRUE;
104
105  return FALSE;
106 }
107
108
109 /** is edge in range? */
111  const GRAPH* g, /**< the graph */
112  int e /**< the edge */
113  )
114 {
115  assert(g);
116
117  return (0 <= e && e < g->edges);
118 }
119
120 /** has edge been deleted? */
122  const GRAPH* g, /**< the graph */
123  int e /**< the edge */
124  )
125 {
126  assert(g);
127
128  return (g->oeat[e] == EAT_FREE);
129 }
130
131
132 /** print information on edge */
134  const GRAPH* g, /**< the graph */
135  int e /**< the edge */
136  )
137 {
138  const int t = g->tail[e];
139  const int h = g->head[e];
140
141  if( !graph_typeIsUndirected(g) )
142  printf("e: %d %d->%d (%d->%d) cost:=%f costrev=%f \n", e, t, h, g->term[t], g->term[h], g->cost[e], g->cost[flipedge(e)]);
143  else if( graph_pc_isPcMw(g) )
144  printf("e: %d %d->%d (%d->%d) cost:=%f costrev=%f \n", e, t, h, g->term[t], g->term[h], g->cost[e], g->cost[flipedge(e)]);
145  else
146  printf("e: %d %d->%d (%d->%d) cost:=%f \n", e, t, h, g->term[t], g->term[h], g->cost[e]);
147 }
148
149
150 /** print information on node */
152  const GRAPH* g, /**< the graph */
153  int k /**< the node */
154  )
155 {
156  assert(!graph_pc_isPcMw(g) || g->term2edge != NULL);
157
158  if( graph_pc_isPcMw(g) )
159  {
160  assert(g->prize);
161
162  if( graph_pc_knotIsNonLeafTerm(g, k) )
163  printf("node %d: term=%d grad=%d prize=%f (non-leaf terminal) \n", k, g->term[k], g->grad[k], g->prize[k]);
164  else if( graph_pc_knotIsFixedTerm(g, k) )
165  printf("node %d: term=%d grad=%d prize=%f (fixed terminal) \n", k, g->term[k], g->grad[k], g->prize[k]);
166  else if( Is_term(g->term[k]) )
167  printf("node %d: term=%d grad=%d prize=%f (standard terminal) \n", k, g->term[k], g->grad[k], g->prize[k]);
168  else
170  }
171  else
172  {
174  }
175
176  if( k == g->source )
177  printf("...%d is the root! \n", k);
178
179  if( g->stp_type == STP_NWPTSPG && graph_knotIsNWLeaf(g, k) )
180  printf("...%d is a leaf-terminal \n", k);
181 }
182
183
184 /** graph with multi-edges? */
186  SCIP* scip, /**< SCIP data structure */
187  const GRAPH* g, /**< graph data structure */
188  SCIP_Bool verbose /**< be verbose? */
189 )
190 {
191  const int nnodes = graph_get_nNodes(g);
192  int* count;
193  SCIP_Bool hasMultiEdges = FALSE;
194
195  assert(scip);
196
197  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &count, nnodes) );
198
199  for( int k = 0; k < nnodes; k++ )
200  count[k] = 0;
201
202  for( int k = 0; k < nnodes && !hasMultiEdges; k++ )
203  {
204  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
205  {
207
208  if( count[head] > 0 )
209  {
210  SCIPdebugMessage("problem for edge %d->%d \n", k, head);
211
212  if( verbose )
213  {
214  SCIPerrorMessage("parallel edge %d->%d found \n", k + 1, head + 1);
215  }
216
217  hasMultiEdges = TRUE;
218  }
219
221  }
222
223  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
224  {
227  }
228  }
229
230  SCIPfreeBufferArray(scip, &count);
231
232  return hasMultiEdges;
233 }
234
235
236 /** has the graph almost uniform edge weights? */
238  const GRAPH* g /**< the graph */
239  )
240 {
241  const int nedges = graph_get_nEdges(g);
242  SCIP_Real avg = 0.0;
243  SCIP_Real avg_lower;
244  SCIP_Real avg_upper;
245  int edgecount = 0;
246  int nrangeedges = 0;
247
248  for( int e = 0; e < nedges; e+= 2 )
249  {
250  SCIP_Real edgecost;
251  if( g->oeat[e] == EAT_FREE )
252  continue;
253
254  edgecost = g->cost[e];
255
256  if( EQ(edgecost, 0.0) || EQ(edgecost, FARAWAY) )
257  continue;
258
259  edgecount++;
260  avg += edgecost;
261  }
262
263  if( edgecount == 0 )
264  return TRUE;
265
266  avg /= (SCIP_Real) edgecount;
267
268  assert(STP_UNIFORM_RANGEMIN < 1.0);
269  assert(STP_UNIFORM_RANGEMAX > 1.0);
270
271  avg_lower = avg * STP_UNIFORM_RANGEMIN;
272  avg_upper = avg * STP_UNIFORM_RANGEMAX;
273
274  for( int e = 0; e < nedges; e += 2 )
275  {
276  SCIP_Real edgecost;
277  if( g->oeat[e] == EAT_FREE )
278  continue;
279
280  edgecost = g->cost[e];
281
282  if( EQ(edgecost, 0.0) || EQ(edgecost, FARAWAY) )
283  continue;
284
285  if( edgecost < avg_lower || edgecost > avg_upper )
286  continue;
287
288  nrangeedges++;
289  }
290
291  SCIPdebugMessage("number of unreduced edges=%d \n", edgecount);
292  SCIPdebugMessage("number of in-range edges=%d \n", nrangeedges);
293
294  return (((SCIP_Real) nrangeedges / (SCIP_Real) edgecount) > STP_UNIFORM_MINRATIO);
295 }
296
297
298 /** print information on graph */
300  const GRAPH* g /**< the graph */
301  )
302 {
303  char type[64];
304
305  switch( g->stp_type )
306  {
307  case 0:
308  strcpy(type, "STP_SPG");
309  break;
310  case 1:
311  strcpy(type, "STP_SAP");
312  break;
313  case 2:
314  strcpy(type, "STP_PCSPG");
315  break;
316  case 3:
317  strcpy(type, "STP_RPCSPG");
318  break;
319  case 4:
320  strcpy(type, "STP_NWSPG");
321  break;
322  case 5:
323  strcpy(type, "STP_DCSTP");
324  break;
325  case 6:
326  strcpy(type, "STP_NWPTSPG");
327  break;
328  case 7:
329  strcpy(type, "STP_RSMT");
330  break;
331  case 8:
332  strcpy(type, "STP_OARSMT");
333  break;
334  case 9:
335  strcpy(type, "STP_MWCSP");
336  break;
337  case 10:
338  strcpy(type, "STP_DHCSTP");
339  break;
340  case 11:
341  strcpy(type, "STP_GSTP");
342  break;
343  case 12:
344  strcpy(type, "STP_RMWCSP");
345  break;
346  case 13:
347  strcpy(type, "STP_BRMWCSP");
348  break;
349  default:
350  strcpy(type, "UNKNOWN");
351  }
352
353  assert(g != NULL);
354  if( graph_pc_isPcMw(g) )
355  {
356  printf("nodes=%d, edges=%d, terminals=%d, root=%d, type=%s, isExtended=%d\n", g->knots, g->edges, g->terms, g->source, type, g->extended);
357  if( graph_pc_isPc(g) )
358  {
359  printf("non-leaf terminals=%d, ", graph_pc_nNonLeafTerms(g));
360  printf("fixed terminals=%d, ", graph_pc_nFixedTerms(g));
361  printf("proper terminals=%d \n", graph_pc_nProperPotentialTerms(g));
362  }
363  }
364  else
365  {
366  printf("nodes=%d, edges=%d, terminals=%d, root=%d, type=%s \n", g->knots, g->edges, g->terms, g->source, type);
367  }
368
369  if( g->stp_type == STP_BRMWCSP )
370  printf("budget=%f \n", g->budget);
371 }
372
373
374 /** print information on graph that has been subject to reductions */
376  const GRAPH* g /**< the graph */
377 )
378 {
379  int nnodes;
380  int nedges;
381  int nterms;
382
383  graph_get_nVET(g, &nnodes, &nedges, &nterms);
384
385  printf("reduced graph stats: ");
386
387  if( graph_pc_isPcMw(g) )
388  {
389  printf("nodes=%d, edges=%d, terminals=%d, root=%d, type=%d, isExtended=%d \n",
390  nnodes, nedges, nterms, g->source, g->stp_type, g->extended);
391
392  if( graph_pc_isPc(g) )
393  {
394  printf("non-leaf terminals=%d, ", graph_pc_nNonLeafTerms(g));
395  printf("fixed terminals=%d, ", graph_pc_nFixedTerms(g));
396  printf("proper terminals=%d \n", graph_pc_nProperPotentialTerms(g));
397  }
398  }
399  else
400  {
401  printf("nodes=%d, edges=%d, terminals=%d, root=%d, type=%d \n", nnodes,
402  nedges, nterms, g->source, g->stp_type);
403  }
404 }
405
406
407 /** prints edge conflicts */
409  SCIP* scip, /**< SCIP data structure */
410  const GRAPH* g /**< the graph */
411 )
412 {
413  int* childcount;
414  int* pseudonodecount;
415  int nconflicts;
416  int npseudoconflicts;
417  int npseudofixed;
418  const int nnodes = g->knots;
419  const int nedges = g->edges;
420  const int nedgesorg = MAX(g->orgedges, g->edges);
421
422  assert(scip != NULL && g != NULL);
423  assert(g->ancestors != NULL);
424  assert(nedgesorg % 2 == 0);
425
426  SCIP_CALL( SCIPallocBufferArray(scip, &childcount, nedgesorg / 2) );
427  SCIP_CALL( SCIPallocBufferArray(scip, &pseudonodecount, nnodes) );
428
429  for( int e = 0; e < nedgesorg / 2; e++ )
430  childcount[e] = 0;
431
432  for( int e = 0; e < nnodes; e++ )
433  pseudonodecount[e] = 0;
434
435  npseudofixed = graph_getNfixpseudonodes(g);
436  nconflicts = 0;
437  npseudoconflicts = 0;
438
439  for( int e = 0; e < nedges; e += 2 )
440  {
441  SCIP_Bool hasConflict = FALSE;
442  SCIP_Bool hasPseudoConflict = FALSE;
443
444  const int nPseudoAncestors = graph_edge_nPseudoAncestors(g, e);
445  const int* pseudoAncestors = graph_edge_getPseudoAncestors(g, e);
446  for( IDX* curr = g->ancestors[e]; curr != NULL; curr = curr->parent )
447  {
448  assert(curr->index >= 0 && curr->index / 2 < nedgesorg / 2);
449  if( childcount[curr->index / 2] > 0 )
450  hasConflict = TRUE;
451
452  childcount[curr->index / 2]++;
453  }
454
455  for( int k = 0; k < nPseudoAncestors; k++ )
456  {
457  const int a = pseudoAncestors[k];
458  assert(a >= 0 && a < nnodes);
459
460  if( pseudonodecount[a] > 0 )
461  hasPseudoConflict = TRUE;
462
463  pseudonodecount[a]++;
464  }
465
466  if( hasConflict )
467  {
468  nconflicts++;
469  assert(hasPseudoConflict);
470  }
471
472  if( hasPseudoConflict )
473  npseudoconflicts++;
474
475  }
476
477  if( graph_pc_isPcMw(g) )
478  {
479  assert(g->extended);
480
481  for( int e = 0; e < nnodes; e++ )
482  {
483  if( !Is_term(g->term[e]) )
484  {
485  SCIP_Bool hasConflict = FALSE;
486  SCIP_Bool hasPseudoConflict = FALSE;
487
488  const int nPseudoAncestors = graph_knot_nPseudoAncestors(g, e);
489  const int* pseudoAncestors = graph_knot_getPseudoAncestors(g, e);
490  for( IDX* curr = g->pcancestors[e]; curr != NULL; curr = curr->parent )
491  {
492  assert(curr->index >= 0 && curr->index / 2 < nedgesorg / 2);
493  if( childcount[curr->index / 2] > 0 )
494  hasConflict = TRUE;
495
496  childcount[curr->index / 2]++;
497  }
498
499  for( int k = 0; k < nPseudoAncestors; k++ )
500  {
501  const int a = pseudoAncestors[k];
502  assert(a >= 0 && a < nnodes);
503
504  if( pseudonodecount[a] > 0 )
505  hasPseudoConflict = TRUE;
506
507  pseudonodecount[a]++;
508  }
509
510  if( hasConflict )
511  {
512  nconflicts++;
513  assert(hasPseudoConflict);
514  }
515
516  if( hasPseudoConflict )
517  npseudoconflicts++;
518  }
519  }
520  }
521
522  printf("number of edge conflicts %d \n", nconflicts);
523  printf("number of pseudo-ancestor conflicts %d \n", npseudoconflicts);
524  printf("number of fixed pseudo-ancestors %d \n", npseudofixed);
525
526  SCIPfreeBufferArray(scip, &pseudonodecount);
527  SCIPfreeBufferArray(scip, &childcount);
528
529  return SCIP_OKAY;
530 }
531
532
533
534
535 /** get number of nodes */
537  const GRAPH* graph /**< the graph */
538 )
539 {
540  assert(graph);
541  assert(graph->knots >= 1);
542
543  return graph->knots;
544 }
545
546
547 /** get number of edges */
549  const GRAPH* graph /**< the graph */
550 )
551 {
552  assert(graph);
553  assert(graph->edges >= 0);
554
555  return graph->edges;
556 }
557
558
559 /** get number of terminals */
561  const GRAPH* graph /**< the graph */
562 )
563 {
564  assert(graph);
565
566  return graph->terms;
567 }
568
569
570 /** get (real) number of nodes, edges, terminals */
572  const GRAPH* graph, /**< the graph */
573  int* nnodes, /**< number of nodes */
574  int* nedges, /**< number of edges */
575  int* nterms /**< number of terminals */
576  )
577 {
578  int v = 0;
579  int e = 0;
580  int t = 0;
581  int vorg;
582
583  assert(graph != NULL);
584
585  vorg = graph->knots;
586
587  for( int k = 0; k < vorg; k++ )
588  {
589  if( graph->grad[k] > 0 )
590  {
591  v++;
593  }
594
595  if( nterms && Is_term(graph->term[k]) )
596  t++;
597  }
598
599  if( nnodes )
600  *nnodes = MAX(v, 1);
601
602  if( nedges )
603  *nedges = e;
604
605  if( nterms )
606  *nterms = t;
607
608  return;
609 }
610
611
612 /** get (real) average degree of graph */
614  const GRAPH* graph /**< the graph */
615  )
616 {
617  int v = 0;
618  int e = 0;
619  const int vorg = graph->knots;
620
621  assert(graph);
622
623  for( int k = 0; k < vorg; k++ )
624  {
625  if( graph->grad[k] > 0 )
626  {
627  v++;
629  }
630  }
631
632  if( v == 0 )
633  return 0.0;
634
635  return ((double) e / v );
636 }
637
638 /**@} */
int graph_edge_nPseudoAncestors(const GRAPH *, int)
static volatile int nterms
Definition: interrupt.c:38
Definition: graphdefs.h:224
int source
Definition: graphdefs.h:195
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Bool graph_typeIsUndirected(const GRAPH *g)
Definition: graph_stats.c:69
int terms
Definition: graphdefs.h:192
void graph_edge_printInfo(const GRAPH *g, int e)
Definition: graph_stats.c:133
int graph_pc_nFixedTerms(const GRAPH *)
SCIP_RETCODE graph_printEdgeConflicts(SCIP *scip, const GRAPH *g)
Definition: graph_stats.c:408
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
#define STP_SAP
Definition: graphdefs.h:43
const int * graph_knot_getPseudoAncestors(const GRAPH *, int)
#define EAT_LAST
Definition: graphdefs.h:58
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Bool graph_edge_isDeleted(const GRAPH *g, int e)
Definition: graph_stats.c:121
void graph_knot_printInfo(const GRAPH *g, int k)
Definition: graph_stats.c:151
SCIP_Real graph_get_avgDeg(const GRAPH *graph)
Definition: graph_stats.c:613
SCIP_Bool graph_knotIsNWLeaf(const GRAPH *, int)
Definition: graph_node.c:35
#define STP_RSMT
Definition: graphdefs.h:49
int *RESTRICT oeat
Definition: graphdefs.h:231
#define BLOCKED_MINOR
Definition: graphdefs.h:91
#define STP_UNIFORM_MINRATIO
Definition: graph_stats.c:37
SCIP_Bool graph_hasMultiEdges(SCIP *scip, const GRAPH *g, SCIP_Bool verbose)
Definition: graph_stats.c:185
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
int graph_getNfixpseudonodes(const GRAPH *)
IDX ** ancestors
Definition: graphdefs.h:234
int orgedges
Definition: graphdefs.h:220
#define STP_UNIFORM_RANGEMAX
Definition: graph_stats.c:39
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_Real budget
Definition: graphdefs.h:212
int graph_get_nNodes(const GRAPH *graph)
Definition: graph_stats.c:536
void graph_get_nVET(const GRAPH *graph, int *nnodes, int *nedges, int *nterms)
Definition: graph_stats.c:571
SCIP_Real * prize
Definition: graphdefs.h:210
#define STP_UNIFORM_RANGEMIN
Definition: graph_stats.c:38
Definition: graphdefs.h:201
SCIP_Bool graph_typeIsDirected(const GRAPH *g)
Definition: graph_stats.c:83
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
int * term2edge
Definition: graphdefs.h:208
IDX ** pcancestors
Definition: graphdefs.h:235
SCIP_Bool graph_isAlmostUniform(const GRAPH *g)
Definition: graph_stats.c:237
SCIP_VAR * h
Definition: circlepacking.c:59
#define STP_OARSMT
Definition: graphdefs.h:50
SCIP_Bool graph_edge_isInRange(const GRAPH *g, int e)
Definition: graph_stats.c:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_Bool graph_edge_isBlocked(const GRAPH *g, int e)
Definition: graph_stats.c:94
#define SCIP_Bool
Definition: def.h:84
int graph_knot_nPseudoAncestors(const GRAPH *, int)
#define STP_NWPTSPG
Definition: graphdefs.h:48
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
int graph_pc_nProperPotentialTerms(const GRAPH *)
const int * graph_edge_getPseudoAncestors(const GRAPH *, int)
int *RESTRICT term
Definition: graphdefs.h:196
void graph_printInfo(const GRAPH *g)
Definition: graph_stats.c:299
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
SCIP_Bool graph_pc_isPc(const GRAPH *)
Portable definitions.
int graph_pc_nNonLeafTerms(const GRAPH *)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
void graph_printInfoReduced(const GRAPH *g)
Definition: graph_stats.c:375
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIP_Real
Definition: def.h:177
#define BLOCKED
Definition: graphdefs.h:90
SCIP_Bool graph_typeIsSpgLike(const GRAPH *g)
Definition: graph_stats.c:57
int *RESTRICT outbeg
Definition: graphdefs.h:204
#define STP_BRMWCSP
Definition: graphdefs.h:55
int edges
Definition: graphdefs.h:219
#define STP_GSTP
Definition: graphdefs.h:53
#define nnodes
Definition: gastrans.c:65
int graph_get_nTerms(const GRAPH *graph)
Definition: graph_stats.c:560
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
int graph_get_nEdges(const GRAPH *graph)
Definition: graph_stats.c:548