GomoryHuTree.h File Reference

Detailed Description

generator for global cuts in undirected graphs

Author

Georg Skorobohatyj

Timo Berthold

Definition in file GomoryHuTree.h.

#include "objscip/objscip.h"

Go to the source code of this file.

Data Structures
struct	GraphNode
struct	GraphEdge
struct	Graph

Functions
SCIP_Bool	create_graph (int n, int m, GRAPH **gr)
void	capture_graph (GRAPH *gr)
void	release_graph (GRAPH **gr)
SCIP_Bool	ghc_tree (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)

Typedef Documentation

GRAPHNODE

typedef struct GraphNode GRAPHNODE

a node in the graph

GRAPHEDGE

typedef struct GraphEdge GRAPHEDGE

an edge in the graph

GRAPH

typedef struct Graph GRAPH

undirected graph

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, FALSE, NULL, SCIP_Bool, and TRUE.

Referenced by copy_graph(), and SCIP_DECL_READERREAD().

capture_graph()

void capture_graph

(

GRAPH *

gr

)

capture graph

Parameters

gr

graph

Definition at line 102 of file GomoryHuTree.cpp.

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

Referenced by 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(), and NULL.

Referenced by 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().

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

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.

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 632 of file GomoryHuTree.cpp.

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

Referenced by sepaSubtour().