Scippy

SCIP

Solving Constraint Integer Programs

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
 

Typedefs

typedef struct GraphNode GRAPHNODE
 
typedef struct GraphEdge GRAPHEDGE
 
typedef struct Graph 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
nnumber of nodes
mnumber of edges
grpointer to store graph

Definition at line 52 of file GomoryHuTree.cpp.

References BMSallocMemory, BMSallocMemoryArray, BMSfreeMemory, BMSfreeMemoryArray, FALSE, NULL, and TRUE.

Referenced by copy_graph(), and SCIP_DECL_READERREAD().

◆ capture_graph()

void capture_graph ( GRAPH gr)

◆ release_graph()

◆ 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
grgraph
cutsarray of arrays to store cuts
ncutspointer to store number of cuts
minviolminimal 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, and TRUE.

Referenced by sepaSubtour().