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-2024 Zuse Institute Berlin (ZIB) */
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 */
40typedef 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 */
60
61
62/** an edge in the graph */
63typedef 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 */
76
77
78/** undirected graph */
79typedef 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) */
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 */
99void capture_graph(
100 GRAPH* gr /**< graph */
101 );
102
103/** release graph */
104void 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
void capture_graph(GRAPH *gr)
struct GraphNode GRAPHNODE
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
SCIP_Bool ghc_tree(GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol)
void release_graph(GRAPH **gr)
struct GraphEdge GRAPHEDGE
struct Graph GRAPH
#define SCIP_Bool
Definition: def.h:91
C++ wrapper classes for SCIP.
struct GraphEdge * back
Definition: GomoryHuTree.h:70
double rcap
Definition: GomoryHuTree.h:66
double cap
Definition: GomoryHuTree.h:65
GRAPHNODE * adjac
Definition: GomoryHuTree.h:72
SCIP_VAR * var
Definition: GomoryHuTree.h:74
double length
Definition: GomoryHuTree.h:67
struct GraphEdge * next
Definition: GomoryHuTree.h:69
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:53
struct GraphNode * bfs_link
Definition: GomoryHuTree.h:56
double mincap
Definition: GomoryHuTree.h:48
SCIP_Bool unmarked
Definition: GomoryHuTree.h:50
SCIP_Bool alive
Definition: GomoryHuTree.h:51
double excess
Definition: GomoryHuTree.h:47
struct GraphEdge * scan_ptr
Definition: GomoryHuTree.h:54
struct GraphNode * parent
Definition: GomoryHuTree.h:58
struct GraphNode * stack_link
Definition: GomoryHuTree.h:57
double y
Definition: GomoryHuTree.h:46
double x
Definition: GomoryHuTree.h:45
GRAPHNODE * nodes
Definition: GomoryHuTree.h:86
int nedges
Definition: GomoryHuTree.h:83
int nedgesnonzero
Definition: GomoryHuTree.h:84
int nnodes
Definition: GomoryHuTree.h:82
int nuses
Definition: GomoryHuTree.h:81
GRAPHEDGE * edges
Definition: GomoryHuTree.h:87