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-2019 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 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 } GRAPHNODE;
50 
51 
52 typedef struct GraphEdge
53 {
54  double cap; /**< capacity used in maxflow */
55  double rcap; /**< residual capacity used in maxflow */
56  double length; /**< length of the edge measured by some fixed metric */
57 
58  struct GraphEdge *next; /**< in incidence list of node from which edge is emanating */
59  struct GraphEdge *back; /**< pointer to reverse edge */
60 
61  GRAPHNODE *adjac; /**< pointer to adjacent node */
62 
64 } GRAPHEDGE;
65 
66 
67 typedef struct Graph
68 {
69  int nuses;
70  int nnodes; /**< number of nodes of the graph */
71  int nedges; /**< number of edges */
73 
74  GRAPHNODE *nodes; /**< array containing the nodes of the graph */
75 
76  GRAPHEDGE *edges; /**< array containing all halfedges (thus, it's size is two times nedges) */
77 } GRAPH;
78 
79 
80 SCIP_Bool create_graph(int n, int m, GRAPH** gr);
81 
82 void capture_graph(GRAPH* gr);
83 
84 void release_graph(GRAPH** gr);
85 
86 SCIP_Bool gmincut(GRAPH *gr, double *mincap, long *n_shore);
87 
88 SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool** cuts, int* ncuts, double minviol);
89 
90 #endif
struct GraphEdge * next
Definition: GomoryHuTree.h:58
int nnodes
Definition: GomoryHuTree.h:70
GRAPHNODE * nodes
Definition: GomoryHuTree.h:74
double length
Definition: GomoryHuTree.h:56
Definition: grph.h:57
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
struct GraphNode GRAPHNODE
int nedges
Definition: GomoryHuTree.h:71
SCIP_VAR * var
Definition: GomoryHuTree.h:63
struct GraphEdge * scan_ptr
Definition: GomoryHuTree.h:44
struct GraphEdge GRAPHEDGE
double cap
Definition: GomoryHuTree.h:54
GRAPHNODE * adjac
Definition: GomoryHuTree.h:61
struct GraphEdge * back
Definition: GomoryHuTree.h:59
struct GraphNode * parent
Definition: GomoryHuTree.h:48
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:43
GRAPHEDGE * edges
Definition: GomoryHuTree.h:76
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:70
SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
double rcap
Definition: GomoryHuTree.h:55
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:72
struct GraphNode * bfs_link
Definition: GomoryHuTree.h:46
int nuses
Definition: GomoryHuTree.h:69
SCIP_Bool gmincut(GRAPH *gr, double *mincap, long *n_shore)