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-2018 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 email to scip@zib.de. */
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 typedef struct GraphNode
31 {
32  int id; /**< number of the node*/
33  int dist;
34 
35  double x; /**< 2D-coordinate in some metric*/
36  double y; /**< second coordinate */
37  double excess;
38  double mincap; /**< capacity of minimum cut between node and parent in GH cut tree */
39 
40  SCIP_Bool unmarked; /**< while BFS in progress */
42 
43  struct GraphEdge *first_edge; /**< in list of incident edges */
44  struct GraphEdge *scan_ptr; /**< next edge to be scanned when node will be visited again */
45 
46  struct GraphNode *bfs_link; /**< for one way BFS working queue */
47  struct GraphNode *stack_link; /**< for stack of active node */
48  struct GraphNode *parent; /**< pointer of Gomory-Hu cut tree */
49 
50 } GRAPHNODE;
51 
52 
53 typedef struct GraphEdge
54 {
55  double cap; /**< capacity used in maxflow */
56  double rcap; /**< residual capacity used in maxflow */
57  double length; /**< length of the edge measured by some fixed metric */
58 
59  struct GraphEdge *next; /**< in incidence list of node from which edge is emanating */
60  struct GraphEdge *back; /**< pointer to reverse edge */
61 
62  GRAPHNODE *adjac; /**< pointer to adjacent node */
63 
65 
66 } GRAPHEDGE;
67 
68 
69 typedef struct Graph
70 {
71  int nuses;
72  int nnodes; /**< number of nodes of the graph */
73  int nedges; /**< number of edges */
75 
76  GRAPHNODE *nodes; /**< array containing the nodes of the graph */
77 
78  GRAPHEDGE *edges; /**< array containing all halfedges (thus, it's size is two times nedges) */
79 
80 } GRAPH;
81 
82 
83 extern
84 SCIP_Bool create_graph(int n, int m, GRAPH** gr);
85 
86 extern
87 void capture_graph(GRAPH* gr);
88 
89 extern
90 void release_graph(GRAPH** gr);
91 
92 extern
93 SCIP_Bool gmincut(GRAPH *gr, double *mincap, long *n_shore);
94 
95 extern
96 SCIP_Bool ghc_tree (GRAPH *gr, SCIP_Bool** cuts, int* ncuts, double minviol);
97 
98 #endif
struct GraphEdge * next
Definition: GomoryHuTree.h:59
int nnodes
Definition: GomoryHuTree.h:72
GRAPHNODE * nodes
Definition: GomoryHuTree.h:76
double length
Definition: GomoryHuTree.h:57
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
struct GraphNode GRAPHNODE
int nedges
Definition: GomoryHuTree.h:73
SCIP_VAR * var
Definition: GomoryHuTree.h:64
struct GraphEdge * scan_ptr
Definition: GomoryHuTree.h:44
struct GraphEdge GRAPHEDGE
double cap
Definition: GomoryHuTree.h:55
GRAPHNODE * adjac
Definition: GomoryHuTree.h:62
struct GraphEdge * back
Definition: GomoryHuTree.h:60
struct GraphNode * parent
Definition: GomoryHuTree.h:48
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:43
GRAPHEDGE * edges
Definition: GomoryHuTree.h:78
C++ wrapper classes for SCIP.
SCIP_Bool unmarked
Definition: GomoryHuTree.h:40
double excess
Definition: GomoryHuTree.h:37
struct GraphNode * stack_link
Definition: GomoryHuTree.h:47
#define SCIP_Bool
Definition: def.h:61
SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
double rcap
Definition: GomoryHuTree.h:56
SCIP_Bool alive
Definition: GomoryHuTree.h:41
void release_graph(GRAPH **gr)
double mincap
Definition: GomoryHuTree.h:38
struct Graph GRAPH
double x
Definition: GomoryHuTree.h:35
void capture_graph(GRAPH *gr)
double y
Definition: GomoryHuTree.h:36
int nedgesnonzero
Definition: GomoryHuTree.h:74
struct GraphNode * bfs_link
Definition: GomoryHuTree.h:46
int nuses
Definition: GomoryHuTree.h:71
SCIP_Bool gmincut(GRAPH *gr, double *mincap, long *n_shore)