Detailed Description

generator for global cuts in undirected graphs

Author: Georg Skorobohatyj; Timo Berthold

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

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)
static SCIP_Bool	init_maxflow (long n)
static void	fini_maxflow (void)
static void	global_relabel (GRAPH gr, GRAPHNODE tptr)
static double	maxflow (GRAPH gr, GRAPHNODE s_ptr, GRAPHNODE *t_ptr)
static SCIP_Bool	nodeOnRootPath (GRAPH *gr, int i, int j)
static void	constructCutList (GRAPH gr, SCIP_Bool cuts, int ncuts, double minviol)
static 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

epsilon value for numerical comparisons

Definition at line 41 of file GomoryHuTree.cpp.

Function Documentation

◆ create_graph()

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

create a graph

Parameters

n	number of nodes
m	number of edges
gr	pointer to store graph

Definition at line 52 of file GomoryHuTree.cpp.

References assert(), BMSallocMemory, BMSallocMemoryArray, BMSfreeMemory, BMSfreeMemoryArray, create_graph(), FALSE, NULL, SCIP_Bool, and TRUE.

Referenced by copy_graph(), create_graph(), and SCIP_DECL_READERREAD().

◆ free_graph()

void free_graph ( GRAPH ** gr )

static

free a graph

Parameters

gr	pointer a graph

Definition at line 88 of file GomoryHuTree.cpp.

References assert(), BMSfreeMemory, free_graph(), and NULL.

Referenced by free_graph(), and release_graph().

◆ capture_graph()

void capture_graph ( GRAPH * gr )

capture graph

Parameters

gr graph

Definition at line 102 of file GomoryHuTree.cpp.

References assert(), capture_graph(), NULL, and Graph::nuses.

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

◆ release_graph()

void release_graph ( GRAPH ** gr )

release graph

Parameters

gr graph

Definition at line 112 of file GomoryHuTree.cpp.

References assert(), free_graph(), NULL, and release_graph().

Referenced by release_graph(), tsp::ProbDataTSP::scip_copy(), SCIP_DECL_CONSDELETE(), SCIP_DECL_HEUREXIT(), 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().

◆ init_maxflow()

SCIP_Bool init_maxflow ( long n )

static

initialize maximum flow computation

Parameters

n	number of nodes

Definition at line 128 of file GomoryHuTree.cpp.

References active, co_check, FALSE, init_maxflow(), number, SCIP_Bool, and TRUE.

Referenced by ghc_tree(), and init_maxflow().

◆ fini_maxflow()

void fini_maxflow ( void )

static

free initialization data structures

Definition at line 157 of file GomoryHuTree.cpp.

References active, fini_maxflow(), and number.

Referenced by fini_maxflow(), and ghc_tree().

◆ global_relabel()

void global_relabel	(	GRAPH *	gr,
		GRAPHNODE *	tptr )

static

global relabel operation

Parameters

gr	graph
tptr	node to be relabeled

Definition at line 165 of file GomoryHuTree.cpp.

References active, GraphEdge::adjac, GraphNode::alive, assert(), GraphEdge::back, GraphNode::bfs_link, bound, GraphEdge::cap, GraphNode::dist, EPS, GraphNode::excess, FALSE, GraphNode::first_edge, global_relabel(), i, max_dist, GraphEdge::next, Graph::nnodes, Graph::nodes, NULL, number, GraphEdge::rcap, GraphNode::scan_ptr, GraphNode::stack_link, TRUE, and GraphNode::unmarked.

Referenced by global_relabel(), and maxflow().

◆ maxflow()

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

static

compute maximum flow

Determines maximum flow and minimum cut between nodes s (= *s_ptr) and t (= *t_ptr) in an undirected graph

References: A. Goldberg/ E. Tarjan: "A New Approach to the Maximum Flow Problem", in Proc. 18th ACM Symp. on Theory of Computing, 1986.

Parameters

gr	graph
s_ptr	start node
t_ptr	target node

Definition at line 263 of file GomoryHuTree.cpp.

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

Referenced by ghc_tree(), and maxflow().

◆ nodeOnRootPath()

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

static

determine whether node i is on the path to the root starting from j

Parameters

gr	graph
i	node to search for
j	starting node

Definition at line 562 of file GomoryHuTree.cpp.

References FALSE, i, GraphNode::id, nodeOnRootPath(), Graph::nodes, GraphNode::parent, SCIP_Bool, and TRUE.

Referenced by constructCutList(), and nodeOnRootPath().

◆ constructCutList()

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

static

constructs a list of cuts for a TSP relaxation polytope from a Gomory Hu Tree

If the non-zero-edges of a TSP relaxation induce a non-connected graph, an according cut is generated, using information from BFS in method maxflow.

Parameters

gr	graph
cuts	array of arrays to store cuts
ncuts	pointer to store number of cuts
minviol	minimal violation of a cut to be returned

Definition at line 585 of file GomoryHuTree.cpp.

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

Referenced by constructCutList(), and ghc_tree().

◆ constructSingleCut()

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

static

construct a single cut

Parameters

gr	graph
cuts	array of arrays to store cuts

Definition at line 609 of file GomoryHuTree.cpp.

References constructSingleCut(), FALSE, i, Graph::nnodes, Graph::nodes, SCIP_Bool, and GraphNode::unmarked.

Referenced by constructSingleCut(), and ghc_tree().

◆ ghc_tree()

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

Determines Gomory/Hu cut tree for input graph with capacitated edges

The tree structures is represented by parent pointers which are part of the node structure, the capacity of a tree edge is stored at the child node, the root of the cut tree is the first node in the list of graph nodes (&gr->nodes[0]). The implementation is described in [1].

References: 1) D. Gusfield: "Very Simple Algorithms and Programs for All Pairs Network Flow Analysis", Computer Science Division, University of California, Davis, 1987.

2) R.E. Gomory and T.C. Hu: "Multi-Terminal Network Flows", SIAM J. Applied Math. 9 (1961), 551-570.

Determines Gomory/Hu cut tree for input graph with capacitated edges

Parameters