Detailed Description

includes various files containing graph methods used for Steiner problems

Author: Gerald Gamrath; Thorsten Koch; Daniel Rehfeldt

Definition in file grph.h.

#include "scip/scip.h"
#include "misc_stp.h"

Macros
#define	EAT_FREE -1

#define	EAT_LAST -2

#define	EAT_HIDE -3

#define	GRAPH_HAS_COORDINATES 1

#define	GRAPH_IS_GRIDGRAPH 2

#define	GRAPH_IS_DIRECTED 4

#define	STP_UNDIRECTED 0

#define	STP_DIRECTED 1

#define	STP_PRIZE_COLLECTING 2

#define	STP_ROOTED_PRIZE_COLLECTING 3

#define	STP_NODE_WEIGHTS 4

#define	STP_DEG_CONS 5

#define	STP_REVENUES_BUDGET_HOPCONS 6

#define	STP_GRID 7

#define	STP_OBSTACLES_GRID 8

#define	STP_MAX_NODE_WEIGHT 9

#define	STP_HOP_CONS 10

#define	GSTP 11

#define	PRIZE 12

#define	flipedge(edge) (((edge % 2) == 0) ? edge + 1 : edge - 1)

#define	PATH_NIL ((PATH*)0)

#define	CONNECT 0

#define	UNKNOWN (-1)

#define	FARAWAY 1e15

#define	BLOCKED 1e10

#define	MST_MODE 0

#define	FSP_MODE 1

#define	BSP_MODE 2

#define	NO_CHANGE -10

#define	Is_term(a) ((a) >= 0)

#define	Is_pterm(a) ((a) == -2)

#define	Is_gterm(a) ((a) == -2 \|\| (a) >= 0 )

#define	Edge_anti(a) ((((a) % 2) > 0) ? (a) - 1 : (a) + 1)

#define	STP_MAGIC 0x33d32945

#define	VERSION_MAJOR 1

#define	VERSION_MINOR 0

Typedefs
typedef struct presolve_info	PRESOL

typedef struct shortest_path	PATH

Enumerations
enum	FILETYPE { FF_BEA, FF_STP, FF_PRB, FF_GRD }

Functions
void	graph_flags (GRAPH *, int)

void	graph_show (const GRAPH *)

void	graph_ident (const GRAPH *)

void	graph_knot_add (GRAPH *, int)

void	graph_knot_chg (GRAPH *, int, int)

void	graph_knot_contract_dir (GRAPH *, int, int)

void	graph_edge_add (SCIP , GRAPH , int, int, double, double)

void	graph_edge_del (SCIP , GRAPH , int, SCIP_Bool)

void	graph_edge_hide (GRAPH *, int)

void	graph_uncover (GRAPH *)

void	prize_subtract (SCIP , GRAPH , SCIP_Real, int)

void	graph_trail (const GRAPH *, int)

void	graph_free (SCIP , GRAPH , SCIP_Bool)

SCIP_RETCODE	graph_init (SCIP , GRAPH *, int, int, int, int)

SCIP_RETCODE	pcgraphorg (SCIP , GRAPH )

SCIP_RETCODE	pcgraphtrans (SCIP , GRAPH )

SCIP_RETCODE	graph_init_history (SCIP , GRAPH )

SCIP_RETCODE	graph_resize (SCIP , GRAPH , int, int, int)

SCIP_RETCODE	graph_knot_contract (SCIP , GRAPH , int, int)

SCIP_RETCODE	graph_knot_contractpc (SCIP , GRAPH , int, int, int)

SCIP_RETCODE	graph_PcToSap (SCIP , GRAPH )

SCIP_RETCODE	graph_PcSapCopy (SCIP , GRAPH , GRAPH *, SCIP_Real )

SCIP_RETCODE	graph_edge_reinsert (SCIP , GRAPH , int, int, int, SCIP_Real, IDX , IDX , IDX , IDX )

SCIP_RETCODE	graph_MwcsToSap (SCIP , GRAPH , SCIP_Real *)

SCIP_RETCODE	graph_prize_transform (SCIP , GRAPH )

SCIP_RETCODE	graph_rootprize_transform (SCIP , GRAPH )

SCIP_RETCODE	graph_maxweight_transform (SCIP , GRAPH , SCIP_Real *)

SCIP_RETCODE	graph_grid_create (SCIP , GRAPH , int *, int, int, int)

SCIP_RETCODE	graph_obstgrid_create (SCIP , GRAPH , int , int *, int, int, int, int)

SCIP_RETCODE	graph_grid_coordinates (SCIP , int , int , int , int, int)

SCIP_RETCODE	graph_copy (SCIP , GRAPH , GRAPH **)

SCIP_RETCODE	graph_pack (SCIP , GRAPH , GRAPH **, SCIP_Bool)

int	graph_edge_redirect (SCIP , GRAPH , int, int, int, SCIP_Real)

int	graph_valid (const GRAPH *)

char	graph_valid2 (SCIP , const GRAPH , SCIP_Real *)

SCIP_Bool	graph_sol_valid (SCIP , const GRAPH , int *)

void	graph_path_exit (SCIP , GRAPH )

void	graph_path_exec (SCIP , const GRAPH , int, int, SCIP_Real , PATH )

void	graph_path_execX (SCIP , const GRAPH , int, SCIP_Real , SCIP_Real , int *)

void	graph_path_st (SCIP , const GRAPH , SCIP_Real , SCIP_Real , int , int, unsigned int , char *)

void	voronoi (SCIP scip, const GRAPH , SCIP_Real , SCIP_Real , char , int , PATH *)

void	get2next (SCIP , const GRAPH , SCIP_Real , SCIP_Real , PATH , int , int , int )

void	get3next (SCIP , const GRAPH , SCIP_Real , SCIP_Real , PATH , int , int , int )

void	get4next (SCIP , const GRAPH , SCIP_Real , SCIP_Real , PATH , int , int , int )

void	getnext3terms (SCIP , const GRAPH , SCIP_Real , SCIP_Real , PATH , int , int , int )

void	getnext4terms (SCIP , const GRAPH , SCIP_Real , SCIP_Real , PATH , int , int , int )

void	getnext4tterms (SCIP , const GRAPH , SCIP_Real , SCIP_Real , PATH , int , int , int )

void	voronoi_terms (SCIP , const GRAPH , SCIP_Real , PATH , int , int , int *)

void	voronoi_inout (const GRAPH *)

void	voronoi_term (const GRAPH , double , double , double , PATH , int , int , int , int *, int)

void	voronoi_hop (const GRAPH , double , double , double , PATH , int , int , int , int , int )

void	heap_add (int , int , int , int, PATH )

void	voronoi_repair (SCIP , const GRAPH , SCIP_Real , int , int , PATH , int , int, UF )

void	voronoi_repair_mult (SCIP , const GRAPH , SCIP_Real , int , int , int , int , char , UF , PATH )

void	voronoi_slrepair (SCIP , const GRAPH , SCIP_Real , PATH , int , int , int *, int, int)

void	voronoiSteinerTreeExt (SCIP , const GRAPH , SCIP_Real , int , char , PATH )

void	sdpaths (SCIP , const GRAPH , PATH , SCIP_Real , SCIP_Real, int , int , int , int , int, int, int)

void	graph_path_length (const GRAPH , const PATH )

SCIP_RETCODE	voronoi_extend (SCIP , const GRAPH , SCIP_Real , PATH , VLIST *, char , int , int , int *, int, int, int)

SCIP_RETCODE	voronoi_extend2 (SCIP , const GRAPH , SCIP_Real , PATH , SCIP_Real , int , int *, char , int , int , int *, int, int, int)

SCIP_RETCODE	graph_path_init (SCIP , GRAPH )

SCIP_RETCODE	voronoi_dist (SCIP , const GRAPH , SCIP_Real , double , int , int , int , int , int , int , PATH *)

SCIP_RETCODE	voronoi_radius (SCIP scip, const GRAPH , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int )

void	graph_mincut_exit (SCIP , GRAPH )

void	graph_mincut_exec (GRAPH , int, int, const int , int *, int)

SCIP_RETCODE	graph_mincut_init (SCIP , GRAPH )

SCIP_RETCODE	graph_load (SCIP , GRAPH , const char , PRESOL *)

void	graph_save (const GRAPH , const char , FILETYPE)

void	SCIPwriteStp (SCIP , const GRAPH , FILE *, SCIP_Real)

void	graph_writefig (const GRAPH , const char , const double *, int)

void	graph_bfscoord (GRAPH *g)

void	graph_boxcoord (GRAPH *g)

void	level0 (SCIP , GRAPH )

SCIP_RETCODE	reduce (SCIP , GRAPH , SCIP_Real , int, int)

SCIP_RETCODE	sd_reduction (SCIP , GRAPH , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int , int, unsigned int )

SCIP_RETCODE	sdsp_reduction (SCIP , GRAPH , PATH , PATH , int , int , int , int , int , int , int)

SCIP_RETCODE	sdsp_sap_reduction (SCIP , GRAPH , PATH , PATH , int , int , int , int , int , int , int)

SCIP_RETCODE	sd_red (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , int , int , int , int , int , int , int )

SCIP_RETCODE	sdpc_reduction (SCIP , GRAPH , PATH , SCIP_Real , int , int , int , int , int , int )

SCIP_RETCODE	sd2_reduction (SCIP , GRAPH , SCIP_Real , int , int *)

SCIP_RETCODE	getSD (SCIP , GRAPH , PATH , PATH , SCIP_Real , SCIP_Real, int , int , int , int , int , int, int, int, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	bd3_reduction (SCIP , GRAPH , PATH , PATH , int , int , int , int , int , int , int)

SCIP_RETCODE	bdr_reduction (SCIP , GRAPH , GRAPH , PATH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int , int *)

SCIP_RETCODE	nv_reduction (SCIP , GRAPH , PATH , double , int , int , int , int , int *)

SCIP_RETCODE	nv_reductionAdv (SCIP , GRAPH , PATH , SCIP_Real , double , int , int , int , int , int , int , int )

SCIP_RETCODE	sl_reduction (SCIP , GRAPH , PATH , double , int , int , int , int , char , int )

SCIP_RETCODE	ledge_reduction (SCIP , GRAPH , PATH , int , int , int , int *)

SCIP_RETCODE	ansReduction (SCIP , GRAPH , SCIP_Real , int , int *)

SCIP_RETCODE	ansadvReduction (SCIP , GRAPH , SCIP_Real , int , int *)

SCIP_RETCODE	ansadv2Reduction (SCIP , GRAPH , SCIP_Real , int , int *)

SCIP_RETCODE	cnsAdvReduction (SCIP , GRAPH , int , int )

SCIP_RETCODE	nnpReduction (SCIP , GRAPH , SCIP_Real , int , int , int , int , int, char )

SCIP_RETCODE	npvReduction (SCIP , GRAPH , PATH , PATH , int , int , int , int , int , int , int)

SCIP_RETCODE	chain2Reduction (SCIP , GRAPH , PATH , PATH , int , int , int , int , int , int , int)

SCIP_RETCODE	da_reduce (SCIP , GRAPH , PATH , GNODE , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int , int , char , int *)

SCIP_RETCODE	daPc_reduce (SCIP , GRAPH , PATH , GNODE , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int , char , int )

SCIP_RETCODE	bound_reduce (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int *)

SCIP_RETCODE	hopbound_reduce (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int )

SCIP_RETCODE	hcrbound_reduce (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int , int *)

SCIP_RETCODE	hcrcbound_reduce (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real, int , int , int , int , int *, SCIP_Bool)

SCIP_RETCODE	degree_test (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	degree_test_hc (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	degree_test_mw (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	degree_test_pc (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	degree_test_sap (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	rptReduction (SCIP , GRAPH , SCIP_Real , int )

int	deleteterm (SCIP , GRAPH , int)

SCIP_RETCODE	SCIPvalidateStpSol (SCIP , const GRAPH , const double , SCIP_Bool )

Macro Definition Documentation

#define BLOCKED 1e10

Definition at line 150 of file grph.h.

Referenced by bound_reduce(), da_reduce(), graph_PcToSap(), graph_valid2(), hcrcbound_reduce(), prune(), SCIP_DECL_HEUREXEC(), and SCIPheurComputeSteinerTree().

#define BSP_MODE 2

Definition at line 154 of file grph.h.

Referenced by graph_path_st().

#define CONNECT 0

#define EAT_FREE -1

Definition at line 30 of file grph.h.

Referenced by bea_save(), graph_edge_del(), graph_edge_hide(), graph_edge_redirect(), graph_pack(), graph_show(), graph_valid(), nvsl_reduction(), pcgraphtrans(), SCIPprobdataPrintGraph2(), SCIPwriteStp(), sd_red(), sddeltable(), sdpc_reduction(), and stp_save().

#define EAT_HIDE -3

Definition at line 32 of file grph.h.

Referenced by graph_edge_del(), graph_edge_hide(), and graph_uncover().

#define EAT_LAST -2

Definition at line 31 of file grph.h.

Referenced by ansadv2Reduction(), ansadvReduction(), ansReduction(), bd3_reduction(), bdr_reduction(), bfs(), bound_reduce(), buildsolgraph(), cnsAdvReduction(), compTMstarts(), compute_sd(), computeDegConsTree(), computeSteinerTreeVnoi(), createVariables(), da_reduce(), daPc_reduce(), degree_test(), degree_test_hc(), degree_test_mw(), degree_test_pc(), degree_test_sap(), deleteterm(), do_prizecoll_trivial(), extendSteinerTreePcMw(), get2next(), get3next(), get4next(), getnext4tterms(), getRSD(), getSD(), graph_edge_redirect(), graph_knot_add(), graph_knot_contract(), graph_knot_contractpc(), graph_load(), graph_maxweight_transform(), graph_mincut_exec(), graph_MwcsToSap(), graph_path_exec(), graph_path_execX(), graph_path_st(), graph_PcSapCopy(), graph_sol_valid(), graph_trail(), graph_valid(), graph_valid2(), hcrbound_reduce(), hcrcbound_reduce(), hopbound_reduce(), initialise(), lca(), ledge_reduction(), level0(), nnpReduction(), npvReduction(), nv_reduction(), nv_reductionAdv(), nvsl_reduction(), prize_subtract(), rptReduction(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROPEXEC(), SCIPdualAscentPcStp(), SCIPdualAscentStp(), SCIPheurComputeSteinerTree(), SCIPheurImproveSteinerTree(), SCIPheurPruneDegConsSteinerTree(), SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), SCIPprobdataAddNewSol(), SCIPvalidateStpSol(), SCIPwriteStp(), sd2_reduction(), sd_red(), sd_reduction(), sddeltable(), sdpaths(), sdpc_reduction(), sdsp_reduction(), sdsp_sap_reduction(), selectBranchingVertex(), sep_flow(), sl_reduction(), trail(), traverseChain(), trydg1edgepc(), voronoi(), voronoi_dist(), voronoi_extend(), voronoi_extend2(), voronoi_radius(), voronoi_repair(), voronoi_repair_mult(), voronoi_slrepair(), voronoi_terms(), and voronoiSteinerTreeExt().

#define Edge_anti ( a ) ((((a) % 2) > 0) ? (a) - 1 : (a) + 1)

Definition at line 161 of file grph.h.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), da_reduce(), degree_test(), degree_test_mw(), degree_test_pc(), degree_test_sap(), graph_edge_del(), graph_edge_redirect(), graph_edge_reinsert(), graph_knot_contract(), graph_mincut_exec(), graph_pack(), initialise(), ledge_reduction(), nvsl_reduction(), pcgraphtrans(), SCIPwriteStp(), sd_red(), sd_reduction(), sdpc_reduction(), voronoi_dist(), and voronoi_radius().

#define FARAWAY 1e15

Definition at line 149 of file grph.h.

Referenced by bd3_reduction(), bound_reduce(), buildsolgraph(), central_terminal(), chain2Reduction(), compute_sd(), computeDegConsTree(), computeSteinerTree(), computeSteinerTreeVnoi(), da_reduce(), daPc_reduce(), degree_test(), degree_test_hc(), degree_test_pc(), degree_test_sap(), get2next(), get3next(), get4next(), getnext4tterms(), getRSD(), getSD(), graph_load(), graph_pack(), graph_path_exec(), graph_path_execX(), graph_path_st(), graph_PcSapCopy(), graph_PcToSap(), graph_prize_transform(), graph_rootprize_transform(), hcrbound_reduce(), hcrcbound_reduce(), hopbound_reduce(), npvReduction(), nv_reduction(), nv_reductionAdv(), nvsl_reduction(), reduceSap(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROPEXEC(), SCIPdualAscentPcStp(), SCIPdualAscentStp(), SCIPheurComputeSteinerTree(), SCIPheurImproveSteinerTree(), sd_reduction(), sdpc_reduction(), sdsp_reduction(), sdsp_sap_reduction(), sl_reduction(), voronoi(), voronoi_dist(), voronoi_radius(), voronoi_terms(), and voronoiSteinerTreeExt().

#define flipedge ( edge ) (((edge % 2) == 0) ? edge + 1 : edge - 1)

#define FSP_MODE 1

Definition at line 153 of file grph.h.

Referenced by bd3_reduction(), central_terminal(), createVariables(), get2next(), get3next(), get4next(), graph_path_exec(), graph_path_st(), nvsl_reduction(), pricing(), SCIPprobdataAddNewSol(), sdpaths(), sep_2cut(), voronoi(), voronoi_dist(), voronoi_extend(), voronoi_extend2(), voronoi_radius(), voronoi_repair(), voronoi_repair_mult(), voronoi_slrepair(), voronoi_terms(), and voronoiSteinerTreeExt().

#define GRAPH_HAS_COORDINATES 1

Definition at line 34 of file grph.h.

Referenced by graph_load().

#define GRAPH_IS_DIRECTED 4

Definition at line 36 of file grph.h.

#define GRAPH_IS_GRIDGRAPH 2

Definition at line 35 of file grph.h.

Referenced by graph_load().

#define GSTP 11

Definition at line 49 of file grph.h.

Referenced by buildsolgraph(), graph_load(), SCIP_DECL_HEUREXEC(), SCIPheurImproveSteinerTree(), and SCIPprobdataWriteSolution().

#define Is_gterm ( a ) ((a) == -2 || (a) >= 0 )

Definition at line 160 of file grph.h.

Referenced by buildsolgraph(), and daPc_reduce().

#define Is_pterm ( a ) ((a) == -2)

Definition at line 159 of file grph.h.

Referenced by bound_reduce(), buildsolgraph(), deleteterm(), extendSteinerTreePcMw(), graph_knot_contractpc(), graph_PcSapCopy(), pcgraphorg(), pcgraphtrans(), prize_subtract(), SCIPheurImproveSteinerTree(), sl_reduction(), trydg1edgepc(), and voronoiSteinerTreeExt().

#define Is_term ( a ) ((a) >= 0)

Definition at line 158 of file grph.h.

Referenced by ansadv2Reduction(), ansadvReduction(), bd3_reduction(), bdr_reduction(), bea_save(), bound_reduce(), buildsolgraph(), central_terminal(), chain2Reduction(), cnsAdvReduction(), compTMstarts(), compute_sd(), computeDegConsTree(), computeSteinerTree(), computeSteinerTreeVnoi(), createVariables(), da_reduce(), daPc_reduce(), degree_test(), degree_test_hc(), degree_test_mw(), degree_test_pc(), degree_test_sap(), deleteterm(), do_prizecoll_trivial(), extendSteinerTreePcMw(), get2next(), get3next(), get4next(), getnext4tterms(), getRSD(), getSD(), graph_knot_add(), graph_knot_chg(), graph_knot_contract(), graph_knot_contractpc(), graph_load(), graph_maxweight_transform(), graph_MwcsToSap(), graph_pack(), graph_path_execX(), graph_path_st(), graph_PcSapCopy(), graph_PcToSap(), graph_prize_transform(), graph_rootprize_transform(), graph_sol_valid(), graph_valid(), graph_valid2(), hcrbound_reduce(), hcrcbound_reduce(), hopbound_reduce(), ledge_reduction(), level0(), maxprize(), npvReduction(), nv_reduction(), nv_reductionAdv(), nvsl_reduction(), pcgraphorg(), pcgraphtrans(), rptReduction(), SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROPEXEC(), SCIPdualAscentAddCutsStp(), SCIPdualAscentPcStp(), SCIPdualAscentStp(), SCIPheurComputeSteinerTree(), SCIPheurImproveSteinerTree(), SCIPheurPruneDegConsSteinerTree(), SCIPheurPrunePCSteinerTree(), SCIPprobdataAddNewSol(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPwriteStp(), sd2_reduction(), sd_red(), sd_reduction(), sddeltable(), sdpaths(), sdpc_reduction(), sdsp_reduction(), selectBranchingVertex(), selectdiffsols(), sl_reduction(), stp_save(), traverseChain(), trydg1edgepc(), utdist(), voronoi_dist(), voronoi_extend2(), voronoi_radius(), voronoi_slrepair(), voronoi_terms(), and voronoiSteinerTreeExt().

#define MST_MODE 0

Definition at line 152 of file grph.h.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), correct(), graph_path_exec(), hopbound_reduce(), ledge_reduction(), npvReduction(), nvsl_reduction(), SCIPheurImproveSteinerTree(), SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), and sd_red().

#define NO_CHANGE -10

Definition at line 156 of file grph.h.

#define PATH_NIL ((PATH*)0)

Definition at line 145 of file grph.h.

#define PRIZE 12

Definition at line 50 of file grph.h.

#define STP_DEG_CONS 5

Definition at line 43 of file grph.h.

Referenced by buildsolgraph(), createVariables(), graph_copy(), graph_free(), graph_load(), probdataFree(), reduce(), SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBTRANS(), SCIPheurComputeSteinerTree(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPvalidateStpSol(), and SCIPwriteStp().

#define STP_DIRECTED 1

Definition at line 39 of file grph.h.

Referenced by bd3_reduction(), computeSteinerTree(), graph_load(), graph_PcSapCopy(), reduce(), SCIPheurComputeSteinerTree(), SCIPheurPruneSteinerTree(), SCIPprobdataCreate(), and SCIPprobdataWriteSolution().

#define STP_GRID 7

Definition at line 45 of file grph.h.

Referenced by buildsolgraph(), graph_copy(), graph_free(), graph_grid_create(), graph_load(), SCIP_DECL_HEUREXEC(), SCIPheurImproveSteinerTree(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), and SCIPwriteStp().

#define STP_HOP_CONS 10

Definition at line 48 of file grph.h.

Referenced by bd3_reduction(), bound_reduce(), computeSteinerTree(), createVariables(), da_reduce(), degree_test_hc(), graph_load(), prune(), reduce(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIPheurComputeSteinerTree(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPwriteStp(), sd_reduction(), and voronoi_radius().

#define STP_MAGIC 0x33d32945

Definition at line 163 of file grph.h.

Referenced by open_file(), SCIPwriteStp(), and stp_save().

#define STP_MAX_NODE_WEIGHT 9

Definition at line 47 of file grph.h.

Referenced by ansadv2Reduction(), ansadvReduction(), ansReduction(), bd3_reduction(), bound_reduce(), buildsolgraph(), cnsAdvReduction(), createVariables(), degree_test_mw(), extendSteinerTreePcMw(), graph_copy(), graph_init_history(), graph_knot_contractpc(), graph_load(), graph_maxweight_transform(), graph_MwcsToSap(), graph_pack(), graph_PcToSap(), graph_prize_transform(), graph_valid(), nnpReduction(), prize_subtract(), probdataFree(), prune(), reduce(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBEXITSOL(), SCIP_DECL_PROBTRANS(), SCIP_DECL_PROPEXEC(), SCIPheurComputeSteinerTree(), SCIPheurImproveSteinerTree(), SCIPprobdataAddNewSol(), SCIPprobdataCreate(), SCIPprobdataWriteLogfileEnd(), SCIPprobdataWriteSolution(), SCIPwriteStp(), sd_reduction(), sdpaths(), sep_2cut(), trydg1edgepc(), and voronoi_radius().

#define STP_NODE_WEIGHTS 4

Definition at line 42 of file grph.h.

Referenced by graph_load(), reduce(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), and SCIPwriteStp().

#define STP_OBSTACLES_GRID 8

Definition at line 46 of file grph.h.

Referenced by buildsolgraph(), graph_load(), graph_obstgrid_create(), SCIP_DECL_HEUREXEC(), SCIPheurImproveSteinerTree(), SCIPprobdataCreate(), and SCIPwriteStp().

#define STP_PRIZE_COLLECTING 2

#define STP_REVENUES_BUDGET_HOPCONS 6

Definition at line 44 of file grph.h.

#define STP_ROOTED_PRIZE_COLLECTING 3

#define STP_UNDIRECTED 0

Definition at line 38 of file grph.h.

Referenced by buildsolgraph(), graph_load(), probdataCreate(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIPheurImproveSteinerTree(), SCIPheurPruneSteinerTree(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), and SCIPwriteStp().

#define UNKNOWN (-1)

Definition at line 148 of file grph.h.

Referenced by ansadv2Reduction(), bd3_reduction(), bdr_reduction(), bound_reduce(), buildsolgraph(), chain2Reduction(), cnsAdvReduction(), compute_sd(), computeDegConsTree(), computeSteinerTreeVnoi(), correct(), correctX(), da_reduce(), daPc_reduce(), degree_test(), degree_test_pc(), deleteterm(), do_prizecoll_trivial(), extendSteinerTreePcMw(), get2next(), get3next(), get4next(), getnext4tterms(), getSD(), graph_edge_add(), graph_init(), graph_knot_contract(), graph_load(), graph_pack(), graph_path_exec(), graph_path_execX(), graph_path_st(), hcrcbound_reduce(), ledge_reduction(), npvReduction(), nv_reduction(), nv_reductionAdv(), pcgraphtrans(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_HEUREXEC(), SCIPheurComputeSteinerTree(), SCIPheurImproveSteinerTree(), SCIPheurPruneDegConsSteinerTree(), sd_red(), sdpaths(), sdpc_reduction(), sdsp_reduction(), sdsp_sap_reduction(), selectBranchingVertex(), sl_reduction(), trydg1edgepc(), voronoi(), voronoi_dist(), voronoi_radius(), voronoi_repair(), voronoi_slrepair(), voronoi_terms(), and voronoiSteinerTreeExt().

#define VERSION_MAJOR 1

Definition at line 164 of file grph.h.

Referenced by open_file(), SCIPwriteStp(), and stp_save().

#define VERSION_MINOR 0

Definition at line 165 of file grph.h.

Referenced by open_file(), SCIPwriteStp(), and stp_save().

Typedef Documentation

typedef struct shortest_path PATH

typedef struct presolve_info PRESOL

Enumeration Type Documentation

enum FILETYPE

Enumerator
FF_BEA
FF_STP
FF_PRB
FF_GRD

Definition at line 167 of file grph.h.

Function Documentation

SCIP_RETCODE ansadv2Reduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	marked,
		int *	count
	)

alternative advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
marked	nodes array
count	pointer to number of reductions

Definition at line 4991 of file reduce_alt.c.

References CNSNN, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, maxprize(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

SCIP_RETCODE ansadvReduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	marked,
		int *	count
	)

advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
marked	nodes array
count	pointer to number of reductions

Definition at line 4867 of file reduce_alt.c.

References CNSNN, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduceMwcs().

SCIP_RETCODE ansReduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	marked,
		int *	count
	)

adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
marked	nodes array
count	pointer to number of reductions

Definition at line 4579 of file reduce_alt.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, and TRUE.

Referenced by reduceMwcs().

SCIP_RETCODE bd3_reduction	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		PATH *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int
	)

Definition at line 2817 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, EQ, FALSE, FARAWAY, GRAPH::fixedges, flipedge, FSP_MODE, GE, getSD(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_edge_redirect(), graph_edge_reinsert(), graph_free(), graph_init(), graph_knot_add(), graph_knot_contract(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GT, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, Is_term, KNOTFREQ, KNOTLIMIT, GRAPH::knots, LE, LT, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_DIRECTED, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_term().

Referenced by reducePc(), and reduceStp().

SCIP_RETCODE bdr_reduction	(	SCIP *	,
		GRAPH *	,
		GRAPH *	,
		PATH *	,
		PATH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 2538 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, Edge_anti, FALSE, flipedge, getRSD(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_edge_reinsert(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by sd_red().

SCIP_RETCODE bound_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	prize,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		SCIP_Real *	offset,
		SCIP_Real *	upperbound,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP

Definition at line 845 of file reduce_bnd.c.

References GRAPH::ancestors, BLOCKED, compTMstarts(), CONNECT, GRAPH::cost, DEFAULT_HOPFACTOR, deleteterm(), shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, FARAWAY, flipedge, get2next(), get3next(), get4next(), getnext4tterms(), GRAPH::grad, graph_edge_del(), graph_edge_reinsert(), graph_free(), graph_init(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, pcgraphorg(), pcgraphtrans(), GRAPH::prize, SCIPheurComputeSteinerTree(), SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_radius().

Referenced by reduceHc(), reduceMwcs(), reducePc(), and reduceStp().

SCIP_RETCODE chain2Reduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

chain reduction (NPV_2) for the MWCSP

Definition at line 5484 of file reduce_alt.c.

References shortest_path::dist, shortest_path::edge, FALSE, FARAWAY, getSD(), GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

SCIP_RETCODE cnsAdvReduction	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

advanced connected neighbourhood subset reduction test for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of reductions

Definition at line 4675 of file reduce_alt.c.

References CNSNN, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

SCIP_RETCODE da_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	edgearrint,
		int *	vbase,
		int *	pathedge,
		int *	state,
		int *	heursources,
		char *	nodearrchar,
		int *	nelims
	)

dual ascent based reductions

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
edgearrint	int edges array for internal computations or NULL
vbase	array for Voronoi bases
pathedge	array for predecessor edge on a path
state	int 4 * nnodes array for internal computations
heursources	array to store starting points of TM heuristic
nodearrchar	char node array for internal computations or NULL
nelims	pointer to store number of reduced edges

Definition at line 202 of file reduce_bnd.c.

References GRAPH::ancestors, BLOCKED, compTMstarts(), CONNECT, GRAPH::cost, DEFAULT_DARUNS, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, Edge_anti, GRAPH::edges, extendSteinerTreePcMw(), FALSE, FARAWAY, flipedge, getnext4terms(), GRAPH::grad, graph_edge_del(), graph_edge_reinsert(), graph_path_execX(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pcgraphorg(), pcgraphtrans(), SCIPdualAscentStp(), SCIPheurComputeSteinerTree(), SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_HOP_CONS, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduceHc(), reducePc(), and reduceStp().

SCIP_RETCODE daPc_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	pathedge,
		int *	edgearrint,
		int *	state,
		char *	nodearrchar,
		int *	nelims
	)

dual ascent based reductions for PCSPG and MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shorest path incoming edge array for shortest path calculations
edgearrint	int edges array for internal computations or NULL
state	int 4 * vertices array
nodearrchar	char node array for internal computations
nelims	pointer to store number of reduced edges

Definition at line 577 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, extendSteinerTreePcMw(), FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_PcSapCopy(), GRAPH::head, Is_gterm, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, pcgraphorg(), pcgraphtrans(), SCIPdualAscentStp(), SCIPheurComputeSteinerTree(), SCIPintListNodeFree(), GRAPH::source, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_terms().

Referenced by reduceMwcs(), and reducePc().

SCIP_RETCODE degree_test	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	nelims
	)

basic reduction tests for the STP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
nelims	pointer to number of reductions

Definition at line 390 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, EQ, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by nvsl_reduction(), and reduceStp().

SCIP_RETCODE degree_test_hc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the HCDSTP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 968 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_HOP_CONS, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduceHc().

SCIP_RETCODE degree_test_mw	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the MWCS problem

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 811 of file reduce_simple.c.

References GRAPH::cost, deleteterm(), EAT_LAST, Edge_anti, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_del(), graph_knot_contractpc(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, maxprize(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::source, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, traverseChain(), TRUE, and trydg1edgepc().

Referenced by reduceMwcs().

SCIP_RETCODE degree_test_pc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reductions for RPCSTP and PCSPG

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 1048 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, deleteterm(), EAT_LAST, Edge_anti, EQ, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, maxprize(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, trydg1edgepc(), and UNKNOWN.

Referenced by nvsl_reduction(), and reducePc().

SCIP_RETCODE degree_test_sap	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the SAP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 566 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduceSap().

int 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 343 of file reduce_simple.c.

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

Referenced by bound_reduce(), degree_test_mw(), degree_test_pc(), and trydg1edgepc().

void get2next	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		PATH *	path,
		int *	vbase,
		int *	heap,
		int *	state
	)

2th next terminal to all non terminal nodes

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
path	path data struture (leading to first and second nearest terminal)
vbase	first and second nearest terminal to each non terminal
heap	array representing a heap
state	array to mark the state of each node during calculation

Definition at line 1214 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by bound_reduce(), getnext3terms(), getnext4terms(), and hopbound_reduce().

void get3next	(	SCIP *	,
		const GRAPH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		PATH *	,
		int *	,
		int *	,
		int *
	)

Definition at line 1310 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by bound_reduce(), getnext3terms(), and getnext4terms().

void get4next	(	SCIP *	,
		const GRAPH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		PATH *	,
		int *	,
		int *	,
		int *
	)

Definition at line 1417 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by bound_reduce(), and getnext4terms().

void getnext3terms	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		PATH *	path3,
		int *	vbase,
		int *	heap,
		int *	state
	)

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
path3	path data struture (leading to first, second and third nearest terminal)
vbase	first, second and third nearest terminal to each non terminal
heap	array representing a heap
state	array to mark the state of each node during calculation

Definition at line 1526 of file grphpath.c.

References get2next(), get3next(), GRAPH::grad, GRAPH::knots, GRAPH::mark, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, and voronoi_terms().

void getnext4terms	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		PATH *	path,
		int *	vbase,
		int *	heap,
		int *	state
	)

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
path	path data struture (leading to first, second, third and fouth nearest terminal)
vbase	first, second and third nearest terminal to each non terminal
heap	array representing a heap
state	array to mark the state of each node during calculation

Definition at line 1562 of file grphpath.c.

References get2next(), get3next(), get4next(), GRAPH::grad, GRAPH::knots, GRAPH::mark, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, and voronoi_terms().

Referenced by da_reduce(), sd_red(), and sdpc_reduction().

void getnext4tterms	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		SCIP_Real *	boundedges,
		PATH *	path,
		int *	vbase,
		int *	heap,
		int *	state
	)

get 4 close terminals to each terminal

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
boundedges	array to store boundary edges
path	path data struture (leading to first, second, third and fouth nearest terminal)
vbase	first, second and third nearest terminal to each non terminal
heap	array representing a heap
state	array to mark the state of each node during calculation

Definition at line 1603 of file grphpath.c.

References shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, UNKNOWN, and utdist().

Referenced by bound_reduce(), and sdpc_reduction().

SCIP_RETCODE getSD	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		SCIP_Real *	sdist,
		SCIP_Real	distlimit,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int	i,
		int	i2,
		int	limit,
		SCIP_Bool	pc,
		SCIP_Bool	mw
	)

get SD to a single edge

Definition at line 1658 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, sdpaths(), GRAPH::term, and UNKNOWN.

Referenced by bd3_reduction(), chain2Reduction(), and npvReduction().

void graph_bfscoord ( GRAPH * g )

void graph_boxcoord ( GRAPH * g )

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

copy the graph

Parameters

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

Definition at line 1228 of file grphbase.c.

References GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::flags, GRAPH::grad, graph_init(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::locals, GRAPH::mark, GRAPH::maxdeg, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::oeat, GRAPH::orgedges, GRAPH::orgknots, GRAPH::outbeg, GRAPH::prize, GRAPH::source, STP_DEG_CONS, STP_GRID, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::terms.

Referenced by graph_PcSapCopy(), and SCIP_DECL_PROBCOPY().

void graph_edge_add	(	SCIP *	,
		GRAPH *	,
		int	,
		int	,
		double	,
		double
	)

Referenced by bd3_reduction(), bdr_reduction(), buildsolgraph(), graph_load(), ledge_reduction(), npvReduction(), SCIPheurImproveSteinerTree(), sd_red(), sdpc_reduction(), and voronoi_radius().

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 1965 of file grphbase.c.

References GRAPH::ancestors, EAT_FREE, EAT_HIDE, Edge_anti, edge_remove(), GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::oeat, SCIPintListNodeFree(), and GRAPH::tail.

Referenced by ansadv2Reduction(), ansadvReduction(), ansReduction(), bd3_reduction(), bdr_reduction(), bound_reduce(), chain2Reduction(), cnsAdvReduction(), da_reduce(), daPc_reduce(), degree_test_hc(), degree_test_mw(), degree_test_pc(), degree_test_sap(), deleteterm(), graph_edge_redirect(), graph_knot_contract(), graph_knot_contractpc(), hcrbound_reduce(), hcrcbound_reduce(), hopbound_reduce(), ledge_reduction(), level0(), nnpReduction(), npvReduction(), nvsl_reduction(), sd2_reduction(), sd_red(), sd_reduction(), sdpc_reduction(), sdsp_reduction(), sdsp_sap_reduction(), traverseChain(), and trydg1edgepc().

void graph_edge_hide	(	GRAPH *	g,
		int	e
	)

hide edge

Parameters

g	the graph
e	the edge

Definition at line 2015 of file grphbase.c.

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

int graph_edge_redirect	(	SCIP *	,
		GRAPH *	,
		int	,
		int	,
		int	,
		SCIP_Real
	)

Definition at line 1783 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, GRAPH::oeat, GRAPH::outbeg, and GRAPH::tail.

Referenced by bd3_reduction(), degree_test_pc(), graph_edge_reinsert(), graph_PcSapCopy(), and traverseChain().

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
	)

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	edgecost
ancestors0	ancestors of first edge
ancestors1	ancestors of second edge
revancestors0	reverse ancestors of first edge
revancestors1	reverse ancestors of first edge

Definition at line 1846 of file grphbase.c.

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

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), and da_reduce().

void graph_flags	(	GRAPH *	p,
		int	flags
	)

set flags

Parameters

p	the graph
flags	new flags

Definition at line 1307 of file grphbase.c.

References GRAPH::flags.

Referenced by graph_load().

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

free the graph

Parameters

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

Definition at line 1137 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, GRAPH::edges, GRAPH::fixedges, GRAPH::grad, GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::locals, GRAPH::mark, GRAPH::maxdeg, GRAPH::norgmodelknots, GRAPH::oeat, GRAPH::orghead, GRAPH::orgtail, GRAPH::outbeg, Int_List_Node::parent, GRAPH::pcancestors, GRAPH::prize, GRAPH::source, STP_DEG_CONS, STP_GRID, GRAPH::stp_type, GRAPH::tail, and GRAPH::term.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), daPc_reduce(), graph_pack(), hopbound_reduce(), ledge_reduction(), npvReduction(), pcgraphtrans(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBDELORIG(), SCIPdualAscentPcStp(), SCIPheurImproveSteinerTree(), sd_red(), and sdpc_reduction().

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 691 of file grphbase.c.

Referenced by SCIPprobdataWriteSolution().

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 535 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, GRAPH::source, STP_GRID, and GRAPH::stp_type.

Referenced by graph_load().

void graph_ident ( const GRAPH * )

Definition at line 1341 of file grphbase.c.

References GRAPH::cost, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and GRAPH::term.

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

initalize a 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)
flags	flags

Definition at line 44 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::fixedges, GRAPH::flags, GRAPH::grad, GRAPH::grid_coordinates, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::locals, 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, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgtail, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, GRAPH::prize, GRAPH::source, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), buildsolgraph(), graph_copy(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), hopbound_reduce(), ledge_reduction(), npvReduction(), pcgraphtrans(), SCIPheurImproveSteinerTree(), sd_red(), and sdpc_reduction().

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 128 of file grphbase.c.

References GRAPH::ancestors, GRAPH::edges, GRAPH::head, GRAPH::knots, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, and GRAPH::tail.

Referenced by daPc_reduce(), and reduce().

void graph_knot_add	(	GRAPH *	p,
		int	term
	)

add a vertex

Parameters

p	the graph
term	terminal property

Definition at line 1362 of file grphbase.c.

References EAT_LAST, GRAPH::grad, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::locals, GRAPH::mark, GRAPH::outbeg, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by bd3_reduction(), bdr_reduction(), buildsolgraph(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), graph_PcSapCopy(), graph_PcToSap(), graph_prize_transform(), graph_rootprize_transform(), ledge_reduction(), npvReduction(), pcgraphtrans(), SCIPheurImproveSteinerTree(), sd_red(), sdpc_reduction(), and voronoi_radius().

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 1386 of file grphbase.c.

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

Referenced by bound_reduce(), deleteterm(), graph_grid_create(), graph_knot_contract(), graph_knot_contractpc(), graph_load(), graph_maxweight_transform(), graph_MwcsToSap(), graph_obstgrid_create(), graph_PcToSap(), graph_prize_transform(), graph_rootprize_transform(), hopbound_reduce(), pcgraphorg(), pcgraphtrans(), sd_red(), and trydg1edgepc().

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

contract an edge, given by its endpoints

Parameters

scip	SCIP data structure
p	graph data structure
t	tail node to be contracted
s	head node to be contracted

Definition at line 1415 of file grphbase.c.

References GRAPH::ancestors, 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, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by bd3_reduction(), degree_test(), degree_test_pc(), degree_test_sap(), graph_knot_contractpc(), nv_reduction(), nv_reductionAdv(), nvsl_reduction(), rptReduction(), and sl_reduction().

void graph_knot_contract_dir	(	GRAPH *	,
		int	,
		int
	)

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

contract an edge of (rooted) prize-collecting Steiner tree problem

Parameters

scip	SCIP data structure
g	the graph
t	tail node to be contracted
s	head node to be contracted
i	terminal to add offset to

Definition at line 1679 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::grad, graph_edge_del(), graph_knot_chg(), graph_knot_contract(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, prize_subtract(), SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by degree_test_mw(), degree_test_pc(), nv_reduction(), nv_reductionAdv(), sl_reduction(), and trydg1edgepc().

SCIP_RETCODE graph_load	(	SCIP *	,
		GRAPH **	,
		const char *	,
		PRESOL *
	)

Definition at line 780 of file grphload.c.

References GRAPH::cost, DIRSEP, EAT_LAST, GRAPH::edges, section::extension, EXTSEP, FAILURE, FALSE, FARAWAY, current_file::filename, presolve_info::fixed, section::flag, FLAG_REQUIRED, key::format, current_file::fp, get_arguments(), GRAPH::grad, graph_edge_add(), graph_flags(), graph_grid_create(), GRAPH_HAS_COORDINATES, graph_init(), GRAPH_IS_GRIDGRAPH, graph_knot_add(), graph_knot_chg(), graph_maxweight_transform(), graph_MwcsToSap(), graph_obstgrid_create(), graph_PcToSap(), graph_prize_transform(), graph_rootprize_transform(), graph_valid(), GSTP, GRAPH::hoplimit, GRAPH::ieat, init_coordinates(), GRAPH::inpbeg, Is_term, KEY_COMMENT_CREATOR, KEY_COMMENT_DATE, KEY_COMMENT_NAME, KEY_COMMENT_PROBLEM, KEY_COMMENT_REMARK, KEY_COORDINATES_DD, KEY_COORDINATES_DDD, KEY_COORDINATES_DDDD, KEY_COORDINATES_DDDDD, KEY_COORDINATES_DDDDDD, KEY_COORDINATES_DDDDDDD, KEY_COORDINATES_DDDDDDDD, KEY_COORDINATES_END, KEY_COORDINATES_GRID, KEY_END, KEY_EOF, KEY_GRAPH_A, KEY_GRAPH_AA, KEY_GRAPH_E, KEY_GRAPH_EDGES, KEY_GRAPH_HOPLIMIT, KEY_GRAPH_NODES, KEY_GRAPH_OBSTACLES, KEY_MAXDEGS_MD, KEY_NODEWEIGHTS_END, KEY_NODEWEIGHTS_NW, KEY_OBSTACLES_END, KEY_OBSTACLES_RR, KEY_PRESOLVE_DATE, KEY_PRESOLVE_EA, KEY_PRESOLVE_EC, KEY_PRESOLVE_ED, KEY_PRESOLVE_ES, KEY_PRESOLVE_FIXED, KEY_PRESOLVE_LOWER, KEY_PRESOLVE_TIME, KEY_PRESOLVE_UPPER, KEY_SECTION, KEY_TERMINALS_END, KEY_TERMINALS_GROUPS, KEY_TERMINALS_ROOT, KEY_TERMINALS_ROOTP, KEY_TERMINALS_T, KEY_TERMINALS_TERMINALS, KEY_TERMINALS_TG, KEY_TERMINALS_TP, key::keyword, GRAPH::knots, current_file::line, presolve_info::lower, section::mark, MAX_ARGUMENTS, MAX_KEYWORD_LEN, MAX_LINE_LEN, MAX_PATH_LEN, GRAPH::maxdeg, message(), MSG_DEBUG, MSG_ERROR, MSG_FATAL, MSG_INFO, parameter::n, section::name, open_file(), GRAPH::prize, scale_coords(), current_file::section, SECTION_EXISTEND, SECTION_MISSING, GRAPH::source, start_section(), STP_DEG_CONS, STP_DIRECTED, STP_GRID, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_NODE_WEIGHTS, STP_OBSTACLES_GRID, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, SUCCESS, key::sw_code, GRAPH::tail, GRAPH::term, GRAPH::terms, presolve_info::time, TRUE, UNKNOWN, and presolve_info::upper.

Referenced by SCIPprobdataCreate().

SCIP_RETCODE graph_maxweight_transform	(	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 1020 of file grphbase.c.

References GRAPH::cost, EAT_LAST, graph_knot_chg(), graph_prize_transform(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load().

void graph_mincut_exec	(	GRAPH *	,
		int	,
		int	,
		const int *	,
		int *	,
		int
	)

Definition at line 568 of file grphmcut.c.

References EAT_LAST, Edge_anti, GRAPH::edges, FALSE, GRAPH::head, initialise(), insert(), GRAPH::knots, Min, 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::oeat, GRAPH::outbeg, Q_LAST, Q_NMOQ, reinitialise(), GRAPH::tail, and TRUE.

Referenced by sep_2cut().

void graph_mincut_exit	(	SCIP *	,
		GRAPH *
	)

Definition at line 115 of file grphmcut.c.

References GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, and GRAPH::mincut_x.

Referenced by SCIP_DECL_PROBDELORIG().

SCIP_RETCODE graph_mincut_init	(	SCIP *	,
		GRAPH *
	)

Definition at line 80 of file grphmcut.c.

References GRAPH::edges, GRAPH::knots, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, and GRAPH::mincut_x.

Referenced by SCIP_DECL_PROBCOPY(), and SCIPprobdataCreate().

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

tansforms an MWCSP to an SAP

Parameters

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

Definition at line 1079 of file grphbase.c.

References GRAPH::cost, EAT_LAST, graph_knot_chg(), graph_PcToSap(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load().

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 374 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, GRAPH::source, STP_OBSTACLES_GRID, GRAPH::stp_type, and TRUE.

Referenced by graph_load().

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 2342 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, Edge_anti, GRAPH::edges, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::flags, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::maxdeg, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgtail, GRAPH::pcancestors, GRAPH::prize, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

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

void graph_path_exec	(	SCIP *	,
		const GRAPH *	,
		int	,
		int	,
		SCIP_Real *	,
		PATH *
	)

Definition at line 453 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, MST_MODE, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and UNKNOWN.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), central_terminal(), createVariables(), graph_path_st(), hopbound_reduce(), ledge_reduction(), npvReduction(), nvsl_reduction(), pricing(), SCIPheurImproveSteinerTree(), SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), SCIPprobdataAddNewSol(), sd_red(), and sep_2cut().

void graph_path_execX	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		SCIP_Real *	cost,
		SCIP_Real *	pathdist,
		int *	pathedge
	)

Dijkstra's algorithm starting from node 'start'

Parameters

scip	SCIP data structure
g	graph data structure
start	start vertex
cost	edgecosts
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)

Definition at line 639 of file grphpath.c.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::term, and UNKNOWN.

Referenced by da_reduce(), daPc_reduce(), hcrbound_reduce(), hcrcbound_reduce(), rptReduction(), SCIP_DECL_PROPEXEC(), SCIPheurComputeSteinerTree(), and sd_red().

void graph_path_exit	(	SCIP *	,
		GRAPH *
	)

Definition at line 429 of file grphpath.c.

References GRAPH::path_heap, and GRAPH::path_state.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), daPc_reduce(), hopbound_reduce(), ledge_reduction(), npvReduction(), reduce(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBDELORIG(), SCIPheurImproveSteinerTree(), and sd_red().

SCIP_RETCODE graph_path_init	(	SCIP *	,
		GRAPH *
	)

Definition at line 407 of file grphpath.c.

References GRAPH::knots, GRAPH::path_heap, and GRAPH::path_state.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), daPc_reduce(), hopbound_reduce(), ledge_reduction(), npvReduction(), reduce(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIPheurImproveSteinerTree(), SCIPprobdataCreate(), and sd_red().

void graph_path_length	(	const GRAPH *	,
		const PATH *
	)

Definition at line 2359 of file grphpath.c.

References GRAPH::cost, and GRAPH::knots.

void graph_path_st	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		SCIP_Real *	pathdist,
		int *	pathedge,
		int	start,
		unsigned int *	randseed,
		char *	connected
	)

Find a directed tree rooted in node 'start' and spanning all terminals

Parameters

scip	SCIP data structure
g	graph data structure
cost	edgecosts
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
start	start vertex
randseed	random seed
connected	array to mark whether a vertex is part of computed Steiner tree

Definition at line 707 of file grphpath.c.

References BSP_MODE, correctX(), EAT_LAST, FALSE, FARAWAY, FSP_MODE, GRAPH::grad, graph_path_exec(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijk().

SCIP_RETCODE graph_PcSapCopy	(	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 792 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, FARAWAY, flipedge, graph_copy(), graph_edge_add(), graph_edge_redirect(), graph_knot_add(), graph_resize(), Is_pterm, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::prize, GRAPH::source, STP_DIRECTED, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by daPc_reduce(), and SCIPdualAscentPcStp().

SCIP_RETCODE graph_PcToSap	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 880 of file grphbase.c.

References BLOCKED, GRAPH::edges, GRAPH::esize, FARAWAY, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_resize(), Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::prize, GRAPH::source, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load(), and graph_MwcsToSap().

SCIP_RETCODE graph_prize_transform	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 726 of file grphbase.c.

References GRAPH::edges, GRAPH::esize, FARAWAY, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_resize(), Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::prize, GRAPH::source, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load(), and graph_maxweight_transform().

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

enlarge the 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 186 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::locals, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by graph_PcSapCopy(), graph_PcToSap(), graph_prize_transform(), and graph_rootprize_transform().

SCIP_RETCODE graph_rootprize_transform	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for rooted prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 955 of file grphbase.c.

References GRAPH::edges, GRAPH::esize, FARAWAY, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_resize(), Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::prize, GRAPH::source, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load().

void graph_save	(	const GRAPH *	,
		const char *	,
		FILETYPE
	)

Definition at line 309 of file grphsave.c.

References bea_save(), FALSE, FF_BEA, FF_GRD, FF_PRB, FF_STP, graph_valid(), and stp_save().

void graph_show ( const GRAPH * )

Definition at line 1318 of file grphbase.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and GRAPH::term.

SCIP_Bool graph_sol_valid	(	SCIP *	scip,
		const GRAPH *	graph,
		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 2639 of file grphbase.c.

References CONNECT, EAT_LAST, FALSE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPheurPrunePCSteinerTree().

void graph_trail	(	const GRAPH *	p,
		int	i
	)

traverse the graph

Parameters

p	the new graph
i	node to start from

Definition at line 2510 of file grphbase.c.

References EAT_LAST, GRAPH::head, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, and TRUE.

Referenced by graph_valid(), and level0().

void graph_uncover ( GRAPH * g )

reinsert all hidden edges

Parameters

g the graph

Definition at line 2058 of file grphbase.c.

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

int graph_valid ( const GRAPH * p )

is the graph valid?

Parameters

p	the new graph

Definition at line 2532 of file grphbase.c.

References EAT_FREE, EAT_LAST, GRAPH::edges, FALSE, GRAPH::grad, graph_trail(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::locals, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by bd3_reduction(), degree_test(), degree_test_sap(), graph_copy(), graph_load(), graph_pack(), graph_save(), hcrbound_reduce(), hcrcbound_reduce(), hopbound_reduce(), ledge_reduction(), nvsl_reduction(), pcgraphtrans(), reduce(), SCIP_DECL_HEUREXEC(), SCIPheurImproveSteinerTree(), and sd_reduction().

char graph_valid2	(	SCIP *	,
		const GRAPH *	,
		SCIP_Real *
	)

Definition at line 2706 of file grphbase.c.

References BLOCKED, EAT_LAST, FALSE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.

void graph_writefig	(	const GRAPH *	,
		const char *	,
		const double *	,
		int
	)

SCIP_RETCODE hcrbound_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims,
		int *	pathedge
	)

hop bound-based reduction test for the HCDSTP

Definition at line 1750 of file reduce_bnd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, TRUE, and voronoi_terms().

Referenced by reduceHc().

SCIP_RETCODE hcrcbound_reduce	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		SCIP_Bool
	)

Definition at line 1878 of file reduce_bnd.c.

References BLOCKED, CONNECT, GRAPH::cost, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, fixedgevar(), flipedge, GRAPH::grad, graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, SCIPheurComputeSteinerTree(), SCIPprobdataGetVars(), GRAPH::source, GRAPH::term, TRUE, UNKNOWN, and voronoi_terms().

Referenced by reduceHc(), and SCIP_DECL_EVENTEXEC().

void heap_add	(	int *	,
		int *	,
		int *	,
		int	,
		PATH *
	)

Definition at line 241 of file grphpath.c.

References GT.

Referenced by computeSteinerTreeVnoi(), and SCIPheurImproveSteinerTree().

SCIP_RETCODE hopbound_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reduction test for the HCDSTP

Definition at line 1552 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, get2next(), GRAPH::grad, graph_edge_del(), graph_free(), graph_init(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and voronoi_radius().

Referenced by reduceHc().

SCIP_RETCODE ledge_reduction	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 4372 of file reduce_alt.c.

References CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, level0(), GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, and voronoi_terms().

Referenced by reduceStp().

void level0	(	SCIP *	,
		GRAPH *
	)

Definition at line 791 of file reduce.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_trail(), GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::source, GRAPH::term, and TRUE.

Referenced by ledge_reduction(), reduce(), and reduceMwcs().

SCIP_RETCODE nnpReduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	mem,
		int *	marked,
		int *	visited,
		int *	count,
		int	maxniter,
		char *	positive
	)

non-negative path reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
mem	nodes array
marked	nodes array
visited	nodes array
count	pointer to number of reductions
maxniter	max number of edges to check
positive	nodes array

Definition at line 5564 of file reduce_alt.c.

References EAT_LAST, FALSE, flipedge, graph_edge_del(), GRAPH::head, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, and TRUE.

Referenced by reduceMwcs().

SCIP_RETCODE npvReduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

non-positive vertex reduction for the MWCSP

Definition at line 5146 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, getSD(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

SCIP_RETCODE nv_reduction	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		double *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 3892 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, UNKNOWN, and voronoi_dist().

SCIP_RETCODE nv_reductionAdv	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		SCIP_Real *	,
		double *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 4083 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_dist().

Referenced by nvsl_reduction().

SCIP_RETCODE pcgraphorg	(	SCIP *	scip,
		GRAPH *	graph
	)

mark terminals and switch terminal property to original terminals

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 2104 of file grphbase.c.

References FALSE, GRAPH::grad, graph_knot_chg(), Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::source, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by bound_reduce(), da_reduce(), daPc_reduce(), reduceMwcs(), and reducePc().

SCIP_RETCODE pcgraphtrans	(	SCIP *	scip,
		GRAPH *	graph
	)

unmark terminals and switch terminal property to transformed terminals

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 2142 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, Edge_anti, GRAPH::edges, FALSE, GRAPH::fixedges, GRAPH::flags, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, Is_pterm, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::mark, GRAPH::maxdeg, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgtail, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by bound_reduce(), da_reduce(), daPc_reduce(), reduceMwcs(), and reducePc().

void prize_subtract	(	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 1637 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::source, STP_MAX_NODE_WEIGHT, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, and GRAPH::term.

Referenced by graph_knot_contractpc().

SCIP_RETCODE reduce	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	offset,
		int	level,
		int	minelims
	)

reduces the graph

Parameters

scip	SCIP data structure
graph	graph structure
offset	pointer to store offset generated by reductions
level	reduction level 0: none, 1: basic, 2: advanced
minelims	minimal amount of reductions to reiterate reduction methods

Definition at line 1886 of file reduce.c.

References FALSE, graph_init_history(), graph_path_exit(), graph_path_init(), graph_valid(), level0(), reduceHc(), reduceMwcs(), reducePc(), reduceSap(), reduceStp(), STP_DEG_CONS, STP_DIRECTED, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_NODE_WEIGHTS, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPprobdataCreate().

SCIP_RETCODE rptReduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

root proximity terminal test (SAP)

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 739 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_path_execX(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, SCIPintListNodeAppendCopy(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by reduceSap().

SCIP_RETCODE SCIPvalidateStpSol	(	SCIP *	scip,
		const GRAPH *	g,
		const double *	xval,
		SCIP_Bool *	feasible
	)

validates whether a (LP) solution is feasible

Definition at line 206 of file validate.c.

References EAT_LAST, GRAPH::edges, EPSILON, EQ, FALSE, flipedge, GRAPH::grad, GRAPH::knots, GRAPH::layers, GRAPH::maxdeg, nail(), GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_DEG_CONS, GRAPH::stp_type, GRAPH::term, trail(), and TRUE.

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_HEUREXEC().

void SCIPwriteStp	(	SCIP *	,
		const GRAPH *	,
		FILE *	,
		SCIP_Real
	)

Definition at line 38 of file grphsave.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, GRAPH::edges, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_DEG_CONS, STP_GRID, STP_HOP_CONS, STP_MAGIC, STP_MAX_NODE_WEIGHT, STP_NODE_WEIGHTS, STP_OBSTACLES_GRID, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::tail, GRAPH::term, GRAPH::terms, VERSION_MAJOR, and VERSION_MINOR.

Referenced by SCIP_DECL_READERWRITE().

SCIP_RETCODE sd2_reduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	nodecost,
		int *	nelims,
		int *	adjacent
	)

SD test using only two edges

Definition at line 1799 of file reduce_alt.c.

References GRAPH::cost, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, and TRUE.

SCIP_RETCODE sd_red	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	edgepreds,
		SCIP_Real *	mstsdist,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodesid,
		int *	nodesorg,
		int *	forbidden,
		int *	nelims
	)

Special distance test

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
edgepreds	array to store edge predecessors of auxiliary graph
mstsdist	array to store mst distances in auxiliary graph
heap	array representing a heap
state	array to indicate whether a node has been scanned during SP calculation
vbase	Voronoi base to each vertex
nodesid	array to map nodes in auxiliary graph to original ones
nodesorg	array to map terminals of original graph vertices of auxiliary graph
forbidden	array to mark whether an edge may be eliminated
nelims	point to store number of deleted edges

Definition at line 598 of file reduce_alt.c.

References bdr_reduction(), GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, flipedge, getcloseterms(), getlecloseterms(), getnext4terms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_path_exec(), graph_path_execX(), graph_path_exit(), graph_path_init(), GRAPH::head, GRAPH::ieat, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIPprobdataPrintGraph2(), sddeltable(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduceStp().

SCIP_RETCODE sd_reduction	(	SCIP *	,
		GRAPH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int	,
		unsigned int *
	)

Definition at line 2227 of file reduce_alt.c.

References compute_sd(), GRAPH::cost, EAT_LAST, Edge_anti, GRAPH::edges, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_valid(), GT, GRAPH::head, Is_term, KNOTFREQ, KNOTLIMIT, GRAPH::knots, LT, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduceStp().

void sdpaths	(	SCIP *	scip,
		const GRAPH *	g,
		PATH *	path,
		SCIP_Real *	cost,
		SCIP_Real	distlimit,
		int *	heap,
		int *	state,
		int *	memlbl,
		int *	nlbl,
		int	tail,
		int	head,
		int	limit
	)

limited Dijkstra, stopping at terminals

Parameters

scip	SCIP data structure
g	graph data structure
path	shortest paths data structure
cost	edge costs
distlimit	distance limit of the search
heap	array representing a heap
state	array to indicate whether a node has been scanned during SP calculation
memlbl	array to save labelled nodes
nlbl	number of labelled nodes
tail	tail of the edge
head	head of the edge
limit	maximum number of edges to consider during execution

Definition at line 542 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by getSD(), sdsp_reduction(), and sdsp_sap_reduction().

SCIP_RETCODE sdpc_reduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	boundedges,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodesid,
		int *	nodesorg,
		int *	nelims
	)

SD test for PC

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
boundedges	array to store bound edges
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nodesid	array
nodesorg	array
nelims	pointer to store number of eliminated edges

Definition at line 1144 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, Edge_anti, GRAPH::edges, FARAWAY, getcloseterms(), getnext4terms(), getnext4tterms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reducePc().

SCIP_RETCODE sdsp_reduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

SD test using only limited dijkstra from both endpoints of an edge

Definition at line 2058 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, sdpaths(), STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reducePc(), and reduceStp().

SCIP_RETCODE sdsp_sap_reduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

SDC test for the SAP using a limited version of Dijkstra's algorithm from both endpoints of an arc

Definition at line 1900 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), GRAPH::head, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, sdpaths(), TRUE, and UNKNOWN.

Referenced by reduceSap().

SCIP_RETCODE sl_reduction	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		double *	,
		int *	,
		int *	,
		int *	,
		int *	,
		char *	,
		int *
	)

Definition at line 3656 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, and voronoi_terms().

Referenced by nvsl_reduction().

void voronoi	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		char *	base,
		int *	vbase,
		PATH *	path
	)

build a voronoi region, w.r.t. shortest paths, for a given set of bases

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
base	array to indicate whether a vertex is a Voronoi base
vbase	voronoi base to each vertex
path	path data struture (leading to respective Voronoi base)

Definition at line 1034 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, GRAPH::knots, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::source, and UNKNOWN.

Referenced by computeSteinerTreeVnoi(), and SCIPheurImproveSteinerTree().

SCIP_RETCODE voronoi_dist	(	SCIP *	,
		const GRAPH *	,
		SCIP_Real *	,
		double *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		PATH *
	)

Referenced by nv_reduction(), and nv_reductionAdv().

SCIP_RETCODE voronoi_extend	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		PATH *	path,
		VLIST **	adjterms,
		char *	termsmark,
		int *	reachednodes,
		int *	nreachednodes,
		int *	nodenterms,
		int	nneighbterms,
		int	base,
		int	countex
	)

extend a voronoi region until all neighbouring terminals are spanned

Parameters

scip	SCIP data structure
g	graph data structure
cost	edgecosts
path	shortest paths data structure
adjterms	structure for adjacent terminal data
termsmark	array to mark terminal
reachednodes	array to mark reached nodes
nreachednodes	pointer to number of reached nodes
nodenterms	array to store number of terimals to each node
nneighbterms	number of neighbouring terminals
base	voronoi base
countex	number of heap elements

Definition at line 862 of file grphpath.c.

References Vnoi_List_Node::base, CONNECT, correct(), Vnoi_List_Node::dist, shortest_path::dist, EAT_LAST, Vnoi_List_Node::edge, shortest_path::edge, FALSE, FSP_MODE, GT, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), Vnoi_List_Node::next, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and TRUE.

SCIP_RETCODE voronoi_extend2	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		PATH *	path,
		SCIP_Real **	distarr,
		int **	basearr,
		int **	edgearr,
		char *	termsmark,
		int *	reachednodes,
		int *	nreachednodes,
		int *	nodenterms,
		int	nneighbterms,
		int	base,
		int	countex
	)

extend a voronoi region until all neighbouring terminals are spanned

Parameters

scip	SCIP data structure
g	graph data structure
cost	edgecosts
path	shortest paths data structure
distarr	array to store distance from each node to its base
basearr	array to store the bases
edgearr	array to store the ancestor edge
termsmark	array to mark terminal
reachednodes	array to mark reached nodes
nreachednodes	pointer to number of reached nodes
nodenterms	array to store number of terimals to each node
nneighbterms	number of neighbouring terminals
base	voronoi base
countex	count of heap elements

Definition at line 954 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FSP_MODE, GT, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::term, and TRUE.

Referenced by computeSteinerTreeVnoi().

void voronoi_hop	(	const GRAPH *	,
		double *	,
		double *	,
		double *	,
		PATH *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

void voronoi_inout ( const GRAPH * )

SCIP_RETCODE voronoi_radius	(	SCIP *	scip,
		const GRAPH *	graph,
		GRAPH *	adjgraph,
		PATH *	path,
		SCIP_Real *	rad,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		int *	vbase,
		int *	heap,
		int *	state
	)

build voronoi regions, w.r.t. shortest paths, for all terminals and compute the radii

Parameters

scip	SCIP data structure
graph	graph data structure
adjgraph	graph data structure
path	array containing Voronoi paths data
rad	array storing shortest way from a terminal out of its Voronoi region
cost	edge costs
costrev	reversed edge costs
vbase	array containing Voronoi base of each node
heap	array representing a heap
state	array to mark state of each node during calculation

Definition at line 1912 of file grphpath.c.

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, FARAWAY, FSP_MODE, graph_edge_add(), graph_knot_add(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::source, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by bound_reduce(), and hopbound_reduce().

void voronoi_repair	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		int *	count,
		int *	vbase,
		PATH *	path,
		int *	newedge,
		int	crucnode,
		UF *	uf
	)

repair the voronoi diagram for a given set nodes

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
count	pointer to number of heap elements
vbase	array containing Voronoi base of each node
path	Voronoi paths data struture
newedge	the new edge
crucnode	the current crucial node
uf	union find data structure

Definition at line 2211 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPunionfindFind(), GRAPH::tail, and UNKNOWN.

Referenced by SCIPheurImproveSteinerTree().

void voronoi_repair_mult	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		int *	count,
		int *	vbase,
		int *	boundedges,
		int *	nboundedges,
		char *	nodesmark,
		UF *	uf,
		PATH *	path
	)

repair the voronoi diagram for a given set nodes

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
count	pointer to number of heap elements
vbase	array containing Voronoi base of each node
boundedges	boundary edges
nboundedges	number of boundary edges
nodesmark	array to mark temporarily discarded nodes
uf	union find data structure
path	Voronoi paths data struture

Definition at line 2289 of file grphpath.c.

References CONNECT, correct(), EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and SCIPunionfindFind().

Referenced by SCIPheurImproveSteinerTree().

void voronoi_slrepair	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		PATH *	path,
		int *	vbase,
		int *	heap,
		int *	state,
		int	start,
		int	adjnode
	)

repair the voronoi diagram for SL reduction

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
path	array to store
vbase	array containing Voronoi base of each node
heap	array representing a heap
state	array indicating state of each vertex during calculation of Voronoi regions
start	node to start repair from
adjnode	adjacent node

Definition at line 2136 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and UNKNOWN.

void voronoi_term	(	const GRAPH *	,
		double *	,
		double *	,
		double *	,
		PATH *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int
	)

Referenced by bd3_reduction().

void voronoi_terms	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		PATH *	path,
		int *	vbase,
		int *	heap,
		int *	state
	)

build a Voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
path	path data struture (leading to respective Voronoi base)
vbase	Voronoi base to each vertex
heap	array representing a heap
state	array to mark the state of each node during calculation

Definition at line 1679 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and UNKNOWN.

Referenced by daPc_reduce(), getnext3terms(), getnext4terms(), hcrbound_reduce(), hcrcbound_reduce(), ledge_reduction(), SCIP_DECL_PROPEXEC(), and sl_reduction().

void voronoiSteinerTreeExt	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	costrev,
		int *	vbase,
		char *	stvertex,
		PATH *	path
	)

Voronoi Steiner tree extension for RPC, PC and MW

Parameters

scip	SCIP data structure
g	graph data structure
costrev	reversed edge costs
vbase	voronoi base to each vertex
stvertex	array to indicate whether a vertex is a Voronoi base
path	path data struture (leading to respective Voronoi base)

Definition at line 1121 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, GRAPH::term, and UNKNOWN.

Referenced by extendSteinerTreePcMw().

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation