Detailed Description

includes graph utility methods for Steiner problems

Author: Daniel Rehfeldt

Graph utility methods for Steiner problems, such as CSR data structure

Definition in file graph_util.c.

#include "graph.h"
#include "reduce.h"
#include "portab.h"

Data Structures
struct	compressed_sparse_storages_depository

Macros
#define	DHEAP_MAX_KEY (1e20)

#define	DHEAP_MIN_KEY -(1e20)

Functions
static SCIP_RETCODE	trail (SCIP scip, const GRAPH g, int start, SCIP_Bool costAware, SCIP_Bool *nodevisited)

static SCIP_Bool	csrdepoCsrIsSet (const CSR *csr, SCIP_Bool verbose)

static void	csrdepoCsrUnsetDebug (CSR *csr)

static void	csrdepoCleanDebug (CSRDEPO *depository)

static SCIP_Real	csrdepoCsrWeight (const CSR *csr)

static SCIP_Real	csrdepoGetTopWeight (const CSRDEPO *depository)

static int	csrdepoGetTopIndex (const CSRDEPO *depository)

static int	csrdepoGetNnodes (const CSRDEPO *depository, int index)

static int	csrdepoGetNedges (const CSRDEPO *depository, int index)

static void	csrdepoFillCSR (const CSRDEPO depository, int index, CSR csr)

SCIP_RETCODE	graph_trail_arr (SCIP scip, const GRAPH g, int start, SCIP_Bool *nodevisited)

SCIP_RETCODE	graph_trail_costAware (SCIP scip, const GRAPH g, int start, SCIP_Bool *nodevisited)

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

SCIP_RETCODE	graph_findCentralTerminal (SCIP scip, const GRAPH g, int centertype, int *central_term)

void	graph_buildOrgNodesToReducedMap (const GRAPH g, int map)

SCIP_RETCODE	graph_csrdepo_init (SCIP scip, int ncsrs_max, int datasize_max, CSRDEPO *depository)

void	graph_csrdepo_free (SCIP scip, CSRDEPO *depository)

void	graph_csrdepo_getCSR (const CSRDEPO depository, int index, CSR csr)

void	graph_csrdepo_getTopCSR (const CSRDEPO depository, CSR csr)

int	graph_csrdepo_getDataSize (const CSRDEPO *depository)

int	graph_csrdepo_getNcsrs (const CSRDEPO *depository)

void	graph_csrdepo_removeTop (CSRDEPO *depository)

void	graph_csrdepo_clean (CSRDEPO *depository)

void	graph_csrdepo_addEmptyTop (CSRDEPO *depository, int nnodes, int nedges)

void	graph_csrdepo_addEmptyTopTree (CSRDEPO *depository, int nnodes)

SCIP_Bool	graph_csrdepo_isEmpty (const CSRDEPO *depository)

SCIP_Bool	graph_csrdepo_hasEmptyTop (const CSRDEPO *depository)

void	graph_csrdepo_getEmptyTop (const CSRDEPO depository, CSR csr)

void	graph_csrdepo_emptyTopSetMarked (CSRDEPO *depository)

void	graph_csrdepo_print (const CSRDEPO *depository)

void	graph_heap_clean (SCIP_Bool cleanposition, DHEAP *heap)

SCIP_Bool	graph_heap_isClean (const DHEAP *heap)

SCIP_RETCODE	graph_heap_create (SCIP scip, int capacity, int position, DENTRY entries, DHEAP *heap)

void	graph_heap_free (SCIP scip, SCIP_Bool freePositions, SCIP_Bool freeEntries, DHEAP *heap)

void	graph_heap_deleteMin (int node, SCIP_Real key, DHEAP *heap)

void	graph_heap_deleteMinGetNode (int node, DHEAP heap)

int	graph_heap_deleteMinReturnNode (DHEAP *heap)

void	graph_heap_correct (int node, SCIP_Real newkey, DHEAP *heap)

SCIP_RETCODE	graph_csr_alloc (SCIP scip, int nnodes, int nedges, CSR *csr)

SCIP_RETCODE	graph_csr_allocWithEdgeId (SCIP scip, int nnodes, int nedges, CSR *csr)

void	graph_csr_chgCosts (const GRAPH g, const SCIP_Real edgecosts, CSR *csr)

void	graph_csr_build (const GRAPH g, const SCIP_Real edgecosts, CSR *csr)

void	graph_csr_buildCosts (const GRAPH g, const CSR csr, const SCIP_Real edgecosts_g, SCIP_Real RESTRICT edgecosts_csr)

SCIP_Bool	graph_csr_costsAreInSync (const GRAPH g, const CSR csr, const SCIP_Real *edgecosts_g)

void	graph_csr_copy (const CSR csr_in, CSR csr_out)

void	graph_csr_print (const CSR *csr)

int	graph_csr_getNedges (const CSR *csr)

void	graph_csr_free (SCIP scip, CSR *csr)

SCIP_RETCODE	graph_init_csr (SCIP scip, GRAPH g)

SCIP_RETCODE	graph_init_csrWithEdgeId (SCIP scip, GRAPH g)

void	graph_free_csr (SCIP scip, GRAPH g)

SCIP_Bool	graph_csr_isValid (const CSR *csr, SCIP_Bool verbose)

SCIP_Bool	graph_valid_csr (const GRAPH *g, SCIP_Bool verbose)

SCIP_RETCODE	graph_init_dcsr (SCIP scip, GRAPH g)

void	graph_free_dcsr (SCIP scip, GRAPH g)

void	graph_update_dcsr (SCIP scip, GRAPH g)

void	graph_dcsr_deleteEdge (DCSR *dcsr, int tail, int e_csr)

void	graph_dcsr_deleteEdgeBi (SCIP scip, DCSR dcsr, int e_csr)

SCIP_Bool	graph_valid_dcsr (const GRAPH *g, SCIP_Bool verbose)

SCIP_RETCODE	graph_dijkLimited_init (SCIP scip, const GRAPH g, DIJK **dijkdata)

SCIP_RETCODE	graph_dijkLimited_initPcShifts (SCIP scip, const GRAPH g, DIJK *dijkdata)

void	graph_dijkLimited_clean (const GRAPH g, DIJK dijkdata)

void	graph_dijkLimited_reset (const GRAPH g, DIJK dijkdata)

void	graph_dijkLimited_free (SCIP scip, DIJK *dijkdata)

Macro Definition Documentation

◆ DHEAP_MAX_KEY

#define DHEAP_MAX_KEY (1e20)

Definition at line 29 of file graph_util.c.

Referenced by graph_heap_correct(), graph_heap_create(), and graph_heap_deleteMinReturnNode().

◆ DHEAP_MIN_KEY

#define DHEAP_MIN_KEY -(1e20)

Definition at line 30 of file graph_util.c.

Referenced by graph_heap_correct(), and graph_heap_create().

Function Documentation

◆ trail()

static SCIP_RETCODE trail	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		SCIP_Bool	costAware,
		SCIP_Bool *	nodevisited
	)

static

traverses the graph from vertex 'start' and marks all reached nodes

Parameters

scip	SCIP
g	the new graph
start	node to start from
costAware	be cost aware?
nodevisited	marks which node has been visited

Definition at line 60 of file graph_util.c.

References a, GRAPH::cost, EAT_LAST, FALSE, FARAWAY, GE, GRAPH::grad, GRAPH::head, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by graph_trail_arr(), and graph_trail_costAware().

◆ csrdepoCsrIsSet()

static SCIP_Bool csrdepoCsrIsSet	(	const CSR *	csr,
		SCIP_Bool	verbose
	)

static

has the CSR been initialized?

Parameters

csr	pointer to CSR struct to fill
verbose	be verbose?

Definition at line 114 of file graph_util.c.

References csr_storage::cost, FALSE, csr_storage::head, LT, csr_storage::nedges_max, csr_storage::nnodes, csr_storage::start, and TRUE.

Referenced by graph_csrdepo_getTopCSR().

◆ csrdepoCsrUnsetDebug()

static void csrdepoCsrUnsetDebug ( CSR * csr )

static

de-initialize CSR (in debug mode)

Parameters

csr	pointer to CSR struct to fill

Definition at line 161 of file graph_util.c.

References csr_storage::cost, csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, and csr_storage::start.

Referenced by graph_csrdepo_removeTop().

◆ csrdepoCleanDebug()

static void csrdepoCleanDebug ( CSRDEPO * depository )

static

cleaning (in debug mode)

Parameters

depository the depository

Definition at line 178 of file graph_util.c.

Referenced by graph_csrdepo_clean(), and graph_csrdepo_init().

◆ csrdepoCsrWeight()

static SCIP_Real csrdepoCsrWeight ( const CSR * csr )

static

gets top CSR edge weight

Parameters

csr	pointer to CSR struct to fill

Definition at line 215 of file graph_util.c.

References csr_storage::cost, csr_storage::nedges_max, and SCIP_Real.

Referenced by csrdepoGetTopWeight(), and graph_csrdepo_getTopCSR().

◆ csrdepoGetTopWeight()

static SCIP_Real csrdepoGetTopWeight ( const CSRDEPO * depository )

static

gets top CSR edge weight

Parameters

depository the depository

Definition at line 232 of file graph_util.c.

References csrdepoCsrWeight(), graph_csrdepo_getCSR(), and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by graph_csrdepo_emptyTopSetMarked().

◆ csrdepoGetTopIndex()

static int csrdepoGetTopIndex ( const CSRDEPO * depository )

inlinestatic

gets top index

Parameters

depository the depository

Definition at line 248 of file graph_util.c.

References compressed_sparse_storages_depository::ncsrs_curr.

Referenced by graph_csrdepo_addEmptyTop(), graph_csrdepo_emptyTopSetMarked(), graph_csrdepo_getDataSize(), graph_csrdepo_getEmptyTop(), graph_csrdepo_getTopCSR(), graph_csrdepo_hasEmptyTop(), and graph_csrdepo_removeTop().

◆ csrdepoGetNnodes()

static int csrdepoGetNnodes	(	const CSRDEPO *	depository,
		int	index
	)

inlinestatic

gets number of nodes of CSR stored at position 'index'

Parameters

depository	the depository
index	the index of the CSR

Definition at line 262 of file graph_util.c.

References compressed_sparse_storages_depository::csr_nnodes, compressed_sparse_storages_depository::csr_ptrsStart, compressed_sparse_storages_depository::ncsrs_curr, and nnodes.

Referenced by csrdepoFillCSR(), and graph_csrdepo_getDataSize().

◆ csrdepoGetNedges()

static int csrdepoGetNedges	(	const CSRDEPO *	depository,
		int	index
	)

inlinestatic

gets number of edges of CSR stored at position 'index'

Parameters

depository	the depository
index	the index of the CSR

Definition at line 283 of file graph_util.c.

References compressed_sparse_storages_depository::csr_nedges, compressed_sparse_storages_depository::csr_ptrsData, and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by csrdepoFillCSR(), and graph_csrdepo_getDataSize().

◆ csrdepoFillCSR()

static void csrdepoFillCSR	(	const CSRDEPO *	depository,
		int	index,
		CSR *	csr
	)

inlinestatic

fills the CSR structure

Parameters

depository	the depository
index	the index
csr	pointer to CSR struct to fill

Definition at line 304 of file graph_util.c.

References compressed_sparse_storages_depository::all_costs, compressed_sparse_storages_depository::all_heads, compressed_sparse_storages_depository::all_starts, csr_storage::cost, compressed_sparse_storages_depository::csr_ptrsData, compressed_sparse_storages_depository::csr_ptrsStart, csrdepoGetNedges(), csrdepoGetNnodes(), csr_storage::edge_id, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, NULL, and csr_storage::start.

Referenced by graph_csrdepo_getCSR(), graph_csrdepo_getEmptyTop(), and graph_csrdepo_removeTop().

◆ graph_trail_arr()

SCIP_RETCODE graph_trail_arr	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		SCIP_Bool *	nodevisited
	)

traverses the graph from vertex 'start' and marks all reached nodes

Parameters

scip	SCIP
g	the new graph
start	node to start from
nodevisited	marks which node has been visited

Definition at line 336 of file graph_util.c.

References FALSE, SCIP_OKAY, and trail().

Referenced by graph_termsReachable(), graph_valid(), graph_validInput(), reduce_unconnected(), and reduce_unconnectedInfeas().

◆ graph_trail_costAware()

SCIP_RETCODE graph_trail_costAware	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		SCIP_Bool *	nodevisited
	)

traverses the graph and marks all reached nodes, does not take edge of cost >= FARAWAY

Parameters

scip	SCIP
g	the new graph
start	node to start from
nodevisited	marks which node has been visited

Definition at line 353 of file graph_util.c.

References SCIP_OKAY, trail(), and TRUE.

Referenced by graphisValidPcMw(), pcmwUpdate(), and reduce_unconnectedForDirected().

◆ 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 370 of file graph_util.c.

References FALSE, graph_trail_arr(), Is_term, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

◆ graph_findCentralTerminal()

SCIP_RETCODE graph_findCentralTerminal	(	SCIP *	scip,
		const GRAPH *	g,
		int	centertype,
		int *	central_term
	)

Parameters

scip	SCIP data structure
g	graph data structure
centertype	type of root selection
central_term	pointer to store the selected (terminal) vertex

Definition at line 410 of file graph_util.c.

References shortest_path::dist, GRAPH::edges, FARAWAY, FSP_MODE, GRAPH::grad, graph_get_nNodes(), graph_knotIsNWLeaf(), graph_path_exec(), Is_term, GRAPH::layers, GRAPH::mark, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisLT(), SCIPverbMessage(), GRAPH::source, STP_CENTER_ALL, STP_CENTER_DEG, STP_CENTER_MIN, STP_CENTER_OK, STP_CENTER_SUM, STP_NWPTSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by SCIPprobdataCreateFromGraph().

◆ graph_buildOrgNodesToReducedMap()

void graph_buildOrgNodesToReducedMap	(	const GRAPH *	g,
		int *	map
	)

builds mapping from original vertices to non-zero degree ones

Parameters

g	the graph
map	map

Definition at line 560 of file graph_util.c.

References GRAPH::grad, graph_get_nNodes(), nnodes, and UNKNOWN.

◆ graph_csrdepo_init()

SCIP_RETCODE graph_csrdepo_init	(	SCIP *	scip,
		int	ncsrs_max,
		int	datasize_max,
		CSRDEPO **	depository
	)

initializes CSR depository

Parameters

scip	SCIP data structure
ncsrs_max	maximum number of CSRs
datasize_max	the maximum capacity
depository	the depository

Definition at line 590 of file graph_util.c.

Referenced by csrdepoTest1(), csrdepoTest2(), and extreduce_extPermaInit().

◆ graph_csrdepo_free()

void graph_csrdepo_free	(	SCIP *	scip,
		CSRDEPO **	depository
	)

frees CSR depository

Parameters

scip	SCIP data structure
depository	the depository

Definition at line 637 of file graph_util.c.

Referenced by csrdepoTest1(), csrdepoTest2(), and extreduce_extPermaFree().

◆ graph_csrdepo_getCSR()

void graph_csrdepo_getCSR	(	const CSRDEPO *	depository,
		int	index,
		CSR *	csr
	)

gets CSR from depository

Parameters

depository	the depository
index	the index of the CSR to get
csr	pointer to CSR struct to fill

Definition at line 667 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, csrdepoFillCSR(), compressed_sparse_storages_depository::ncsrs_curr, and csr_storage::start.

Referenced by csrdepoGetTopWeight(), csrdepoTest2(), graph_csrdepo_getTopCSR(), graph_csrdepo_print(), and ruledOut().

◆ graph_csrdepo_getTopCSR()

void graph_csrdepo_getTopCSR	(	const CSRDEPO *	depository,
		CSR *	csr
	)

gets top (last added) CSR from depository

Parameters

depository	the depository
csr	pointer to CSR struct to fill

Definition at line 684 of file graph_util.c.

References compressed_sparse_storages_depository::csr_weight, csrdepoCsrIsSet(), csrdepoCsrWeight(), csrdepoGetTopIndex(), EQ, FALSE, graph_csrdepo_getCSR(), graph_csrdepo_hasEmptyTop(), compressed_sparse_storages_depository::ncsrs_curr, and SCIP_Real.

Referenced by baseMstInitMsts(), compMstInitMsts(), extreduce_mstTopCompInSync(), extreduce_mstTopLevelBaseObjValid(), mstCompRuleOut(), and mstLevelLeafTryExtMst().

◆ graph_csrdepo_getDataSize()

int graph_csrdepo_getDataSize ( const CSRDEPO * depository )

gets current size of data (from all CSRs) in depository

Parameters

depository the depository

Definition at line 709 of file graph_util.c.

References compressed_sparse_storages_depository::csr_ptrsData, compressed_sparse_storages_depository::csr_ptrsStart, csrdepoGetNedges(), csrdepoGetNnodes(), csrdepoGetTopIndex(), compressed_sparse_storages_depository::datasize_max, MAX, and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by graph_csrdepo_addEmptyTop().

◆ graph_csrdepo_getNcsrs()

int graph_csrdepo_getNcsrs ( const CSRDEPO * depository )

gets number of CSRs in depository

Parameters

depository the depository

Definition at line 741 of file graph_util.c.

References compressed_sparse_storages_depository::ncsrs_curr.

Referenced by compMstInitMsts(), extreduce_mstCompRemove(), extreduce_mstInternalsInSync(), extreduce_mstLevelRemove(), graph_csrdepo_print(), mstLevelBuildBaseMstRoot(), and postCleanMSTs().

◆ graph_csrdepo_removeTop()

void graph_csrdepo_removeTop ( CSRDEPO * depository )

removes top of CSR depository

Parameters

depository the depository

Definition at line 753 of file graph_util.c.

References compressed_sparse_storages_depository::csr_nedges, compressed_sparse_storages_depository::csr_nnodes, compressed_sparse_storages_depository::csr_weight, csrdepoCsrUnsetDebug(), csrdepoFillCSR(), csrdepoGetTopIndex(), graph_csrdepo_hasEmptyTop(), graph_csrdepo_isEmpty(), and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by compMstFinalizeNew(), csrdepoTest1(), csrdepoTest2(), extreduce_mstCompRemove(), extreduce_mstLevelRemove(), and graph_csrdepo_clean().

◆ graph_csrdepo_clean()

void graph_csrdepo_clean ( CSRDEPO * depository )

cleans CSR depository

Parameters

depository the depository

Definition at line 781 of file graph_util.c.

References csrdepoCleanDebug(), graph_csrdepo_isEmpty(), graph_csrdepo_removeTop(), and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by postCleanMSTs().

◆ graph_csrdepo_addEmptyTop()

void graph_csrdepo_addEmptyTop	(	CSRDEPO *	depository,
		int	nnodes,
		int	nedges
	)

adds empty top to CSR depository

Parameters

depository	the depository
nnodes	nodes of new top
nedges	number of (directed!) edges of new top

Definition at line 800 of file graph_util.c.

Referenced by add1NodeMst(), csrdepoTest1(), csrdepoTest2(), and graph_csrdepo_addEmptyTopTree().

◆ graph_csrdepo_addEmptyTopTree()

void graph_csrdepo_addEmptyTopTree	(	CSRDEPO *	depository,
		int	nnodes
	)

adds empty top for tree to CSR depository

Parameters

depository	the depository
nnodes	nodes of new top

Definition at line 836 of file graph_util.c.

References graph_csrdepo_addEmptyTop().

Referenced by baseMstInitMsts(), and compMstInitMsts().

◆ graph_csrdepo_isEmpty()

SCIP_Bool graph_csrdepo_isEmpty ( const CSRDEPO * depository )

is the CSR depository empty?

Parameters

depository the depository

Definition at line 851 of file graph_util.c.

References compressed_sparse_storages_depository::ncsrs_curr.

Referenced by csrdepoTest1(), csrdepoTest2(), extreduce_extPermaIsClean(), graph_csrdepo_addEmptyTop(), graph_csrdepo_clean(), graph_csrdepo_init(), graph_csrdepo_removeTop(), mstAddRootLevelMsts(), and mstLevelBuildBaseMstRoot().

◆ graph_csrdepo_hasEmptyTop()

SCIP_Bool graph_csrdepo_hasEmptyTop ( const CSRDEPO * depository )

is top of CSR depository empty?

Parameters

depository the depository

Definition at line 863 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, and csrdepoGetTopIndex().

Referenced by graph_csrdepo_addEmptyTop(), graph_csrdepo_getTopCSR(), and graph_csrdepo_removeTop().

◆ graph_csrdepo_getEmptyTop()

void graph_csrdepo_getEmptyTop	(	const CSRDEPO *	depository,
		CSR *	csr
	)

Gets empty top of current depository.

Parameters

depository	the depository
csr	pointer to csr struct to fill

Definition at line 874 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, csrdepoFillCSR(), csrdepoGetTopIndex(), and compressed_sparse_storages_depository::ncsrs_max.

Referenced by add1NodeMst(), baseMstInitMsts(), compMstInitMsts(), csrdepoTest1(), and csrdepoTest2().

◆ graph_csrdepo_emptyTopSetMarked()

void graph_csrdepo_emptyTopSetMarked ( CSRDEPO * depository )

Sets formerly empty top to marked.

Parameters

depository the depository

Definition at line 890 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, compressed_sparse_storages_depository::csr_weight, csrdepoGetTopIndex(), csrdepoGetTopWeight(), EQ, and FALSE.

Referenced by add1NodeMst(), baseMstFinalizeNew(), compMstFinalizeNew(), csrdepoTest1(), and csrdepoTest2().

◆ graph_csrdepo_print()

void graph_csrdepo_print ( const CSRDEPO * depository )

Prints depository.

Parameters

depository the depository

Definition at line 908 of file graph_util.c.

References compressed_sparse_storages_depository::csr_weight, graph_csrdepo_getCSR(), graph_csrdepo_getNcsrs(), csr_storage::nedges_max, and csr_storage::nnodes.

Referenced by baseMstFinalizeNew(), and compMstFinalizeNew().

◆ graph_heap_clean()

void graph_heap_clean	(	SCIP_Bool	cleanposition,
		DHEAP *	heap
	)

clean the heap

Parameters

cleanposition	clean position array?
heap	the heap

Definition at line 938 of file graph_util.c.

References dijkstra_heap::capacity, graph_heap_isClean(), dijkstra_heap::position, SCIP_Bool, dijkstra_heap::size, and UNKNOWN.

Referenced by computeOnMarked_init(), computeSteinerTree_init(), graph_dijkLimited_clean(), graph_dijkLimited_reset(), graph_heap_create(), graph_path_st_pcmw_extendOut(), propagateUBs(), reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), sdStarReset(), stptest_dheap(), subtreesExtend(), and subtreesRemoveNonValids().

◆ graph_heap_isClean()

SCIP_Bool graph_heap_isClean ( const DHEAP * heap )

is the heap clean?

Parameters

heap the heap

Definition at line 962 of file graph_util.c.

References dijkstra_heap::capacity, FALSE, dijkstra_heap::position, SCIPdebugMessage, dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by cmst_computeMst(), graph_heap_clean(), sdCliqueStarInit(), sdStarInit(), and vnoiInit().

◆ graph_heap_create()

SCIP_RETCODE graph_heap_create	(	SCIP *	scip,
		int	capacity,
		int *	position,
		DENTRY *	entries,
		DHEAP **	heap
	)

creates new heap. If entries array is provided, it must be of size capacity + 2

Parameters

scip	SCIP
capacity	heap capacity
position	heap position array or NULL
entries	entries array or NULL
heap	the heap

Definition at line 992 of file graph_util.c.

References DHEAP_MAX_KEY, DHEAP_MIN_KEY, graph_heap_clean(), dijkstra_heap_entry::key, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and TRUE.

Referenced by checkSdWalk(), cmst_init(), distCloseNodesCompute(), distGetRestricted(), dpsolverInitData(), extreduce_distDataInit(), graph_dijkLimited_init(), graph_vnoiCompute(), graph_vnoiComputeImplied(), mst_init(), reduce_redLoopPc(), SCIPStpHeurLocalExtendPcMwOut(), stptest_dheap(), and tmBaseInit().

◆ graph_heap_free()

void graph_heap_free	(	SCIP *	scip,
		SCIP_Bool	freePositions,
		SCIP_Bool	freeEntries,
		DHEAP **	heap
	)

frees the heap

Parameters

scip	SCIP
freePositions	free positions array?
freeEntries	free entries array?
heap	the heap

Definition at line 1034 of file graph_util.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by checkSdWalk(), cmst_free(), distCloseNodesCompute(), distGetRestricted(), dpsolverFreeData(), extreduce_distDataFree(), graph_dijkLimited_free(), graph_vnoiCompute(), graph_vnoiComputeImplied(), mst_free(), reduce_redLoopPc(), SCIPStpHeurLocalExtendPcMwOut(), stptest_dheap(), and tmBaseFree().

◆ graph_heap_deleteMin()

void graph_heap_deleteMin	(	int *	node,
		SCIP_Real *	key,
		DHEAP *	heap
	)

deletes heap minimum

Parameters

node	pointer to value of minimum
key	pointer to key of minimum
heap	the heap

Definition at line 1053 of file graph_util.c.

References dijkstra_heap::entries, graph_heap_deleteMinGetNode(), and dijkstra_heap_entry::key.

Referenced by propagateUBs(), subtreesExtend(), and subtreesRemoveNonValids().

◆ graph_heap_deleteMinGetNode()

void graph_heap_deleteMinGetNode	(	int *	node,
		DHEAP *	heap
	)

deletes heap minimum

Parameters

node	pointer to node stored in minimum (set by method)
heap	the heap

Definition at line 1065 of file graph_util.c.

References graph_heap_deleteMinReturnNode().

Referenced by graph_heap_deleteMin(), and stptest_dheap().

◆ graph_heap_deleteMinReturnNode()

int graph_heap_deleteMinReturnNode ( DHEAP * heap )

deletes heap minimum and returns corresponding node

Parameters

heap the heap

Definition at line 1076 of file graph_util.c.

References CONNECT, DHEAP_MAX_KEY, dijkstra_heap::entries, dijkstra_heap::position, SCIP_Real, and dijkstra_heap::size.

Referenced by closeNodesRunCompute(), cmst_computeMst(), computeOnMarked_exec(), computeSteinerTree_exec(), computeSteinerTree_execBiased(), computeSteinerTree_execDirected(), computeSteinerTree_execPcMw(), computeSteinerTree_execPcMwFull(), computeSteinerTree_execRpcMw(), distCloseNodesCompute(), distGetRestricted(), graph_heap_deleteMinGetNode(), graph_path_st_pcmw_extendOut(), graph_pathInLimitedExec(), graph_sdCloseNodesBiased(), graph_sdStar(), graph_sdStarBiased(), graph_sdWalks_csr(), graph_sdWalksTriangle(), sdCliqueStarComputeSds(), vnoiCompute(), and vnoiComputeImplied().

◆ graph_heap_correct()

void graph_heap_correct	(	int	node,
		SCIP_Real	newkey,
		DHEAP *	heap
	)

corrects node position in heap according to new key (or newly inserts the node)

Parameters

node	the node
newkey	the new key (needs to be smaller than current one)
heap	the heap

Definition at line 1166 of file graph_util.c.

References dijkstra_heap::capacity, CONNECT, DHEAP_MAX_KEY, DHEAP_MIN_KEY, dijkstra_heap::entries, GE, dijkstra_heap::position, SCIP_Real, dijkstra_heap::size, and UNKNOWN.

◆ graph_csr_alloc()

SCIP_RETCODE graph_csr_alloc	(	SCIP *	scip,
		int	nnodes,
		int	nedges,
		CSR **	csr
	)

allocates empty (and invalid!) CSR storage

Parameters

scip	SCIP data structure
nnodes	nodes
nedges	edges
csr	CSR

Definition at line 1231 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and csr_storage::start.

Referenced by csrdepoTest2(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), extreduce_contractionInit(), graph_csr_allocWithEdgeId(), and graph_init_csr().

◆ graph_csr_allocWithEdgeId()

SCIP_RETCODE graph_csr_allocWithEdgeId	(	SCIP *	scip,
		int	nnodes,
		int	nedges,
		CSR **	csr
	)

allocates empty (and invalid!) CSR storage

Parameters

scip	SCIP data structure
nnodes	nodes
nedges	edges
csr	CSR

Definition at line 1270 of file graph_util.c.

References csr_storage::edge_id, graph_csr_alloc(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by graph_init_csrWithEdgeId(), mst_init(), and tmBaseInit().

◆ graph_csr_chgCosts()

void graph_csr_chgCosts	(	const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		CSR *	csr
	)

Changes edge costs. NOTE: for PC/MW no dummy nodes are considered!

Parameters

g	the graph
edgecosts	edge costs (w.r.t graph 'g')
csr	CSR

Definition at line 1298 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_csr_isValid(), graph_get_nEdges(), graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), csr_storage::head, GRAPH::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, csr_storage::start, and TRUE.

Referenced by pcmwSetEdgeCosts().

◆ graph_csr_build()

void graph_csr_build	(	const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		CSR *	csr
	)

Builds CSR storage from graph and cost array. NOTE: for PC/MW no dummy nodes are considered!

Parameters

g	the graph
edgecosts	edge costs (w.r.t graph 'g')
csr	CSR

Definition at line 1351 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_csr_isValid(), graph_get_nEdges(), graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), graph_typeIsDirected(), csr_storage::head, GRAPH::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, csr_storage::start, STP_DCSTP, GRAPH::stp_type, and TRUE.

Referenced by graph_init_csr(), graph_init_csrWithEdgeId(), mst_init(), and tmBaseInit().

◆ graph_csr_buildCosts()

void graph_csr_buildCosts	(	const GRAPH *	g,
		const CSR *	csr,
		const SCIP_Real *	edgecosts_g,
		SCIP_Real *RESTRICT	edgecosts_csr
	)

builds CSR costs from given edgecosts array

Parameters

g	the graph
csr	CSR
edgecosts_g	edge costs (w.r.t graph 'g')
edgecosts_csr	new edgecosts for CSR

Definition at line 1418 of file graph_util.c.

References csr_storage::edge_id, graph_get_nEdges(), graph_get_nNodes(), nnodes, csr_storage::nnodes, and csr_storage::start.

◆ graph_csr_costsAreInSync()

SCIP_Bool graph_csr_costsAreInSync	(	const GRAPH *	g,
		const CSR *	csr,
		const SCIP_Real *	edgecosts_g
	)

are CSR and graph costs corresponding?

Parameters

g	the graph
csr	CSR
edgecosts_g	edge costs w.r.t graph 'g'

Definition at line 1448 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, EQ, FALSE, graph_get_nEdges(), graph_get_nNodes(), nnodes, csr_storage::nnodes, SCIP_Real, csr_storage::start, and TRUE.

Referenced by runTmPcMW_mode(), and solstp_pruneFromTmHeur_csr().

◆ graph_csr_copy()

void graph_csr_copy	(	const CSR *	csr_in,
		CSR *	csr_out
	)

copies CSR storage

Parameters

csr_in	CSR source
csr_out	CSR target

Definition at line 1483 of file graph_util.c.

References BMScopyMemoryArray, csr_storage::cost, csr_storage::edge_id, FALSE, graph_csr_isValid(), csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, NULL, and csr_storage::start.

Referenced by baseMstBuildNew(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), and dcmstTest3().

◆ graph_csr_print()

void graph_csr_print ( const CSR * csr )

prints CSR storage

Parameters

csr	CSR to print

Definition at line 1514 of file graph_util.c.

References csr_storage::cost, FALSE, graph_csr_isValid(), csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, SCIP_Real, and csr_storage::start.

Referenced by baseMstFinalizeNew(), and compMstFinalizeNew().

◆ graph_csr_getNedges()

int graph_csr_getNedges ( const CSR * csr )

gets currently used CSR edges

Parameters

csr	CSR to print

Definition at line 1536 of file graph_util.c.

References csr_storage::nedges_max, nnodes, csr_storage::nnodes, and csr_storage::start.

Referenced by pruneSteinerTreePc_csr(), pruneSteinerTreeStp_csr(), solstp_convertCsrToGraph(), solstp_getObjCsr(), solstp_pcGetObjCsr(), and strongPruneSteinerTreePc_csr().

◆ graph_csr_free()

void graph_csr_free	(	SCIP *	scip,
		CSR **	csr
	)

frees dynamic CSR storage

Parameters

scip	SCIP data structure
csr	CSR

Definition at line 1554 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, csr_storage::head, csr_storage::nnodes, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, and csr_storage::start.

Referenced by csrdepoTest2(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), extreduce_contractionFree(), graph_free_csr(), mst_free(), and tmBaseFree().

◆ graph_init_csr()

SCIP_RETCODE graph_init_csr	(	SCIP *	scip,
		GRAPH *	g
	)

initializes CSR storage of graph

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1581 of file graph_util.c.

References GRAPH::cost, GRAPH::csr_storage, GRAPH::edges, graph_csr_alloc(), graph_csr_build(), graph_valid_csr(), GRAPH::knots, NULL, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by dpborder_solve(), and SCIPStpHeurLocalExtendPcMwOut().

◆ graph_init_csrWithEdgeId()

SCIP_RETCODE graph_init_csrWithEdgeId	(	SCIP *	scip,
		GRAPH *	g
	)

initializes CSR storage of graph

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1603 of file graph_util.c.

References GRAPH::cost, GRAPH::csr_storage, GRAPH::edges, graph_csr_allocWithEdgeId(), graph_csr_build(), graph_valid_csr(), GRAPH::knots, NULL, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by dpborder_probePotential(), and dpterms_solve().

◆ graph_free_csr()

void graph_free_csr	(	SCIP *	scip,
		GRAPH *	g
	)

frees dynamic CSR storage of graph

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1623 of file graph_util.c.

References GRAPH::csr_storage, graph_csr_free(), and NULL.

Referenced by dpborder_probePotential(), dpborder_solve(), dpterms_solve(), graph_free(), and SCIPStpHeurLocalExtendPcMwOut().

◆ graph_csr_isValid()

SCIP_Bool graph_csr_isValid	(	const CSR *	csr,
		SCIP_Bool	verbose
	)

is CSR storage valid?

Parameters

csr	the CSR graph
verbose	be verbose?

Definition at line 1637 of file graph_util.c.

References FALSE, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, csr_storage::start, and TRUE.

Referenced by graph_csr_build(), graph_csr_chgCosts(), graph_csr_copy(), graph_csr_print(), graph_valid_csr(), and reduce_dcmstMstIsValid().

◆ graph_valid_csr()

SCIP_Bool graph_valid_csr	(	const GRAPH *	g,
		SCIP_Bool	verbose
	)

is CSR storage of graph valid?

Parameters

g	the graph
verbose	be verbose?

Definition at line 1694 of file graph_util.c.

References csr_storage::cost, GRAPH::csr_storage, GRAPH::edges, FALSE, graph_csr_isValid(), csr_storage::head, GRAPH::knots, csr_storage::nedges_max, and csr_storage::nnodes.

Referenced by graph_init_csr(), and graph_init_csrWithEdgeId().

◆ graph_init_dcsr()

SCIP_RETCODE graph_init_dcsr	(	SCIP *	scip,
		GRAPH *	g
	)

initializes dynamic CSR storage

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1721 of file graph_util.c.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extInit(), extreduce_init(), fixVarsRedbased(), reduce_pathreplace(), reduce_pathreplaceExt(), reduce_sdStar(), reduce_sdStarBiasedWithProfit(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), reduce_termsepaDa(), sdneighborUpdateInit(), sepafullInitDistdata(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().

◆ graph_free_dcsr()

void graph_free_dcsr	(	SCIP *	scip,
		GRAPH *	g
	)

frees dynamic CSR storage

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1807 of file graph_util.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, dynamic_csr_storage::edgeid, dynamic_csr_storage::head, dynamic_csr_storage::id2csredge, dynamic_csr_storage::nnodes, NULL, dynamic_csr_storage::range, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extFree(), extreduce_exit(), fixVarsRedbased(), graph_free(), reduce_pathreplace(), reduce_pathreplaceExt(), reduce_sdStar(), reduce_sdStarBiasedWithProfit(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), sdneighborUpdateFree(), sepafullInitDistdata(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().

◆ graph_update_dcsr()

void graph_update_dcsr	(	SCIP *	scip,
		GRAPH *	g
	)

updates dynamic CSR storage

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1829 of file graph_util.c.

◆ graph_dcsr_deleteEdge()

void graph_dcsr_deleteEdge	(	DCSR *	dcsr,
		int	tail,
		int	e_csr
	)

deletes CSR indexed edge

Parameters

dcsr	DCSR container
tail	tail of edge
e_csr	CSR indexed edge

Definition at line 1840 of file graph_util.c.

References dynamic_csr_storage::cost, dynamic_csr_storage::cost2, dynamic_csr_storage::cost3, dynamic_csr_storage::edgeid, csr_range::end, FARAWAY, dynamic_csr_storage::head, dynamic_csr_storage::id2csredge, nnodes, dynamic_csr_storage::range, and SCIP_Real.

Referenced by graph_dcsr_deleteEdgeBi().

◆ graph_dcsr_deleteEdgeBi()

void graph_dcsr_deleteEdgeBi	(	SCIP *	scip,
		DCSR *	dcsr,
		int	e_csr
	)

deletes CSR indexed edge and anti-parallel one

Parameters

scip	SCIP data structure
dcsr	DCSR container
e_csr	CSR indexed edge

Definition at line 1894 of file graph_util.c.

References dynamic_csr_storage::cost, dynamic_csr_storage::edgeid, flipedge, graph_dcsr_deleteEdge(), dynamic_csr_storage::head, dynamic_csr_storage::id2csredge, SCIPdebugMessage, and SCIPisEQ().

Referenced by graph_edge_delFull(), reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), replaceEdgeByPath(), and sdStarBiasedProcessNode().

◆ graph_valid_dcsr()

SCIP_Bool graph_valid_dcsr	(	const GRAPH *	g,
		SCIP_Bool	verbose
	)

is DCSR storage of graph valid?

Parameters

g	the graph
verbose	be verbose?

Definition at line 1919 of file graph_util.c.

References GRAPH::dcsr_storage, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, FALSE, dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, dynamic_csr_storage::nedges, nnodes, dynamic_csr_storage::nnodes, dynamic_csr_storage::range, csr_range::start, GRAPH::tail, and TRUE.

Referenced by extreduce_distDataInit(), graph_edge_delFull(), graph_init_dcsr(), and replaceEdgeByPath().

◆ graph_dijkLimited_init()

SCIP_RETCODE graph_dijkLimited_init	(	SCIP *	scip,
		const GRAPH *	g,
		DIJK **	dijkdata
	)

initializes (allocates and fills) limited Dijkstra structure members

Parameters

scip	SCIP
g	the graph
dijkdata	data for limited Dijkstra

Definition at line 1989 of file graph_util.c.

References dijkstra_data::dheap, dijkstra_data::edgelimit, FALSE, FARAWAY, graph_heap_create(), GRAPH::knots, nnodes, dijkstra_data::node_bias, dijkstra_data::node_distance, dijkstra_data::node_visited, NULL, dijkstra_data::nvisits, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, and dijkstra_data::visitlist.

Referenced by dapathsInit(), extreduce_distDataInit(), reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), sdneighborUpdateInit(), sdStarInit(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdGetterReturnsCorrectSds(), and testSdStarPcKillsEdge().

◆ graph_dijkLimited_initPcShifts()

SCIP_RETCODE graph_dijkLimited_initPcShifts	(	SCIP *	scip,
		const GRAPH *	g,
		DIJK *	dijkdata
	)

initializes PC shifts per node

Parameters

scip	SCIP
g	the graph
dijkdata	data for limited Dijkstra

Definition at line 2031 of file graph_util.c.

References GRAPH::cost, EAT_LAST, EQ, GRAPH::extended, FARAWAY, graph_get_nNodes(), graph_pc_isPc(), graph_pc_isRootedPcMw(), GT, GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, dijkstra_data::node_bias, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by extreduce_distDataInit().

◆ graph_dijkLimited_clean()

void graph_dijkLimited_clean	(	const GRAPH *	g,
		DIJK *	dijkdata
	)

cleans limited Dijkstra structure members

Parameters

g	the graph
dijkdata	data for limited Dijkstra

Definition at line 2083 of file graph_util.c.

References dijkstra_data::dheap, dijkstra_data::edgelimit, FALSE, FARAWAY, graph_heap_clean(), GRAPH::knots, nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, SCIP_Real, and TRUE.

Referenced by reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), and testSdGetterReturnsCorrectSds().

◆ graph_dijkLimited_reset()

void graph_dijkLimited_reset	(	const GRAPH *	g,
		DIJK *	dijkdata
	)

reset data of limited Dijkstra structure

Parameters

g	the graph
dijkdata	data for limited Dijkstra

Definition at line 2105 of file graph_util.c.

References dijkstra_data::dheap, FALSE, FARAWAY, graph_heap_clean(), GRAPH::knots, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dijkstra_heap::position, SCIP_Real, UNKNOWN, and dijkstra_data::visitlist.

Referenced by dapathsRunShortestPaths(), distDataRecomputeNormalDist(), extreduce_distDataInit(), reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), and sdneighborMarkCloseNodes().

◆ graph_dijkLimited_free()

void graph_dijkLimited_free	(	SCIP *	scip,
		DIJK **	dijkdata
	)

frees limited Dijkstra structure member

Parameters

scip	SCIP
dijkdata	data for limited Dijkstra

Definition at line 2143 of file graph_util.c.

References dijkstra_data::dheap, graph_heap_free(), dijkstra_data::node_bias, dijkstra_data::node_distance, dijkstra_data::node_visited, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, TRUE, and dijkstra_data::visitlist.

Referenced by dapathsFreeMembers(), extreduce_distDataFree(), reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), sdneighborUpdateFree(), sdStarFinalize(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdGetterReturnsCorrectSds(), and testSdStarPcKillsEdge().

SCIP

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ DHEAP_MAX_KEY

◆ DHEAP_MIN_KEY

Function Documentation

◆ trail()

◆ csrdepoCsrIsSet()

◆ csrdepoCsrUnsetDebug()

◆ csrdepoCleanDebug()

◆ csrdepoCsrWeight()

◆ csrdepoGetTopWeight()

◆ csrdepoGetTopIndex()

◆ csrdepoGetNnodes()

◆ csrdepoGetNedges()

◆ csrdepoFillCSR()

◆ graph_trail_arr()

◆ graph_trail_costAware()

◆ graph_termsReachable()

◆ graph_findCentralTerminal()

◆ graph_buildOrgNodesToReducedMap()

◆ graph_csrdepo_init()

◆ graph_csrdepo_free()

◆ graph_csrdepo_getCSR()

◆ graph_csrdepo_getTopCSR()

◆ graph_csrdepo_getDataSize()

◆ graph_csrdepo_getNcsrs()

◆ graph_csrdepo_removeTop()

◆ graph_csrdepo_clean()

◆ graph_csrdepo_addEmptyTop()

◆ graph_csrdepo_addEmptyTopTree()

◆ graph_csrdepo_isEmpty()

◆ graph_csrdepo_hasEmptyTop()

◆ graph_csrdepo_getEmptyTop()

◆ graph_csrdepo_emptyTopSetMarked()

◆ graph_csrdepo_print()

◆ graph_heap_clean()

◆ graph_heap_isClean()

◆ graph_heap_create()

◆ graph_heap_free()

◆ graph_heap_deleteMin()

◆ graph_heap_deleteMinGetNode()

◆ graph_heap_deleteMinReturnNode()

◆ graph_heap_correct()

◆ graph_csr_alloc()

◆ graph_csr_allocWithEdgeId()

◆ graph_csr_chgCosts()

◆ graph_csr_build()

◆ graph_csr_buildCosts()

◆ graph_csr_costsAreInSync()

◆ graph_csr_copy()

◆ graph_csr_print()

◆ graph_csr_getNedges()

◆ graph_csr_free()

◆ graph_init_csr()

◆ graph_init_csrWithEdgeId()

◆ graph_free_csr()

◆ graph_csr_isValid()

◆ graph_valid_csr()

◆ graph_init_dcsr()

◆ graph_free_dcsr()

◆ graph_update_dcsr()

◆ graph_dcsr_deleteEdge()

◆ graph_dcsr_deleteEdgeBi()

◆ graph_valid_dcsr()

◆ graph_dijkLimited_init()

◆ graph_dijkLimited_initPcShifts()

◆ graph_dijkLimited_clean()

◆ graph_dijkLimited_reset()

◆ graph_dijkLimited_free()