Detailed Description
generator for global cuts in undirected graphs
Definition in file GomoryHuTree.h.
#include "objscip/objscip.h"
Go to the source code of this file.
Data Structures | |
struct | GraphNode |
struct | GraphEdge |
struct | Graph |
Typedefs | |
typedef struct GraphNode | GRAPHNODE |
typedef struct GraphEdge | GRAPHEDGE |
typedef struct Graph | GRAPH |
Functions | |
SCIP_Bool | create_graph (int n, int m, GRAPH **gr) |
void | capture_graph (GRAPH *gr) |
void | release_graph (GRAPH **gr) |
SCIP_Bool | ghc_tree (GRAPH *gr, SCIP_Bool **cuts, int *ncuts, double minviol) |
Typedef Documentation
◆ GRAPHNODE
◆ GRAPHEDGE
◆ GRAPH
Function Documentation
◆ create_graph()
create a graph
- Parameters
-
n number of nodes m number of edges gr pointer to store graph
Definition at line 52 of file GomoryHuTree.cpp.
References BMSallocMemory, BMSallocMemoryArray, BMSfreeMemory, BMSfreeMemoryArray, FALSE, NULL, and TRUE.
Referenced by copy_graph(), and SCIP_DECL_READERREAD().
◆ capture_graph()
void capture_graph | ( | GRAPH * | gr | ) |
capture graph
- Parameters
-
gr graph
Definition at line 102 of file GomoryHuTree.cpp.
References NULL, and Graph::nuses.
Referenced by tsp::ProbDataTSP::ProbDataTSP(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSTRANS(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and tsp::SCIPcreateConsSubtour().
◆ release_graph()
void release_graph | ( | GRAPH ** | gr | ) |
release graph
- Parameters
-
gr graph
Definition at line 112 of file GomoryHuTree.cpp.
References free_graph(), and NULL.
Referenced by tsp::ProbDataTSP::scip_copy(), SCIP_DECL_CONSDELETE(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_READERREAD(), tsp::ProbDataTSP::scip_delorig(), tsp::ProbDataTSP::scip_deltrans(), tsp::ProbDataTSP::scip_trans(), tsp::HeurFarthestInsert::~HeurFarthestInsert(), and tsp::ProbDataTSP::~ProbDataTSP().
◆ ghc_tree()
Determines Gomory/Hu cut tree for input graph with capacitated edges
Determines Gomory/Hu cut tree for input graph with capacitated edges
The tree structures is represented by parent pointers which are part of the node structure, the capacity of a tree edge is stored at the child node, the root of the cut tree is the first node in the list of graph nodes (&gr->nodes[0]). The implementation is described in [1].
References: 1) D. Gusfield: "Very Simple Algorithms and Programs for All Pairs Network Flow Analysis", Computer Science Division, University of California, Davis, 1987.
2) R.E. Gomory and T.C. Hu: "Multi-Terminal Network Flows", SIAM J. Applied Math. 9 (1961), 551-570.
- Parameters
-
gr graph cuts array of arrays to store cuts ncuts pointer to store number of cuts minviol minimal violation of a cut to be returned
Definition at line 632 of file GomoryHuTree.cpp.
References GraphNode::alive, constructCutList(), constructSingleCut(), FALSE, fini_maxflow(), init_maxflow(), maxflow(), GraphNode::mincap, Graph::nnodes, Graph::nodes, GraphNode::parent, and TRUE.
Referenced by sepaSubtour().