Detailed Description

includes several methodes for Steiner problem graphs

Author: Thorsten Koch; Daniel Rehfeldt

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

Definition in file grphbase.c.

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

Go to the source code of this file.

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

SCIP_RETCODE	graph_init_history (SCIP scip, GRAPH graph)

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

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

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

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

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

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

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

SCIP_RETCODE	graph_prize_transform (SCIP scip, GRAPH graph)

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

SCIP_RETCODE	graph_PcToSap (SCIP scip, GRAPH graph)

SCIP_RETCODE	graph_rootprize_transform (SCIP scip, GRAPH graph)

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

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

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

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

void	graph_flags (GRAPH *p, int flags)

void	graph_show (const GRAPH *p)

void	graph_ident (const GRAPH *p)

void	graph_knot_add (GRAPH *p, int term)

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

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

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

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

int	graph_edge_redirect (SCIP scip, GRAPH g, int eki, int k, int j, SCIP_Real cost)

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)

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

static void	edge_remove (GRAPH *g, int e)

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

void	graph_edge_hide (GRAPH *g, int e)

void	graph_uncover (GRAPH *g)

SCIP_RETCODE	pcgraphorg (SCIP scip, GRAPH graph)

SCIP_RETCODE	pcgraphtrans (SCIP scip, GRAPH graph)

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

void	graph_trail (const GRAPH *p, int i)

int	graph_valid (const GRAPH *p)

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

char	graph_valid2 (SCIP scip, const GRAPH graph, SCIP_Real *cost)

Function Documentation

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

static

used by graph_grid_create

Definition at line 336 of file grphbase.c.

References getNodeNumber().

Referenced by graph_grid_create().

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

static

used by graph_obstgrid_create

Definition at line 266 of file grphbase.c.

References FALSE, getNodeNumber(), and TRUE.

Referenced by graph_obstgrid_create().

static void edge_remove	(	GRAPH *	g,
		int	e
	)

inlinestatic

Parameters

g	the graph
e	the edge to be removed

Definition at line 1928 of file grphbase.c.

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

Referenced by graph_edge_del(), and graph_edge_hide().

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

static

used by graph_grid_create

Definition at line 237 of file grphbase.c.

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

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 *	scip,
		GRAPH *	g,
		int	tail,
		int	head,
		SCIP_Real	cost1,
		SCIP_Real	cost2
	)

add a new edge to the graph

Parameters

scip	SCIP data structure
g	the graph
tail	tail of the new edge
head	head of the new edge
cost1	tail to head cost
cost2	head to tail cost

Definition at line 1879 of file grphbase.c.

References GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and UNKNOWN.

Referenced by graph_grid_create(), graph_obstgrid_create(), graph_pack(), graph_PcSapCopy(), graph_PcToSap(), graph_prize_transform(), graph_rootprize_transform(), and pcgraphtrans().

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 *	scip,
		GRAPH *	g,
		int	eki,
		int	k,
		int	j,
		SCIP_Real	cost
	)

Parameters

scip	SCIP data structure
g	the graph
eki	the edge
k	new tail
j	new head
cost	new cost

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 * p )

Parameters

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

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

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

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_show ( const GRAPH * p )

Parameters

p the 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 *	scip,
		const GRAPH *	graph,
		SCIP_Real *	cost
	)

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.

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

Detailed Description

Functions

Function Documentation