grphmcut.c File Reference

#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	Q_LAST   -1 /* Last Element of Queue */
#define	Q_NMOQ   -2 /* Not a Member Of the Queue */

Functions
SCIP_RETCODE	graph_mincut_init (SCIP *scip, GRAPH *p)
void	graph_mincut_exit (SCIP *scip, GRAPH *p)
static void	delete (const int knot, int *q_dist, int *q_head, int *q_prev, int *q_next)
static int	insert (const int knot, int *q_dist, int *q_head, int *q_prev, int *q_next, int dmin)
static int	bfs (const GRAPH *p, const int s, const int t, int *q_dist, int *q_numb, int *q_temp, int *w)
static void	initialise (const GRAPH *p, const int s, const int t, const int *capa, int *q_dist, int *q_numb, int *q_head, int *q_prev, int *q_next, int *q_temp, int *excess, int *transx, int *residi, int *w, int *dmax)
static void	reinitialise (const GRAPH *p, const int s, const int t, const int *capa, int *q_dist, int *q_numb, int *q_head, int *q_prev, int *q_next, int *q_temp, int *excess, int *transx, int *residi, int *w, int *dmax)
void	graph_mincut_exec (GRAPH *p, int s, int t, const int *capa, int *w, int rerun)

Macro Definition Documentation

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

Definition at line 40 of file grphmcut.c.

#define Q_LAST   -1 /* Last Element of Queue */

Definition at line 50 of file grphmcut.c.

Referenced by delete(), graph_mincut_exec(), initialise(), insert(), and reinitialise().

#define Q_NMOQ   -2 /* Not a Member Of the Queue */

Definition at line 51 of file grphmcut.c.

Referenced by delete(), graph_mincut_exec(), initialise(), insert(), and reinitialise().

#define STATIST   0

Definition at line 41 of file grphmcut.c.

Function Documentation

static int bfs ( const GRAPH *  p, const int  s, const int  t, int *  q_dist, int *  q_numb, int *  q_temp, int *  w  )

static

Definition at line 230 of file grphmcut.c.

References EAT_LAST, GRAPH::head, GRAPH::knots, GRAPH::oeat, and GRAPH::outbeg.

Referenced by initialise(), and reinitialise().

static void delete ( const int  knot, int *  q_dist, int *  q_head, int *  q_prev, int *  q_next  )

inlinestatic

Definition at line 145 of file grphmcut.c.

References Q_LAST, and Q_NMOQ.

void graph_mincut_exec	(	GRAPH *	p,
		int	s,
		int	t,
		const int *	capa,
		int *	w,
		int	rerun
	)

Definition at line 568 of file grphmcut.c.

References EAT_LAST, Edge_anti, GRAPH::edges, FALSE, GRAPH::head, initialise(), insert(), GRAPH::knots, Min, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, GRAPH::oeat, GRAPH::outbeg, Q_LAST, Q_NMOQ, reinitialise(), GRAPH::tail, and TRUE.

Referenced by sep_2cut().

void graph_mincut_exit	(	SCIP *	scip,
		GRAPH *	p
	)

Parameters

scip	SCIP data structure
p	graph data structure

Definition at line 115 of file grphmcut.c.

References GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, and GRAPH::mincut_x.

Referenced by SCIP_DECL_PROBDELORIG().

SCIP_RETCODE graph_mincut_init	(	SCIP *	scip,
		GRAPH *	p
	)

Parameters

scip	SCIP data structure
p	graph data structure

Definition at line 80 of file grphmcut.c.

References GRAPH::edges, GRAPH::knots, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, and GRAPH::mincut_x.

Referenced by SCIP_DECL_PROBCOPY(), and SCIPprobdataCreate().

static void initialise ( const GRAPH *  p, const int  s, const int  t, const int *  capa, int *  q_dist, int *  q_numb, int *  q_head, int *  q_prev, int *  q_next, int *  q_temp, int *  excess, int *  transx, int *  residi, int *  w, int *  dmax  )

static

Definition at line 317 of file grphmcut.c.

References bfs(), EAT_LAST, Edge_anti, GRAPH::edges, GRAPH::head, insert(), GRAPH::knots, GRAPH::mincut_r, GRAPH::mincut_x, GRAPH::oeat, GRAPH::outbeg, Q_LAST, and Q_NMOQ.

Referenced by graph_mincut_exec().

static int insert ( const int  knot, int *  q_dist, int *  q_head, int *  q_prev, int *  q_next, int  dmin  )

inlinestatic

Definition at line 194 of file grphmcut.c.

References Q_LAST, and Q_NMOQ.

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

static void reinitialise ( const GRAPH *  p, const int  s, const int  t, const int *  capa, int *  q_dist, int *  q_numb, int *  q_head, int *  q_prev, int *  q_next, int *  q_temp, int *  excess, int *  transx, int *  residi, int *  w, int *  dmax  )

static

Definition at line 443 of file grphmcut.c.

References bfs(), GRAPH::edges, GRAPH::head, insert(), GRAPH::knots, Q_LAST, Q_NMOQ, and GRAPH::tail.

Referenced by graph_mincut_exec().