SCIP Doxygen Documentation
Loading...
Searching...
No Matches
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-2025 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
double rcap
double cap
GRAPHNODE * adjac
SCIP_VAR * var
double length
struct GraphEdge * next
struct GraphEdge * first_edge
struct GraphNode * bfs_link
double mincap
SCIP_Bool unmarked
SCIP_Bool alive
double excess
struct GraphEdge * scan_ptr
struct GraphNode * parent
struct GraphNode * stack_link
GRAPHNODE * nodes
int nedges
int nedgesnonzero
int nnodes
int nuses
GRAPHEDGE * edges
struct SCIP_Var SCIP_VAR
Definition type_var.h:119