Scippy

SCIP

Solving Constraint Integer Programs

grphmcut.c File Reference

Detailed Description

Minimum cut routine for Steiner problems.

Author
Gerald Gamrath
Thorsten Koch
Daniel Rehfeldt

This file implements a graph minimum cut routine for Steiner problems. For more details see Graph minimum cut routine page.

Definition in file grphmcut.c.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "portab.h"
#include "grph.h"

Go to the source code of this file.

Macros

#define DEBUG   0 /* 0 = No, 1 = Validation, 2 = Show flow */
 
#define STATIST   0
 
#define CHECK   0
 
#define Q_NULL   -1 /* NULL element of queue/list */
 
#define GLOBALRELABEL_ADD   10 /* constant for global relabel heuristic */
 
#define GLOBALRELABEL_MULT   10 /* constant for global relabel heuristic */
 
#define listdelete(node, nodedist, next, headactive)
 
#define listinsert(node, nodedist, next, headactive, actmin, actmax)
 
#define activedelete(node, nodedist, next, headactive)
 
#define activeinsert(node, nodedist, next, headactive, actmin, actmax, glbmax)
 
#define inactivedelete(node, nodedist, next, prev, headinactive, nextnode, prevnode)
 
#define inactiveinsert(node, nodedist, next, prev, headinactive, nextnode)
 

Functions

SCIP_RETCODE graph_mincut_init (SCIP *scip, GRAPH *p)
 
void graph_mincut_exit (SCIP *scip, GRAPH *p)
 
static void globalrelabel (const GRAPH *p, const int s, const int t, int *RESTRICT dist, int *RESTRICT headactive, int *RESTRICT headinactive, int *RESTRICT edgecurr, int *RESTRICT next, int *RESTRICT prev, int *RESTRICT excess, int *RESTRICT residual, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, int *actmin, int *actmax, int *glbmax, int *dormmax)
 
static void initialise (const GRAPH *p, const int s, const int t, const int rootcutsize, const int *rootcut, const int *capa, int *RESTRICT dist, int *RESTRICT headactive, int *RESTRICT headinactive, int *RESTRICT edgecurr, int *RESTRICT next, int *RESTRICT prev, int *RESTRICT temp, int *RESTRICT excess, int *RESTRICT residual, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, int *dormmax, int *actmin, int *actmax, int *glbmax)
 
static void reinitialise (const GRAPH *p, const int s, const int t, const int rootcutsize, const int *rootcut, const int *capa, int *RESTRICT dist, int *RESTRICT headactive, int *RESTRICT headinactive, int *RESTRICT edgecurr, int *RESTRICT next, int *RESTRICT prev, int *RESTRICT temp, int *RESTRICT excess, int *RESTRICT residual, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, int *dormmax, int *actmin, int *actmax, int *glbmax)
 
void graph_mincut_exec (const GRAPH *p, const int s, const int t, const int nnodesreal, const int nedgesreal, const int rootcutsize, const int *rootcut, const int *capa, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, const SCIP_Bool rerun)
 

Macro Definition Documentation

◆ DEBUG

#define DEBUG   0 /* 0 = No, 1 = Validation, 2 = Show flow */

Definition at line 40 of file grphmcut.c.

◆ STATIST

#define STATIST   0

Definition at line 41 of file grphmcut.c.

◆ CHECK

#define CHECK   0

Definition at line 42 of file grphmcut.c.

Referenced by SCIPreoptCheckCutoff().

◆ Q_NULL

#define Q_NULL   -1 /* NULL element of queue/list */

Definition at line 55 of file grphmcut.c.

Referenced by globalrelabel(), graph_mincut_exec(), initialise(), and reinitialise().

◆ GLOBALRELABEL_ADD

#define GLOBALRELABEL_ADD   10 /* constant for global relabel heuristic */

Definition at line 56 of file grphmcut.c.

Referenced by graph_mincut_exec().

◆ GLOBALRELABEL_MULT

#define GLOBALRELABEL_MULT   10 /* constant for global relabel heuristic */

Definition at line 57 of file grphmcut.c.

Referenced by graph_mincut_exec().

◆ listdelete

#define listdelete (   node,
  nodedist,
  next,
  headactive 
)
Value:
{\
assert(node >= 0);\
assert(nodedist >= 0);\
assert(headactive != NULL);\
headactive[nodedist] = next[node];\
}
#define NULL
Definition: def.h:239

remove first element from active (singly-linked) list

Definition at line 60 of file grphmcut.c.

Referenced by graph_mincut_exec().

◆ listinsert

#define listinsert (   node,
  nodedist,
  next,
  headactive,
  actmin,
  actmax 
)
Value:
{\
assert(node >= 0);\
assert(next != NULL);\
assert(headactive != NULL);\
assert(nodedist >= 0);\
next[node] = headactive[nodedist];\
headactive[nodedist] = node;\
if( nodedist < (actmin) )\
actmin = nodedist;\
if( nodedist > (actmax) )\
actmax = nodedist;\
}
#define NULL
Definition: def.h:239

add element to active (singly-linked) list

Definition at line 69 of file grphmcut.c.

Referenced by graph_mincut_exec().

◆ activedelete

#define activedelete (   node,
  nodedist,
  next,
  headactive 
)
Value:
{\
assert(node >= 0);\
assert(nodedist >= 0);\
assert(headactive != NULL);\
headactive[nodedist] = next[node];\
}
#define NULL
Definition: def.h:239

remove first element from active (singly-linked) list

Definition at line 101 of file grphmcut.c.

Referenced by graph_mincut_exec().

◆ activeinsert

#define activeinsert (   node,
  nodedist,
  next,
  headactive,
  actmin,
  actmax,
  glbmax 
)
Value:
{\
assert(node >= 0);\
assert(next != NULL);\
assert(headactive != NULL);\
assert(nodedist >= 0);\
next[node] = headactive[nodedist];\
headactive[nodedist] = node;\
if( nodedist < (actmin) )\
actmin = nodedist;\
if( nodedist > (actmax) )\
actmax = nodedist;\
if( (actmax) > (glbmax) )\
glbmax = (actmax);\
}
#define NULL
Definition: def.h:239

add element to active (singly-linked) list

Definition at line 110 of file grphmcut.c.

Referenced by globalrelabel(), graph_mincut_exec(), initialise(), and reinitialise().

◆ inactivedelete

#define inactivedelete (   node,
  nodedist,
  next,
  prev,
  headinactive,
  nextnode,
  prevnode 
)
Value:
{\
assert(node >= 0);\
assert(nodedist >= 0);\
assert(next != NULL);\
assert(prev != NULL);\
assert(headinactive != NULL);\
nextnode = next[node];\
if( headinactive[nodedist] == node )\
{\
headinactive[nodedist] = nextnode;\
if( nextnode >= 0 )\
prev[nextnode] = Q_NULL;\
}\
else\
{\
prevnode = prev[node];\
assert(prevnode >= 0);\
assert(next[prevnode] == node);\
next[prevnode] = nextnode;\
if( nextnode >= 0 )\
prev[nextnode] = prevnode;\
}\
}
#define NULL
Definition: def.h:239
#define Q_NULL
Definition: grphmcut.c:55

remove element from inactive (doubly-linked) list

Definition at line 127 of file grphmcut.c.

Referenced by graph_mincut_exec().

◆ inactiveinsert

#define inactiveinsert (   node,
  nodedist,
  next,
  prev,
  headinactive,
  nextnode 
)
Value:
{\
assert(node >= 0);\
assert(nodedist >= 0);\
assert(next != NULL);\
assert(prev != NULL);\
assert(headinactive != NULL);\
nextnode = headinactive[nodedist];\
next[node] = nextnode;\
prev[node] = Q_NULL;\
if( nextnode >= 0 )\
prev[nextnode] = node;\
headinactive[nodedist] = node;\
}
#define NULL
Definition: def.h:239
#define Q_NULL
Definition: grphmcut.c:55

add element to inactive (doubly-linked) list

Definition at line 153 of file grphmcut.c.

Referenced by globalrelabel(), graph_mincut_exec(), initialise(), and reinitialise().

Function Documentation

◆ graph_mincut_init()

◆ graph_mincut_exit()

void graph_mincut_exit ( SCIP scip,
GRAPH p 
)

◆ globalrelabel()

static void globalrelabel ( const GRAPH p,
const int  s,
const int  t,
int *RESTRICT  dist,
int *RESTRICT  headactive,
int *RESTRICT  headinactive,
int *RESTRICT  edgecurr,
int *RESTRICT  next,
int *RESTRICT  prev,
int *RESTRICT  excess,
int *RESTRICT  residual,
int *RESTRICT  w,
const int *  edgestart,
const int *  edgearr,
const int *  headarr,
int *  actmin,
int *  actmax,
int *  glbmax,
int *  dormmax 
)
static

global relabel heuristic that sets distance of sink to zero and relabels all other nodes using backward bfs on residual graph, starting from the sink.

Definition at line 407 of file grphmcut.c.

References activeinsert, FALSE, inactiveinsert, GRAPH::knots, nnodes, NULL, Q_NULL, SCIP_Bool, and TRUE.

Referenced by graph_mincut_exec().

◆ initialise()

static void initialise ( const GRAPH p,
const int  s,
const int  t,
const int  rootcutsize,
const int *  rootcut,
const int *  capa,
int *RESTRICT  dist,
int *RESTRICT  headactive,
int *RESTRICT  headinactive,
int *RESTRICT  edgecurr,
int *RESTRICT  next,
int *RESTRICT  prev,
int *RESTRICT  temp,
int *RESTRICT  excess,
int *RESTRICT  residual,
int *RESTRICT  w,
const int *  edgestart,
const int *  edgearr,
const int *  headarr,
int *  dormmax,
int *  actmin,
int *  actmax,
int *  glbmax 
)
static

initialize data for the first max-flow run

Definition at line 599 of file grphmcut.c.

References activeinsert, GRAPH::edges, flipedge, inactiveinsert, GRAPH::knots, nnodes, NULL, and Q_NULL.

Referenced by graph_mincut_exec().

◆ reinitialise()

static void reinitialise ( const GRAPH p,
const int  s,
const int  t,
const int  rootcutsize,
const int *  rootcut,
const int *  capa,
int *RESTRICT  dist,
int *RESTRICT  headactive,
int *RESTRICT  headinactive,
int *RESTRICT  edgecurr,
int *RESTRICT  next,
int *RESTRICT  prev,
int *RESTRICT  temp,
int *RESTRICT  excess,
int *RESTRICT  residual,
int *RESTRICT  w,
const int *  edgestart,
const int *  edgearr,
const int *  headarr,
int *  dormmax,
int *  actmin,
int *  actmax,
int *  glbmax 
)
static

initialize data for the repeated max-flow run

Definition at line 869 of file grphmcut.c.

References a, activeinsert, FALSE, flipedge, inactiveinsert, GRAPH::knots, nnodes, NULL, Q_NULL, SCIP_Bool, and TRUE.

Referenced by graph_mincut_exec().

◆ graph_mincut_exec()

void graph_mincut_exec ( const GRAPH p,
const int  s,
const int  t,
const int  nnodesreal,
const int  nedgesreal,
const int  rootcutsize,
const int *  rootcut,
const int *  capa,
int *RESTRICT  w,
const int *  edgestart,
const int *  edgearr,
const int *  headarr,
const SCIP_Bool  rerun 
)