# SCIP

Solving Constraint Integer Programs

grphbase.c File Reference

## Detailed Description

includes several methods for Steiner problem graphs

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_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

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().

## ◆ 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
 scip SCIP data cutoffs cutoff values for each incident edge cutoffsrev revere cutoff values (or NULL if undirected) ecost edge cost ecostrev reverse edge cost edgeidx1 index of first edge to be checked (wrt provided arrays) edgeidx2 index of second edge to be checked (wrt provided arrays) cutoffidx index 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
 g the graph e the edge to be removed

Definition at line 89 of file grphbase.c.

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

used by graph_grid_create

Definition at line 237 of file grphbase.c.

Referenced by graph_grid_create().

## ◆ 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
 scip SCIP data structure gridgraph the (obstacle) grid graph to be constructed coords coordinates of all points obst_coords coordinates of obstacles nterms number of terminals grid_dim dimension of the problem nobstacles number of obstacles scale_order scale factor

Definition at line 419 of file grphbase.c.

## ◆ 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
 scip SCIP data structure gridgraph the grid graph to be constructed coords coordinates nterms number of terminals grid_dim problem dimension scale_order scale order

Definition at line 582 of file grphbase.c.

## ◆ 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
 scip SCIP data structure coords coordinates nodecoords coordinates of the node (to be computed) ncoords array with number of coordinate node the node grid_dim problem 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
 scip SCIP data structure g the graph sizeprize size of prize array to allocate (or -1) sizeterm2edge size 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.

## ◆ graph_pc_presolInit()

 SCIP_RETCODE graph_pc_presolInit ( SCIP * scip, GRAPH * g )

changes graph of PC and MW problems needed for presolving routines

Parameters
 scip SCIP data structure g the graph

Definition at line 794 of file grphbase.c.

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
 scip SCIP data structure g the 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
 g the graph

Definition at line 853 of file grphbase.c.

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
 g the graph node node to be changed

Definition at line 909 of file grphbase.c.

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
 newgraph the new graph oldgraph the old graph newtail tail in new graph newhead head in new graph oldtail tail in old graph oldhead head 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()

 void graph_pc_2org ( GRAPH * graph )

mark terminals and switch terminal property to original terminals

Parameters
 graph the graph

Definition at line 964 of file grphbase.c.

## ◆ graph_pc_2trans()

 void graph_pc_2trans ( GRAPH * graph )

unmark terminals and switch terminal property to transformed terminals

Parameters
 graph the graph

Definition at line 1002 of file grphbase.c.

## ◆ graph_pc_2orgcheck()

 void graph_pc_2orgcheck ( GRAPH * graph )

graph_pc_2org if extended

Parameters
 graph the 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
 graph the graph

Definition at line 1041 of file grphbase.c.

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

## ◆ graph_pc_getPosPrizeSum()

 SCIP_Real graph_pc_getPosPrizeSum ( SCIP * scip, const GRAPH * graph )
Parameters
 scip SCIP data structure graph the 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 )

alters the graph for prize collecting problems

Parameters
 scip SCIP data structure graph the graph newgraph the new graph offset offset

Definition at line 1075 of file grphbase.c.

Referenced by reduce_daPcMw(), reduce_daSlackPruneMw(), and SCIPStpDualAscentPcMw().

 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
 scip SCIP data structure bigM new big M value graph the SAP graph offset the 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 )

alters the graph for prize collecting problems and shifts weights to reduce number of terminal

Parameters
 scip SCIP data structure graph the graph newgraph the new graph offset offset

Definition at line 1204 of file grphbase.c.

## ◆ 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
 scip SCIP data structure graph the graph newgraph the new graph rootcands array containing all vertices that could be used as root nrootcands number of all vertices could be used as root root the root of the new SAP

Definition at line 1365 of file grphbase.c.

Referenced by reduce_daPcMw().

## ◆ graph_pc_2pc()

 SCIP_RETCODE graph_pc_2pc ( SCIP * scip, GRAPH * graph )

alters the graph for prize collecting problems

Parameters
 scip SCIP data structure graph the graph

Definition at line 1516 of file grphbase.c.

Referenced by graph_load(), and graph_pc_2mw().

## ◆ graph_pc_2rpc()

 SCIP_RETCODE graph_pc_2rpc ( SCIP * scip, GRAPH * graph )

alters the graph for rooted prize collecting problems

Parameters
 scip SCIP data structure graph the graph

Definition at line 1597 of file grphbase.c.

## ◆ graph_pc_2mw()

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

alters the graph for MWCS problems

Parameters
 scip SCIP data structure graph the graph maxweights array containing the weight of each node

Definition at line 1678 of file grphbase.c.

## ◆ graph_pc_2rmw()

 SCIP_RETCODE graph_pc_2rmw ( SCIP * scip, GRAPH * graph )

alters the graph for RMWCS problems

Parameters
 scip SCIP data structure graph the graph

Definition at line 1737 of file grphbase.c.

## ◆ graph_pc_mw2rmw()

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

transforms MWCSP to RMWCSP if possible

Parameters
 scip SCIP data structure graph the graph prizesum sum of positive prizes

Definition at line 1846 of file grphbase.c.

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
 scip SCIP data structure g graph data structure i index of the terminal

Definition at line 1941 of file grphbase.c.

## ◆ 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
 scip SCIP data structure g the graph cost cost to be subtracted i the terminal

Definition at line 1988 of file grphbase.c.

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
 scip SCIP data structure g the graph newprize prize to be subtracted i the terminal

Definition at line 2031 of file grphbase.c.

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
 scip SCIP data structure g the graph t tail node to be contracted (surviving node) s head node to be contracted ets edge from t to s or -1

Definition at line 2075 of file grphbase.c.

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
 scip SCIP data structure g the graph solnode solution nodes or NULL t tail node to be contracted (surviving node) s head node to be contracted i terminal to add offset to

Definition at line 2101 of file grphbase.c.

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
 g the graph

Definition at line 2184 of file grphbase.c.

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

 void graph_knot_add ( GRAPH * p, int term )

Parameters
 p the graph term terminal property

Definition at line 2196 of file grphbase.c.

## ◆ graph_knot_chg()

 void graph_knot_chg ( GRAPH * p, int node, int term )

change terminal property of a vertex

Parameters
 p the graph node node to be changed term terminal property

Definition at line 2218 of file grphbase.c.

References Is_term, NULL, GRAPH::term, and GRAPH::terms.

## ◆ graph_knot_del()

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

delete node

Parameters
 scip SCIP data structure g the graph k the node freeancestors free edge ancestors?

Definition at line 2242 of file grphbase.c.

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

## ◆ 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
 scip SCIP data structure g the graph edgecosts edge costs for cutoff cutoffs cutoff values for each incident edge cutoffsrev revere cutoff values (or NULL if undirected) vertex the vertex success has node been pseudo-eliminated?

Definition at line 2258 of file grphbase.c.

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
 scip SCIP data structure p graph data structure solnode node array to mark whether an node is part of a given solution (CONNECT), or NULL t tail node to be contracted s head node to be contracted

Definition at line 2429 of file grphbase.c.

## ◆ 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
 scip SCIP data structure g graph data structure solnode node array to mark whether an node is part of a given solution (CONNECT), or NULL t tail node to be contracted s head node to be contracted

Definition at line 2662 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
 scip SCIP data structure g the graph eki the edge k new tail j new head cost new cost forcedelete delete edge eki if it is not used?

Definition at line 2681 of file grphbase.c.

## ◆ 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
 scip SCIP data structure g the graph e1 edge to reinsert k1 tail k2 head cost edge cost ancestors0 ancestors of first edge ancestors1 ancestors of second edge revancestors0 reverse ancestors of first edge revancestors1 reverse ancestors of first edge forcedelete delete edge e1 if it is not used?

Definition at line 2753 of file grphbase.c.

Referenced by graph_knot_delPseudo().

 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
 scip SCIP data structure g the graph tail tail of the new edge head head of the new edge cost1 tail to head cost cost2 head to tail cost

Definition at line 2786 of file grphbase.c.

## ◆ graph_edge_del()

 void graph_edge_del ( SCIP * scip, GRAPH * g, int e, SCIP_Bool freeancestors )

delete an edge

Parameters
 scip SCIP data structure g the graph e the edge freeancestors free edge ancestors?

Definition at line 2837 of file grphbase.c.

## ◆ graph_edge_hide()

 void graph_edge_hide ( GRAPH * g, int e )

hide edge

Parameters
 g the graph e the edge

Definition at line 2887 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
 scip SCIP data structure g the graph e the edge

Definition at line 2931 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
 scip SCIP data structure g the graph result solution array (CONNECT/UNKNOWN) newroot the new root

Definition at line 2943 of file grphbase.c.

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
 scip SCIP data structure graph graph data structure result solution array, indicating whether an edge is in the solution

Definition at line 3046 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()

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

verifies whether a given primal solution is feasible

Parameters
 scip SCIP data structure graph graph data structure result solution array, indicating whether an edge is in the solution

Definition at line 3066 of file grphbase.c.

## ◆ graph_sol_setNodeList()

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

mark endpoints of edges in given list

Parameters
 g graph data structure solnode solution nodes array (TRUE/FALSE) listnode edge list

Definition at line 3170 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 )

compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset

Definition at line 3196 of file grphbase.c.

References CONNECT, and SCIP_Real.

## ◆ 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
 scip SCIP data structure transgraph the transformed graph orggraph the original graph transsoledge solution for transformed problem orgsoledge new retransformed solution

Definition at line 3214 of file grphbase.c.

## ◆ 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
 scip SCIP data structure pcancestors the ancestors tails tails array heads heads array orgnnodes original number of nodes solnodemark solution nodes mark array soledgemark solution edges mark array or NULL solnodequeue solution nodes queue or NULL nsolnodes number of solution nodes or NULL nsoledges number of solution edges or NULL

Definition at line 3288 of file grphbase.c.

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

## ◆ graph_get_NVET()

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

get (real) number of nodes , edges, terminals

Parameters
 graph the graph nnodes number of nodes nedges number of edges nterms number of terminals

Definition at line 3382 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
 g the graph edgearr original edge array [0,...,nedges - 1] tailarr tail of csr edge [0,...,nedges - 1] start start array [0,...,nnodes] nnewedges pointer to store number of new edges

Definition at line 3417 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
 scip SCIP data structure g the graph

Definition at line 3448 of file grphbase.c.

## ◆ graph_init()

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

initialize graph

Parameters
 scip SCIP data structure g new graph ksize slots for nodes esize slots for edges layers number of layers (only needed for packing, otherwise 1)

Definition at line 3491 of file grphbase.c.

## ◆ graph_init_history()

 SCIP_RETCODE graph_init_history ( SCIP * scip, GRAPH * graph )

initialize data structures required to keep track of reductions

Parameters
 scip SCIP data structure graph graph

Definition at line 3569 of file grphbase.c.

## ◆ graph_resize()

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

enlarge given graph

Parameters
 scip SCIP data structure g graph to be resized ksize new node slots esize new edge slots layers layers (set to -1 by default)

Definition at line 3631 of file grphbase.c.

## ◆ graph_free()

 void graph_free ( SCIP * scip, GRAPH ** graph, SCIP_Bool final )

free the graph

Parameters
 scip SCIP data structure graph graph to be freed final delete ancestor data structures?

Definition at line 3674 of file grphbase.c.

## ◆ graph_free_history()

 void graph_free_history ( SCIP * scip, GRAPH * p )

free the history

Parameters
 scip SCIP data p graph data

Definition at line 3736 of file grphbase.c.

Referenced by graph_free(), and redbasedVarfixing().

## ◆ graph_free_historyDeep()

 void graph_free_historyDeep ( SCIP * scip, GRAPH * p )

free the deep history

Parameters
 scip SCIP data p graph data

Definition at line 3760 of file grphbase.c.

Referenced by graph_free(), and redbasedVarfixing().

## ◆ graph_copy_data()

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

copy the data of the graph

Parameters
 scip SCIP data structure orgraph original graph copygraph graph to be copied to

Definition at line 3805 of file grphbase.c.

Referenced by graph_copy(), and redbasedVarfixing().

## ◆ graph_copy()

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

copy the graph

Parameters
 scip SCIP data structure orgraph original graph copygraph graph to be created

Definition at line 3896 of file grphbase.c.

References GRAPH::esize, graph_copy_data(), graph_init(), GRAPH::ksize, GRAPH::layers, NULL, SCIP_CALL, and SCIP_OKAY.

## ◆ graph_show()

 void graph_show ( const GRAPH * p )
Parameters
 p the graph

Definition at line 3912 of file grphbase.c.

## ◆ graph_uncover()

 void graph_uncover ( GRAPH * g )

reinsert all hidden edges

Parameters
 g the graph

Definition at line 3937 of file grphbase.c.

## ◆ graph_pack()

 SCIP_RETCODE graph_pack ( SCIP * scip, GRAPH * graph, GRAPH ** newgraph, SCIP_Bool verbose )

pack the graph, i.e. build a new graph that discards deleted edges and nodes

Parameters
 scip SCIP data structure graph the graph newgraph the new graph verbose verbose?

Definition at line 3984 of file grphbase.c.

Referenced by graph_obstgrid_create(), SCIPprobdataCreate(), and SCIPStpHeurRecRun().

## ◆ 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
 g the new graph i node to start from

Definition at line 4184 of file grphbase.c.

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
 scip scip struct g the new graph i node to start from

Definition at line 4238 of file grphbase.c.

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
 scip scip struct g the new graph reachable are they reachable?

Definition at line 4295 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()

 SCIP_Bool graph_valid ( const GRAPH * g )

is the given graph valid?

Parameters
 g the new graph

Definition at line 4324 of file grphbase.c.