Scippy

SCIP

Solving Constraint Integer Programs

grphbase.c File Reference

Detailed Description

includes several methods for Steiner problem graphs

Author
Thorsten Koch
Daniel Rehfeldt

This file contains several basic methods to process Steiner problem graphs. A graph can not be reduced in terms of edge or node size, but edges can be marked as EAT_FREE (to not be used anymore) and nodes may have degree one. The method 'graph_pack()' can be used to build a new graph that discards these nodes and edges.

Definition in file grphbase.c.

#include "scip/misc.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "portab.h"
#include "misc_stp.h"
#include "grph.h"
#include "heur_tm.h"

Go to the source code of this file.

Macros

#define STP_DELPSEUDO_MAXGRAD   5
 
#define STP_DELPSEUDO_MAXNEDGES   10
 

Functions

static SCIP_Bool cutoffEdge (SCIP *scip, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, const SCIP_Real *ecost, const SCIP_Real *ecostrev, int edgeidx1, int edgeidx2, int cutoffidx)
 
static void removeEdge (GRAPH *g, int e)
 
static int getNodeNumber (int grid_dim, int shiftcoord, int *ncoords, int *currcoord)
 
static void compEdgesObst (int coord, int grid_dim, int nobstacles, int *ncoords, int *currcoord, int *edgecosts, int *gridedgecount, int **coords, int **gridedges, int **obst_coords, char *inobstacle)
 
static void compEdges (int coord, int grid_dim, int *ncoords, int *currcoord, int *edgecosts, int *gridedgecount, int **coords, int **gridedges)
 
SCIP_RETCODE graph_obstgrid_create (SCIP *scip, GRAPH **gridgraph, int **coords, int **obst_coords, int nterms, int grid_dim, int nobstacles, int scale_order)
 
SCIP_RETCODE graph_grid_create (SCIP *scip, GRAPH **gridgraph, int **coords, int nterms, int grid_dim, int scale_order)
 
SCIP_RETCODE graph_grid_coordinates (SCIP *scip, int **coords, int **nodecoords, int *ncoords, int node, int grid_dim)
 
SCIP_RETCODE graph_pc_init (SCIP *scip, GRAPH *g, int sizeprize, int sizeterm2edge)
 
SCIP_RETCODE graph_pc_presolInit (SCIP *scip, GRAPH *g)
 
void graph_pc_presolExit (SCIP *scip, GRAPH *g)
 
SCIP_Bool graph_pc_term2edgeConsistent (const GRAPH *g)
 
void graph_pc_knot2nonTerm (GRAPH *g, int node)
 
void graph_pc_updateTerm2edge (GRAPH *newgraph, const GRAPH *oldgraph, int newtail, int newhead, int oldtail, int oldhead)
 
void graph_pc_2org (GRAPH *graph)
 
void graph_pc_2trans (GRAPH *graph)
 
void graph_pc_2orgcheck (GRAPH *graph)
 
void graph_pc_2transcheck (GRAPH *graph)
 
SCIP_Real graph_pc_getPosPrizeSum (SCIP *scip, const GRAPH *graph)
 
SCIP_RETCODE graph_pc_getSap (SCIP *scip, GRAPH *graph, GRAPH **newgraph, SCIP_Real *offset)
 
void graph_pc_adaptSap (SCIP *scip, SCIP_Real bigM, GRAPH *graph, SCIP_Real *offset)
 
SCIP_RETCODE graph_pc_getSapShift (SCIP *scip, GRAPH *graph, GRAPH **newgraph, SCIP_Real *offset)
 
SCIP_RETCODE graph_pc_getRsap (SCIP *scip, GRAPH *graph, GRAPH **newgraph, int *rootcands, int nrootcands, int root)
 
SCIP_RETCODE graph_pc_2pc (SCIP *scip, GRAPH *graph)
 
SCIP_RETCODE graph_pc_2rpc (SCIP *scip, GRAPH *graph)
 
SCIP_RETCODE graph_pc_2mw (SCIP *scip, GRAPH *graph, SCIP_Real *maxweights)
 
SCIP_RETCODE graph_pc_2rmw (SCIP *scip, GRAPH *graph)
 
SCIP_RETCODE graph_pc_mw2rmw (SCIP *scip, GRAPH *graph, SCIP_Real prizesum)
 
int graph_pc_deleteTerm (SCIP *scip, GRAPH *g, int i)
 
void graph_pc_subtractPrize (SCIP *scip, GRAPH *g, SCIP_Real cost, int i)
 
void graph_pc_chgPrize (SCIP *scip, GRAPH *g, SCIP_Real newprize, int i)
 
SCIP_RETCODE graph_pc_contractEdgeAncestors (SCIP *scip, GRAPH *g, int t, int s, int ets)
 
SCIP_RETCODE graph_pc_contractEdge (SCIP *scip, GRAPH *g, int *solnode, int t, int s, int i)
 
SCIP_Bool graph_pc_isPcMw (const GRAPH *g)
 
void graph_knot_add (GRAPH *p, int term)
 
void graph_knot_chg (GRAPH *p, int node, int term)
 
void graph_knot_del (SCIP *scip, GRAPH *g, int k, SCIP_Bool freeancestors)
 
SCIP_RETCODE graph_knot_delPseudo (SCIP *scip, GRAPH *g, const SCIP_Real *edgecosts, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, int vertex, SCIP_Bool *success)
 
SCIP_RETCODE graph_knot_contract (SCIP *scip, GRAPH *p, int *solnode, int t, int s)
 
SCIP_RETCODE graph_knot_contractLowdeg2High (SCIP *scip, GRAPH *g, int *solnode, int t, int s)
 
int graph_edge_redirect (SCIP *scip, GRAPH *g, int eki, int k, int j, SCIP_Real cost, SCIP_Bool forcedelete)
 
SCIP_RETCODE graph_edge_reinsert (SCIP *scip, GRAPH *g, int e1, int k1, int k2, SCIP_Real cost, IDX *ancestors0, IDX *ancestors1, IDX *revancestors0, IDX *revancestors1, SCIP_Bool forcedelete)
 
void graph_edge_add (SCIP *scip, GRAPH *g, int tail, int head, SCIP_Real cost1, SCIP_Real cost2)
 
void graph_edge_del (SCIP *scip, GRAPH *g, int e, SCIP_Bool freeancestors)
 
void graph_edge_hide (GRAPH *g, int e)
 
void graph_edge_printInfo (SCIP *scip, const GRAPH *g, int e)
 
SCIP_RETCODE graph_sol_reroot (SCIP *scip, GRAPH *g, int *result, int newroot)
 
SCIP_Bool graph_sol_unreduced (SCIP *scip, const GRAPH *graph, const int *result)
 
SCIP_Bool graph_sol_valid (SCIP *scip, const GRAPH *graph, const int *result)
 
void graph_sol_setNodeList (const GRAPH *g, STP_Bool *solnode, IDX *listnode)
 
SCIP_Real graph_sol_getObj (const SCIP_Real *edgecost, const int *soledge, SCIP_Real offset, int nedges)
 
SCIP_RETCODE graph_sol_getOrg (SCIP *scip, const GRAPH *transgraph, const GRAPH *orggraph, const int *transsoledge, int *orgsoledge)
 
SCIP_RETCODE graph_sol_markPcancestors (SCIP *scip, IDX **pcancestors, const int *tails, const int *heads, int orgnnodes, STP_Bool *solnodemark, STP_Bool *soledgemark, int *solnodequeue, int *nsolnodes, int *nsoledges)
 
void graph_get_NVET (const GRAPH *graph, int *nnodes, int *nedges, int *nterms)
 
void graph_get_csr (const GRAPH *g, int *RESTRICT edgearr, int *RESTRICT tailarr, int *RESTRICT start, int *nnewedges)
 
SCIP_RETCODE graph_get_edgeConflicts (SCIP *scip, const GRAPH *g)
 
SCIP_RETCODE graph_init (SCIP *scip, GRAPH **g, int ksize, int esize, int layers)
 
SCIP_RETCODE graph_init_history (SCIP *scip, GRAPH *graph)
 
SCIP_RETCODE graph_resize (SCIP *scip, GRAPH *g, int ksize, int esize, int layers)
 
void graph_free (SCIP *scip, GRAPH **graph, SCIP_Bool final)
 
void graph_free_history (SCIP *scip, GRAPH *p)
 
void graph_free_historyDeep (SCIP *scip, GRAPH *p)
 
SCIP_RETCODE graph_copy_data (SCIP *scip, const GRAPH *orgraph, GRAPH *copygraph)
 
SCIP_RETCODE graph_copy (SCIP *scip, const GRAPH *orgraph, GRAPH **copygraph)
 
void graph_show (const GRAPH *p)
 
void graph_uncover (GRAPH *g)
 
SCIP_RETCODE graph_pack (SCIP *scip, GRAPH *graph, GRAPH **newgraph, SCIP_Bool verbose)
 
void graph_trail (const GRAPH *g, int i)
 
SCIP_RETCODE graph_trail_arr (SCIP *scip, const GRAPH *g, int i)
 
SCIP_RETCODE graph_termsReachable (SCIP *scip, const GRAPH *g, SCIP_Bool *reachable)
 
SCIP_Bool graph_valid (const GRAPH *g)
 

Macro Definition Documentation

◆ STP_DELPSEUDO_MAXGRAD

#define STP_DELPSEUDO_MAXGRAD   5

Definition at line 44 of file grphbase.c.

Referenced by graph_knot_delPseudo().

◆ STP_DELPSEUDO_MAXNEDGES

#define STP_DELPSEUDO_MAXNEDGES   10

Definition at line 45 of file grphbase.c.

Referenced by graph_knot_delPseudo().

Function Documentation

◆ cutoffEdge()

static SCIP_Bool cutoffEdge ( SCIP scip,
const SCIP_Real cutoffs,
const SCIP_Real cutoffsrev,
const SCIP_Real ecost,
const SCIP_Real ecostrev,
int  edgeidx1,
int  edgeidx2,
int  cutoffidx 
)
inlinestatic

can edge in pseudo-elimination method be cut off?

Parameters
scipSCIP data
cutoffscutoff values for each incident edge
cutoffsrevrevere cutoff values (or NULL if undirected)
ecostedge cost
ecostrevreverse edge cost
edgeidx1index of first edge to be checked (wrt provided arrays)
edgeidx2index of second edge to be checked (wrt provided arrays)
cutoffidxindex for cutoff array

Definition at line 53 of file grphbase.c.

References FALSE, NULL, SCIP_Real, SCIPisGT(), and TRUE.

Referenced by graph_knot_delPseudo().

◆ removeEdge()

static void removeEdge ( GRAPH g,
int  e 
)
inlinestatic
Parameters
gthe graph
ethe edge to be removed

Definition at line 89 of file grphbase.c.

References GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::rootedgeprevs, GRAPH::source, and GRAPH::tail.

Referenced by graph_edge_del(), and graph_edge_hide().

◆ getNodeNumber()

static int getNodeNumber ( int  grid_dim,
int  shiftcoord,
int *  ncoords,
int *  currcoord 
)
static

used by graph_grid_create

Definition at line 143 of file grphbase.c.

References number.

Referenced by compEdges(), compEdgesObst(), graph_grid_create(), and graph_obstgrid_create().

◆ compEdgesObst()

static void compEdgesObst ( int  coord,
int  grid_dim,
int  nobstacles,
int *  ncoords,
int *  currcoord,
int *  edgecosts,
int *  gridedgecount,
int **  coords,
int **  gridedges,
int **  obst_coords,
char *  inobstacle 
)
static

used by graph_obstgrid_create

Definition at line 172 of file grphbase.c.

References FALSE, getNodeNumber(), TRUE, x, and y.

Referenced by graph_obstgrid_create().

◆ compEdges()

static void compEdges ( int  coord,
int  grid_dim,
int *  ncoords,
int *  currcoord,
int *  edgecosts,
int *  gridedgecount,
int **  coords,
int **  gridedges 
)
static

◆ graph_obstgrid_create()

SCIP_RETCODE graph_obstgrid_create ( SCIP scip,
GRAPH **  gridgraph,
int **  coords,
int **  obst_coords,
int  nterms,
int  grid_dim,
int  nobstacles,
int  scale_order 
)

creates a graph out of a given grid

Parameters
scipSCIP data structure
gridgraphthe (obstacle) grid graph to be constructed
coordscoordinates of all points
obst_coordscoordinates of obstacles
ntermsnumber of terminals
grid_dimdimension of the problem
nobstaclesnumber of obstacles
scale_orderscale factor

Definition at line 419 of file grphbase.c.

References compEdgesObst(), FALSE, getNodeNumber(), graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pack(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, nnodes, nterms, NULL, pow(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPsortInt(), GRAPH::source, STP_OARSMT, GRAPH::stp_type, and TRUE.

Referenced by graph_load().

◆ graph_grid_create()

SCIP_RETCODE graph_grid_create ( SCIP scip,
GRAPH **  gridgraph,
int **  coords,
int  nterms,
int  grid_dim,
int  scale_order 
)

creates a graph out of a given grid

Parameters
scipSCIP data structure
gridgraphthe grid graph to be constructed
coordscoordinates
ntermsnumber of terminals
grid_dimproblem dimension
scale_orderscale order

Definition at line 582 of file grphbase.c.

References compEdges(), getNodeNumber(), graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, nnodes, nterms, NULL, pow(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPsortInt(), STP_RSMT, and GRAPH::stp_type.

Referenced by graph_load().

◆ graph_grid_coordinates()

SCIP_RETCODE graph_grid_coordinates ( SCIP scip,
int **  coords,
int **  nodecoords,
int *  ncoords,
int  node,
int  grid_dim 
)

computes coordinates of node 'node'

Parameters
scipSCIP data structure
coordscoordinates
nodecoordscoordinates of the node (to be computed)
ncoordsarray with number of coordinate
nodethe node
grid_dimproblem dimension

Definition at line 730 of file grphbase.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by SCIPprobdataWriteSolution().

◆ graph_pc_init()

SCIP_RETCODE graph_pc_init ( SCIP scip,
GRAPH g,
int  sizeprize,
int  sizeterm2edge 
)

allocates (first and second) and initializes (only second) arrays for PC and MW problems

Parameters
scipSCIP data structure
gthe graph
sizeprizesize of prize array to allocate (or -1)
sizeterm2edgesize of term2edge array to allocate and initialize to -1 (or -1)

Definition at line 766 of file grphbase.c.

References NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and GRAPH::term2edge.

Referenced by buildsolgraph(), graph_load(), graph_pack(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getRsap(), SCIPStpHeurAscendPruneRun(), and SCIPStpHeurRecExclude().

◆ graph_pc_presolInit()

SCIP_RETCODE graph_pc_presolInit ( SCIP scip,
GRAPH g 
)

changes graph of PC and MW problems needed for presolving routines

Parameters
scipSCIP data structure
gthe graph

Definition at line 794 of file grphbase.c.

References EAT_LAST, GRAPH::edges, GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::rootedgeprevs, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, GRAPH::source, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_pc_getRsap(), graph_pc_getSap(), and redLoopPc().

◆ graph_pc_presolExit()

void graph_pc_presolExit ( SCIP scip,
GRAPH g 
)

changes graph of PC and MW problems needed after exiting presolving routines

Parameters
scipSCIP data structure
gthe graph

Definition at line 837 of file grphbase.c.

References NULL, GRAPH::rootedgeprevs, SCIPfreeMemoryArray, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_pc_getRsap(), graph_pc_getSap(), and redLoopPc().

◆ graph_pc_term2edgeConsistent()

SCIP_Bool graph_pc_term2edgeConsistent ( const GRAPH g)

checks consistency of term2edge array ONLY for non-extended graphs!

Parameters
gthe graph

Definition at line 853 of file grphbase.c.

References EAT_LAST, GRAPH::extended, FALSE, flipedge, GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPdebugMessage, GRAPH::source, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by redLoopMw(), redLoopPc(), and SCIPStpHeurRecRun().

◆ graph_pc_knot2nonTerm()

void graph_pc_knot2nonTerm ( GRAPH g,
int  node 
)

change property of node to non-terminal

Parameters
gthe graph
nodenode to be changed

Definition at line 909 of file grphbase.c.

References Is_term, NULL, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, and GRAPH::terms.

Referenced by adjust0term(), graph_pc_deleteTerm(), reduce_simple_pc(), and trydg1edgepc().

◆ graph_pc_updateTerm2edge()

void graph_pc_updateTerm2edge ( GRAPH newgraph,
const GRAPH oldgraph,
int  newtail,
int  newhead,
int  oldtail,
int  oldhead 
)

updates term2edge array for new graph

Parameters
newgraphthe new graph
oldgraphthe old graph
newtailtail in new graph
newheadhead in new graph
oldtailtail in old graph
oldheadhead in old graph

Definition at line 928 of file grphbase.c.

References GRAPH::edges, GRAPH::extended, flipedge, Is_gterm, NULL, GRAPH::source, GRAPH::term, and GRAPH::term2edge.

Referenced by buildsolgraph(), graph_pack(), SCIPStpHeurAscendPruneRun(), and SCIPStpHeurRecExclude().

◆ graph_pc_2org()

◆ graph_pc_2trans()

void graph_pc_2trans ( GRAPH graph)

◆ graph_pc_2orgcheck()

void graph_pc_2orgcheck ( GRAPH graph)

graph_pc_2org if extended

Parameters
graphthe graph

Definition at line 1028 of file grphbase.c.

References GRAPH::extended, graph_pc_2org(), and NULL.

Referenced by reduce_daPcMw(), reduce_extendedEdge(), and reducePcMw().

◆ graph_pc_2transcheck()

void graph_pc_2transcheck ( GRAPH graph)

graph_pc_2trans if not extended

Parameters
graphthe graph

Definition at line 1041 of file grphbase.c.

References GRAPH::extended, graph_pc_2trans(), and NULL.

Referenced by computePertubedSol(), graph_pc_getRsap(), reduce_da(), SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurTMRun().

◆ graph_pc_getPosPrizeSum()

SCIP_Real graph_pc_getPosPrizeSum ( SCIP scip,
const GRAPH graph 
)
Parameters
scipSCIP data structure
graphthe graph

Definition at line 1054 of file grphbase.c.

References BLOCKED, GRAPH::extended, Is_term, GRAPH::knots, NULL, GRAPH::prize, SCIP_Real, GRAPH::source, and GRAPH::term.

Referenced by redLoopMw(), and redLoopPc().

◆ graph_pc_getSap()

SCIP_RETCODE graph_pc_getSap ( SCIP scip,
GRAPH graph,
GRAPH **  newgraph,
SCIP_Real offset 
)

◆ graph_pc_adaptSap()

void graph_pc_adaptSap ( SCIP scip,
SCIP_Real  bigM,
GRAPH graph,
SCIP_Real offset 
)

adapts SAP deriving from PCST or MWCS problem with new big M

Parameters
scipSCIP data structure
bigMnew big M value
graphthe SAP graph
offsetthe offset

Definition at line 1174 of file grphbase.c.

References GRAPH::cost, EAT_LAST, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, and GRAPH::source.

◆ graph_pc_getSapShift()

SCIP_RETCODE graph_pc_getSapShift ( SCIP scip,
GRAPH graph,
GRAPH **  newgraph,
SCIP_Real offset 
)

◆ graph_pc_getRsap()

SCIP_RETCODE graph_pc_getRsap ( SCIP scip,
GRAPH graph,
GRAPH **  newgraph,
int *  rootcands,
int  nrootcands,
int  root 
)

alters the graph for prize-collecting problems with given root

Parameters
scipSCIP data structure
graphthe graph
newgraphthe new graph
rootcandsarray containing all vertices that could be used as root
nrootcandsnumber of all vertices could be used as root
rootthe root of the new SAP

Definition at line 1365 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_copy(), graph_edge_del(), graph_edge_redirect(), graph_knot_chg(), graph_pc_2transcheck(), graph_pc_init(), graph_pc_presolExit(), graph_pc_presolInit(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by reduce_daPcMw().

◆ graph_pc_2pc()

◆ graph_pc_2rpc()

◆ graph_pc_2mw()

SCIP_RETCODE graph_pc_2mw ( SCIP scip,
GRAPH graph,
SCIP_Real maxweights 
)

alters the graph for MWCS problems

Parameters
scipSCIP data structure
graphthe graph
maxweightsarray containing the weight of each node

Definition at line 1682 of file grphbase.c.

References GRAPH::cost, EAT_LAST, graph_knot_chg(), graph_pc_2pc(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load().

◆ graph_pc_2rmw()

◆ graph_pc_mw2rmw()

SCIP_RETCODE graph_pc_mw2rmw ( SCIP scip,
GRAPH graph,
SCIP_Real  prizesum 
)

transforms MWCSP to RMWCSP if possible

Parameters
scipSCIP data structure
graphthe graph
prizesumsum of positive prizes

Definition at line 1850 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), graph_knot_chg(), GRAPH::head, Is_pterm, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisZero(), GRAPH::source, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by redLoopMw().

◆ graph_pc_deleteTerm()

int graph_pc_deleteTerm ( SCIP scip,
GRAPH g,
int  i 
)

delete a terminal for a (rooted) prize-collecting problem

Parameters
scipSCIP data structure
ggraph data structure
iindex of the terminal

Definition at line 1945 of file grphbase.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_pc_knot2nonTerm(), GRAPH::head, Is_pterm, Is_term, GRAPH::mark, NULL, GRAPH::outbeg, GRAPH::source, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.

Referenced by reduce_bound(), reduce_simple_mw(), reduce_simple_pc(), reduceSPG(), STPStpBranchruleParseConsname(), and trydg1edgepc().

◆ graph_pc_subtractPrize()

void graph_pc_subtractPrize ( SCIP scip,
GRAPH g,
SCIP_Real  cost,
int  i 
)

subtract a given sum from the prize of a terminal

Parameters
scipSCIP data structure
gthe graph
costcost to be subtracted
ithe terminal

Definition at line 1992 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisEQ(), SCIPisGE(), GRAPH::source, STP_MWCSP, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, and GRAPH::term.

Referenced by graph_pc_contractEdge().

◆ graph_pc_chgPrize()

void graph_pc_chgPrize ( SCIP scip,
GRAPH g,
SCIP_Real  newprize,
int  i 
)

change prize of a terminal

Parameters
scipSCIP data structure
gthe graph
newprizeprize to be subtracted
ithe terminal

Definition at line 2035 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisEQ(), SCIPisGE(), GRAPH::source, STP_MWCSP, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, and GRAPH::term.

Referenced by STPStpBranchruleParseConsname().

◆ graph_pc_contractEdgeAncestors()

SCIP_RETCODE graph_pc_contractEdgeAncestors ( SCIP scip,
GRAPH g,
int  t,
int  s,
int  ets 
)

contract ancestors of an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem

Parameters
scipSCIP data structure
gthe graph
ttail node to be contracted (surviving node)
shead node to be contracted
etsedge from t to s or -1

Definition at line 2079 of file grphbase.c.

References GRAPH::ancestors, EAT_LAST, GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, and SCIPintListNodeAppendCopy().

Referenced by graph_pc_contractEdge(), and reduce_simple_mw().

◆ graph_pc_contractEdge()

SCIP_RETCODE graph_pc_contractEdge ( SCIP scip,
GRAPH g,
int *  solnode,
int  t,
int  s,
int  i 
)

contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem

Parameters
scipSCIP data structure
gthe graph
solnodesolution nodes or NULL
ttail node to be contracted (surviving node)
shead node to be contracted
iterminal to add offset to

Definition at line 2105 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::grad, graph_edge_del(), graph_knot_chg(), graph_knot_contract(), graph_pc_contractEdgeAncestors(), graph_pc_subtractPrize(), GRAPH::head, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), GRAPH::source, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by reduce_nv(), reduce_nvAdv(), reduce_simple_mw(), reduce_simple_pc(), reduce_sl(), and trydg1edgepc().

◆ graph_pc_isPcMw()

SCIP_Bool graph_pc_isPcMw ( const GRAPH g)

is this graph a prize-collecting or maximum-weight variant?

Parameters
gthe graph

Definition at line 2188 of file grphbase.c.

References NULL, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_init_history(), graph_sol_getOrg(), selectBranchingVertexByDegree(), and selectBranchingVertexBySol().

◆ graph_knot_add()

◆ graph_knot_chg()

◆ graph_knot_del()

void graph_knot_del ( SCIP scip,
GRAPH g,
int  k,
SCIP_Bool  freeancestors 
)

delete node

Parameters
scipSCIP data structure
gthe graph
kthe node
freeancestorsfree edge ancestors?

Definition at line 2246 of file grphbase.c.

References EAT_LAST, graph_edge_del(), NULL, and GRAPH::outbeg.

Referenced by graph_knot_delPseudo(), reduceSPG(), reduceWithNodeFixingBounds(), and STPStpBranchruleParseConsname().

◆ graph_knot_delPseudo()

SCIP_RETCODE graph_knot_delPseudo ( SCIP scip,
GRAPH g,
const SCIP_Real edgecosts,
const SCIP_Real cutoffs,
const SCIP_Real cutoffsrev,
int  vertex,
SCIP_Bool success 
)

pseudo delete node, i.e. reconnect neighbors; maximum degree of 4!

Parameters
scipSCIP data structure
gthe graph
edgecostsedge costs for cutoff
cutoffscutoff values for each incident edge
cutoffsrevrevere cutoff values (or NULL if undirected)
vertexthe vertex
successhas node been pseudo-eliminated?

Definition at line 2262 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, cutoffEdge(), EAT_LAST, FALSE, flipedge, GRAPH::grad, graph_edge_reinsert(), graph_knot_del(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, GRAPH::tail, and TRUE.

Referenced by reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundPrune(), and reduceWithNodeReplaceBounds().

◆ graph_knot_contract()

SCIP_RETCODE graph_knot_contract ( SCIP scip,
GRAPH p,
int *  solnode,
int  t,
int  s 
)

contract an edge, given by its endpoints

Parameters
scipSCIP data structure
pgraph data structure
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
ttail node to be contracted
shead node to be contracted

Definition at line 2433 of file grphbase.c.

References GRAPH::ancestors, CONNECT, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, GRAPH::grad, graph_edge_del(), graph_knot_chg(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::layers, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by getlecloseterms(), graph_knot_contractLowdeg2High(), graph_pc_contractEdge(), reduce_contractZeroEdges(), reduce_nv(), reduce_nvAdv(), reduce_rpt(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), and reduce_sl().

◆ graph_knot_contractLowdeg2High()

SCIP_RETCODE graph_knot_contractLowdeg2High ( SCIP scip,
GRAPH g,
int *  solnode,
int  t,
int  s 
)

contract endpoint of lower degree into endpoint of higher degree

Parameters
scipSCIP data structure
ggraph data structure
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
ttail node to be contracted
shead node to be contracted

Definition at line 2666 of file grphbase.c.

References GRAPH::grad, graph_knot_contract(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_simple().

◆ graph_edge_redirect()

int graph_edge_redirect ( SCIP scip,
GRAPH g,
int  eki,
int  k,
int  j,
SCIP_Real  cost,
SCIP_Bool  forcedelete 
)
Parameters
scipSCIP data structure
gthe graph
ekithe edge
knew tail
jnew head
costnew cost
forcedeletedelete edge eki if it is not used?

Definition at line 2685 of file grphbase.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), and GRAPH::tail.

Referenced by graph_edge_reinsert(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), reduce_simple_pc(), and traverseChain().

◆ graph_edge_reinsert()

SCIP_RETCODE graph_edge_reinsert ( SCIP scip,
GRAPH g,
int  e1,
int  k1,
int  k2,
SCIP_Real  cost,
IDX ancestors0,
IDX ancestors1,
IDX revancestors0,
IDX revancestors1,
SCIP_Bool  forcedelete 
)

reinsert an edge to replace two other edges

Parameters
scipSCIP data structure
gthe graph
e1edge to reinsert
k1tail
k2head
costedge cost
ancestors0ancestors of first edge
ancestors1ancestors of second edge
revancestors0reverse ancestors of first edge
revancestors1reverse ancestors of first edge
forcedeletedelete edge e1 if it is not used?

Definition at line 2757 of file grphbase.c.

References GRAPH::ancestors, Edge_anti, graph_edge_redirect(), NULL, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), and SCIPintListNodeFree().

Referenced by graph_knot_delPseudo().

◆ graph_edge_add()

void graph_edge_add ( SCIP scip,
GRAPH g,
int  tail,
int  head,
SCIP_Real  cost1,
SCIP_Real  cost2 
)

add a new edge to the graph

Parameters
scipSCIP data structure
gthe graph
tailtail of the new edge
headhead of the new edge
cost1tail to head cost
cost2head to tail cost

Definition at line 2790 of file grphbase.c.

References GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisEQ(), SCIPisGE(), GRAPH::tail, and UNKNOWN.

Referenced by compEdges(), graph_grid_create(), graph_obstgrid_create(), graph_pack(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getSap(), and graph_pc_getSapShift().

◆ graph_edge_del()

◆ graph_edge_hide()

void graph_edge_hide ( GRAPH g,
int  e 
)

hide edge

Parameters
gthe graph
ethe edge

Definition at line 2891 of file grphbase.c.

References EAT_FREE, EAT_HIDE, GRAPH::grad, GRAPH::head, GRAPH::ieat, NULL, GRAPH::oeat, removeEdge(), and GRAPH::tail.

◆ graph_edge_printInfo()

void graph_edge_printInfo ( SCIP scip,
const GRAPH g,
int  e 
)

print edge info

Parameters
scipSCIP data structure
gthe graph
ethe edge

Definition at line 2935 of file grphbase.c.

References h, GRAPH::head, GRAPH::tail, and GRAPH::term.

◆ graph_sol_reroot()

SCIP_RETCODE graph_sol_reroot ( SCIP scip,
GRAPH g,
int *  result,
int  newroot 
)

changes solution according to given root

Parameters
scipSCIP data structure
gthe graph
resultsolution array (CONNECT/UNKNOWN)
newrootthe new root

Definition at line 2947 of file grphbase.c.

References a, CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_da(), and reduce_daPcMw().

◆ graph_sol_unreduced()

SCIP_Bool graph_sol_unreduced ( SCIP scip,
const GRAPH graph,
const int *  result 
)

checks whether edge(s) of given primal solution have been deleted

Parameters
scipSCIP data structure
graphgraph data structure
resultsolution array, indicating whether an edge is in the solution

Definition at line 3050 of file grphbase.c.

References CONNECT, EAT_FREE, GRAPH::edges, FALSE, NULL, GRAPH::oeat, and TRUE.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

◆ graph_sol_valid()

◆ graph_sol_setNodeList()

void graph_sol_setNodeList ( const GRAPH g,
STP_Bool solnode,
IDX listnode 
)

mark endpoints of edges in given list

Parameters
ggraph data structure
solnodesolution nodes array (TRUE/FALSE)
listnodeedge list

Definition at line 3174 of file grphbase.c.

References GRAPH::head, Int_List_Node::index, NULL, Int_List_Node::parent, GRAPH::tail, and TRUE.

Referenced by graph_sol_getOrg(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_sol_getObj()

SCIP_Real graph_sol_getObj ( const SCIP_Real edgecost,
const int *  soledge,
SCIP_Real  offset,
int  nedges 
)

◆ graph_sol_getOrg()

SCIP_RETCODE graph_sol_getOrg ( SCIP scip,
const GRAPH transgraph,
const GRAPH orggraph,
const int *  transsoledge,
int *  orgsoledge 
)

get original solution

Parameters
scipSCIP data structure
transgraphthe transformed graph
orggraphthe original graph
transsoledgesolution for transformed problem
orgsoledgenew retransformed solution

Definition at line 3218 of file grphbase.c.

References GRAPH::ancestors, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, GRAPH::fixedges, graph_pc_isPcMw(), graph_sol_markPcancestors(), graph_sol_setNodeList(), graph_sol_valid(), GRAPH::head, GRAPH::knots, NULL, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), GRAPH::stp_type, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurPruneUpdateSols().

◆ graph_sol_markPcancestors()

SCIP_RETCODE graph_sol_markPcancestors ( SCIP scip,
IDX **  pcancestors,
const int *  tails,
const int *  heads,
int  orgnnodes,
STP_Bool solnodemark,
STP_Bool soledgemark,
int *  solnodequeue,
int *  nsolnodes,
int *  nsoledges 
)

mark original solution

Parameters
scipSCIP data structure
pcancestorsthe ancestors
tailstails array
headsheads array
orgnnodesoriginal number of nodes
solnodemarksolution nodes mark array
soledgemarksolution edges mark array or NULL
solnodequeuesolution nodes queue or NULL
nsolnodesnumber of solution nodes or NULL
nsoledgesnumber of solution edges or NULL

Definition at line 3292 of file grphbase.c.

References nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by graph_sol_getOrg(), SCIPprobdataWriteSolution(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_get_NVET()

void graph_get_NVET ( const GRAPH graph,
int *  nnodes,
int *  nedges,
int *  nterms 
)

get (real) number of nodes , edges, terminals

Parameters
graphthe graph
nnodesnumber of nodes
nedgesnumber of edges
ntermsnumber of terminals

Definition at line 3386 of file grphbase.c.

References GRAPH::grad, Is_term, GRAPH::knots, NULL, and GRAPH::term.

Referenced by SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_get_csr()

void graph_get_csr ( const GRAPH g,
int *RESTRICT  edgearr,
int *RESTRICT  tailarr,
int *RESTRICT  start,
int *  nnewedges 
)
Parameters
gthe graph
edgearroriginal edge array [0,...,nedges - 1]
tailarrtail of csr edge [0,...,nedges - 1]
startstart array [0,...,nnodes]
nnewedgespointer to store number of new edges

Definition at line 3421 of file grphbase.c.

References EAT_LAST, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, nnodes, NULL, and GRAPH::tail.

◆ graph_get_edgeConflicts()

SCIP_RETCODE graph_get_edgeConflicts ( SCIP scip,
const GRAPH g 
)
Parameters
scipSCIP data structure
gthe graph

Definition at line 3452 of file grphbase.c.

References GRAPH::ancestors, GRAPH::edges, NULL, GRAPH::orgedges, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

◆ graph_init()

SCIP_RETCODE graph_init ( SCIP scip,
GRAPH **  g,
int  ksize,
int  esize,
int  layers 
)

initialize graph

Parameters
scipSCIP data structure
gnew graph
ksizeslots for nodes
esizeslots for edges
layersnumber of layers (only needed for packing, otherwise 1)

Definition at line 3495 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, GRAPH::fixedges, GRAPH::grad, GRAPH::grid_coordinates, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, GRAPH::maxdeg, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, GRAPH::prize, GRAPH::rootedgeprevs, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, SCIPdebugMessage, GRAPH::source, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and UNKNOWN.

Referenced by buildsolgraph(), graph_copy(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), reduce_sdPc(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), and SCIPStpHeurRecExclude().

◆ graph_init_history()

◆ graph_resize()

SCIP_RETCODE graph_resize ( SCIP scip,
GRAPH g,
int  ksize,
int  esize,
int  layers 
)

enlarge given graph

Parameters
scipSCIP data structure
ggraph to be resized
ksizenew node slots
esizenew edge slots
layerslayers (set to -1 by default)

Definition at line 3635 of file grphbase.c.

References GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPreallocMemoryArray, GRAPH::tail, and GRAPH::term.

Referenced by compEdges(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getSap(), and graph_pc_getSapShift().

◆ graph_free()

◆ graph_free_history()

void graph_free_history ( SCIP scip,
GRAPH p 
)

free the history

Parameters
scipSCIP data
pgraph data

Definition at line 3740 of file grphbase.c.

References GRAPH::ancestors, GRAPH::edges, NULL, Int_List_Node::parent, SCIPfreeBlockMemory, and SCIPfreeMemoryArray.

Referenced by graph_free(), and redbasedVarfixing().

◆ graph_free_historyDeep()

void graph_free_historyDeep ( SCIP scip,
GRAPH p 
)

free the deep history

Parameters
scipSCIP data
pgraph data

Definition at line 3764 of file grphbase.c.

References GRAPH::fixedges, GRAPH::norgmodelknots, NULL, GRAPH::orghead, GRAPH::orgtail, Int_List_Node::parent, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, SCIPfreeBlockMemory, and SCIPfreeMemoryArray.

Referenced by graph_free(), and redbasedVarfixing().

◆ graph_copy_data()

◆ graph_copy()

SCIP_RETCODE graph_copy ( SCIP scip,
const GRAPH orgraph,
GRAPH **  copygraph 
)

◆ graph_show()

void graph_show ( const GRAPH p)

◆ graph_uncover()

void graph_uncover ( GRAPH g)

reinsert all hidden edges

Parameters
gthe graph

Definition at line 3941 of file grphbase.c.

References EAT_HIDE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, and GRAPH::tail.

◆ graph_pack()

◆ graph_trail()

void graph_trail ( const GRAPH g,
int  i 
)

traverse the graph and mark all reached nodes (g->mark[i] has to be FALSE for all i)

Parameters
gthe new graph
inode to start from

Definition at line 4188 of file grphbase.c.

References a, EAT_LAST, GRAPH::grad, GRAPH::head, GRAPH::knots, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL_ABORT, SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), and TRUE.

Referenced by graph_valid().

◆ graph_trail_arr()

SCIP_RETCODE graph_trail_arr ( SCIP scip,
const GRAPH g,
int  i 
)

traverse the graph and mark all reached nodes (g->mark[i] has to be FALSE for all i) .... uses an array and should be faster than graph_trail, but needs a scip

Parameters
scipscip struct
gthe new graph
inode to start from

Definition at line 4242 of file grphbase.c.

References a, EAT_LAST, GRAPH::grad, GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by graph_termsReachable(), level0(), and level0save().

◆ graph_termsReachable()

SCIP_RETCODE graph_termsReachable ( SCIP scip,
const GRAPH g,
SCIP_Bool reachable 
)

checks whether all terminals are reachable from root

Parameters
scipscip struct
gthe new graph
reachableare they reachable?

Definition at line 4299 of file grphbase.c.

References FALSE, graph_trail_arr(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_OKAY, GRAPH::source, GRAPH::term, and TRUE.

◆ graph_valid()