Scippy

SCIP

Solving Constraint Integer Programs

GomoryHuTree.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License. */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file GomoryHuTree.h
17  * @brief generator for global cuts in undirected graphs
18  * @author Georg Skorobohatyj
19  * @author Timo Berthold
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __GOMORYHUTREE_H__
25 #define __GOMORYHUTREE_H__
26 
27 #include "objscip/objscip.h"
28 
29 
30 /** a node in the graph */
31 typedef struct GraphNode
32 {
33  int id; /**< number of the node*/
34  int dist; /**< distances used in push-relabel */
35 
36  double x; /**< 2D-coordinate in some metric */
37  double y; /**< second coordinate */
38  double excess; /**< excess of node used in push-relabel */
39  double mincap; /**< capacity of minimum cut between node and parent in GH cut tree */
40 
41  SCIP_Bool unmarked; /**< while BFS in progress */
42  SCIP_Bool alive; /**< marks alive (active) nodes in push-relabel */
43 
44  struct GraphEdge* first_edge; /**< in list of incident edges */
45  struct GraphEdge* scan_ptr; /**< next edge to be scanned when node will be visited again */
46 
47  struct GraphNode* bfs_link; /**< for one way BFS working queue */
48  struct GraphNode* stack_link; /**< for stack of active node */
49  struct GraphNode* parent; /**< pointer of Gomory-Hu cut tree */
50 } GRAPHNODE;
51 
52 
53 /** an edge in the graph */
54 typedef struct GraphEdge
55 {
56  double cap; /**< capacity used in maxflow */
57  double rcap; /**< residual capacity used in maxflow */
58  double length; /**< length of the edge measured by some fixed metric */
59 
60  struct GraphEdge* next; /**< in incidence list of node from which edge is emanating */
61  struct GraphEdge* back; /**< pointer to reverse edge */
62 
63  GRAPHNODE* adjac; /**< pointer to adjacent node */
64 
65  SCIP_VAR* var; /**< variable associated to edge */
66 } GRAPHEDGE;
67 
68 
69 /** undirected graph */
70 typedef struct Graph
71 {
72  int nuses; /**< usage counter */
73  int nnodes; /**< number of nodes of the graph */
74  int nedges; /**< number of edges */
75  int nedgesnonzero; /**< nonzero edges (not currently used) */
76 
77  GRAPHNODE* nodes; /**< array containing the nodes of the graph */
78  GRAPHEDGE* edges; /**< array containing all halfedges (thus, it's size is two times nedges) */
79 } GRAPH;
80 
81 
82 /** create a graph */
84  int n, /**< number of nodes */
85  int m, /**< number of edges */
86  GRAPH** gr /**< pointer to store graph */
87  );
88 
89 /** capture graph */
90 void capture_graph(
91  GRAPH* gr /**< graph */
92  );
93 
94 /** release graph */
95 void release_graph(
96  GRAPH** gr /**< graph */
97  );
98 
99 /** Determines Gomory/Hu cut tree for input graph with capacitated edges */
101  GRAPH* gr, /**< graph */
102  SCIP_Bool** cuts, /**< array of arrays to store cuts */
103  int* ncuts, /**< pointer to store number of cuts */
104  double minviol /**< minimal violation of a cut to be returned */
105  );
106 
107 #endif
struct GraphEdge * next
Definition: GomoryHuTree.h:60
int nnodes
Definition: GomoryHuTree.h:73
GRAPHNODE * nodes
Definition: GomoryHuTree.h:77
double length
Definition: GomoryHuTree.h:58
Definition: grph.h:57
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
struct GraphNode GRAPHNODE
int nedges
Definition: GomoryHuTree.h:74
SCIP_VAR * var
Definition: GomoryHuTree.h:65
struct GraphEdge * scan_ptr
Definition: GomoryHuTree.h:45
struct GraphEdge GRAPHEDGE
double cap
Definition: GomoryHuTree.h:56
GRAPHNODE * adjac
Definition: GomoryHuTree.h:63
struct GraphEdge * back
Definition: GomoryHuTree.h:61
struct GraphNode * parent
Definition: GomoryHuTree.h:49
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:44
GRAPHEDGE * edges
Definition: GomoryHuTree.h:78
C++ wrapper classes for SCIP.
SCIP_Bool unmarked
Definition: GomoryHuTree.h:41
double excess
Definition: GomoryHuTree.h:38
struct GraphNode * stack_link
Definition: GomoryHuTree.h:48
#define SCIP_Bool
Definition: def.h:70
SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
double rcap
Definition: GomoryHuTree.h:57
SCIP_Bool alive
Definition: GomoryHuTree.h:42
void release_graph(GRAPH **gr)
double mincap
Definition: GomoryHuTree.h:39
struct Graph GRAPH
double x
Definition: GomoryHuTree.h:36
void capture_graph(GRAPH *gr)
double y
Definition: GomoryHuTree.h:37
int nedgesnonzero
Definition: GomoryHuTree.h:75
struct GraphNode * bfs_link
Definition: GomoryHuTree.h:47
int nuses
Definition: GomoryHuTree.h:72