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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file GomoryHuTree.h
26  * @brief generator for global cuts in undirected graphs
27  * @author Georg Skorobohatyj
28  * @author Timo Berthold
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __GOMORYHUTREE_H__
34 #define __GOMORYHUTREE_H__
35 
36 #include "objscip/objscip.h"
37 
38 
39 /** a node in the graph */
40 typedef struct GraphNode
41 {
42  int id; /**< number of the node*/
43  int dist; /**< distances used in push-relabel */
44 
45  double x; /**< 2D-coordinate in some metric */
46  double y; /**< second coordinate */
47  double excess; /**< excess of node used in push-relabel */
48  double mincap; /**< capacity of minimum cut between node and parent in GH cut tree */
49 
50  SCIP_Bool unmarked; /**< while BFS in progress */
51  SCIP_Bool alive; /**< marks alive (active) nodes in push-relabel */
52 
53  struct GraphEdge* first_edge; /**< in list of incident edges */
54  struct GraphEdge* scan_ptr; /**< next edge to be scanned when node will be visited again */
55 
56  struct GraphNode* bfs_link; /**< for one way BFS working queue */
57  struct GraphNode* stack_link; /**< for stack of active node */
58  struct GraphNode* parent; /**< pointer of Gomory-Hu cut tree */
59 } GRAPHNODE;
60 
61 
62 /** an edge in the graph */
63 typedef struct GraphEdge
64 {
65  double cap; /**< capacity used in maxflow */
66  double rcap; /**< residual capacity used in maxflow */
67  double length; /**< length of the edge measured by some fixed metric */
68 
69  struct GraphEdge* next; /**< in incidence list of node from which edge is emanating */
70  struct GraphEdge* back; /**< pointer to reverse edge */
71 
72  GRAPHNODE* adjac; /**< pointer to adjacent node */
73 
74  SCIP_VAR* var; /**< variable associated to edge */
75 } GRAPHEDGE;
76 
77 
78 /** undirected graph */
79 typedef struct Graph
80 {
81  int nuses; /**< usage counter */
82  int nnodes; /**< number of nodes of the graph */
83  int nedges; /**< number of edges */
84  int nedgesnonzero; /**< nonzero edges (not currently used) */
85 
86  GRAPHNODE* nodes; /**< array containing the nodes of the graph */
87  GRAPHEDGE* edges; /**< array containing all halfedges (thus, it's size is two times nedges) */
88 } GRAPH;
89 
90 
91 /** create a graph */
93  int n, /**< number of nodes */
94  int m, /**< number of edges */
95  GRAPH** gr /**< pointer to store graph */
96  );
97 
98 /** capture graph */
99 void capture_graph(
100  GRAPH* gr /**< graph */
101  );
102 
103 /** release graph */
104 void release_graph(
105  GRAPH** gr /**< graph */
106  );
107 
108 /** Determines Gomory/Hu cut tree for input graph with capacitated edges */
110  GRAPH* gr, /**< graph */
111  SCIP_Bool** cuts, /**< array of arrays to store cuts */
112  int* ncuts, /**< pointer to store number of cuts */
113  double minviol /**< minimal violation of a cut to be returned */
114  );
115 
116 #endif
struct GraphEdge * next
Definition: GomoryHuTree.h:69
int nnodes
Definition: GomoryHuTree.h:82
GRAPHNODE * nodes
Definition: GomoryHuTree.h:86
double length
Definition: GomoryHuTree.h:67
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
struct GraphNode GRAPHNODE
int nedges
Definition: GomoryHuTree.h:83
SCIP_VAR * var
Definition: GomoryHuTree.h:74
struct GraphEdge * scan_ptr
Definition: GomoryHuTree.h:54
struct GraphEdge GRAPHEDGE
double cap
Definition: GomoryHuTree.h:65
GRAPHNODE * adjac
Definition: GomoryHuTree.h:72
struct GraphEdge * back
Definition: GomoryHuTree.h:70
struct GraphNode * parent
Definition: GomoryHuTree.h:58
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:53
GRAPHEDGE * edges
Definition: GomoryHuTree.h:87
C++ wrapper classes for SCIP.
SCIP_Bool unmarked
Definition: GomoryHuTree.h:50
double excess
Definition: GomoryHuTree.h:47
struct GraphNode * stack_link
Definition: GomoryHuTree.h:57
#define SCIP_Bool
Definition: def.h:93
SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
double rcap
Definition: GomoryHuTree.h:66
SCIP_Bool alive
Definition: GomoryHuTree.h:51
void release_graph(GRAPH **gr)
double mincap
Definition: GomoryHuTree.h:48
struct Graph GRAPH
double x
Definition: GomoryHuTree.h:45
void capture_graph(GRAPH *gr)
double y
Definition: GomoryHuTree.h:46
int nedgesnonzero
Definition: GomoryHuTree.h:84
struct GraphNode * bfs_link
Definition: GomoryHuTree.h:56
int nuses
Definition: GomoryHuTree.h:81