Detailed Description

includes several methods for Steiner problem graphs

Author: Thorsten Koch; Daniel Rehfeldt

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

Definition in file grphbase.c.

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

Go to the source code of this file.

Macros
#define	STP_DELPSEUDO_MAXGRAD 5

#define	STP_DELPSEUDO_MAXNEDGES 10

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

static void	removeEdge (GRAPH *g, int e)

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

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

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

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

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

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

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

SCIP_RETCODE	graph_pc_presolInit (SCIP scip, GRAPH g)

void	graph_pc_presolExit (SCIP scip, GRAPH g)

SCIP_Bool	graph_pc_term2edgeConsistent (const GRAPH *g)

void	graph_pc_knot2nonTerm (GRAPH *g, int node)

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

void	graph_pc_2org (GRAPH *graph)

void	graph_pc_2trans (GRAPH *graph)

void	graph_pc_2orgcheck (GRAPH *graph)

void	graph_pc_2transcheck (GRAPH *graph)

SCIP_Real	graph_pc_getPosPrizeSum (SCIP scip, const GRAPH graph)

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

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

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

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

SCIP_RETCODE	graph_pc_2pc (SCIP scip, GRAPH graph)

SCIP_RETCODE	graph_pc_2rpc (SCIP scip, GRAPH graph)

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

SCIP_RETCODE	graph_pc_2rmw (SCIP scip, GRAPH graph)

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

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

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

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

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

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

SCIP_Bool	graph_pc_isPcMw (const GRAPH *g)

void	graph_knot_add (GRAPH *p, int term)

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

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

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

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

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

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

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

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

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

void	graph_edge_hide (GRAPH *g, int e)

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

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

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

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

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

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

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

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

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

void	graph_get_csr (const GRAPH g, int RESTRICT edgearr, int RESTRICT tailarr, int RESTRICT start, int *nnewedges)

SCIP_RETCODE	graph_get_edgeConflicts (SCIP scip, const GRAPH g)

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

SCIP_RETCODE	graph_init_history (SCIP scip, GRAPH graph)

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

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

void	graph_free_history (SCIP scip, GRAPH p)

void	graph_free_historyDeep (SCIP scip, GRAPH p)

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

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

void	graph_show (const GRAPH *p)

void	graph_uncover (GRAPH *g)

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

void	graph_trail (const GRAPH *g, int i)

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

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

SCIP_Bool	graph_valid (const GRAPH *g)

Macro Definition Documentation

◆ STP_DELPSEUDO_MAXGRAD

#define STP_DELPSEUDO_MAXGRAD 5

Definition at line 44 of file grphbase.c.

Referenced by graph_knot_delPseudo().

◆ STP_DELPSEUDO_MAXNEDGES

#define STP_DELPSEUDO_MAXNEDGES 10

Definition at line 45 of file grphbase.c.

Referenced by graph_knot_delPseudo().

Function Documentation

◆ cutoffEdge()

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

inlinestatic

can edge in pseudo-elimination method be cut off?

Parameters

scip	SCIP data
cutoffs	cutoff values for each incident edge
cutoffsrev	revere cutoff values (or NULL if undirected)
ecost	edge cost
ecostrev	reverse edge cost
edgeidx1	index of first edge to be checked (wrt provided arrays)
edgeidx2	index of second edge to be checked (wrt provided arrays)
cutoffidx	index for cutoff array

Definition at line 53 of file grphbase.c.

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

Referenced by graph_knot_delPseudo().

◆ removeEdge()

static void removeEdge	(	GRAPH *	g,
		int	e
	)

inlinestatic

Parameters

g	the graph
e	the edge to be removed

Definition at line 89 of file grphbase.c.

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

Referenced by graph_edge_del(), and graph_edge_hide().

◆ getNodeNumber()

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

static

used by graph_grid_create

Definition at line 143 of file grphbase.c.

References number.

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

◆ compEdgesObst()

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

static

used by graph_obstgrid_create

Definition at line 172 of file grphbase.c.

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

Referenced by graph_obstgrid_create().

◆ compEdges()

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

static

used by graph_grid_create

Definition at line 237 of file grphbase.c.

References BLOCKED, GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, getNodeNumber(), graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_resize(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by graph_grid_create().

◆ graph_obstgrid_create()

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

creates a graph out of a given grid

Parameters

scip	SCIP data structure
gridgraph	the (obstacle) grid graph to be constructed
coords	coordinates of all points
obst_coords	coordinates of obstacles
nterms	number of terminals
grid_dim	dimension of the problem
nobstacles	number of obstacles
scale_order	scale factor

Definition at line 419 of file grphbase.c.

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

Referenced by graph_load().

◆ graph_grid_create()

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

creates a graph out of a given grid

Parameters

scip	SCIP data structure
gridgraph	the grid graph to be constructed
coords	coordinates
nterms	number of terminals
grid_dim	problem dimension
scale_order	scale order

Definition at line 582 of file grphbase.c.

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

Referenced by graph_load().

◆ graph_grid_coordinates()

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

computes coordinates of node 'node'

Parameters

scip	SCIP data structure
coords	coordinates
nodecoords	coordinates of the node (to be computed)
ncoords	array with number of coordinate
node	the node
grid_dim	problem dimension

Definition at line 730 of file grphbase.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by SCIPprobdataWriteSolution().

◆ graph_pc_init()

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

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

Parameters

scip	SCIP data structure
g	the graph
sizeprize	size of prize array to allocate (or -1)
sizeterm2edge	size of term2edge array to allocate and initialize to -1 (or -1)

Definition at line 766 of file grphbase.c.

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

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

◆ graph_pc_presolInit()

SCIP_RETCODE graph_pc_presolInit	(	SCIP *	scip,
		GRAPH *	g
	)

changes graph of PC and MW problems needed for presolving routines

Parameters

scip	SCIP data structure
g	the graph

Definition at line 794 of file grphbase.c.

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

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

◆ graph_pc_presolExit()

void graph_pc_presolExit	(	SCIP *	scip,
		GRAPH *	g
	)

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

Parameters

scip	SCIP data structure
g	the graph

Definition at line 837 of file grphbase.c.

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

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

◆ graph_pc_term2edgeConsistent()

SCIP_Bool graph_pc_term2edgeConsistent ( const GRAPH * g )

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

Parameters

g the graph

Definition at line 853 of file grphbase.c.

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

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

◆ graph_pc_knot2nonTerm()

void graph_pc_knot2nonTerm	(	GRAPH *	g,
		int	node
	)

change property of node to non-terminal

Parameters

g	the graph
node	node to be changed

Definition at line 909 of file grphbase.c.

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

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

◆ graph_pc_updateTerm2edge()

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

updates term2edge array for new graph

Parameters

newgraph	the new graph
oldgraph	the old graph
newtail	tail in new graph
newhead	head in new graph
oldtail	tail in old graph
oldhead	head in old graph

Definition at line 928 of file grphbase.c.

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

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

◆ graph_pc_2org()

void graph_pc_2org ( GRAPH * graph )

mark terminals and switch terminal property to original terminals

Parameters

graph the graph

Definition at line 964 of file grphbase.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_knot_chg(), Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::source, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by findDaRoots(), graph_pc_2orgcheck(), markPcMwRoots(), redLoopMw(), redLoopPc(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduceSPG(), SCIPStpHeurPruneRun(), and SCIPStpHeurRecRun().

◆ graph_pc_2trans()

void graph_pc_2trans ( GRAPH * graph )

unmark terminals and switch terminal property to transformed terminals

Parameters

graph the graph

Definition at line 1002 of file grphbase.c.

References GRAPH::extended, GRAPH::grad, graph_knot_chg(), Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::source, GRAPH::term, and TRUE.

Referenced by findDaRoots(), graph_pc_2transcheck(), markPcMwRoots(), redLoopMw(), redLoopPc(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), SCIPStpHeurPruneRun(), and SCIPStpHeurRecRun().

◆ graph_pc_2orgcheck()

void graph_pc_2orgcheck ( GRAPH * graph )

graph_pc_2org if extended

Parameters

graph the graph

Definition at line 1028 of file grphbase.c.

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

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

◆ graph_pc_2transcheck()

void graph_pc_2transcheck ( GRAPH * graph )

graph_pc_2trans if not extended

Parameters

graph the graph

Definition at line 1041 of file grphbase.c.

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

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

◆ graph_pc_getPosPrizeSum()

SCIP_Real graph_pc_getPosPrizeSum	(	SCIP *	scip,
		const GRAPH *	graph
	)

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1054 of file grphbase.c.

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

Referenced by redLoopMw(), and redLoopPc().

◆ graph_pc_getSap()

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

alters the graph for prize collecting problems

Parameters

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

Definition at line 1075 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, FARAWAY, flipedge, graph_copy(), graph_edge_add(), graph_edge_redirect(), graph_knot_add(), graph_pc_presolExit(), graph_pc_presolInit(), graph_resize(), Is_pterm, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, and TRUE.

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

◆ graph_pc_adaptSap()

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

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

Parameters

scip	SCIP data structure
bigM	new big M value
graph	the SAP graph
offset	the offset

Definition at line 1174 of file grphbase.c.

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

◆ graph_pc_getSapShift()

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

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

Parameters

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

Definition at line 1204 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_copy(), graph_edge_add(), graph_edge_del(), graph_edge_redirect(), graph_knot_add(), graph_knot_chg(), graph_resize(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

◆ graph_pc_getRsap()

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

alters the graph for prize-collecting problems with given root

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
rootcands	array containing all vertices that could be used as root
nrootcands	number of all vertices could be used as root
root	the root of the new SAP

Definition at line 1365 of file grphbase.c.

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

Referenced by reduce_daPcMw().

◆ graph_pc_2pc()

SCIP_RETCODE graph_pc_2pc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1520 of file grphbase.c.

References GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_init(), graph_resize(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load(), and graph_pc_2mw().

◆ graph_pc_2rpc()

SCIP_RETCODE graph_pc_2rpc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for rooted prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1601 of file grphbase.c.

References GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_init(), graph_resize(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load().

◆ graph_pc_2mw()

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

alters the graph for MWCS problems

Parameters

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

Definition at line 1682 of file grphbase.c.

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

Referenced by graph_load().

◆ graph_pc_2rmw()

SCIP_RETCODE graph_pc_2rmw	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for RMWCS problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1741 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_init(), graph_resize(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load().

◆ graph_pc_mw2rmw()

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

transforms MWCSP to RMWCSP if possible

Parameters

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

Definition at line 1850 of file grphbase.c.

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

Referenced by redLoopMw().

◆ graph_pc_deleteTerm()

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

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

Parameters

scip	SCIP data structure
g	graph data structure
i	index of the terminal

Definition at line 1945 of file grphbase.c.

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

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

◆ graph_pc_subtractPrize()

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

subtract a given sum from the prize of a terminal

Parameters

scip	SCIP data structure
g	the graph
cost	cost to be subtracted
i	the terminal

Definition at line 1992 of file grphbase.c.

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

Referenced by graph_pc_contractEdge().

◆ graph_pc_chgPrize()

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

change prize of a terminal

Parameters

scip	SCIP data structure
g	the graph
newprize	prize to be subtracted
i	the terminal

Definition at line 2035 of file grphbase.c.

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

Referenced by STPStpBranchruleParseConsname().

◆ graph_pc_contractEdgeAncestors()

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

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

Parameters

scip	SCIP data structure
g	the graph
t	tail node to be contracted (surviving node)
s	head node to be contracted
ets	edge from t to s or -1

Definition at line 2079 of file grphbase.c.

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

Referenced by graph_pc_contractEdge(), and reduce_simple_mw().

◆ graph_pc_contractEdge()

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

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

Parameters

scip	SCIP data structure
g	the graph
solnode	solution nodes or NULL
t	tail node to be contracted (surviving node)
s	head node to be contracted
i	terminal to add offset to

Definition at line 2105 of file grphbase.c.

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

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

◆ graph_pc_isPcMw()

SCIP_Bool graph_pc_isPcMw ( const GRAPH * g )

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

Parameters

g the graph

Definition at line 2188 of file grphbase.c.

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

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

◆ graph_knot_add()

void graph_knot_add	(	GRAPH *	p,
		int	term
	)

add a vertex

Parameters

p	the graph
term	terminal property

Definition at line 2200 of file grphbase.c.

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

Referenced by buildsolgraph(), compEdges(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getSap(), graph_pc_getSapShift(), graph_voronoiWithRadius(), reduce_bd34(), reduce_bdr(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), reduce_sdPc(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), and SCIPStpHeurRecExclude().

◆ graph_knot_chg()

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

change terminal property of a vertex

Parameters

p	the graph
node	node to be changed
term	terminal property

Definition at line 2222 of file grphbase.c.

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

Referenced by compEdges(), graph_grid_create(), graph_knot_contract(), graph_load(), graph_obstgrid_create(), graph_pc_2mw(), graph_pc_2org(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_2trans(), graph_pc_contractEdge(), graph_pc_getRsap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), initReceivedSubproblem(), redbasedVarfixing(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_sd(), reduce_sl(), SCIP_DECL_CONSSEPALP(), selectBranchingVertexBySol(), and STPStpBranchruleParseConsname().

◆ graph_knot_del()

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

delete node

Parameters

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

Definition at line 2246 of file grphbase.c.

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

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

◆ graph_knot_delPseudo()

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

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

Parameters

scip	SCIP data structure
g	the graph
edgecosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge
cutoffsrev	revere cutoff values (or NULL if undirected)
vertex	the vertex
success	has node been pseudo-eliminated?

Definition at line 2262 of file grphbase.c.

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

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

◆ graph_knot_contract()

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

contract an edge, given by its endpoints

Parameters

scip	SCIP data structure
p	graph data structure
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
t	tail node to be contracted
s	head node to be contracted

Definition at line 2433 of file grphbase.c.

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

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

◆ graph_knot_contractLowdeg2High()

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

contract endpoint of lower degree into endpoint of higher degree

Parameters

scip	SCIP data structure
g	graph data structure
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
t	tail node to be contracted
s	head node to be contracted

Definition at line 2666 of file grphbase.c.

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

Referenced by reduce_simple().

◆ graph_edge_redirect()

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

Parameters

scip	SCIP data structure
g	the graph
eki	the edge
k	new tail
j	new head
cost	new cost
forcedelete	delete edge eki if it is not used?

Definition at line 2685 of file grphbase.c.

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

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

◆ graph_edge_reinsert()

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

reinsert an edge to replace two other edges

Parameters

scip	SCIP data structure
g	the graph
e1	edge to reinsert
k1	tail
k2	head
cost	edge cost
ancestors0	ancestors of first edge
ancestors1	ancestors of second edge
revancestors0	reverse ancestors of first edge
revancestors1	reverse ancestors of first edge
forcedelete	delete edge e1 if it is not used?

Definition at line 2757 of file grphbase.c.

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

Referenced by graph_knot_delPseudo().

◆ graph_edge_add()

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

add a new edge to the graph

Parameters

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

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

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

◆ graph_edge_del()

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

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

Referenced by adjust0term(), ansProcessCandidate(), getlecloseterms(), graph_edge_redirect(), graph_knot_contract(), graph_knot_del(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_getRsap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), level0(), level0save(), redbasedVarfixing(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), reduce_chain2(), reduce_cnsAdv(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_deleteConflictEdges(), reduce_extendedEdge(), reduce_ledge(), reduce_nnp(), reduce_npv(), reduce_sd(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_simple(), reduce_simple_hc(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), reducePcMw(), reduceSPG(), reduceWithEdgeFixingBounds(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurSlackPruneRunPcMw(), traverseChain(), and trydg1edgepc().

◆ graph_edge_hide()

void graph_edge_hide	(	GRAPH *	g,
		int	e
	)

hide edge

Parameters

g	the graph
e	the edge

Definition at line 2891 of file grphbase.c.

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

◆ graph_edge_printInfo()

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

print edge info

Parameters

scip	SCIP data structure
g	the graph
e	the edge

Definition at line 2935 of file grphbase.c.

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

◆ graph_sol_reroot()

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

changes solution according to given root

Parameters

scip	SCIP data structure
g	the graph
result	solution array (CONNECT/UNKNOWN)
newroot	the new root

Definition at line 2947 of file grphbase.c.

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

Referenced by reduce_da(), and reduce_daPcMw().

◆ graph_sol_unreduced()

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

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

Parameters

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

Definition at line 3050 of file grphbase.c.

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

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

◆ graph_sol_valid()

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

verifies whether a given primal solution is feasible

Parameters

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

Definition at line 3070 of file grphbase.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by computeDaSolPcMw(), computePertubedSol(), graph_sol_getOrg(), reduce_da(), reduce_daPcMw(), reduce_daSlackPruneMw(), reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurSlackPruneRunPcMw(), SCIPStpHeurTMPrunePc(), and selectBranchingVertexBySol().

◆ graph_sol_setNodeList()

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

mark endpoints of edges in given list

Parameters

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

Definition at line 3174 of file grphbase.c.

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

Referenced by graph_sol_getOrg(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_sol_getObj()

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

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

Definition at line 3200 of file grphbase.c.

References CONNECT, and SCIP_Real.

Referenced by computeDaSolPcMw(), computePertubedSol(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_sol_getOrg()

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

get original solution

Parameters

scip	SCIP data structure
transgraph	the transformed graph
orggraph	the original graph
transsoledge	solution for transformed problem
orgsoledge	new retransformed solution

Definition at line 3218 of file grphbase.c.

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

Referenced by SCIPStpHeurPruneUpdateSols().

◆ graph_sol_markPcancestors()

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

mark original solution

Parameters

scip	SCIP data structure
pcancestors	the ancestors
tails	tails array
heads	heads array
orgnnodes	original number of nodes
solnodemark	solution nodes mark array
soledgemark	solution edges mark array or NULL
solnodequeue	solution nodes queue or NULL
nsolnodes	number of solution nodes or NULL
nsoledges	number of solution edges or NULL

Definition at line 3292 of file grphbase.c.

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

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

◆ graph_get_NVET()

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

get (real) number of nodes , edges, terminals

Parameters

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

Definition at line 3386 of file grphbase.c.

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

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

◆ graph_get_csr()

void graph_get_csr	(	const GRAPH *	g,
		int *RESTRICT	edgearr,
		int *RESTRICT	tailarr,
		int *RESTRICT	start,
		int *	nnewedges
	)

Parameters

g	the graph
edgearr	original edge array [0,...,nedges - 1]
tailarr	tail of csr edge [0,...,nedges - 1]
start	start array [0,...,nnodes]
nnewedges	pointer to store number of new edges

Definition at line 3421 of file grphbase.c.

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

◆ graph_get_edgeConflicts()

SCIP_RETCODE graph_get_edgeConflicts	(	SCIP *	scip,
		const GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	the graph

Definition at line 3452 of file grphbase.c.

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

◆ graph_init()

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

initialize graph

Parameters

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

Definition at line 3495 of file grphbase.c.

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

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

◆ graph_init_history()

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

References GRAPH::ancestors, GRAPH::edges, graph_pc_isPcMw(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocMemoryArray, and GRAPH::tail.

Referenced by initReceivedSubproblem(), redbasedVarfixing(), reduce(), reduce_daPcMw(), reduce_daSlackPruneMw(), SCIP_DECL_PROPEXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_resize()

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

enlarge given graph

Parameters

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

Definition at line 3635 of file grphbase.c.

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

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

◆ graph_free()

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

free the graph

Parameters

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

Definition at line 3678 of file grphbase.c.

References GRAPH::cost, GRAPH::grad, graph_free_history(), graph_free_historyDeep(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::mark, GRAPH::maxdeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::rootedgeprevs, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, STP_DCSTP, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by graph_pack(), initReceivedSubproblem(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), reduce_sdPc(), SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROPEXITSOL(), SCIPprobdataWriteSolution(), SCIPStpDualAscentPcMw(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_free_history()

void graph_free_history	(	SCIP *	scip,
		GRAPH *	p
	)

free the history

Parameters

scip	SCIP data
p	graph data

Definition at line 3740 of file grphbase.c.

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

Referenced by graph_free(), and redbasedVarfixing().

◆ graph_free_historyDeep()

void graph_free_historyDeep	(	SCIP *	scip,
		GRAPH *	p
	)

free the deep history

Parameters

scip	SCIP data
p	graph data

Definition at line 3764 of file grphbase.c.

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

Referenced by graph_free(), and redbasedVarfixing().

◆ graph_copy_data()

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

copy the data of the graph

Parameters

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

Definition at line 3809 of file grphbase.c.

References BMScopyMemoryArray, GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::extended, GRAPH::grad, graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, GRAPH::maxdeg, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orgknots, GRAPH::orgsource, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, GRAPH::source, STP_DCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and GRAPH::terms.

Referenced by graph_copy(), and redbasedVarfixing().

◆ graph_copy()

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

copy the graph

Parameters

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

Definition at line 3900 of file grphbase.c.

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

Referenced by graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), initReceivedSubproblem(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROPEXEC(), SCIPprobdataCreate(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_show()

void graph_show ( const GRAPH * p )

Parameters

p the graph

Definition at line 3916 of file grphbase.c.

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

◆ graph_uncover()

void graph_uncover ( GRAPH * g )

reinsert all hidden edges

Parameters

g the graph

Definition at line 3941 of file grphbase.c.

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

◆ graph_pack()

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

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exit(), graph_pc_init(), graph_pc_updateTerm2edge(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::mark, GRAPH::maxdeg, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, GRAPH::path_heap, GRAPH::pcancestors, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGT(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

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

◆ graph_trail()

void graph_trail	(	const GRAPH *	g,
		int	i
	)

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

Parameters

g	the new graph
i	node to start from

Definition at line 4188 of file grphbase.c.

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

Referenced by graph_valid().

◆ graph_trail_arr()

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

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

Parameters

scip	scip struct
g	the new graph
i	node to start from

Definition at line 4242 of file grphbase.c.

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

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

◆ graph_termsReachable()

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

checks whether all terminals are reachable from root

Parameters

scip	scip struct
g	the new graph
reachable	are they reachable?

Definition at line 4299 of file grphbase.c.

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

◆ graph_valid()

SCIP_Bool graph_valid ( const GRAPH * g )

is the given graph valid?

Parameters

g	the new graph

Definition at line 4328 of file grphbase.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::grad, graph_trail(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIPdebugMessage, GRAPH::source, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by buildsolgraph(), computeNewSols(), computePertubedSol(), computeSteinerTree(), getlecloseterms(), graph_copy_data(), graph_load(), graph_pack(), graph_save(), nvreduce_sl(), redbasedVarfixing(), redLoopStp(), reduce(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_bd34(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundPrune(), reduce_da(), reduce_daPcMw(), reduce_ledge(), reduce_nnp(), reduce_nts(), reduce_sdPc(), reduce_sdsp(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ STP_DELPSEUDO_MAXGRAD

◆ STP_DELPSEUDO_MAXNEDGES

Function Documentation

◆ cutoffEdge()

◆ removeEdge()

◆ getNodeNumber()

◆ compEdgesObst()

◆ compEdges()

◆ graph_obstgrid_create()

◆ graph_grid_create()

◆ graph_grid_coordinates()

◆ graph_pc_init()

◆ graph_pc_presolInit()

◆ graph_pc_presolExit()

◆ graph_pc_term2edgeConsistent()

◆ graph_pc_knot2nonTerm()

◆ graph_pc_updateTerm2edge()

◆ graph_pc_2org()

◆ graph_pc_2trans()

◆ graph_pc_2orgcheck()

◆ graph_pc_2transcheck()

◆ graph_pc_getPosPrizeSum()

◆ graph_pc_getSap()

◆ graph_pc_adaptSap()

◆ graph_pc_getSapShift()

◆ graph_pc_getRsap()

◆ graph_pc_2pc()

◆ graph_pc_2rpc()

◆ graph_pc_2mw()

◆ graph_pc_2rmw()

◆ graph_pc_mw2rmw()

◆ graph_pc_deleteTerm()

◆ graph_pc_subtractPrize()

◆ graph_pc_chgPrize()

◆ graph_pc_contractEdgeAncestors()

◆ graph_pc_contractEdge()

◆ graph_pc_isPcMw()

◆ graph_knot_add()

◆ graph_knot_chg()

◆ graph_knot_del()

◆ graph_knot_delPseudo()

◆ graph_knot_contract()

◆ graph_knot_contractLowdeg2High()

◆ graph_edge_redirect()

◆ graph_edge_reinsert()

◆ graph_edge_add()

◆ graph_edge_del()

◆ graph_edge_hide()

◆ graph_edge_printInfo()

◆ graph_sol_reroot()

◆ graph_sol_unreduced()

◆ graph_sol_valid()

◆ graph_sol_setNodeList()

◆ graph_sol_getObj()

◆ graph_sol_getOrg()

◆ graph_sol_markPcancestors()

◆ graph_get_NVET()

◆ graph_get_csr()

◆ graph_get_edgeConflicts()

◆ graph_init()

◆ graph_init_history()

◆ graph_resize()

◆ graph_free()

◆ graph_free_history()

◆ graph_free_historyDeep()

◆ graph_copy_data()

◆ graph_copy()

◆ graph_show()

◆ graph_uncover()

◆ graph_pack()

◆ graph_trail()

◆ graph_trail_arr()

◆ graph_termsReachable()

◆ graph_valid()