Scippy

SCIP

Solving Constraint Integer Programs

GomoryHuTree.cpp File Reference

Detailed Description

generator for global cuts in undirected graphs

Author
Georg Skorobohatyj
Timo Berthold

Definition in file GomoryHuTree.cpp.

#include <stdio.h>
#include <assert.h>
#include "objscip/objscip.h"
#include "GomoryHuTree.h"

Go to the source code of this file.

Macros

#define EPS   1.0E-10
 

Functions

SCIP_Bool create_graph (int n, int m, GRAPH **gr)
 
static void free_graph (GRAPH **gr)
 
void capture_graph (GRAPH *gr)
 
void release_graph (GRAPH **gr)
 
SCIP_Bool init_maxflow (long n)
 
void fini_maxflow ()
 
void global_relabel (GRAPH *gr, GRAPHNODE *tptr)
 
double maxflow (GRAPH *gr, GRAPHNODE *s_ptr, GRAPHNODE *t_ptr)
 
SCIP_Bool nodeOnRootPath (GRAPH *gr, int i, int j)
 
void constructCutList (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
 
void constructSingleCut (GRAPH *gr, SCIP_Bool **cuts)
 
SCIP_Bool ghc_tree (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
 

Variables

static GRAPHNODE ** active
 
static long * number
 
static long max_dist
 
static long bound
 
static SCIP_Bool co_check
 

Macro Definition Documentation

◆ EPS

#define EPS   1.0E-10

Definition at line 31 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

Function Documentation

◆ create_graph()

SCIP_Bool create_graph ( int  n,
int  m,
GRAPH **  gr 
)

◆ free_graph()

static void free_graph ( GRAPH **  gr)
static

Definition at line 68 of file GomoryHuTree.cpp.

References BMSfreeMemory.

Referenced by release_graph().

◆ capture_graph()

◆ release_graph()

◆ init_maxflow()

SCIP_Bool init_maxflow ( long  n)

Definition at line 94 of file GomoryHuTree.cpp.

References co_check, FALSE, number, and TRUE.

Referenced by ghc_tree().

◆ fini_maxflow()

void fini_maxflow ( )

Definition at line 118 of file GomoryHuTree.cpp.

References number.

Referenced by ghc_tree().

◆ global_relabel()

◆ maxflow()

◆ nodeOnRootPath()

SCIP_Bool nodeOnRootPath ( GRAPH gr,
int  i,
int  j 
)

Definition at line 500 of file GomoryHuTree.cpp.

References FALSE, GraphNode::id, Graph::nodes, GraphNode::parent, and TRUE.

Referenced by constructCutList().

◆ constructCutList()

void constructCutList ( GRAPH gr,
SCIP_Bool **  cuts,
int *  ncuts,
double  minviol 
)

Definition at line 513 of file GomoryHuTree.cpp.

References FALSE, GraphNode::mincap, Graph::nnodes, nodeOnRootPath(), and Graph::nodes.

Referenced by ghc_tree().

◆ constructSingleCut()

void constructSingleCut ( GRAPH gr,
SCIP_Bool **  cuts 
)

Definition at line 531 of file GomoryHuTree.cpp.

References FALSE, Graph::nnodes, Graph::nodes, and GraphNode::unmarked.

Referenced by ghc_tree().

◆ ghc_tree()

SCIP_Bool ghc_tree ( GRAPH gr,
SCIP_Bool **  cuts,
int *  ncuts,
double  minviol 
)

Variable Documentation

◆ active

◆ number

◆ max_dist

long max_dist
static

Definition at line 35 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

◆ bound

◆ co_check

SCIP_Bool co_check
static

Definition at line 36 of file GomoryHuTree.cpp.

Referenced by init_maxflow(), and maxflow().