Detailed Description
Minimum cut routine for Steiner problems.
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.
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 | |||
) |
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 | |||
) |
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 | |||
) |
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 | |||
) |
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 | |||
) |
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 | |||
) |
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()
SCIP_RETCODE graph_mincut_init | ( | SCIP * | scip, |
GRAPH * | p | ||
) |
initialize min cut arrays
- Parameters
-
scip SCIP data structure p graph data structure
Definition at line 275 of file grphmcut.c.
References GRAPH::edges, GRAPH::knots, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.
Referenced by graph_mincut_exec(), initReceivedSubproblem(), SCIP_DECL_PROBCOPY(), and SCIPprobdataCreate().
◆ graph_mincut_exit()
frees min cut arrays
- Parameters
-
scip SCIP data structure p graph data structure
Definition at line 305 of file grphmcut.c.
References GRAPH::knots, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, nnodes, NULL, and SCIPfreeMemoryArray.
Referenced by graph_mincut_exec(), initReceivedSubproblem(), and SCIP_DECL_PROBDELORIG().
◆ globalrelabel()
|
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 |
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 |
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 | ||
) |
finds a minimum s-t cut
Definition at line 1125 of file grphmcut.c.
References a, activedelete, activeinsert, EAT_LAST, Edge_anti, GRAPH::edges, FALSE, flipedge, globalrelabel(), GLOBALRELABEL_ADD, GLOBALRELABEL_MULT, graph_mincut_exit(), graph_mincut_init(), GRAPH::head, inactivedelete, inactiveinsert, initialise(), GRAPH::knots, listdelete, listinsert, Min, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, Q_NULL, r, reinitialise(), SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocMemoryArray, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArray, GRAPH::tail, TRUE, and x.