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"

Include dependency graph for GomoryHuTree.cpp:

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

#define EPS   1.0E-10

Definition at line 31 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

Function Documentation

void capture_graph

(

GRAPH *

gr

)

Definition at line 78 of file GomoryHuTree.cpp.

References Graph::nuses.

Referenced by tsp::ProbDataTSP::ProbDataTSP(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSTRANS(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and tsp::SCIPcreateConsSubtour().

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

Definition at line 513 of file GomoryHuTree.cpp.

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

Referenced by ghc_tree().

void constructSingleCut	(	GRAPH *	gr,
		SCIP_Bool **	cuts
	)

Definition at line 530 of file GomoryHuTree.cpp.

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

Referenced by ghc_tree().

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

Definition at line 38 of file GomoryHuTree.cpp.

Referenced by copy_graph(), and SCIP_DECL_READERREAD().

void fini_maxflow

(

)

Definition at line 118 of file GomoryHuTree.cpp.

References number.

Referenced by ghc_tree().

static void free_graph ( GRAPH **  gr )

static

Definition at line 68 of file GomoryHuTree.cpp.

Referenced by release_graph().

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

Definition at line 536 of file GomoryHuTree.cpp.

References GraphNode::alive, constructCutList(), constructSingleCut(), fini_maxflow(), init_maxflow(), maxflow(), GraphNode::mincap, Graph::nnodes, Graph::nodes, and GraphNode::parent.

Referenced by sepaSubtour().

void global_relabel	(	GRAPH *	gr,
		GRAPHNODE *	tptr
	)

Definition at line 126 of file GomoryHuTree.cpp.

References active, GraphEdge::adjac, GraphNode::alive, GraphEdge::back, GraphNode::bfs_link, bound, GraphEdge::cap, GraphNode::dist, EPS, GraphNode::excess, GraphNode::first_edge, max_dist, GraphEdge::next, Graph::nnodes, Graph::nodes, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, and GraphNode::unmarked.

Referenced by maxflow().

SCIP_Bool init_maxflow

(

long

n

)

Definition at line 94 of file GomoryHuTree.cpp.

References co_check, and number.

Referenced by ghc_tree().

double maxflow	(	GRAPH *	gr,
		GRAPHNODE *	s_ptr,
		GRAPHNODE *	t_ptr
	)

Definition at line 207 of file GomoryHuTree.cpp.

References GraphEdge::adjac, GraphNode::alive, GraphEdge::back, GraphNode::bfs_link, bound, GraphEdge::cap, co_check, GraphNode::dist, Graph::edges, EPS, GraphNode::excess, GraphNode::first_edge, global_relabel(), max_dist, Graph::nedges, Graph::nedgesnonzero, GraphEdge::next, Graph::nnodes, Graph::nodes, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, and GraphNode::unmarked.

Referenced by ghc_tree().

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

Definition at line 500 of file GomoryHuTree.cpp.

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

Referenced by constructCutList().

void release_graph

(

GRAPH **

gr

)

Definition at line 84 of file GomoryHuTree.cpp.

References free_graph().

Referenced by tsp::ProbDataTSP::scip_copy(), SCIP_DECL_CONSDELETE(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_READERREAD(), tsp::ProbDataTSP::scip_delorig(), tsp::ProbDataTSP::scip_deltrans(), tsp::ProbDataTSP::scip_trans(), tsp::HeurFarthestInsert::~HeurFarthestInsert(), and tsp::ProbDataTSP::~ProbDataTSP().

Variable Documentation

GRAPHNODE** active

static

Definition at line 33 of file GomoryHuTree.cpp.

Referenced by global_relabel().

long bound

static

Definition at line 35 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

SCIP_Bool co_check

static

Definition at line 36 of file GomoryHuTree.cpp.

Referenced by init_maxflow(), and maxflow().

long max_dist

static

Definition at line 35 of file GomoryHuTree.cpp.

Referenced by global_relabel(), and maxflow().

long* number

static

Definition at line 34 of file GomoryHuTree.cpp.

Referenced by fini_maxflow(), global_relabel(), init_maxflow(), and maxflow().